Generating lists populated with random objects For the purposes of unit-testing in Python, I've written a very simple function for generating variable-length lists populated with random objects:

constructors = [
    object,
    dict,
    lambda: bool(randint(0, 1)),
    lambda: randint(1, 1000),
    lambda: ''.join(choice(digits) for _ in range(randint(1, 10)))
]

choices = (
    lambda _: choice(constructors)(),
    lambda off: fake_list(off),
    lambda off: tuple(fake_list(off))
)

def fake_list(off = None):
    '''Creates a list populated with random objects.'''
    off = (off or 0) + 1
    return [choice(choices)(off) for _ in range(max(randint(1, 10) - off, 0))]

List generated with this function typically look something like this:

[(269, '6'), [{}, 990, 347, <object object at 0x7f51b230b130>, {}, [{}, '91921063', 302, '0047953', {}, ()], True], '70262', True]

Do you see any problems with it? Is there a more efficient/elegant way of doing this that you could suggest?

Quality of the generated primitives (strings, integers) is not of priority (i.e. string.digits should be enough).

Requirements may vary so I find it hard to use with the "hardcoded" constructors. Instead I would define a function that accept such constructors as an argument.

I would also define the function returning the list-comprehension as an inner function so the off parameter is hidden from the public interface (the end-user does not need to know such implementation details). Besides, off is a terrible name for such variable when all it does it to track the recursion depth, better call it depth, then.

An other thing that could be worth taking as parameter (even though a sensible default would make sense most of the time) is the maximum length of the inner lists (and thus the maximum allowed recursion level):

import random
from string import digits

def fake_list(items, max_size=10):
    """Create a list populated with random objects constructed from `items`"""

    choices = (
            lambda _: random.choice(items)(),
            lambda depth: random_list(depth),
            lambda depth: tuple(random_list(depth)),
    )

    def random_list(depth):
        return [
                random.choice(choices)(depth + 1)
                for _ in range(max(random.randint(1, max_size) - depth, 0))
        ]

    if max_size < 1:
        raise ValueError('minimal size of output should be at least 1')

    return random_list(0)

def test():
    constructors = [
        object,
        dict,
        lambda: bool(random.randint(0, 1)),
        lambda: random.randint(1, 1000),
        lambda: ''.join(
            random.choice(digits)
            for _ in range(random.randint(1, 10))),
    ]

    print(fake_list(constructors))

if __name__ == '__main__':
    test()

That way I can call:

fake_list([lambda: float('-inf'), lambda: range(random.randint(-100, -10), random.randint(10, 100)), set])

if I need to.


Error Handling - Controller's OnException and Application_Error I'm pretty new to MVC. Below is the code that I have added to an existing MVC 5 application.  The code is using log4net to log any run-time error/exception.

NOTE: I could override OnException() in MVC filter "HandleErrorAttribute" but I preferred to have this functionality in my custom Controller base class.

Can anyone please review and provide feedback?

BaseController.cs

public class BaseController: Controller
{
    private log4net.ILog logger;

    protected override void OnException(ExceptionContext filterContext)
    {
        //Log error
        logger = log4net.LogManager.GetLogger(filterContext.Controller.ToString());
        logger.Error(filterContext.Exception.Message, filterContext.Exception);

        //If the request is AJAX return JSON else redirect user to Error view.
        if (filterContext.HttpContext.Request.Headers["X-Requested-With"] == "XMLHttpRequest")
        {
            //Return JSON
            filterContext.Result = new JsonResult
            {
                    JsonRequestBehavior = JsonRequestBehavior.AllowGet,
                    Data = new { error = true, message = "Sorry, an error occurred while processing your request." }
            };
        }
        else
        {
            //Redirect user to error page
            filterContext.ExceptionHandled = true;
            filterContext.Result = this.RedirectToAction("Index", "Error");
        }
        base.OnException(filterContext);
    }
}

HomeController.cs

public class HomeController : BaseController
{
    ...
}

Global.asax.cs

public class MvcApplication : System.Web.HttpApplication
{
    private static readonly ILog log = LogManager.GetLogger(typeof(MvcApplication));

    protected void Application_Error(object sender, EventArgs e)
    {
        //Log exception
        Exception exception = Server.GetLastError();
        log.Error(exception);

        //Clear error from response stream
        Response.Clear();
        Server.ClearError();

        //Redirect user
        Context.Server.TransferRequest("~/Error/");
    }
    ...
}

For displaying errors, I have a basic ErrorController.cs with just Index() Action along with its associated Error/Index.cshtml.

Some blogs suggests different error pages for different type of errors (such as 404 error). Do I need to handle them separately?

Please share if you have any ideas to improve upon my code in terms of usability and logging details.

The OnException() methods does 2 things.

It logs the exception
It creates an return value

So let us refactor these two points to two separate methods.

private void LogException(ExceptionContext exceptionContext)
{
    logger = log4net.LogManager.GetLogger(exceptionContext.Controller.ToString());
    logger.Error(exceptionContext.Exception.Message, exceptionContext.Exception);
}

private const String XMLHttpRequest = "XMLHttpRequest";
private const String XRequestedWithHeadername= "X-Requested-With";
private const String JSONErrorMessage = "Sorry, an error occurred while processing your request.";
private void CreateExceptionContextResult(ExceptionContext exceptionContext)
{
    if (exceptionContext.HttpContext.Request.Headers[XRequestedWithHeadername] == XMLHttpRequest )
    {
        //Return JSON
        exceptionContext.Result = new JsonResult
        {
                JsonRequestBehavior = JsonRequestBehavior.AllowGet,
                Data = new { error = true, message = JSONErrorMessage }
        };
    }
    else
    {
        //Redirect user to error page
        exceptionContext.ExceptionHandled = true;
        exceptionContext.Result = this.RedirectToAction("Index", "Error");
    }
}

If we want to handle the different error types, we should create a new class which only keeps the values for actionName and controllerName.

public class ActionControllerName
{
     public String ActionName { get; private set; }
     public String ControllerName { get; private set; }
     public ActionControllerName(String actionName, String controllerName)
     {
         ActionName = actionName;
         ControllerName = controllerName;
     }
}

Now we add a Dictionary and a method to fill this dictionary, which should be called in the constructor, or injected by an property.

private const int DefaultEntryKey = -1;
private Dictionary<int,ActionControllerName> redirectDictionary = new Dictionary<int,ActionControllerName>();
private void FillRedirectDictionary()
{
    redirectDictionary.Add(DefaultEntryKey , new ActionControllerName("Index", "Error"));
    // more to add
}

Next we implement a method to get a RedirectToRouteResult passing the exception as parameter

private RedirectToRouteResult GetRedirect(Exception exception)
{
    int errorCode = DefaultEntryKey;
    HttpException httpException = exception as HttpException;
    if (httpException != null)
    {
        errorCode = httpException.ErrorCode;
        if (!redirectDictionary.ContainsKey(errorCode))
        {
            errorCode = DefaultEntryKey;
        }
    }
    ActionControllerName acn = redirectDictionary[errorCode];
    return this.RedirectToAction(acn.ActionName , acn.ControllerName);
}

We go back to this else part

else
{
    //Redirect user to error page
    exceptionContext.ExceptionHandled = true;
    exceptionContext.Result = this.RedirectToAction("Index", "Error");
}

and change it to

else
{
    //Redirect user to error page
    exceptionContext.ExceptionHandled = true;
    exceptionContext.Result = GetRedirect(exceptionContext.Exception);
}


Running code snippets in a background thread I'm working on a dataset from a MOOC.  I have a lot of python3 code snippets that I need to run and get the results from.  To do this I've written a python script that loops over each snippet.  For each snippet I:

Create new StringIO objects
Set sys.stdout and sys.stderr to my stringIO buffers
Execute the code snippet in a threading.thread object
Join the thread
Log the results in the stringIO buffers
Restore stdout and stderr

This works fine for "correct" code, but this has undesired side effects in other cases:

When the code has an infinite loop, thread.join doesn't kill the thread.  The thread itself is a daemon thread, so it runs quietly in the background until my loop finishes.
When the code has an infinite loop with a print(), the thread starts overwriting my actual stdout when I set it back to the default (away from the StringIO buffer).  This pollutes my reporting.

Here is my current code:
def execCode(code, testScript=None):
    # create file-like string to capture output
    codeOut = io.StringIO()
    codeErr = io.StringIO()

    # capture output and errors
    sys.stdout = codeOut
    sys.stderr = codeErr

    def worker():
        exec(code, globals())

        if testScript:
            # flush stdout/stderror
            sys.stdout.truncate(0)
            sys.stdout.seek(0)
            # sys.stderr.truncate(0)
            # sys.stderr.seek(0)
            exec(testScript)

    thread = threading.Thread(target=worker, daemon=True)
    # thread = Process(target=worker) #, stdout=codeOut, stderr=codeErr)
    thread.start()
    thread.join(0.5)  # 500ms

    execError = codeErr.getvalue().strip()
    execOutput = codeOut.getvalue().strip()

    if thread.is_alive():
        thread.terminate()
        execError = "TimeError: run time exceeded"

    codeOut.close()
    codeErr.close()

    # restore stdout and stderr
    sys.stdout = sys.__stdout__
    sys.stderr = sys.__stderr__

    # restore any overridden functions
    restoreBuiltinFunctions()

    if execError:
        return False, stripOuterException(execError)
    else:
        return True, execOutput

To handle the undesirable cases, I've tried to use multithreading.Process and/or contextlib.redirect_stdout to run the code in a process (then I can call process.terminate()), but I'm not having any success capturing stdout/stderr.
So my question is:  What can I do to make this better/more robust to handle bad code snippets?
(And yes, I know this is a bad idea in general; I'm running it in a virtual machine just in case there is malicious code in there somewhere)
Python version is 3.5.3

Update
It occurs to me that there is a little more flexibility in this situation.  I have a function, preprocess(code) that accepts a the code submission as a string and alters it.  Mostly I've been using it to swap out the value of some variables using regular expressions.
Here is an example implementation:
def preprocess(code):
    import re
    rx = re.compile('earlier_date\s*=\s*.+')
    code = re.sub(rx, "earlier_date = date(2016, 5, 3)", code)
    rx = re.compile('later_date\s*=\s*.+')
    code = re.sub(rx, "later_date = date(2016, 5, 24)", code)
    return code

I could use the preprocess function to help redirect STDOUT

Sorry, didn't have time to look at the issue of preventing the infinite loops, but here is a way to address the printing issue.

Enforce thread-local printing

As you've found, because each thread shares sys.stdout there isn't a good way to redirect printing from distinct threads to distinct streams.
As you discovered, and as is documented, contextlib.redirect_stdout does not work in threaded applications, and has no effect on the output of subprocesses.
However, because you're using Python 3 print is a function, and because Python is a dynamic language, we can (ab)use that.

Consider the following function signature:

def print(*objects, sep='', end='\n', file=sys.stdout, flush=False)

An astute reader may notice that this is Python 3's print function. Suppose we changed it just a little bit, to not use
sys.stdout as the default stream and instead use a thread-local stream. Now we may be tempted to use the builtin threading.local function,
however that will make it hard to recover the output after the fact. Let's start by making a mechanism for getting a thread-local output stream.

thread_local_data = {
    'stdout': {},
    'stderr': {}
}

def register_thread(thread_ident=None):
    """Register a thread with the monitor."""

    thread_ident = thread_ident or threading.get_ident()

    thread_local_data['stdout'][thread_ident] = io.StringIO()
    thread_local_data['stderr'][thread_ident] = io.StringIO()

def unregister_thread(thread_ident=None):
    """Unregister a thread with the monitor."""

    thread_ident = thread_ident or threading.get_ident()

    thread_local_data['stdout'][thread_ident].close()
    thread_local_data['stderr'][thread_ident].close()

def get_thread_stdout(thread_ident=None):
    """Get output stream for a thread."""

    thread_ident = thread_ident or threading.get_ident()
    return thread_local_data['stdout'][thread_ident]

def get_thread_stderr(thread_ident=None):
    """Get error stream for a thread."""

    thread_ident = thread_ident or threading.get_ident()
    return thread_local_data['stderr'][thread_ident]

original_print = print
def print(*objects, sep='', end='\n', file=None, flush=False):
    if file is None or file is sys.stdout:
        file = get_thread_stdout()
    if file is sys.stderr:
        file = get_thread_stderr()

    original_print(*objects, sep=sep, end=end, file=file, flush=flush)

You can test a simplified version of it right from the REPL - notice that we now have a print function in our globals() dict,
where there was not one previously. Then we can see

>>> old_print=globals()['__builtins__'].print
>>> old_print("test")
test
>>> def print(): old_print("I WIN")
...
>>> import pprint
>>> pprint.pprint(globals())
{'__annotations__': {},
 '__builtins__': <module 'builtins' (built-in)>,
 '__doc__': None,
 '__loader__': <class '_frozen_importlib.BuiltinImporter'>,
 '__name__': '__main__',
 '__package__': None,
 '__spec__': None,
 'old_print': <built-in function print>,
 'pprint': <module 'pprint' from 'C:\\Users\\dobermil\\AppData\\Local\\Programs\\Python\\Python36-32\\lib\\pprint.py'>,
 'print': <function print at 0x02BD5198>}
>>> exec("print()", globals())
I WIN

Now that we have the mechanism to print as we want to, you just need to make sure you register the thread before starting it. That will setup the thread-local stdout.


Project Euler 4 The Functional Way I'm learning Scala (and functional programming). Is there a better way to solve Euler problem 4 than either of these two solutions.

Euler 4

I like this array comprehension solution, but it wastes so much space.

def isPal(n: Int): Boolean = {
  val sN = n + ""
  sN == sN.reverse
}
def euler4Iter: Int = {
  var largestPal = 0
  for (i <- 100 to 1000; j <- i to 1000) {
    if (i * j > largestPal && isPal(i*j)) {
      largestPal = i*j
    }
  }
  largestPal
}
def euler4ArrayCompre: Int = {
  (for(i <- 100 to 1000; j <- i to 1000 if isPal(i*j)) yield i*j).max
}

Inefficiencies

Your iteration is wasteful for several reasons

You generate every product of two 3-digit numbers, which will not be reaped until the calculation is finished.
You start at the lowest end of a large range, when the desired result is clearly going to be near the top end.
You keep iterating after the largest number has been found
You are iterating over nearly twice as many results as you need to, because of duplicate products

Just to prove the final point:

scala> (for (i <- 100 to 999; j <- i to 999) yield (i * j)).size
res0: Int = 405450

(for (i <- 100 to 999; j <- i to 999) yield (i * j)).sorted.distinct.size
res1: Int = 227521

for (i <- 100 to 999; j <- i to 999 if i * j == 100000) yield (i, j)
res2: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((125,800), (160,625), (200,500), (250,400))

Improvements

The first point can easily be addressed with iterators, since you only need to traverse each range once. As to the others...

You could look for a way to start at the top of the range and work down, in such a way that each iteration tests the next lowest product of two 3-digitnumbers.  If you could think of a way to do that recursively, you could safely return as soon as you found a palindromic number.  But consider this:

There are only 999 6-digit palindromic numbers
It is trivial to generate a sequence of them in descending order
Testing a decreasing sequence of potential divisors, starting at 999, can be abandoned as soon as palindrome / divisor > 999
The search can stop as soon as palindrome % divisor == 0

As long as the target number is near the top of the range (which of course it will be), working backwards like this will involve much fewer operations,  which makes this cheaper even with the higher cost of modulo division.

Here's a simple attempt:

def ps = for (i <- Iterator.from(9, -1) take 9;
              j <- Iterator.from(9, -1) take 10;
              k <- Iterator.from(9, -1) take 10;)
              yield (i + 10 * j + 100 * k + 1000 * k + 10000 * j + 100000 * i)

ps find {p =>
  Iterator.from(999, -1) take 900 takeWhile (p / _ < 1000) exists (p % _ == 0)
}

If you are not happy that this only looks at the 6-digit palindromes and worry that the highest palindrome might be in the 5-digit range, laziness means that it is cheap to append 5-digit palindromes to the 6-digit iterator:

// Lazily generate all 999 palindromic 6-digit numbers in reverse order
def ps6 = for ((i <- Iterator.from(9, -1) take 9;
                j <- Iterator.from(9, -1) take 10;
                k <- Iterator.from(9, -1) take 10)
              yield (i + 10 * j + 100 * k + 1000 * k + 10000 * j + 100000 * i)

// Even more lazy generation of the 5-digit palindromes
def ps5 = ps6 map (i => (i / 1000) * 100 + i % 100)

// Put them together.  Iterator ++ is lazy
def ps = (ps6 dropWhile (_ > 999 * 999)) ++ (ps5 takeWhile (_ > 9999))

There are ways to do this without modulo arithmetic and/or even fewer iterations.  While my simple solution addresses the first 3 inefficiencies I listed, it is iterating rather more than is needed (mitigated significantly by working down from the top). Maybe you can improve on this from here.


Readability of array_* vs foreach in PHP for filtering and extracting With functional programming all the rage, I feel I should be using PHP's array_* functions more.  But when I compare these two identical implementations, I can't help but think foreach is more readable.  Am I just being a dinosaur?

(The foreach implementation takes 1/4 the time, but performance is not of interest for me here, now).

Which do you like better and why?

// Create $attendeeNames from $allPeople who are in the $selectedPeople array
foreach ($allPeople as $person) {
    $id = $person['id'];
    $name = $person['name'];
    if (in_array($id, $selectedPeople)) {
        $attendeeNames[] = $name;
    }
}

// Same, but with array functions
$attendees = array_filter($allPeople,
    function($item) use ($selectedPeople) {
        $id = $item['id'];
        return in_array($id, $selectedPeople);
    });

$attendeeNames = array_map(
    function($attendee) {
        return $attendee['name'];
    }, $attendees);

If your functional code is a filter and then a map it's likely a good candidate for array_reduce.

One of the main advantages of a function first approach here is that you can name the inner operation (the filtering operation), but using a closure (or a foreach) robs of you of a name (which could have been used to signal intent) and often robs of us of reuse so wrap the Closure in a named, reusable context (another named function).

A named function will also allow us to pre-inject the variable $selectedPeople into the Closure before array_ functions interact with the Closure inside.

See: http://www.phptherightway.com/pages/Functional-Programming.html for more information on this.

Now we can type hint all the inputs.

function selected_attendee_names(array $selectedPeople) : Closure {
  return function (array $attendeeNames, array $attendee) use ($selectedPeople) : array {
    $isSelectedAttendee = in_array($attendee['id'], $selectedPeople);
    $isSelectedAttendee ? $attendeeNames[] = $attendee['name'] : NULL;
    return $attendeeNames;
  };
}

$attendeeNames = array_reduce($allPeope, selected_attendee_names($selectedPeople), []);

Another approach that could have increased reuse is to array_filter and then use array_column.

function is_selected_attendee(array $selectedPeople) : Closure {
  return function (array $attendee) use ($selectedPeople) : bool {
      $isSelectedAttendee = in_array($attendee['id'], $selectedPeople);
      return $isSelectedAttendee;
  };
}

$selected_attendees = array_filter($allPeople, is_selected_attendee($selectedPeople));
$selected_attendees_names = array_column($selected_attendees, 'name');

Generally speaking I'd prefer the bottom approach because you'll usually find you want to do something else with the selected attendees later in your program.


Convert exam marks to overall grade I have started working on the code below here. I want to practice my C coding skills.

It is a grading program: given a set of subject marks, calculates the sum, average and it converts the computed average to an alphabetic grade letter.

I would love to be pointed out any mistakes that I have made or any opinions to make my code more presentable.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char name[100];
    int physics,chemistry,maths,biology,business,total_marks;
    // physics,chemistry,maths,biology,business are just but subjects names.
    float mean;

    printf("Please enter your name \n");
    fgets(name,100,stdin);
    {

    printf("Please enter the marks for physics \n");
    scanf("%d",&physics);

    printf("Please enter the marks for chemistry \n");
    scanf("%d",&chemistry);

    printf("Please enter the marks for maths \n");
    scanf("%d",&maths);

    printf("Please enter the marks for biology \n");
    scanf("%d",&biology);

    printf("Please enter the marks for business\n");
    scanf("%d",&business);

    total_marks=physics+chemistry+maths+biology+business;
    mean= (float)total_marks/5;}

    printf("%s\t",name);
    printf(" HAS TOTAL MARKS OF : %d,\t",total_marks);
    printf(" MEAN OF :  %.2f\t",mean, round(mean) );

if (mean>=70)
   printf("AND THE  GRADE IS A  \n");

if(mean>=60 && mean<69)
   printf("AND THE  GRADE IS B  \n");

if(mean>=50 && mean<59)
   printf("AND THE  GRADE IS C  \n");

if(mean>=40 && mean<49)
   printf("AND THE  GRADE IS D  \n");

if (mean<40)
   printf("AND THE  GRADE IS E \n");

   printf(" Thank you for your time  \n");

   return 0;
}

Formatting - if the code looks the same in your editor as it does here, you could really do with an automatic indentation tool (many editors have that built-in, or you could use GNU Indent, for instance).
I'll assume that the inconsistent indentation is due to the way you've copied your code into the site; a good way to avoid problems is to consistently use either spaces or tabs for indentation, but never to mix the two.

It's a good idea to specify that main() takes no arguments:
int main(void)

When we read input, we must check whether it was successful or not:
int physics;
if (scanf("%d", &physics) == 1) {
   // physics has been set, and we can safely use it
} else {
   // physics is still uninitialised
}

If input fails, then we might want to re-ask (but be careful about doing this if we reach end of the input stream, or we'll try and try again, indefinitely).
Output can also fail, but for this application, that's less of a concern.

There's an unused argument to printf() here:

printf(" MEAN OF :  %.2f\t",mean, round(mean) );

That suggests that you could enable more compiler warnings (e.g. gcc -Wall -Wextra - other compilers should have similar options).

If mean is between (say) 59.0 and 60.0, then it will fall in between the grade boundaries, and no grade will be printed.  The easy way to avoid this is to use else if:
if (mean >= 70) {
    puts("AND THE  GRADE IS A");
} else if (mean >= 60) {
    puts("AND THE  GRADE IS B");
} else if (mean >= 50) {
    puts("AND THE  GRADE IS C");
} else if (mean >= 40) {
    puts("AND THE  GRADE IS D");
} else {
    puts("AND THE  GRADE IS E");
}

Now, exactly one of those blocks will be executed.
I also changed the printf() to puts() there - prefer the simpler function when you just need to print a single string and a newline.

More advanced ideas
Should the grade thresholds be fixed in the code?  If they change, you need to re-compile the program.  Think about how you might read them from a configuration file.
Should the list of subjects be fixed?  How would you make the program more flexible for students of different courses?


Return whether a string is a palindrome if you can delete at most k elements The task:

  Given a string which we can delete at most k, return whether you can
  make a palindrome.

  For example, given 'waterrfetawx' and a k of 2, you could delete f and
  x to get 'waterretaw'.

The following solution is partially inspired by @Oh My Goodness's answer.

const s = "waterrfetawx";
const del = 2;

function palindromePossible(str, deleteAtMost) {
  const set = new Set();
  for (let i = 0, len = str.length; i < len; i++) {
    const char = str[i];
    void(set.delete(char) || set.add(char)); // <--is this good code?
  }

  let iStart = 0, iEnd = str.length - 1, possibleDeletion = 0;

  function isSame() {
    do {
      if (str[iStart] === str[iEnd]) {
        iStart++;
        iEnd--;
        return true;
      }
      if (++possibleDeletion > deleteAtMost) { return false; }
      if (set.has(str[iStart])) { iStart++; }
      if (set.has(str[iEnd])) { iEnd--; }
      if (iStart > iEnd) { return false; }
    } while(str[iStart] !== str[iEnd]);

    return true;
  }

  if (set.size <= deleteAtMost + 1) {
    for (let i = 0, len = Math.floor(str.length/2); i < len && iStart <= iEnd; i++) {
      if (!isSame()) { return false; }
    }
    return true;
  }
  return false;
}

console.log(palindromePossible(s, del));

You have a question embedded in the code:

void(set.delete(char) || set.add(char)); // <--is this good code?

The void operator "evaluates the given expression and then returns undefined"1. It doesn't appear that there is a need to have undefined be the final value of that expression because that expression doesn't get assigned or returned. The void() can be removed without changing the functionality of the code. I wouldn't say it is bad code, but unnecessary.

That for loop could be simplified:

for (let i = 0, len = str.length; i < len; i++) {
  const char = str[i];
  void(set.delete(char) || set.add(char)); // <--is this good code?
}

using a for...of loop:

for (const char of str) {
  set.delete(char) || set.add(char);
}

1https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/void


Tic-Tac-Toe Recursive Solver I am attempting to create a Tic-Tac-Toe game that uses a recursively checks every possible game board, and finds which boards result in a victory for X. (I ultimately plan to turn this into an AI which implements a minimax algorithm to play against a human player.) I am running into issues with the time efficiency of my code.

import time

X, O, NONE = ("X", "O", ".")

class Board():
    def __init__(self):
        self.board_length = 9;
        self.squares = [NONE for idx in range(self.board_length)]
        self.winning_combinations = [
            [0,1,2], [3,4,5], [6,7,8],
            [0,3,6], [1,4,7], [2,5,8],
            [0,4,8], [2,4,6]]

    def __str__(self):
        return  ("-------------\n| {} | {} | {} |\n" * 3 + "-------------").format(*self.squares)

    def make_move(self, location, player):
        if self.is_valid_move(location):
            self.squares[location] = player
            return True
        return False

    def undo_move(self, location):
        if self.is_valid_location(location):
            self.squares[location] = NONE
            return True
        return False

    def is_valid_move(self, location):
        return self.is_valid_location(location) and self.squares[location] == NONE

    def is_valid_location(self, location):
        return location >= 0 and location < self.board_length

    def get_winner(self):
        for player in (X, O):
            for combo in self.winning_combinations:
                if self.squares[combo[0]] == player and self.squares[combo[1]] == player and self.squares[combo[2]] == player:
                    return player
        return NONE

    def get_moves(self):
        return filter(self.is_valid_move, range(9))

iters = 0
def find_winners(board, depth=0, player=X):
    global iters
    iters += 1
    for move in board.get_moves():
        board.make_move(move, player)
        if board.get_winner() == X:
            #print(board)
            _ = 1
        else:
            find_winners(board, depth + 1, O if player == X else X)
        board.undo_move(move)

if __name__ == "__main__":
    start = time.time()
    find_winners(Board())
    print("Took: {time:.4f} seconds to execute {iters} times.".format(time=(time.time() - start), iters=iters))

When I run this code, I get an output of: Took: 8.4968 seconds to execute 986410 times.

Considering my code is only executing ~1m times, a time of almost 10 seconds to execute seems rather extreme. I can't find anything in my code that would particularly lead to this slowdown, or much that I can do to improve the efficiency of my code.

Any and all advice, on the efficiency of my code, or on my coding style in general, would be much appreciated.

Some remarks:

def is_valid_location(self, location):
    return location >= 0 and location < self.board_length

In contrast to many other programming languages, this can be expressed
in Python more succinctly as a chained comparison:

def is_valid_location(self, location):
    return 0 <= location < self.board_length

However, that function seems unnecessary to me, since nowhere in your
program an invalid location is created.

The winning combinations are not dependent on the particular
instance of a board, it is more logical to define them as a
class variable:

class Board():
    winning_combinations = [
            [0,1,2], [3,4,5], [6,7,8],
            [0,3,6], [1,4,7], [2,5,8],
            [0,4,8], [2,4,6]]

    def __init__(self):
        self.board_length = 9;
        self.squares = [NONE for idx in range(self.board_length)]

    // ...

The efficiency of the get_winner function can be improved.
It is not necessary to check both players against each winning combination:

def get_winner(self):
    for combo in self.winning_combinations:
        player = self.squares[combo[0]]
        if player is not None and self.squares[combo[1]] == player and self.squares[combo[2]] == player:
            return player
    return NONE

The only purpose of  _ = 1 in

    if board.get_winner() == X:
        #print(board)
        _ = 1
    else:
        find_winners(board, depth + 1, O if player == X else X)

seems to be to avoid an empty if-block. Python has a pass statement
for that purpose:

    if board.get_winner() == X:
        #print(board)
        pass
    else:
        find_winners(board, depth + 1, O if player == X else X)

You define three variables

X, O, NONE = ("X", "O", ".")

for the possible states of a cell. A better way to express mutually
exclusive values is an enumeration:

from enum import Enum

class Cell(Enum):
    X = "X"
    O = "O"
    empty = "."


String building attribute selectors I'm dynamically selecting elements in jQuery, how can I make it more resilient?

$('[data-example="' + exampleData + '"]').each(...);

I'm concerned that the data might contain special characters.

Avoid string building jQuery selectors. If your exampleData variable might contain special characters, or possibly contains user input, you've opened yourself to selector injection.

For example, if exampleData has a value of:

'"],body,[a="'

The computed selector becomes:

[data-example=""],body,[a=""]

which might cause unexpected behavior.

More typically, the selector will just fail outright, and your page or app will not work as expected.

Although jQuery calls itself the "write less, do more" library, this is a case where you'll need to write a bit more.

Instead of string building a single selector, use .filter():

$('[data-example]').filter(function () {
  return $(this).data('example') === exampleData;
});


Printing inputted, largest, odd integer The program asks the user to input 10 integers, and then prints the largest odd number that was entered. If no odd number was entered, it prints a message to that effect.

q = int(raw_input("Please enter an integer:"))
r = int(raw_input("Please enter another integer:"))
s = int(raw_input("Please enter another integer:"))
t = int(raw_input("Please enter another integer:"))
u = int(raw_input("Please enter another integer:"))
v = int(raw_input("Please enter another integer:"))
w = int(raw_input("Please enter another integer:"))
x = int(raw_input("Please enter another integer:"))
y = int(raw_input("Please enter another integer:"))
z = int(raw_input("Please enter one last integer:"))

odd = []
if q%2 != 0:
    odd += [q]
if r%2 != 0:
    odd += [r]
if s%2 != 0:
    odd += [s]
if t%2 != 0:
    odd += [t]
if u%2 != 0:
    odd += [u]
if v%2 != 0:
    odd += [v]
if w%2 != 0:
    odd += [w]
if x%2 != 0:
    odd += [x]
if y%2 != 0:
    odd += [y]
if z%2 != 0:
    odd += [z]
if q%2 == 0 and r%2 == 0 and s%2 == 0 and t%2 == 0 and u%2 == 0 and v%2 == 0 and w%2 == 0 and x%2 == 0 and y%2 == 0 and z%2 == 0:
    print "None of the values given are odd."
else:
    print max(odd), "is the largest odd number."

Use loops!

odd_nums = []
for i in xrange(10):
    value = int(raw_input('Enter an integer: '))
    if value % 2 != 0:
        odd_nums.append(value)

if len(odd_nums) != 0:
    print max(odd_nums)
else:
    print "No odd values"

How to read this line:

for i in xrange(10):

This line means starting at 0 (the default starting point for xrange()), and ending at 10-1 (upper bound is not included), execute the following code with i set to the current iteration of the loop. This executes the code exactly 10 times (i = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9).

The rest was made as similar to your code as possible, and so should be understandable.


Min heap C++ implementation I have implemented a min heap in C++, and I want to improve it in every possible way. Could you please review it and let me know your suggestions/comments?

#include <iostream>
#include <vector>
#include <algorithm>  // std::swap

class MinHeap {

    private:
    std::vector<int> heap;

    void heapify(int);
    int parent(int);
    int left(int);
    int right(int);

    public:
    void insert(int);
    int extractMin();

};

// heapifies down the index-i
void MinHeap::heapify(int i) {

    int l = left(i);
    int r = right(i);

    // find the smallest amongst the parent, it's left & right child
    int smallest;
    smallest = (l != -1 && heap[l] < heap[i]) ? l : i;
    smallest = (r != -1 && heap[r] < heap[smallest]) ? r : smallest;

    // If heap[i] (parent) is the smallest, then it is already a Heap!
    if (smallest != i) {
        std::swap(heap[i], heap[smallest]);
        heapify(smallest);
    }
}

// Returns the index of the left-child of the ith element
// Returns -1 if the index > heap size
int MinHeap::left(int i) {
    int l = (((2 * i) + 1) < heap.size() - 1) ? (2 * i) + 1 : -1;
    return l;
}

// Returns the index of the Right-child of the ith element
// Returns -1 if the index > heap size
int MinHeap::right(int i) {
    int r = (((2 * i) + 2) < heap.size() - 1)? (2 * i) + 2 : -1;
    return r;
}

// Returns the index of the Parent of the ith element
// Returns -1 if parent-index < 0
int MinHeap::parent(int i) {
    int p = (((i - 1) / 2) >= 0)? (i - 1) / 2 : -1;
    return p;
}

// Returns the minimum element from the heap and also deletes it from the heap
int MinHeap::extractMin() {

    // back-up the root, it's the min value
    int min = heap[0];

    // copy the value of the very-last element into the root and delete the last element
    heap[0] = heap.back();
    heap.pop_back();

    // heapify-down the root
    heapify(0);

    return min;
}

// inserts a value at the right-spot in the heap, ensures the heap property is maintained.
void MinHeap::insert(int value) {

    // insert the new element at the end of heap
    heap.push_back(value);

    // bubble-up the new value to its right position, thus maintaining the heap property
    int i = heap.size() - 1;
    while (heap[parent(i)] > heap[i]) {
        std::swap(heap[parent(i)], heap[i]);
        i = parent(i);
    }

}

Overall, LGTM.
A protection against negative indices being passed to parent doesn't worth the effort. parent is a private method, so you are in control of the indices at all times. A strong indication that the protection is not needed is the fact that insert doesn't bother to test the return value for validity.
Along the same line, left() and right() returning -1 doesn't look like a good idea. Effectively, you test the same condition twice: ((2 * i) + 1) < heap.size() - 1 in left, and l != -1 in heapify.
Notice that anytime right is valid, left is also valid. That allows a certain optimization (see below).
C++ is very good in recognizing tail recursion and optimizing it out. I strongly recommend to do it explicitly anyway.
Combining the three bullets above, consider

void heapify(int i)
{
    while ((r = right(i)) < heap.size()) {
        follow your swapping logic
    }

    if ((l = left(i)) < heap_size()) { // No need to loop - it may only happen once!
        if (heap[l] < heap[i]) {
            std::swap(heap[i], heap[l]);
        }
    }
}

MinHeap::heapify is a misnomer, and somewhat confusing. Usually heapify refers to the process of turning an array into a heap. Your method is normally called sift_down.
Too many comments to my taste.


This is a Monoid instance I wrote for a Tree data type. Is this the most terse way to express mappend? Here's my type:

data Tree a = Empty | Node a (Tree a) (Tree a)

Here's the instance declaration for Monoid:

instance (Monoid a) => Monoid (Tree a) where
    mempty = Empty
    mappend Empty Empty = Empty
    mappend Empty t = t
    mappend t Empty = t
    mappend (Node val ta tb) (Node val' ta' tb') = (Node (mappend val val') (mappend ta ta') (mappend tb tb'))

This compiles, but it was tedious to write and very repetitive. Is there a better way of doing this?

You can remove mappend Empty Empty = Empty because that case will be caught by mappend Empty t = t.

instance (Monoid a) => Monoid (Tree a) where
    mempty = Empty
    mappend Empty t = t
    mappend t Empty = t
    mappend (Node val ta tb) (Node val' ta' tb') = (Node (mappend val val') (mappend ta ta') (mappend tb tb'))


F# Simple message reader using TCP I have a review request about this part of the code:

let private startReading (client:TcpClient) (bus:IBus) =
    //TODO check if that can be changed to rec parameter
    let frameNumber = ref 0
    let rec StartReading (client:TcpClient) =
        async{
            match client with
            | null -> async { return 0 } |> Async.StartAsTask |> ignore
            | _ ->
                match (client.IsConnectionEstablished()) with
                | true ->
                    incr frameNumber
                    DeployService.DeployCabninetService
                    let! messange = MessagingHandler.ReadMessage client

                    match(messange) with
                        | Some data ->
                            let frameNumber = uint32 frameNumber.Value
                            logger.Info(sprintf "Received message with Frame Number: %i" frameNumber)

                        | None ->
                            _logger.Info(sprintf "Client disconnected : %O" client.Client.RemoteEndPoint)
                            return! DisconnectClient client None

                    return! StartReading client
                | false ->
                    _logger.Info(sprintf "Client disconnected : %O" client.Client.RemoteEndPoint)
                    return! DisconnectClient client None
        }

    StartReading client |> Async.StartAsTask

It is simple reading message procedure from tcp client in f#, but I feel this can be written more gracefully, especially todo part with frame number incrementation using ref in f# feels wrong.

Any suggestions?

Why do you make this call Async.StartAsTask instead of just return the Async<T> to let the client handle that as needed?

  let rec StartReading (client:TcpClient) =

I would call it reader and then give it the signature of:

let rec reader frameNo (client:TcpClient) =

in order to get rid of reffor frameNumber.

You can then initially call it:

reader 0 client |> Async.StartAsTask

and recursively:

return! reader (frameNo + 1) client


LeetCode 76: Minimum Window Substring - Python I'm posting a two-pointer, sliding-window problem of LeetCode (Minimum Window Substring) solved with Python. If you have time and would like to review the code, please do so, I appreciate that.
On LeetCode, we are only allowed to change the variable names and brute force algorithms are discouraged, usually fail with TLE (Time Limit Error) or MLE (Memory Limit Error).
Problem

Given a string base_string and a string target, find the minimum window
in base_string which will contain all the characters in target in
complexity O(n).
Example:
Input: base_string = "ADOBECODEBANC", target = "ABC" Output: "BANC"
Note:
If there is no such window in base_string that covers all characters in
target, return the empty string "". If there is such window, you are
guaranteed that there will always be only one unique minimum window in
base_string.

Solution 1
import collections

class Solution:
    def minWindow(self, base_string: str, target: str) -> str:
        count_map = collections.Counter(target)
        left = 0
        min_left, min_right = 0, 0
        target_length = len(target)

        for right, char in enumerate(base_string, 1):
            target_length -= count_map[char] > 0
            count_map[char] -= 1
            if not target_length:
                while left < right and count_map[base_string[left]] < 0:
                    count_map[base_string[left]], left = -~count_map[base_string[left]], -~left
                if not min_right or right - left <= min_right - min_left:
                    min_left, min_right = left, right

        return base_string[min_left:min_right]

Solution 2
import collections

class Solution:
    def minWindow(self, base_string: str, target: str) -> str:
        count_map = collections.Counter(target)
        left, right = 0, 0
        min_left, min_right, min_window = 0, float('inf'), ''
        target_length = len(target)

        while right < len(base_string):
            if count_map[base_string[right]] > 0:
                target_length -= 1

            count_map[base_string[right]] -= 1

            while target_length == 0:
                sliding_window = -~right - left

                if not min_window or sliding_window < len(min_window):
                    min_window = base_string[left:-~right]

                count_map[base_string[left]] += 1

                if count_map[base_string[left]] > 0:
                    target_length += 1
                left += 1
            right += 1

        return min_window

Reference

Question

Solution

Discussion

I'm not sure if online courses even go into this, but this is the exact opposite of what good code should look like. Unless there is a dire performance requirement (which is rarer than you think) the aim is always to make your code as readable (clear/stupid/simple) as possible, so that:

Errors have fewer places to hide
It is easier to reason about what the code is doing without going into how, which in turn helps you uncover errors, and makes it easier to change.

The most important factor in readability is intent. If you can't tell what the programmer is trying to accomplish, or how they are going about it, it will be very difficult to detect bugs.
So the real focus should be on making it clear from your code what your intention is, preferably baked into the code itself (structure, variable names etc...) and failing that, add comments.
This means you first need to decide on your overall strategy, so in this case: how are you going to find this window? There are many options, here are some:

Are you going to first get all possible windows and try each of them?
Are you going to try all windows at position 0, then move to position 1 etc...?
Are you going to try all windows of smallest size, then next size etc...?

In your code, I am really not sure what you're going for. Both are also big functions with a lot of variables. So I didn't even try to figure out what it does (and it would be the same in a professional code review: if I don't understand at a glance what the code is even trying to do, it gets rejected).
I'll go with that last option to give you an idea of how I would write code which makes the intention clear. You'll note that by forcing the code to clearly show its intention you also end up having to break things into smaller parts, and use clear variable names, and all of these things help.
Ps: you don't need to define a class in python ;-)
def find_window(base_string, target):
    """
    Try all windows in ascending size order, left to right.
    """
    base_string_length = len(base_string)

    def all_chars_in_window(window):
        for c in target:
            if c not in window:
                return False
        return True

    def find_match_at_size(try_length):
        end = try_length
        start = 0
        while end <= base_string_length:
            window = base_string[start:end]
            if all_chars_in_window(window):
                return window
            start += 1
            end += 1

    try_length = len(target)
    while (try_length <= base_string_length):
        window_found = find_match_at_size(try_length)
        if window_found:
            return window_found
        try_length += 1
    return ''

base_string = "ADOBECODEBANC"
target = "ABC"
expected = "BANC"

print(find_window(base_string, target))

This took 7 minutes to write, because I only had to write simple code: each bit only has a couple of variables and does something very simple. If I had forced myself to do it the way you did with all those variables and calculations, I would have been at it much longer.
Hope this helps.


Stack implemented with linked list I have looked at some previous posts and changed my code accordingly.  Do you have some suggestions about my current code?

Here are my specific questions:

What should top() return if the stack is empty?
Why it’s better to use size_t for count?
I didn’t use new to create the stack in main().  Do I need to call the destructor? If no, why? If yes, how should I do it?
According to the rule of three, how will I define the assignment operator for stack? Can you give one example?
I feel I have some misunderstanding about private.  I put top_node in the private section, but why I am able to access top_node in the copy constructor?

The following code compiles and runs.

#include<iostream>
using namespace std;

template<class T>
class MyStack{
public:
    MyStack(): top_node(nullptr), count(0){};

    MyStack(MyStack& st){
        top_node = new Node(st.top());
        Node* temp = st.top_node->next;
        Node* pre = top_node;
        while(temp){
            Node* cur = new Node(temp->val);
            pre->next = cur;
            temp = temp->next;
        }
        count = st.size();
    }

    void push(T item){
        Node* temp = new Node(item);
        if(empty()){
            top_node = temp;
        }else{
            temp->next = top_node;
            top_node = temp;
        }
        count++;
    }

    void pop(){
        if(empty()){
            cout<<"Nothing to pop!"<<endl;
            return;
        }
        Node* temp = top_node;
        top_node = temp->next;
        delete temp;
    }

    int top() const{
        if(empty()){
            cout<<"Nothing to top!"<<endl;
            return -1;
        }
        return top_node->val;
    }

    size_t size() const{
        return count;
    }

    void print() const{
        Node* temp = top_node;
        while(temp){
            cout<<temp->val<<" ";
            temp = temp->next;
        }
        cout<<endl;
    }

    bool empty() const{
        return count==0;
    }

    ~MyStack(){
        Node* temp = top_node;
        while(temp){
            Node* t = temp;
            temp = temp->next;
            delete t;
        }
        top_node = nullptr;
    }

private:
    struct Node{
        T val;
        Node* next;
        Node(T x): val(x), next(nullptr){};
    };
    Node* top_node;
    size_t count;

};

int main(){

    MyStack<char> sasa;
    cout<<"default top: "<<sasa.top()<<endl;
    cout<<"default count: "<<sasa.size()<<endl;

    sasa.pop();
    sasa.push('a');
    sasa.push('p');
    sasa.push('p');
    sasa.print();
    sasa.top();
    cout<<"The current size is "<<sasa.size()<<endl;
    sasa.pop();
    sasa.print();
    cout<<"if empty: "<<sasa.empty()<<endl;

    MyStack<char> sec(sasa);
    sec.print();

    return 0;
}

Implementation issues

using namespace std; is frowned upon, especially in header files. Assuming MyStack is intended to be included elsewhere, this might cause name collisions in other unrelated code.

There's a superfluous (and possibly confusing) semicolon after default constructor.

Memory leak: If something inside the copy constructor were to throw an exception (e.g. one of those calls to new), already created nodes will not be deleted.

Another memory leak/bug in the copy constructor: pre doesn't get advanced during the while loop, so it's always pointing to top_node. Every assignment pre->next = cur overwrites the current value of top_node->next, resulting in a stack of depth 2.

Also, since the copy constructor doesn't modify st, it could be made const MyStack&.

Memory leak: MyStack<T>::push leaks temp in case the Node constructor throws an exception (e.g. because Ts copy constructor throws one).

Wrong return type: MyStack::top() is declared to return an int, but actually returns MyStack<T>::Node::val, which is of type T.

No need for top_node = nullptr inside the destructor: Nobody is going to read that value again.

The whole destructor body could be extracted into a clear member function, which the destructor then calls.

A lot of the member functions (basically everything not calling new) can be marked noexcept. Doing so allows for better code generation and allows others to use MyStack to its fullest.

pop doesn't decrease count.

Design issues

MyStack::print might be helpful with debugging, but likely shouldn't be in the final product (unless there is a specific requirement for it).
print can likely be very easily implemented using an iterator interface if one is provided.

MyStack is unable to contain types that cannot be copy-constructed. Think about splitting push(T) into two functions push(const T&) and push(T&&), and maybe add an emplace member function that forwards its arguments in order to construct the T in place.

top could return a referene instead of a copy. This prevents issues with non-copyable types. Might require two overloads, though (const T& top() const and T& top()), to accomodate for constness of this.

Technically, MyStack<T> can be copied only if T is copy-constructible. This can be asserted at compile time using some template metaprogramming (which might be too advanced at the moment), but at the very least I'd expect this behavior to be documented.

C++11 features
C++11 introduced smart pointer like std::unique_ptr and std::shared_ptr into the standard library. You might want to read up on them, as they come in quite handy and help a lot to prevent memory leaks. Just know their limits (recursive destruction/cycles).
Using them would have prevented a lot of the memory issues mentioned above. For more information on the topic I can recommend this talk by Herb Sutter.

Also, C++11 introduced {} for object initialization, in order to "fix" the so-called most vexing parse: What is foo in the following snippet?
int foo(A);

That answer depends on what A is:

If A can be interpreted as a type then foo is declared as a function taking an A as parameter and returning an int.

If A is a value then foo is a local int variable that gets initialized to the value of A.

In order to prevent this ambiguity (and a huge list of similar ones) prefer to use brackets {} for object initialization instead of () if possible.

There are some cases where this isn't possible; however, those cases are rare (I can only think of one off my head, and that's the std::vector<T>::vector(size_t, T) constructor where T is some arithmetic type like int or float, as the initializer-list constructor takes precedence there).

Q&A

What should top() return if the stack is empty?

What can it meaningfully return? Nothing!
The precondition of calling top is that the stack must not be empty. If top is called while the stack is empty, that operation is meaningless. You can be nice and throw an exception to signal that this function was called erroneously, or not be nice and force checking upon the caller in order to avoid internal nullptr dereferences.

Usually, stack implementations throw an exception, unless the environment forbids those or safety is sacrificed to gain some minimal performance.

Why it’s better to use size_t for count?

This point has been up for debate quite a lot, and most often the consensus is: Don't use unsigned values for sizes, as it can cause unexpected interactions with signed values.

It got into the standard library as "the" size type because they wanted to use another bit for size (in order to use up to 4 GiB RAM on 32-bit machines), but in hindsight (and with modern 64-bit processors) the unexpected interactions with signed values tipped the scale towards that conclusion.

I didn’t use new to create the stack in main(). Do I need to call the destructor? If no, why? If yes, how should I do it?

sasa and sec in main have automatic storage duration, which means that they get automatically destructed once they fall out of scope (at the closing } of main) in reverse order of construction.

According to the rule of three, how will I define the assignment operator for stack? Can you give one example?

The "Rule of Three" got extended to "Rule of Five" in C++11 and onwards in order to accomodate for move constructors and move assignment operators. So, let's get started with those additions (as they are fairly easy to implement):
MyStack(MyStack&& other) noexcept : top_node{other.top_node}, count{other.count} {
    other.top_node = nullptr;
    other.count = 0;
}

MyStack& operator=(MyStack&& other) noexcept {
    if(this != &other) {
        // destroy current list
        clear();

        // move others list
        top_node = other.top_node;
        count = other.count;

        // leave other in a valid state
        other.top_node = nullptr;
        other.count = 0;
    }

    return *this;
}

One way to do the copy assignment operator is to use the copy-and-swap idiom:
MyStack& operator=(const MyStack& other) {
    auto copy = other;
    swap(other);
    return *this;
}

But this requires a swap function, which might look like this:
void swap(MyStack& other) noexcept {
    using std::swap;
    swap(top_node, other.top_node);
    swap(count, other.count);
}

Most implementations also provide a freestanding swap(MyType& a, MyType& b) function (which basically forwards to a.swap(b)) to allow their types to be used in this fashion.

I feel I have some misunderstanding about private. I put top_node in the private section, but why I am able to access top_node in the copy constructor?

You can access st.top_node and st.count inside the copy constructor because you are still inside the same class!
private just means "nobody outside of this class (or its friends) can see this" - but the copy constructor is obviously inside. (Otherwise, how could it initialize this->top_node?)
This level of access can also be granted to other classes or functions by making them a friend of the class:
class A;
void foo(B b);

class B {
    friend class A;
    friend void foo(B b);

    int c;
};

Now B::c is visible inside A or foo, too.

Use this sparingly, though, as it breaks encapsulation. Sometimes it is needed, but more often than not there is a better alternative available.


Switching first names with surnames The objective is to get a list of number and then switch the last person surname with the first person surname; when I type '$' it do the changes and finish the program! (POINTERS and DYNAMIC ALLOCATION).
I have to use pointers and dynamic allocation, my code is nice, but I know that it can be better.
How can I start to identify parts of my code that could be extracted to functions?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char ***names=NULL;
        int i, j, k, letter, totalNames, auxInt;
        int *wordsbyname= NULL;
        char *auxWord;
        i=j=k=0;

        do
        {
                names=realloc(names, (i+1)*sizeof(char**));
                names[i]=NULL;
                wordsbyname=realloc(wordsbyname, (i+1)*sizeof(int));
                j=0;
            do
            {
                names[i]=realloc(names[i],(j+1)*sizeof(char*));
                names[i][j]=NULL;
                k=0;
                    do{
                        letter=getchar();
                        names[i][j]=realloc(names[i][j], (k+1)*sizeof(char));
                        names[i][j][k]=letter;
                        k++;
                    }while ((letter!= 10) && (letter!=32) && (letter!=36));
                    names[i][j][k-1]='\0';
                    j++;
            }while((letter!= 10)&&(letter!=36));
            wordsbyname[i]=j;
            i++;
        }while (letter!=36);
        totalNames=i;
        printf("\n");

        for(i=0;i<totalNames/2;i++){
            auxInt=totalNames-i-1;
            auxWord=malloc(sizeof(char)*(strlen(names[i][wordsbyname[i]-1])+1));
            strcpy(auxWord,names[i][wordsbyname[i]-1]);
            names[i][wordsbyname[i]-1]=realloc(names[i][wordsbyname[i]-1], sizeof(char)*strlen((names[auxInt][wordsbyname[auxInt]-1])+1));
            strcpy(names[i][wordsbyname[i]-1],names[auxInt][wordsbyname[auxInt]-1]);
            names[auxInt][wordsbyname[auxInt]-1]=realloc(names[auxInt][wordsbyname[auxInt]-1],sizeof(char)*(strlen(auxWord)+1));
            strcpy(names[auxInt][wordsbyname[auxInt]-1],auxWord);
            free (auxWord);
        }

        for(i=0 ; i<totalNames; i++){
            for (j=0; j<wordsbyname[i];j++){
                printf("%s ", names[i][j]);
                free(names[i][j]);
            }
            free(names[i]);
            printf("\n");
        }
    free(wordsbyname);
    free(names);

    return 0;
}

I can't comment on variable names because I don't know your language, this will limit the scope of the review I can do and I hope you understand everything in this review / answer. The memory management is good, I don't see any memory leaks.
Test for Possible Memory Allocation Errors
In modern high level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in unknown behavior (UB).
Possible unknown behavior in this case can be a memory page error (in Unix this would be call Segmentation Violation), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).
To prevent this unknown behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.
Example of Current Code:
        nomes = realloc(nomes, (i + 1) * sizeof(char **));
        nomes[i] = NULL;
        palavraspornome = realloc(palavraspornome, (i + 1) * sizeof(int));
        j = 0;
        do

Example of Current Code with Test:
    do
    {
        nomes = realloc(nomes, (i + 1) * sizeof(char **));
        if (nomes != NULL)
        {
            nomes[i] = NULL;
            palavraspornome = realloc(palavraspornome, (i + 1) * sizeof(int));
            if (palavraspornome == NULL)
            {
                fprintf(stderr, "Memory allocation error when allocating palavraspornome.\nUnable to recover, program exiting.\n");
                return EXIT_FAILURE;
            }
        }
        else {
            fprintf(stderr, "Memory allocation error when allocating nomes.\nUnable to recover, program exiting.\n");
            return EXIT_FAILURE;
        }
        j = 0;
        do

A good way to get rid of some of the code repetition would be to create a function that allocates memory, does the test, reports the error when it happens and exits the program.
void *safe_memory_allocation(size_t size_to_allocate)
{
    void *return_pointer = malloc(size_to_allocate);
    if (return_pointer == NULL)
    {
        fprintf(stderr, "Memory allocation error .\nUnable to recover, program exiting.\n");
        exit(EXIT_FAILURE);
    }

    return return_pointer;
}

Convention When Using Memory Allocation in C
When using malloc(), calloc() or realloc() in C a common convetion is to sizeof(*PTR) rather sizeof(PTR_TYPE), this make the code easier to maintain and less error prone, since less editing is required if the type of the pointer changes.
    do
    {
        nomes = realloc(nomes, (i + 1) * sizeof(*nomes);
        if (nomes != NULL)
        {
            nomes[i] = NULL;
            palavraspornome = realloc(palavraspornome, (i + 1) * sizeof(*palavraspornome));
            if (palavraspornome == NULL)
            {
                fprintf(stderr, "Memory allocation error when allocating palavraspornome.\nUnable to recover, program exiting.\n");
                return EXIT_FAILURE;
            }
        }
        else {
            fprintf(stderr, "Memory allocation error when allocating nomes.\nUnable to recover, program exiting.\n");
            return EXIT_FAILURE;
        }
        j = 0;
        do

Complexity
The function main() is too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.
There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

There are at least 3 sub functions that can be extracted from main(), each of the major loops is a candidate for a function, some of the smaller loops may also be good candidates. A sample function that you could implement if you are not on a POSIX where this is a C library function is char *strdup(const char *str1) (this function was merged into the C ISO standard in 2019).
The implementation of strdup() would look something like this:
char *strdup(const char *original_string)
{
    size_t new_size = strlen(original_string) + 1;
    char *duplicate = calloc(sizeof(*original_string), new_size);
    if (duplicate != NULL)
    {
        memcpy(&duplicate[0], original_string, new_size);
    }
    return duplicate;
}

Whether you write or own or use the library version strdup() returns NULL if the memory allocation failed so the value must be tested before use.
Possible Performance Improvements
Rather than use character input (letra = getchar();) get a line of text at a time using fgets(char *buffer, size_t buffer_size, FILE *filename). This reduces the amount of code necessary and it will be faster than character input.
Instead of
        do
        {
            nomes[i] = realloc(nomes[i], (j + 1) * sizeof(char *));
            nomes[i][j] = NULL;
            k = 0;
            do
            {
                letra = getchar();
                nomes[i][j] = realloc(nomes[i][j], (k + 1) * sizeof(char));
                nomes[i][j][k] = letra;
                k++;
            } while ((letra != 10) && (letra != 32) && (letra != 36));
            nomes[i][j][k - 1] = '\0';
            j++;
        } while ((letra != 10) && (letra != 36));

Use
        do
        {
            nomes[i] = realloc(nomes[i], (j + 1) * sizeof(char *));
            nomes[i][j] = NULL;
            k = 0;
            char buffer[1024];
            if (fgets(buffer, 1024, stdin) != 0)
            {
                nomes[i] = strdup(buffer);
            }
            j++;
        } while ((letra != 10) && (letra != 36));
        palavraspornome[i] = j;

Rather than calling realloc() for every new string create an array of an arbitrary number of names and then reallocate that array when the capacity is reached.
the following code is a basic idea, it may not compile properly or run
char ***resize_nomes_array(char ***nomes, size_t *current_capacity, int i)
{
    char ***new_nomes = NULL;

    if (current_capacity == 0)
    {
        *current_capacity = 10;
    }
    else
    {
        *current_capacity = (size_t)(*current_capacity * 1.5);
    }

    if (nomes == NULL)
    {
        new_nomes = calloc(*current_capacity, sizeof(*new_nomes));
    }
    else
    {
        new_nomes = realloc(nomes, *current_capacity * sizeof(*nomes));
    }

    if (new_nomes == NULL) {
        fprintf(stderr, "Memory allocation error when allocating nomes.\nUnable to recover, program exiting.\n");
        exit(EXIT_FAILURE);
    }

    for (size_t index = i; index < *current_capacity; index++)
    {
        new_nomes[index] = NULL;
    }
    return new_nomes;
}


Detecting if an element is found inside a container I just wrote this template to detect if a given element is found inside a container:

template <typename Iterator> bool is_contained(Iterator begin, Iterator end, decltype(*begin) object)
{
    for (; begin != end; ++begin)
    {
        if (*begin == object)
        {
            return true;
        }
    }
    return false;
}

Which then would be called for examples as:

bool test = is_contained<decltype(container.begin())>(container.begin(), container.end(), anything);

This works fine, but I believe it is not so readable. I am also new to using decltype which makes me wonder if this would crash, and somehow I wont be calling the template correctly. Any feedback is highly appreciated.

Note that for functions the compiler will detect the template types based on the parameters.
So you can simply write:

bool test = is_contained(container.begin(), container.end(), anything);

I don't particularly like the use of decltype in your function. I would simply make it another template parameter.

template <typename Iterator, typename Value>
bool is_contained(Iterator begin, Iterator end, Value const& object);

Because of the compiler deducing the names you can use any type. Also this is more flexable as it allows you to use any type that is comparable to the type inside the container (rather than only allowing values that are the same type (or trivial convertible)).


Custom CursorAdapter Design Here's the code which I use for my Android custom cursor adapter which I use to bind data to my list view.

public class MessageAdapter extends CursorAdapter {
   private Cursor mCursor;
   private Context mContext;
   private final LayoutInflater mInflater;

    public MessageAdapter(Context context, Cursor c) {
        super(context, c);
        mInflater=LayoutInflater.from(context);
    mContext=context;
    }

    @Override
    public void bindView(View view, Context context, Cursor cursor) {

        TextView mobileNo=(TextView)view.findViewById(R.id.mobileNolistitem);
        mobileNo.setText(cursor.getString(cursor.getColumnIndex(TextMeDBAdapter.KEY_MOBILENO)));

        TextView frequency=(TextView)view.findViewById(R.id.frequencylistitem);
        frequency.setText(cursor.getString(cursor.getColumnIndex(TextMeDBAdapter.KEY_FREQUENCY)));

        TextView rowid=(TextView)view.findViewById(R.id.rowidlistitem);
        rowid.setText(cursor.getString(cursor.getColumnIndex(TextMeDBAdapter.KEY_ID)));

    }

    @Override
    public View newView(Context context, Cursor cursor, ViewGroup parent) {
        final View view=mInflater.inflate(R.layout.message_list_item,parent,false);
        return view;
    }

}

I know that there's another efficient way to do this which reuses the list item instantiated.  Can someone tell me how?

This is exactly* the way you should be using your CursorAdapter. I'm sure you're referring to "recycling" the Views as talked about when overriding the getView() method of a BaseAdapter.

In the case of the CursorAdapter, all of that is taken care of for you so that just implementing newView() and bindView() fully takes advantage of the View recycling you're asking about.

Here is the code for CursorAdapter.getView():

public View getView(int position, View convertView, ViewGroup parent) {
    if (!mDataValid) {
        throw new IllegalStateException("this should only be called when the cursor is valid");
    }
    if (!mCursor.moveToPosition(position)) {
        throw new IllegalStateException("couldn't move cursor to position " + position);
    }
    View v;
    if (convertView == null) {
        v = newView(mContext, mCursor, parent);
    } else {
        v = convertView;
    }
    bindView(v, mContext, mCursor);
    return v;
}

So you see, the method attempts to recycle the View that was passed in by checking convertView == null. If successful, it uses that View and simply calls bindView() to set it up appropriately. If convertView is null, it calls newView() to create the View, followed by bindView() to set it up. This is one of the rare instances on SE that I can say "You're doing it right!"

But to nitpick, there's really no reason to maintain a reference to your Context in mContext - You're not using it anywhere and maintaining references to Contexts can lead to memory leaks, and ultimately the end of the world.


Mutually exclusive radio buttons Here is a small code snippet I wrote that I feel is pretty naive. I copied the code directly from my project and renamed some ID/class names.

I'd like to know how you could help to improve/refactor the code. radiobox1 and radiobox2 form a pair, and radiobox3 and radiobox4 form another pair - they're both mutually exclusive - which means select radiobox1 then radiobox2 is disabled, and vice versa. Then I will load the data in terms of the user's selection combination. In total, there are 4 selection combinations.

var viz = (function () {
    var config = {
        width: 960,
        height:600,
        big: true,
        small: true,
        index: 0
    };

    var emptyGraph = function () {
        if (!$('#graph').is(':empty')) {
            $("#graph").empty();
        }
    };

    var bind = function () {
        $("#radiobox1").change(function () {
           if ($(this).is(':checked')) {
               emptyGraph();
               $("#radiobox2").prop("checked", false);
               config.small = true;
               loader.loadData(config);
           }
        });

        $("#radiobox2").change(function () {
            if ($(this).is(':checked')) {
                emptyGraph();
                $("#radiobox1").prop("checked", false);
                config.small = false;
                loader.loadData(config);

            }
        });

        $("#radiobox3").change(function () {
            if ($(this).is(':checked')) {
                emptyGraph();
                $("#radiobox4").prop("checked", false);
                config.big = true;
                loader.loadData(config);
            }
        });

        $("#radiobox4").change(function () {
            if ($(this).is(':checked')) {
                emptyGraph();
                $("#radiobox3").prop("checked", false);
                config.big = false;
                config.index = 1;
                loader.loadData(config);
            }
        });

    };

    return {
        init: bind,
    }

})();

Radio buttons already group together using the name attribute. I suggest throwing away the code.

<input type="radio" name="group1" value="male">Male

<input type="radio" name="group1" value="female">Female

<input type="radio" name="group2" value="1">Active

<input type="radio" name="group2" value="0">Inactive


optimizing a rollercoaster queue I am working on a haskell exercise where I have to compute the amount of people riding a rollercoaster in a day. I have the following data: the number of rides  in a day, the number of seats, and the composition of the queue.

The queue is a list of groups. During each ride, the first few groups of the list enter the ride. A group always rides together. The total number of people cannot exceed the number of seat during one ride.

After the ride, the groups go to the end of the queue (in the same order).

So the exercise is not really hard. But when numbers get big, my haskell implementation becomes quite slow. I have used the profiler to improve some parts, but I wasn't able to spot a bottleneck.

The first time I ran the profiler, the part that was parsing the groups was slow. Here is my second version (1st one was replicateM n $ read <$> getLine):

getGroups :: IO [Int]
getGroups = do
    c <- TIO.getContents
    return $ readInts c

readInts :: T.Text -> [Int]
readInts s
    | T.null s = []
    | otherwise = val : rest where
        (Right (val, s')) = TR.decimal s
        rest = if T.null s'
            then []
            else (readInts $ T.tail s')

Another cost center is the actual computing function:

type Queue = Seq.Seq Int
data Roller = Roller Int Int Queue

compEarn :: Roller -> Int
compEarn (Roller placeNbr rideNbr groups) = go rideNbr groups 0
  where
    go turnsLeft queue accum
        | turnsLeft == 0 = accum
        | otherwise = let
            (riding, waiting) = breakQueue placeNbr queue
            newQueue = waiting Seq.>< riding
            newAccum = accum + (F.sum riding)
            in go (turnsLeft - 1) newQueue newAccum

breakQueue :: Int -> Queue -> (Queue, Queue)
breakQueue placeNbr queue = go Seq.empty queue placeNbr where
    go riding waiting spaceLeft = case Seq.viewl waiting of
            Seq.EmptyL -> (riding, waiting)
            group Seq.:< rest -> if spaceLeft' < 0
                then (riding, waiting)
                else go (riding Seq.|> group) rest spaceLeft'
              where
                spaceLeft' = spaceLeft - group

Am I missing something obvious regarding performances with this program?

So I found a few improvements which solve my problem. First, I used a vector to represent the queue, and a rolling index to store the head of the queue:

type Queue = V.Vector Int
data RollingQ = RollingQ Queue Int

currentVal :: RollingQ -> Int
currentVal (RollingQ v i) = v V.! i

nextVal :: RollingQ -> RollingQ
nextVal (RollingQ v i)
    | i == V.length v = RollingQ v 0
    | otherwise = RollingQ v (i + 1)

This led me to realize that there might be a cycle in the computation: if the number of rides is bigger than the number of groups in the queue, the state of the queue loops. I used a Map to remember information about the computation to detect the loop and compute a shortcut to get the result almost immediately.


Is my first MVC architecture set up to standards? I just started learning about the MVC architecture. And I started to create my own MVC framework to how I like it the most.

Here I've got the index.php, indexcontroller.php and view.php. I'm not too sure if what I am doing is right, or with best practices. So I would like to know if there is anything I missed so far, or what I could improve?

Index.php (updated)

//report all php errors
error_reporting(E_ALL);

//define site root path
define('ABSPATH', dirname(__FILE__));

//include functions
foreach(glob(ABSPATH . '/functions/*.php') as $filename) {
    require $filename;
}

//set config array
$config = parse_ini_file(ABSPATH . '/config.ini', true);
$config = json_decode(json_encode($config));

//auto load classes
spl_autoload_register('autoloadCore');
spl_autoload_register('autoloadController');
spl_autoload_register('autoloadModel');

//url to class router
Glue::stick((Array) $config->routes);

IndexController

class IndexController extends BaseController {
    private $_view;

    public function GET() {
        $this->index();
    }

    public function POST() {
        //don't handle post
    }

    public function __construct() {
        $this->_view = new View();
    }

    public function index() {
        $this->_view->welcome = 'Welcome!';
        $this->_view->render('index');
    }
}

View

class View {
    private $_vars = [];

    public function __set($index, $value) {
        $this->_vars[$index] = $value;
    }

    function render($fileView) {
        $path = ABSPATH . '/view/' . $fileView . '.php';
        if(!file_exists($path)) {
            throw new Exception('View not found: '. $path);
        }
        foreach($this->_vars as $key => $value) {
            $$key = $value;
        }
        include ($path);
    }
}

MVC approaches differ between languages, platforms and frameworks. They are usually termed "MV* frameworks" because they don't exactly follow strict MVC. But we call them MVC nonetheless.

Separate core logic from configurable logic

The way I understand your code, it looks like you've gone over CodeIgniter (or something similar). I assume all your requests run through index.php where the initial logic runs, like the helper loading, routing etc. For that, I suggest you separate the autoloader list and routing list to different files. You can load them via something like include. That way, you don't accidentally modify the core logic.

// autoload.php
$autoload = array(
  'autoloadCore',
  'autoloadController',
  'autoloadModel'
);

// routes.php
$routes = array(
  '/'       => 'Index',
  '/signup' => 'SignUp',
  '/login'  => 'Login'
);

Additionally, the word "Controller" might not be necessary for the routing. You already know that they always go to controllers. You might want to do that in the underlying logic instead, and keep it easy on the configurable parts.

Route lists cons

One thing to note with this routing strategy is that whenever you add a controller, you always need to list down the route. This approach is not that nice, especially when you are going to be handling a hundred routes (and trust me, it ain't a walk in the park).

Auto-route + custom routes

Why not automatically look for controllers based on a predefined convention (like CodeIgniter). A route of /foobar/bam would route to FoobarController and execute the bam method. As for custom routes, you can map it like so:

$routes = array(
  'autobam' => 'foobar/bam` // A route of `/autobam` executes the same as `foobar/bam`
);

And the flow goes like:

- Parse route
- Check for match under custom
  - If match, convert to equivalent route
- Use non-custom/equivalent route for locating the controller
  - If none, throw error
  - Else, load and execute