Monte Carlo coin flip simulation I've been learning about Monte Carlo simulations on MIT's intro to programming class, and I'm trying to implement one that calculates the probability of flipping a coin heads side up 4 times in a row out of ten flips.

Basically, I calculate if the current flip in a 10 flip session is equal to the prior flip, and if it is, I increment a counter. Once that counter has reached 3, I exit the loop even if I haven't done all 10 coin flips since subsequent flips have no bearing on the probability. Then I increment a counter counting the number of flip sessions that successfully had 4 consecutive heads in a row. At the end, I divide the number of successful sessions by the total number of trials.

The simulation runs 10,000 trials.

def simThrows(numFlips):
    consecSuccess = 0   ## number of trials where 4 heads were flipped consecutively
    coin = 0  ## to be assigned to a number between 0 and 1
    numTrials = 10000
    for i in range(numTrials):
        consecCount = 0
        currentFlip = ""
        priorFlip = ""
        while consecCount <= 3:
            for flip in range(numFlips):
                coin = random.random()
                if coin < .5:
                    currentFlip = "Heads"
                    if currentFlip == priorFlip:
                        consecCount += 1
                        priorFlip = "Heads"
                    else:
                        consecCount = 0
                        priorFlip = "Heads"
                elif coin > .5:
                    currentFlip = "Tails"
                    if currentFlip == priorFlip:
                        consecCount = 0
                        priorFlip = "Tails"
                    else:
                        consecCount = 0
                        priorFlip = "Tails"
            break
        if consecCount >= 3:
            print("Success!")
            consecSuccess += 1
    print("Probability of getting 4 or more heads in a row: " + str(consecSuccess/numTrials))

simThrows(10)

The code seems to work (gives me consistent results each time that seem to line up to the analytic probability), but it's a bit verbose for such a simple task.  Does anyone see where my code can get better?

When you're writing code for educational purposes (or sometimes other purposes), verbose is good because it helps you understand what's really going on. So making the code shorter or snappier or whatever is not necessarily going to make it better.

With that disclaimer out of the way: one of the most common ways to condense Python code is to use list comprehensions or generators instead of loops. A list comprehension is what you use when you're constructing a list element by element: in its simplest form, instead of this,

the_list = []
for something in something_else:
    the_list.append(func(something))

you write this:

the_list = [func(something) for something in something_else]

If you're doing something else instead of creating a list, you can have Python create an object that generates the elements on demand, rather than actually creating a list out of them. An object of that sort is called a generator and you can create one like this:

the_generator = (func(something) for something in something_else)

You can omit the parentheses when the generator is passed to another function as an argument, though.

the_sum = sum(func(something) for something in something_else)

would be equivalent to, but better than,

count = 0
for something in something_else:
    count += func(something)

There are a lot of functions in Python that take iterables (list, generators, etc.) and "condense" them into one value using some sort of operation. You can also create your own, corresponding to whatever you would be doing to the result of the loop. You can convert most loops into generator expressions this way.

So let's investigate how you could use a generator to represent the sequences of consecutive throws in each trial. You can create a generator that produces 10 random numbers easily:

(random.random() for i in xrange(10))

(this is for Python 2.x; xrange was renamed to range for Python 3). Or you can create a generator that produces 10 random values which are either 0 or 1:

(random.randint(0,1) for i in xrange(10))

That saves you from having to check each random number against 0.5. In fact, you could produce a generator that produces 10 randomly chosen words, "Heads" or "Tails", like so:

(random.choice(("Heads","Tails")) for i in xrange(10))

but it'll be easier to stick with numbers. (It's usually better to represent things with numbers or objects than with strings.)

But perhaps you're thinking, "why are you telling me to make 10 numbers when I only have to check until I find a group of four consecutive heads?" For one thing, if you're just flipping 10 coins each time, it really doesn't matter because you'll make the computer flip at most 6, and on average 3, extra coins in each trial. That doesn't take very long - it'll extend the runtime of this part of your program by 50%, but we're talking 50% of a fraction of a second. It's not worth the effort to figure out how to do it for such a small number of flips. But if each flip had, say, a billion trials, then you would definitely want to stop early. Fortunately, a generator can do this for you! Since generators produce their elements only on demand, you can stop taking elements from it once you get what you want, and not waste much of any computation. I'll address this more later.

Anyway, suppose we have our generator that produces 10 binary values 0 (tails) or 1 (heads). Is there a way to go through this and check to see whether there is a sequence of four or more heads? It turns out that just such a function is provided in itertools.groupby, which takes any iterable (list, generator, etc.) and groups consecutive identical elements. An example of its usage is

for k, g in itertools.groupby([1,0,0,1,1,1,1,0,0,0]):
    print k, list(g)

and this would print out something like

1 [1]
0 [0,0]
1 [1,1,1,1]
0 [0,0,0]

So you can check for four or more consecutive heads by just looking at the length of the group and whether the key is heads or tails.

for k, g in itertools.groupby(random.randint(0,1) for i in xrange(10)):
    if k and len(g) >= 4:
        # got a run of 4 or more consecutive heads!
        # wait, what now?

(In Python, 1 is true and 0 is false in a boolean context, so if k is equivalent to if k == 1.) OK, what shall we do with our run of 4 or more consecutive heads? Well, you're trying to find the number of trials in which this occurs. So it probably makes sense to set a success flag if this happens.

success = False
for k, g in itertools.groupby(random.randint(0,1) for i in xrange(10)):
    if k and len(g) >= 4:
        success = True
        break # this stops asking the generator for new values

But wait! This is starting to look a lot like the kind of loop that can be converted to a generator expression, isn't it? The only catch is that we're not adding anything up or constructing a list. But there is another function, any, that will go through a generator until it finds an element which matches a condition, and that's just what this for loop does. So you could write this as

success = any(k and len(g) >= 4 for k, g in
                itertools.groupby(random.randint(0,1) for i in xrange(10))

Now finally, you'll want to count how many times this happens over, say, 10000 trials. So you might write that as something like this:

successes = 0
for i in xrange(10000):
    if any(k and len(g) >= 4 for k, g in
                itertools.groupby(random.randint(0,1) for i in xrange(10)):
        successes += 1

But of course, we can also convert this to a generator, since you're just adding up numbers:

successes = sum(1 for i in xrange(10000)
      if any(k and len(g) >= 4 for k, g in
              itertools.groupby(random.randint(0,1) for i in xrange(10)))

The generator produces a 1 each time it finds a group of 4 consecutive 1s among the 10 random numbers generated.

The last thing you'd want to do is divide by the total number of trials. Well, actually, what you really want to do is calculate the average instead of the sum, and in some places you can find a function mean which is kind of like sum except that it calculates the mean instead of the total. You could use such a function if you had it. But I don't know that one is in the Python standard library, so you can just do the division:

probability = sum(1 for i in xrange(10000)
      if any(k and len(g) >= 4 for k, g in
        itertools.groupby(random.randint(0,1) for i in xrange(10))) / 10000

So the task you're trying to accomplish can actually be written in one line of Python. But it's a rather complicated line, and I wouldn't necessarily recommend actually doing this. Sometimes it's good to use a good old fashioned for loop to keep the code clear. More often, though, it's better to split your code up into modular pieces that are more useful than just what you're using them for.


Inserting a node in Binary Search Tree I would like any suggestions and improvements for this code, be it generics or my Node class being completely mutable. Should I make it mutable? Is it good? Why?

package ishan.trees.tree;

class Node implements Comparable<Node> {

    private int data;
    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    private Node leftChild;
    private Node rightChild;

    public Node(int data,Node leftChild,Node rightChild)
    {
        this.data=data;
        this.leftChild=leftChild;
        this.rightChild=rightChild;

    }

    @Override
    public int compareTo(Node o) {
        if(o.getData() > this.data)
        return -1;

        if(o.getData() < this.data)
            return 1;

        return 0;
    }
}

Tree class

package ishan.trees.tree;

public class Tree {

    private Node root=null;

    public Node getRoot() {
        return root;
    }

    public void insertData(int data)
    {
        Node node=new Node(data,null,null);
        insert(node,this.root);

    }

    private Node insert(Comparable<Node> node,Node root1)
    {
            if(root1==null)
            {

                root1=new Node(((Node)node).getData(),null,null);
                if(this.root==null)
                {
                    this.root=root1;
                }
            }
            else if(node.compareTo(root1) <0)
            {
                root1.setLeftChild(insert(node,root1.getLeftChild()));
            }
            else if(node.compareTo(root1) >0)
            {

                root1.setLeftChild(insert(node,root1.getRightChild()));
            }

     return root1;
    }
}

Generics

Since you asked: Sure, generics would be nice. Right now, your Tree would be better named IntBinarySearchTree, as it only accepts integers.

Mutable

  Should I make it mutable? Is it good? Why?

No, mutable objects are not good. Very often, they are necessary (because the data changes after the object is created), but if you can make an object immutable, you should do so (because it's easier to handle if you know that it doesn't change).

In this case, I think that it is ok that it is mutable. You could change it, but the resulting code wouldn't be all that pretty, and it would get even worse when you implement more functionality.

Formatting

You are violating a lot of Java style conventions (opening { should be on same line, as should else; whitespace around ==, >, =; etc). If you paste your code into any IDE, it can format it according to conventions.

By convention, the order of elements in a class is: fields, constructor, methods. I would go with this order, so readers can easily find them.

private Node class

As your Node class is never used on its own, and never outside of the Tree class, it should be a private class inside Tree.

Node constructor

It's always a bit ugly to pass null to a constructor. I would create an additional constructor that only takes data as input.

compareTo

Your compareto method can be replaced with return this.data - o.getData();. It's a bit less readable, but it is how it's done most of the time, so readers will be used to it. You might also want to check if the passed node is not null, and if it is handle it accordingly.

insert

You should move the code for inserting the first root node to insertData. It just complicates insert.

I would also rename root1 to currentRoot.

And I would write a toString method for the tree to test it. Right now, your code doesn't seem quite right (you are doing root1.setLeftChild in both cases).


Neatly printing integers interspersed with spaces - follow-up See the previous iteration.

At this point, I have

"digit group" length assumed to be always 3
the user can pass the delimiter character of his/her own
handles (seems to handle) the minus sign gracefully
hacked away a test in a conditional

import java.util.Scanner;

public class Main {

    /**
     * Handles <b>most</b> locales.
     */
    private static final int GROUP_LENGTH = 3;
    private static final char DEFAULT_DELIMITER_CHAR = ' ';

    public static String neatify(final long number,
                                 final char delimiter) {
        final char[] charArray = Long.toString(number).toCharArray();
        final StringBuilder sb = new StringBuilder();

        int index;

        if (charArray[0] == '-') {
            sb.append('-');
            index = 1;
        } else {
            index = 0;
        }

        sb.append(charArray[index++]);

        for (; index < charArray.length; ++index) {
            if ((charArray.length - index) % GROUP_LENGTH == 0) {
                sb.append(delimiter);
            }

            sb.append(charArray[index]);
        }

        return sb.toString();
    }

    public static String neatify(final long number) {
        return neatify(number, DEFAULT_DELIMITER_CHAR);
    }

    public static void main(final String... args) {
        final Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLong()) {
            System.out.println(neatify(scanner.nextLong()));
        }
    }
}

By default, performance is important for me. If you know how to squeeze just a little bit more of that, let me know!

Style
Why make the delimiter an input parameter, but not the group length (3)? The DEFAULT_DELIMITER_CHAR is also... out of place, either you have DEFAULT values for both, or you have for none, but the mixed concept is cumbersome.
Apart from that incongruity, the code is otherwise really quite neat, and understandable.
For what it's worth, I tend to use magic numbers, and not constants, when confronted with these situations. I am aware that magic numbers are not generally welcomed, but your code here:

public static String neatify(final long number) {
    return neatify(number, DEFAULT_DELIMITER_CHAR);
}

is really not much better, or perhaps even worse, than:
public static String neatify(final long number) {
    return neatify(number, ' ');
}

That's a personal thing.
Algorithm
I dislike the char-by-char algorithm you have chosen. The reason is that, as I see it, you are working in an "arse-backwards" way. The problem is about right-referenced values. The groups-of-3 blocks are referenced to the right-side of the value, not the left, so the trick is getting the reference correct to start with, and then you don't have to play tricks to keep it correct.
The trick is to find the right 'start' point that's correct, relative to the right, but then referenced from the left... let me explain:
    final String raw = Long.toString(val);
    int end = raw.length() - span * ((raw.length() - 1) / span);
    int start = 0;

What does the above code do? It converts the long input value to a string without any spaces. It uses the length() and from that, it subtracts the full number of blocks that have to be padded.
So, the following table gives the 'input' and 'end' result:
1         -> 1
12        -> 2
123       -> 3
1234      -> 1
12345     -> 2
123456    -> 3
.....

So, the start position for the first group is at char 0, and the end position is calculated above. From there on, it is just a simple case of getting the next group, and so on.
The full code I would recommend is:
public static String neatify(final long val, final char pad, final int span) {
    if (val == Long.MIN_VALUE) {
        long minblock = (long)Math.pow(10, span);
        // recursive hot-fix for otherwise impossible-to-make-positive value.
        return neatify(val / minblock, pad, span) + pad + neatify(-(val % minblock), pad, span);
    }
    if (val < 0) {
        return "-" + neatify(-val, pad, span);
    }

    final String raw = Long.toString(val);
    int end = raw.length() - span * ((raw.length() - 1) / span);
    int start = 0;
    StringBuilder sb = new StringBuilder(raw.length() + (raw.length() / span) + 1);
    while (start < raw.length()) {
        sb.append(pad);
        sb.append(raw.substring(start, end));
        start = end;
        end = start + span;
    }
    return sb.substring(1);
}

Note that, for this system, I have enabled all three input parameters, and I have done some simple 1-level-down recursive tricks to handle negative values (and Long.MIN_VALUE which is a PITA).
Update - Performance
Since the question was edited to include performance as a criteria, then the following code will do essentially the same as above, but with some performance tweaks:

it won't use recursion for negatives, but instead do some more complicated sign-juggling
it keeps everything as primitives (chars, etc.) instead of Strings
it pre-computes the output sizes, etc.

It is still referenced against the right-side of the output, and has the same basic concepts, just... faster. About twice as fast, and about 20% faster than the OP's...
public static String neatifyRLP(final long val, final char pad, final int span) {
    final String raw = Long.toString(val);
    final int signlen = val < 0 ? 1 : 0;
    final int digitlen = raw.length() - signlen;
    final char[] out = new char[signlen + digitlen + (digitlen - 1) / span];

    int pos = out.length - 1;
    int src = raw.length() - 1;
    final int ospan = span + 1;
    while (pos >= signlen) {
        out[pos] = (out.length - pos) % ospan == 0 ? pad : raw.charAt(src--);
        pos--;
    }
    if (val < 0) {
        out[0] = '-';
    }
    return new String(out);
}

I am not at all certain that it is more readable, but, it is not horrible either.
Here are the performance numbers based on neatifying 1000 random long values:
Task NumberPad -> OP: (Unit: MILLISECONDS)
  Count    :    10000      Average  :   0.2202
  Fastest  :   0.1960      Slowest  :   9.8499
  95Pctile :   0.2927      99Pctile :   0.4620
  TimeBlock : 0.265 0.222 0.222 0.215 0.218 0.217 0.217 0.208 0.206 0.211
  Histogram :  9769   218     7     1     4     1

Task NumberPad -> RL: (Unit: MILLISECONDS)
  Count    :    10000      Average  :   0.3524
  Fastest  :   0.3127      Slowest  :  15.0630
  95Pctile :   0.5521      99Pctile :   0.6260
  TimeBlock : 0.416 0.368 0.360 0.340 0.366 0.347 0.330 0.334 0.328 0.335
  Histogram :  9900    88     6     2     3     1

Task NumberPad -> RLP: (Unit: MILLISECONDS)
  Count    :    10000      Average  :   0.1866
  Fastest  :   0.1683      Slowest  :   5.9859
  95Pctile :   0.2280      99Pctile :   0.4241
  TimeBlock : 0.218 0.189 0.193 0.181 0.185 0.185 0.177 0.178 0.179 0.182
  Histogram :  9826   165     3     2     2     2


TicTacToe game in Haskell As a beginner, I tried to implement TicTacToe in Haskell. How can I improve my code?

I have refactored my code: General TicTacToe in Haskell

Utils

module Data.List.Utils where

import Data.List (intersperse)

surround :: a -> [a] -> [a]
surround x ys = x : intersperse x ys ++ [x]

nth :: Int -> (a -> a) -> [a] -> [a]
nth _ _ [] = []
nth 0 f (x:xs) = f x : xs
nth n f (x:xs) = x : nth (n - 1) f xs

TicTacToe

module TicTacToe where

import Data.List (transpose)
import Data.Foldable (asum)
import Data.List.Utils (nth, surround)

data Tile = Empty | O | X deriving (Show, Eq)

showTile :: Tile -> String
showTile Empty = " "
showTile O     = "O"
showTile X     = "X"

type Board = [[ Tile ]]

showBoard :: Board -> String
showBoard = unlines
          . surround vert
          . map (concat . surround horiz . map showTile)

    where vert  = "+-+-+-+"
          horiz = "|"

whoWon :: Board -> Maybe Tile
whoWon xs = asum . map winner $ diag : anti : rows ++ cols

    where rows = xs
          cols = transpose xs
          diag = zipWith (!!) xs [0..]
          anti = zipWith (!!) xs [2,1..]

          winner [O, O, O] = Just O
          winner [X, X, X] = Just X
          winner _         = Nothing

fillTile :: Int -> Int -> Tile -> Board -> Board
fillTile row col = nth row . nth col . const

isOver :: Board -> Bool
isOver = all (all (/= Empty))

overMsg :: Maybe Tile -> String
overMsg (Just x) = "Winner: " ++ (showTile x)
overMsg Nothing  = "Game Over! No winner."

inRange :: Int -> Bool
inRange x = x >= 0 && x <= 2

gameLoop :: Tile -> Board -> IO ()
gameLoop player board
    | isOver board || winner /= Nothing = putStrLn $ overMsg winner
    | otherwise    = do

        putStrLn $ showBoard board
        putStrLn $ "Now player " ++ showTile player

        putStr "Row: "
        row <- fmap read getLine

        putStr "Col: "
        col <- fmap read getLine

        if inRange row && inRange col && (board !! row !! col == Empty)

            then gameLoop (if player == O then X else O) $
                     fillTile row col player board

            else do
                putStrLn "Invalid position, please try again."
                gameLoop player board

    where winner = whoWon board

startBoard :: Board
startBoard = replicate 3 (replicate 3 Empty)

main = gameLoop O startBoard

Some thoughts about your Tic-Tac-Toe version.

You made a confusion between Tile and Player. You assume a Player is the same as a Tile but it is not. A Tile can be Empty but a Player cannot be empty. You should separate these two notions. It will make your declarations clearer on what you expect. What if I call "gameLoop Empty startBoard" ?

The putStr function does not flush immediately its output in a compiled program. Your program asks the user for a row and a column and displays these labels after the user inputs.

Is it natural to ask for the row before the column ?

You have intertwined the game logic with the user interface in the gameLoop function. What will you do if you want to implement a computer player ? Or have a GUI to play the game ? You will have to patch your gameLoop function though the game logic has not changed.

Your solution is locked to the fact that your board is a 3×3 grid with a 3 tiles win. For example, your inRange functions works for row indices AND column indices, which are not the same. You use the constants 2 and 3 in your code (inRange, startBoard and whoWon), but nothing implies a relation between them. The 3 rows and 3 columns are characteristics of the Board, not of your functions.

Messages could be more specific. When you tell the user "Invalid position", there’s no way to know if it’s because the coordinates are out of bounds or because the tile has already been played.

Note: there are many Tic-Tac-Toe game related questions on CodeReview, you should take a look at:

Tic Tac Toe game in Haskell (a brute first attempt)
Tic Tac Toe game in haskell follow up (its follow up)
TicTacToe in Haskell (a version using Lens)
m,n,k-game (i.e. generalized tic-tac-toe) (its generalization)


Print all interleavings of two given strings Given two strings str1 and str2, write a function that prints all
  interleavings of the given two strings. You may assume that all
  characters in both strings are different

  Example:

Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

Input: str1 = "AB",  str2 = "C"
Output:
    ABC
    ACB
    CAB

  The idea comes from Ray Toal:

  The base case is when one of the two strings are empty:

interleave(s1, "") = {s1}

interleave("", s2) = {s2}

  Notice the order of the arguments doesn't really matter, because

interleave("ab", "12") = {"ab12", "a1b2", "1ab2", "a12b", "1a2b", "12ab"} = interleave("12", "ab")

  So since the order doesn't matter we'll look at recursing on the length of the first string.

  Okay so let's see how one case leads to the next. I'll just use a
  concrete example, and you can generalize this to real code.

interleave("", "abc") = {"abc"} interleave("1", "abc") = {"1abc",
"a1bc", "ab1c", "abc1"} interleave("12", "abc") = {"12abc", "1a2bc",
"1ab2c", "1abc2", "a12bc", "a1b2c", "a1bc2", "ab12c", "ab1c2" "abc12"}

  So everytime we added a character to the first string, we formed the
  new result set by adding the new character to all possible positions
  in the old result set. Let's look at exactly how we formed the third
  result above from the second. How did each element in the second
  result turn into elements in the third result when we added the "2"?

"1abc" => "12abc", "1a2bc", "1ab2c", "1abc2" "a1bc" => "a12bc",
"a1b2c", "a1bc2" "ab1c" => "ab12c", "ab1c2" "abc1" => "abc2"

  Now look at things this way:

"1abc" => {1 w | w = interleave("2", "abc")} "a1bc" => {a1 w | w =
interleave("2", "bc")} "ab1c" => {ab1 w | w = interleave("2", "c")}
"abc1" => {abc1 w | w = interleave("2", "")}

The following is my code building on top of the above idea.  Can anyone help me verify it?

void interleaving(const string& s2, string result, int start, int depth)
{
    if(depth == s2.size())
        cout << result << endl;
    else
    {
        for(int i = start; i <= result.size(); ++i)
        {
            result.insert(i, 1, s2[depth]);
            interleaving(s2, result, i+1, depth+1);
            result.erase(i, 1);
        }
    }
}

int main()
{
    string s1("");
    string s2("12");
    string result(s1);
   interleaving(s2, result, 0, 0);
    system("pause");
    return 0;
}

There is another much more beautiful solution for this problem comes from an unknown friend akash01:

void printIlsRecur (char *str1, char *str2, char *iStr, int m, int n, int i)
{
    // Base case: If all characters of str1 and str2 have been included in
    // output string, then print the output string
    if ( m==0 && n ==0 )
    {
        printf("%s\n", iStr) ;
    }

    // If some characters of str1 are left to be included, then include the
    // first character from the remaining characters and recur for rest
    if ( m != 0 )
    {
        iStr[i] = str1[0];
        printIlsRecur (str1 + 1, str2, iStr, m-1, n, i+1);
    }

    // If some characters of str2 are left to be included, then include the
    // first character from the remaining characters and recur for rest
    if ( n != 0 )
    {
        iStr[i] = str2[0];
        printIlsRecur (str1, str2+1, iStr, m, n-1, i+1);
    }
}

Your algorithm is correct, as you explained.  However, I didn't find the code easy to understand.

Staying within the spirit of your solution, I've cleaned it up a bit:

Renamed s2 → s1 (because s2 coming first is confusing), result → s2.
Renamed depth → i1, start → i2 to emphasize their relationship with s1 and s2.
Swapped the order of the last two parameters for parallelism.
Provided defaults for the last two parameters to make main() prettier.
Eliminated the variable i, because using i2 directly is clearer.
Used an early return to reduce a level of indentation.

Simultaneously tracking all of those substitutions is tricky, but here is the result:

void interleaving(const string& s1, string s2, int i1=0, int i2=0)
{
    if (i1 == s1.size())
    {
        cout << s2 << endl;
        return;
    }

    // Transfer the first character of s1 into s2
    // anywhere after the last previously inserted
    // character from s1.
    for ( ; i2 <= s2.size(); i2++)
    {
        s2.insert(i2, 1, s1[i1]);
        interleaving(s1, s2, i1 + 1, i2 + 1);
        s2.erase(i2, 1);        // Undo the insert() above
    }
}

Since passing the second parameter by value would cause it to be copied unnecessarily on each recursive call, you might want to change it to be passed by reference instead.

static void interleaving_helper(const string& s1, string &s2, int i1, int i2)
{
    if (i1 == s1.size())
    {
        cout << s2 << endl;
        return;
    }

    for ( ; i2 <= s2.size(); i2++)
    {
        s2.insert(i2, 1, s1[i1]);
        interleaving_helper(s1, s2, i1 + 1, i2 + 1);
        s2.erase(i2, 1);        // Undo the insert above
    }
}

void interleaving(const string& s1, string s2, int i1=0, int i2=0)
{
    interleaving_helper(s1, s2, i1, i2);
}


Allow changing the properties of a mutable controller in a thread safe way I have a (control engineering) controller. These controllers usually need several parameters to do their thing, and in my application it is desirable that these parameters can be changed while the controller is running - in a thread safe and well defined manner.

I came up with this design (extremely simplified):

// This is the class that the user instanciates.
public class Controller
{
    public ControllerInfo Info { get; set; }

    public void Start() { ... }
    public void Stop() { ... }

    private ControllerBody body = new ControllerBody();

    private void ControllerThreadProc()
    {
        while (true)
        {
            var elapsedTime_ms = ...;
            var currentInfo = this.Info;
            // the actual calculation is done in another class
            this.body.SingleStep(currentInfo, elapsedTime_ms);
            Thread.Sleep(currentInfo.SampleTime_ms);
        }
    }
}

// This exists as a separate class so it is possible to test the
// mathematical model without having to do it in real-time.
public class ControllerBody
{
    public void SingleStep(ControllerInfo info, long elapsedTime_ms)
    {
        var referenceValue = info.ReferenceValueGetter();
        var calculationResult = math;
        info.ControlValueSetter(calculationResult);
    }
}

// Immutable class that contains all the info necessary to do stuff.
public class ControllerInfo
{
    public Func<double> ReferenceValueGetter { get; private set; }
    public Action<double> ControlValueSetter { get; private set; }
    public int SampleTime_ms { get; private set; }
    public double SomeConstant { get; private set; }
    public double OtherConstant { get; private set; }
    ...

    public ControllerInfo(/* 1 argument per property :( */) { /* many assignments */ }
}

Usage example:

var controller = new Controller();
controller.Info = new ControllerInfo(/* values */);
controller.Start();
// later:
controller.Info = new ControllerInfo(/* new values */);
// Application is done:
controller.Stop();

Again, it should be possible to change the controller while it is running. Therefore I gave Controller a publicly settable ControllerInfo.

However, if the user decides to change the values of SomeConstant and OtherConstant in this example, it must be guaranteed that no calculation step is executed where only one of these are changed. In other words, changing a bunch of parameters must be an atomic operation. That's why ControllerInfo is not mutable.

I have identified 2 downsides to this architecture:

If I add another mathematical constant to ControllerInfo, I have to add (1) a property, (2) a parameter to the constructor (can be forgotten even if (1) has been done!), and (3) an assigment inside the constructor (can be forgotten even if (1) and (2) have been done!).
If the user wants to change a parameter while the controller is running, they must make another tedious constructor call, passing in values that have changed, as well as values that haven't changed.

To get around the usability problem, I considered introducing a ControllerInfoFactory class, which is basically a mutable copy of ControllerInfo:

public class ControllerInfoFactory
{
    public (SamePropertiesAsControllerInfo) { get; set; }

    public ControllerInfo CreateControllerInfo()
    {
        return new ControllerInfo(/* pass all parameters from this */);
    }
}

However, that makes the first problem even worse: For each property, I now also have to add the property to ControllerInfoFactory. Luckily, this time it's not possible to forget updating the CreateControllerInfo method as long as the ControllerInfo constructor has already been updated.

Now to code review:

Does this design make sense? Is the usability OK?
Can the large amount of repetitive code per property be reduced?

Another option is to create ControllerInfo with mutable properties and a Clone method which would return a copy of the instance.

Then on the ControllerInfo Info set, simply call the Clone method and set _info to the clone of the object passed in.

private ControllerInfo _info;

public Info
{
   get { return _info; }
   set { _info = value.Clone(); }
}

To be clearer you can do away with Info as a property and instead code a method

public Controller SetInfo(ControllerInfo info)
{
     _info = info.Clone();
     return this;
}

Doing away with "get" semantics for Info, is a good idea, as you do not want the interface to suggest that a get followed by mutating the Info object would reflect the changes in the Controller.


Parsing record-jar format in PHP 5.3 Here is a simple function I wrote to parse record-jar data. I need it in a php5.3 application to validate bcp47 language tags. It converts the language subtag registry among other things, into a nested php array. Any suggestions on how I can improve it?

/**
 * Quick script to parse any record-jar data into an array.
 *
 * In particular, this is of use to someone trying to validate bcp47 language codes.
 * @see http://tools.ietf.org/search/bcp47#section-3.1.1
 */
function parse_record_jar($record_jar_string) {
  $records = array();
  $record = array();
  foreach(explode('%%', $record_jar_string) as $recordstr) {
    array_splice($record, null); // truncate $record
    foreach(array_filter(explode("\n", $recordstr)) as $line) {
      $parts = array_map('trim', explode(":", $line, 2));
      if (count($parts) === 2) {
        list($key, $value) = $parts;
      } else {
        // $key retains its value from the previous iteration.
        $value = $parts[0];
      }
      if (!isset($record[$key])) {
        $record[$key] = '';
      }
      $record[$key] .= $value;
    }
    $records[] = $record;
  }
  return $records;
}

I have rewritten the script in another fashion. Beware all your code is almost exactly the same, but not entirely. If you are looking to just improve your script a bit, look closely at the parser.

A number of personal preferences I would like to share that I thought while reading your code but which I did not fix in my own code in all cases:

I like (foo === false) better then (! foo) or (foo !== true).
Strings like '%%' should be replaced with constants, preferably some of the numbers also.
Complex logic should be split up. Even my example does fully split up the responsibilities.
Comments should be plentiful (and meaningful!).

The code example is obese compared to the fine script you made. But I find it

Faster to debug
Testable
Easy to replace dependencies
Easy to change how the converter works (just write a couple parsers and converters)

My code example is far from done. The code should strive towards SOLID principles (which this does not). The main issue I've addressed is to clarify some of the mixed responsibilities in your code. But the new code still has some issues, mainly missing tests and SRP violations (in my code the parser is doing the converter's job). This is to show the disadvantage of bundled complex code that handles too many responsibilities.

I used 5.4 array syntax. PHP 5.3 series will enter an end of life cycle and has only received critical fixes as of March 2013.

As mentioned the code is undone (as in breaks SOLID). If you want to further improve it, you could start by moving the converting part (toArray) of the algorithm into the ToArray class.

namespace jarrecord;

Interface Parser {
    public function parse($parsable);
}

Interface Converter {
    public function convert($convertable);
}

class StringParser implements Parser {
    const RECORD_SPLIT_TOKEN = '%%';
    const KEY_VALUE_SPLIT = ':';
    /**
    * Splits and trims unparsed lines and returns array with key value pair.
    *
    * @return array
    */
    private function splitUnparsedLineToKeyAndValue($line)
    {
        return  array_map('trim', explode(self::KEY_VALUE_SPLIT, $line, 2));
    }

    private function splitToUnparsedRecords($recordJar)
    {
        return explode(self::RECORD_SPLIT_TOKEN, $recordJar);
    }

    private function splitToUnparsedLines($unparsedRecord)
    {
        $lines =  explode(\PHP_EOL, $unparsedRecord);
        // filter to remove null lines

        return array_filter($lines);
    }

    /**
    * Takes a array of strings and returns a record-like array
    * @param string $unparsedLines
    * @return array
    */
    private function unparsedLinesToRecord($lines)
    {
        $record = [];
        foreach($lines as $line)
        {
            $partialRecord = $this->splitUnparsedLineToKeyAndValue($line);
            if(count($partialRecord) === 2)
            {
                list($key, $value) = $partialRecord;
            }
            else
            {
                // $key retains its value from the previous iteration.
                $value = $partialRecord[0];
            }
            if(isset($record[$key]) === false)
            {
                $record[$key] = '';
            }
            $record[$key] .= $value;
        }

        return $record;
    }

    public function parse($parsable)
    {
        $unparsedRecords = $this->splitToUnparsedRecords($parsable);
        foreach($unparsedRecords as $unparsedRecord)
        {
            $unparsedLines = $this->splitToUnparsedLines($unparsedRecord);
            $record = $this->unparsedLinesToRecord($unparsedLines);
            $records[] = $record;
        }

    return $records;
    }
}

class ToArray implements Converter {
    private $parser;

    /**
    * @param Parser $parser
    */
    public function __construct(Parser $parser)
    {
        $this->parser = $parser;
    }

    /**
    * Parses a Record-Jar string and returns it as a array.
    * @throws InvalidArgumentException
    * @param string $unparsedRecordJar
    * @return array
    */
    public function convert($unparsedRecordJar)
    {
        return $this->parser->parse($unparsedRecordJar);
    }
}

$parser = new StringParser();
$Converter = new ToArray($parser);
$array = $Converter->convert($source));


Knuth–Morris–Pratt string search algorithm I finally think I've implemented the Knuth–Morris–Pratt string search algorithm correctly, now time for that lovely criticism that causes me to learn! The code doesn't look all that pretty however it does work as far as I've tested. All of what I gathered on this algorithm comes from the Wikipedia page for it. I would appreciate some feedback and suggestions on improvements/errors. Did I hit the mark? Or did I miss the point? Should I employ other sources for my research?

'''
KMP Algorithm
**Searches for all occurrences of a word w[] in main string s[]

@author: Anonymous3.1415
'''

def KMP_filltable(pattern):

    position = 2
    candidate = 0
    length_pat = len(pattern)

    table = [0]*len(pattern)
    table[0] = -1

    while position < length_pat:
        if pattern[position - 1] == pattern[candidate]:
            position += 1
            candidate += 1
            table[position - 1] = candidate
        elif candidate > 0:
            candidate = table[candidate]
        else:
            table[position] = 0
            position += 1

    return table

def KMP_search(pattern, lst):

    positions = []
    i, j = 0, 0
    length_lst, length_pat  = len(lst), len(pattern)

    table = KMP_filltable(pattern)
    while i < length_lst:
        if pattern[j] == lst[i + j]:
            j += 1
            if j == length_pat:
                positions.append(i)
                i += j
                j = 0
        elif table[j] > 0:
            j = table[j]
            i += j
        else:
            i += (j + 1)
            j = 0

    return positions

This code does not work. In some cases it fails to find the pattern:

>>> KMP_search('ab', 'aab')
[]

In other cases it raises an exception:

>>> KMP_search('ab', 'ba')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "cr190837.py", line 39, in KMP_search
    if pattern[j] == lst[i + j]:
IndexError: string index out of range

How could you have found these problems? Well, by testing the code thoroughly. One way to do this is to use random test case generation. The idea behind randomized testing is that it can test a much larger range of inputs than you could ever enter by hand, and it can test parts of the space of inputs that would not be reached by systematic test case generation.

So one idea for a random test case would be to generate a random string of length k:

haystack = ''.join(random.choices('abc', k=k))

(Here I'm using random.choices which was new in Python 3.6. If you're on an earlier version of Python, you could use a loop like random.choice('abc') for _ in range(k).)

Then pick a random substring:

start, stop = sorted(random.sample(range(k + 1), 2))
needle = haystack[start:stop]

Run KMP_search(needle, haystack) and check that the results are correct, for example by comparing with Python's built-in str.find.

This can all be packaged together into a unit test using the unittest module:

import random
import unittest

class TestKMPSearch(unittest.TestCase):
    "Unit tests for KMP_search."

    def test_positive(self):
        for k in range(1, 100):
            # Generate a random test case with k characters.
            haystack = ''.join(random.choices('abc', k=k))
            start, stop = sorted(random.sample(range(k + 1), 2))
            needle = haystack[start:stop]

            # Use Python's built-in str.find to compute the expected result.
            expected = []
            index = -1
            while True:
                index = haystack.find(needle, index + 1)
                if index == -1:
                    break
                expected.append(index)

            # Compare with the actual result.
            found = KMP_search(needle, haystack)
            self.assertEqual(found, expected,
                             "KMP_search({!r}, {!r})".format(needle, haystack))

(I called the method test_positive because the test cases are positive in the sense that the needle is found in the haystack. For really thorough testing you ought to generate some negative test cases too, ones in which the needle is not found. But this is enough to find some errors.)

Now if you run the unit tests you'll (most likely) get a failure like this:

$ python -munittest cr190837.py
F
======================================================================
FAIL: test_positive (cr190837.TestKMPSearch)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "cr190837.py", line 79, in test_positive
    "KMP_search({!r}, {!r})".format(needle, haystack))
AssertionError: Lists differ: [] != [3]

Second list contains 1 additional elements.
First extra element 0:
3

- []
+ [3]
?  +
 : KMP_search('bac', 'ccbbac')

----------------------------------------------------------------------
Ran 1 test in 0.001s

FAILED (failures=1)


Calculation in Concern module using Rails I wrote the following Concern module. Is it good practice to perform all the calculations in the included scope? How can it be improved?

module Pagination
  module Helper
    extend ActiveSupport::Concern

    included do
      class << self
        def paged(params, custom_per_page = nil, custom_page = nil)
          per_page = params[:per_page] =
            custom_per_page || normalize_per_page(params[:per_page].to_i)
          page = normalize_page(self.all.size,
            custom_page || params[:page].to_i, per_page)

          self.paginate(page: page, per_page: per_page)
        end

        def default_per_page
          Reader::Application.config.custom.default_per_page_pagination
        end

        protected

        def normalize_per_page per_page
          if per_page < 1 || per_page > default_per_page
            return default_per_page
          end
          per_page
        end

        def normalize_page(size, page, per_page)
          if ((page - 1) * per_page) >= size
            page = (size / per_page.to_f).ceil
          end
          page > 0 ? page : 1
        end
      end
    end
  end
end

ActiveRecord::Base.send(:include, Pagination::Helper)

Since you're mixing methods into ActiveRecord::Base, you might as well extend it proper:

class ActiveRecord::Base
  def self.paged(...)
    ...
  end
end

No concerns necessary; you're just extending a class. Put it into a file in config/initializers and it'll load when the app spins up.

About what you're mixing in:

default_per_page doesn't make sense as a mixin. It's not the responsibility of every ActiveRecord-derived class to have a shortcut for fetching a global config value. The methods you add to a class via mixins should make as much sense, as if you'd added them directly to just that class.
I'd place shortcuts like that in e.g. a separate helper module, and call it there.
Use Rails.configuration instead of <YourAppName>.config if you're aiming for reusable code.
Consider using hashes for method parameters. It makes calling your methods simpler and more descriptive.
Be consistent with your parentheses. You declaration of normalize_per_page omits the parentheses, but your declaration of normalize_page includes them. Personally, I always use parens in method declarations.
Do not access params in a model. Keep that in the controller, and only the controller; it's its job. This also means keeping the normalize_page  method (which I'd call constrain_page_number, because it doesn't normalize a page, but constrains a number) in the controller. You can simply add it to ApplicationController to have available:

# in app/application_controller.rb

protected

def constrain_page_number(number, record_count, per_page = nil)
  per_page ||= PagniationHelpers.default_per_page # our helper module
  [1, number, (record_count / per_page).floor + 1].sort[1]
end

However, in my view, your controller should send a redirect if the page number in out of bounds - don't just rewrite it behind the scenes. So you might want something like this instead:

def valid_page_number?(number, record_count, per_page = nil)
  per_page ||= PagniationHelpers.default_per_page # our helper module
  max = (record_count / per_page).floor + 1
  (1..max).cover?(number)
end

Now, something that'd might make more sense to include in every model would be a max_page method. It'd allow you to more easily check the page number in the controller.
Of course, such a method would (unlike the above) have to rely on just the default scope when counting the number of records. Still, it might be useful.

In all I end with something like this (plus the controller method above):

module PagniationHelpers
  module_function

  def default_per_page
    Rails.config.custom.default_per_page_pagination
  end
end

class ActiveRecord::Base
  class << self
    def paged(page, per_page = nil)
      per_page ||= PagniationHelpers.default_per_page
      self.paginate(page: page, per_page: per_page)
    end
  end
end

Buuuut of course, it looks like you're using the will_paginate gem. In that case, forget the code above. Instead, do this in an initializer file somewhere:

WillPaginate.per_page = 10 # or whatever default you want

and in ApplicationController do:

def max_page_number(record_count, per_page = nil)
  per_page ||= WillPaginate.per_page
  (record_count / per_page).floor + 1
end

def valid_page_number?(number, record_count, per_page = nil)
  max = max_page_number(record_count, per_page)
  (1..max).cover?(number)
end

def constrain_page_number(number, record_count, per_page = nil)
  max = max_page_number(record_count, per_page)
  [1, number, max].sort[1]
end

And in your controller actions you can do something like

def index
  page = params[:page].try(:to_i) || 1
  unless valid_page_number?(page, Post.count)
    redirect_to posts_path(page: constrain_page_number(page, Post.count))
  end
  @posts = Post.paginate(:page => page)
  #...
end


Store nested json repsonses in relational database The goal is to collect market data from a free rest api. The response is in json and size per response is above 1MB. I want to get at least updated data once per minute which means about 24h * 60min * 1MB ~ 1.5GB per day of json data. Since i have to collect data over a few weeks in order to start analysing market patterns i have to store the json responses in a space efficient way --> SQLite is my idea so far. Now the ugly part is dealing with nested (4 levels) json and insert it into a relational database.

json example:

{
    'country-id': 1,
    'name': 'USA',
    'states': [
    {
        'country-id': 1,
        'name': 'Alaska',
        'state-id': 11,
        'cities': [
        {
            'state-id': 11,
            'name': 'Anchorage',
            'city-id': 111,
            'streets':
            [
                {
                    'city-id': 111,
                    'name': 'Ingra St.',
                    'street-id': 1111
                }
            ]
        },
        {
            'state-id': 11,
            'name': 'Fairbanks',
            'city-id': 112,
            'streets':
            [
                {
                    'city-id': 112,
                    'name': 'Johansen Expy',
                    'street-id': 1121
                }
            ]
        }
        ]
    },
    ]
}

My approach:

from dataclasses import dataclass
from typing import List

@dataclass
class Country:
    def __init__(self, country_json):
        self.country_id: int = country_json['country-id']
        self.name: str = country_json['name']
        self.states: List(State) = [State(state) for state in country_json['states']]

@dataclass
class State:
    def __init__(self, state_json):
        self.country_id: int = state_json['country_id']
        self.name: str = state_json['name']
        self.state_id: int = state_json['state_id']
        self.cities: List(City) = [City(city) for city in state_json['cities']]

@dataclass
class City:
    def __init__(self, city_json):
        self.state_id: int = city_json['state-id']
        self.name: str = city_json['name']
        self.city_id: int = city_json['city-id']
        self.streets: List(Street) = [Street(street) for street in city_json['street']]

@dataclass
class Street:
    def __init__(self, street_json):
        self.city_id: int = street_json['city-id']
        self.name: str = street_json['name']
        self.street_id: int = street_json['street-id']

Next steps would be to add functions to each dataclass that store the values in a SQlite DB. I am really not sure if my general approach is efficient or if there is a better solution for this kind of problem. My idea in general was that if i build it like this i can easily add other steps e.g. data validation.

You don't use typing properly. Parametrizing generic types should be done using brackets notation (aka __getitem__) not parenthesis (aka instantiation).

You also don't use any feature of dataclasses in your defined classes, so you might as well drop that dependency. Or you could use it properly so that Country(**json_data) will build the whole thing; but:

Keys in the JSON data are not valid python identifiers, you would need to convert them;
You would need to handle converting children "manually" after the __init__ took place;
You will need to swap the order in which you define classes due to scope evaluation.

The closest we would come should be something along the lines of:

from dataclasses import dataclass
from typing import List

def convert_keys(dct):
    return {name.replace('-', '_'): value for name, value in dct.items()}

@dataclass
class Street:
    city_id: int
    name: str
    street_id: int

@dataclass
class City:
    state_id: int
    name: str
    city_id: int
    streets: List[Street]

    def __post_init__(self):
        self.streets = [Street(**convert_keys(street)) for street in self.streets]

@dataclass
class State:
    country_id: int
    name: str
    state_id: int
    cities: List[City]

    def __post_init__(self):
        self.cities = [City(**convert_keys(city)) for city in self.cities]

@dataclass
class Country:
    country_id: int
    name: str
    states: List[State]

    def __port_init__(self):
        self.states = [State(**convert_keys(state)) for state in self.states]

Initiate the call using Country(**convert_keys(json_data)). But this solution doesn't necessary feel cleaner than yours.

Now as regards to using these classes as a mean to store data into a relational database, we need to examine usage.

The DB API 2.0 tells us that you can expect to be able to:

cursor.execute('INSERT INTO Street VALUES (?, ?, ?)', (city_id, name, street_id))

Which means that we need to:

Be able to convert these classes to tuples;
Remove the reverse relationship that we had so much troubles parsing properly Country.states, State.cities, and City.streets).

So here we go, trying to patch our approach. We could use dataclasses.astuple to convert or objects to proper parameters for our query, but we would still need a specific parser to recursively traverse nested JSON layers. Coupling that with the invalid identifiers issue, I don't think storing the data into intermediate classes makes much sense. Instead I would rather write them directly in the database:

def parse_country(cursor, json_data):
    country_id = json_data['country-id']
    name = json_data['name']
    cursor.execute('INSERT INTO Country VALUES (?, ?)', (country_id, name))
    for state in json_data['states']:
        parse_state(cursor, state)

def parse_state(cursor, json_data):
    state_id = json_data['state-id']
    name = json_data['name']
    country_id = json_data['country-id']
    cursor.execute('INSERT INTO State VALUES (?, ?, ?)', (state_id, name, country_id))
    for city in json_data['cities']:
        parse_city(cursor, city)

def parse_city(cursor, json_data):
    city_id = json_data['city-id']
    name = json_data['name']
    state_id = json_data['state-id']
    cursor.execute('INSERT INTO City VALUES (?, ?, ?)', (city_id, name, state_id))
    for street in json_data['streets']:
        parse_street(cursor, street)

def parse_street(cursor, json_data):
    street_id = json_data['street-id']
    name = json_data['name']
    city_id = json_data['city-id']
    cursor.execute('INSERT INTO Street VALUES (?, ?, ?)', (street_id, name, city_id))

And that's pretty much your original code except the data is now in DB and not in memory. Usage being:

conn = # create appropriate DB connection here
with conn:
    parse_country(conn.cursor(), json_data)


Project Euler #18: Maximum path sum I Problem

I want to receive advice on my code, which takes 0.012 seconds.

import numpy as np
import time
start_time = time.time()
raw_data= """
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
"""
def data_input():
    a = raw_data.split("\n")
    new_a = [x.split(" ") if True else None for x in a]
    del(new_a[0]) # delete first element in new_a
    del(new_a[-1])
    return(new_a) # [['75'], ['95', '64'], ['17', '47', '82'], ['18', '35', '87', '10'], ['20', '04', '82', '47', '65'],...

def make_memoi_table():
    #make a table from below to above (to the top)
    new_a = data_input() # new_a : original raw_input data
    size = len(new_a)
    memoi_table = np.zeros((size,size))
    memoi_table[size-1] = [int(x) for x in new_a[size-1]]
    for i in range(2,size + 1):
        for j in range(len(new_a[size-i])):
            memoi_table[size-i][j] = int(new_a[size-i][j]) + max(memoi_table[size-i+1][j],memoi_table[size-i+1][j+1])
    return(memoi_table[0][0],memoi_table)

print(make_memoi_table())

print("--- %s seconds ---" % (time.time() - start_time))

You can save a bit in your input parser. You can run the list comprehension to replace the old list instead of making a new one. It's also easier to just return the list truncated with slicing rather than delete the start and end of it. Also x if True else y will always return x, so I don't know what the point of that is?

Also I'd pass in the data as a parameter, as well as give these variables and the function better names

def parse_data(raw_data):
    data = raw_data.split("\n")
    data = [line.split(" ") for line in data]
    return data[1:-1]

You're also performing inaccurate time testing. You take the start time at the beginning of the whole script. That means that it's measuring how long it takes to initialise constants and create the functions as well as running both functions. For a simple time testing approach, take a look at timeit.


Winforms Circular Checkbox So here is my next creation, a circular checkbox. This is my third custom control, so I'm still learning, but have the basics just about down. Tips and suggestions are most appreciated:

class CircularCheckbox : Control
{
    private Color borderColor;
    public Color BorderColor
    {
        get { return borderColor; }
        set { borderColor = value; }
    }

    private Color background;
    public Color Background
    {
        get { return background; }
        set { background = value; }
    }

    private Color tickColor;
    public Color TickColor
    {
        get { return tickColor; }
        set { tickColor = value; }
    }

    private bool isChecked;
    public bool IsChecked
    {
        get { return isChecked; }
        set { isChecked = value; }
    }

    public CircularCheckbox(bool IsChecked)
    {
        DoubleBuffered = true;
        SetStyle(ControlStyles.SupportsTransparentBackColor, true);
        this.BackColor = Color.Transparent;

        this.IsChecked = IsChecked;
        Background = Color.White;
        BorderColor = Color.Black;
        TickColor = Color.Green;
    }

    public CircularCheckbox()
        : this(false)
    { }

    protected override void OnPaint(PaintEventArgs e)
    {
        base.OnPaint(e);

        e.Graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
        Rectangle rc = this.ClientRectangle;
        Graphics g = e.Graphics;
        StringFormat sf = new StringFormat();
        Font f = new Font("Arial", (float)rc.Height * 0.5f, FontStyle.Bold, GraphicsUnit.Pixel);

        sf.Alignment = StringAlignment.Center;
        sf.LineAlignment = StringAlignment.Center;

        g.FillEllipse(new SolidBrush(Background), rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);
        g.DrawEllipse(new Pen(new SolidBrush(BorderColor), 3.0f), rc.Left + 1.5f, rc.Top + 1.5f, rc.Width - 4.0f, rc.Height - 4.0f);

        if (IsChecked)
            g.DrawString("\u2713", f, new SolidBrush(tickColor) , rc, sf);

    }

    protected override void OnClick(EventArgs e)
    {
        base.OnClick(e);

        IsChecked = IsChecked ? false : true;

        Invalidate();
    }
}

you should use auto properties where you don't need any validation. So all of your properties should use them like instead of

private bool isChecked;
public bool IsChecked
{
    get { return isChecked; }
    set { isChecked = value; }
}

you would use

public bool IsChecked { get; set; }

this example of really unnecessary tenary expression

IsChecked = IsChecked ? false : true;

should be replaced by

IsChecked = !IsChecked;

using braces {} for single if statement also would make your code less errorprone
you should extract your magic numbers into some meaningful aka good named constants ( 3.0f , 1.5f etc)
you should extract "\u2713" to some meaningful constant
you should extract new SolidBrush(tickColor) to a field, as the brush itself won't change.


Dropdown form that shows data from 2 different tables I am very new to this and am using php and MySQLi to create a form which will create a record in a third table.  This works fine but I can't help but think that there is a way to do it with a single query rather than a query for each table as I have now.  The third table is called tblcars, and I will use this form to build records for that table by selecting data from these dropdowns.

    <?php

    //Database Login
    require_once 'includes/connection.php';

    $sql = ("SELECT * FROM tblmake");

    $getclass = ("SELECT * FROM tblclass");

    $result = $conn->query($sql);
    $results = $conn->query($getclass);

    ?>

        <title>Car Makes</title>

Car Makes

            <form action="" method="get">
            <select name="makeID">
                <option value="">Choose Make</option>
                <?php
                    while($make = $result->fetch_assoc()) {
                        echo "<option value={$make['makeID']}>";
                        echo $make['carmake'];
                        echo "</option>";
                    }
                ?>
            </select>
            <select name="classID">
                <option value="">Choose Class</option>
                <?php
                    while($class = $results->fetch_assoc()) {
                        echo "<option value={$class['classID']}>";
                        echo $class['carclass'];
                        echo "</option>";
                    }
                ?>
            </select>
            <input type="submit" value="Insert">
        </form>

I don't see how you could do this in a single queries, because both queries have nothing to do with each other.

Your code does contain a bit of duplication, but otherwise it looks good to me.

You can simplify your code by introducing a function:

<?php
    createTableSelectForm($conn, $table, $columnValue, $columnShow, $title) {
        $sql = ("SELECT * FROM " . $table);
        $results = $conn->query($sql);
        $form = '
                <select name="makeID">
                    <option value="">Choose ' . htmlspecialchars($title, ENT_QUOTES, 'UTF-8') . '</option>';
        while($result = $results->fetch_assoc()) {
            $form .= '<option value="' . htmlspecialchars($result[$columnValue], ENT_QUOTES, 'UTF-8') . '">';
            $form .=  htmlspecialchars($result[$columnShow], ENT_QUOTES, 'UTF-8');
            $form .= '</option>';
        }
        $form .= '</select>';
        return $form;
    }

    require_once 'includes/connection.php';
?>

        <title>Car Makes</title>

Car Makes

            <form action="" method="get">
            <?php echo createTableSelectForm($conn, "tblmake", "makeID", "carmake", "Make");
            echo createTableSelectForm($conn, "tblclass", "classID", "carclass", "Class"); ?>
            <input type="submit" value="Insert">
        </form>

You really only need the first two arguments for the createTableSelectForm, but I added the other ones so that the method is more reusable.

I also added XSS protection, because with variable data, you can never be sure where it comes from (maybe, in the future you will allow visitors to add makes? Or now that the function is reusable, it will be reused somewhere else with user input? Who knows, and better safe than sorry; it also doesn't add that much overhead).

Misc

your naming is a bit confusing. The same thing should always have the same name, because it increases readability . But you have $sql and $getclass for basically the same thing. The same goes for $result vs $results (both hold multiple results). $sqlSelectMake/$sqlSelectClass and $resultMakes/$resultClasses would be better.


Async & ContinueWith I am implementing my own UnitOfWork for an EntityFramework-DataContext.

I want to call SaveChangesAsync and when this succeeds, clear a list. Is my approach with ContinueWith correct?

public async Task<int> CommitAsync(int? commandTimeout = null, bool ignoreCustomLogic = false)
{
    try
    {
        return await DataContext.SaveChangesAsync().ContinueWith((antecedent) =>
        {
            if (!antecedent.IsFaulted)
            {
                _addedEntities.Clear();
                _changedEntities.Clear();
                _deletedEntities.Clear();
            }
            return antecedent.Result;
        });
    }
    catch (DbEntityValidationException dbEx)
    {
        RethrowException(dbEx);
        return default(int);
    }
}

private void RethrowException(DbEntityValidationException dbEx)
{
    string message = "ValidationExceptions: " + Environment.NewLine;
    foreach (var validationResult in dbEx.EntityValidationErrors)
    {
        foreach (var validationError in validationResult.ValidationErrors)
        {
            message += string.Format("Property: {0} Error: {1}{2}", validationError.PropertyName, validationError.ErrorMessage, Environment.NewLine);
        }
    }
    throw new Exception(message, dbEx);
}

I want to call SaveChangesAsync and when this succeeds, clear a list.

You don't need ContinueWith, you can just write it like this

public async Task<int> CommitAsync()
{
    var result = await DataContext.SaveChangesAsync();
    _addedEntities.Clear();
    _changedEntities.Clear();
    _deletedEntities.Clear();
    return result;
}

In the original code, the catch block will never run.

Consider what happens when SaveChangesAsync throws a DbEntityValidationException: antecedent.Result will throw an AggregateException wrapping the DbEntityValidationException.

It's poor practice to throw an Exception as it means client code cannot be specific about the exceptions it catches. I would suggest changing RethrowException to a method that constructs the exception message you want, then calling it like this:

public async Task<int> CommitAsync()
{
    try
    {
        var result = await DataContext.SaveChangesAsync();
        _addedEntities.Clear();
        _changedEntities.Clear();
        _deletedEntities.Clear();
        return result;
    }
    catch (DbEntityValidationException e)
    {
        var exceptionMessage = GetDbEntityValidationExceptionMessage(e);
        throw new DbEntityValidationException(exceptionMessage, e);
    }
}

This also removes the return default(int); which is just there to appease the compiler.


Scala function to parse json with time fields to appropriate case classes. How can I write this better? I have the below function which populates different time-related case classes based on what is present in the JSON input.
def parseTime(timeJson: JsValue) = {
   val day = (timeJson \ "day").getOrElse(JsString("")).as[JsString].value.toInt
   val week = (timeJson \ "month").getOrElse(JsString("")).as[JsString].value.toInt
   val month = (timeJson \ "month").getOrElse(JsString("")).as[JsString].value.toInt
   val year = (timeJson \ "year").getOrElse(JsString("")).as[JsString].value.toInt
   if (day != "") {
     YearMonthDay(
       year = year,
       month = month,
       day = day)
   }
   else if (month != "") {
     YearMonth(
       year = year,
       month = month
     )
   }
   else if (week != "") {
     YearWeek(
       year = year,
       week = week
     )
   }
   else {
     Year(year)
   }
 }

Is there a cleaner way to check whether specific fields are present in my tuple of 4 values (day, week, month, year)

Let this be the definition of your Date types:
sealed trait Date {
  def year: Int
}

case class Year(year: Int) extends Date
case class YearMonth(year: Int, month: Int) extends Date
case class YearWeek(year: Int, week: Int) extends Date
case class YearMonthDay(year: Int, month: Int, day: Int) extends Date

In your question there are problems when value is not defined, or when it is empty string, or when value is present, but it is not a number. So you can use common function readInt to read optional integer from JSON. In case if value is not present or if value is empty or non-integer, the result of function will be scala.util.Failure.
  def parseDate(dateJson: JsValue): Try[Date] = {
    def readInt(fieldName: String): Try[Int] =
      (dateJson \ fieldName).asOpt[String].filter(_.nonEmpty).map(x => Try(x.toInt))
        .getOrElse(Failure(new IllegalArgumentException(s"$fieldName is empty")))

    val maybeDay: Try[Int] = readInt("day")
    val maybeWeek: Try[Int] = readInt("week")
    val maybeMonth: Try[Int] = readInt("month")
    val maybeYear: Try[Int] = readInt("year")

    maybeYear.map { year: Int =>
      maybeMonth match {
        case Success(month) => maybeDay match {
          case Success(day) => YearMonthDay(year, month, day)
          case _ => YearMonth(year, month)
        }
        case _ => maybeWeek match {
          case Success(week) => YearWeek(year, week)
          case _ => Year(year)
        }
      }
    }
  }

My tests:
val date1 = JsObject(Map("year" -> JsString("2001"), "month" -> JsString("11"), "day" -> JsString("30")))
println(parseDate(date1)) // => Success(YearMonthDay(2001,11,30))
val date2 = JsObject(Map("year" -> JsString("2001"), "month" -> JsString("11")))
println(parseDate(date2)) // => Success(YearMonth(2001,11))
val date3 = JsObject(Map("year" -> JsString("2001"), "week" -> JsString("51")))
println(parseDate(date3)) // => Success(YearWeek(2001,51))
val date4 = JsObject(Map("year" -> JsString("")))
println(parseDate(date4)) // => Failure(java.lang.IllegalArgumentException: year is empty)

Sorry for my English


Bubble sort algorithm in Python I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome.

#import pudb; pu.db
def bubble_sort(list_):
    """Implement bubblesort algorithm: iterate L to R in list, switching values
    if Left > Right. Break when no alterations made to to list. """
    not_complete = True
    while not_complete:
        not_complete = False
        for val, item in enumerate(list_):
            if val == len(list_)-1: val = 0
            else:
                if list_[val] > list_[val+1]:
                    list_[val], list_[val+1] = list_[val+1], list_[val]
                    not_complete = True
    return list_

if __name__ == '__main__':
    assert bubble_sort(list(range(9))[::-1]) == list(range(9))

This line seems to be left over from a debugging session:

#import pudb; pu.db

But there is no need to edit your code to debug it — and you should strive to avoid doing so, because it's too easy to forget to remove the debugging code. (And in your other question you did forget to remove it!)

Instead, learn how to use the tools. You can run the built-in debugger pdb from the command line like this:

$ python -mpdb myprogram.py

and you can run pudb from the command line as described in the documentation.
The docstring is written from the wrong point of view:

"""Implement bubblesort algorithm: iterate L to R in list, switching values
if Left > Right. Break when no alterations made to to list. """

Docstrings should be written from the user's point of view: What does this function do? How should I call it? What values does it return? What side effects does it have? For example:

>>> help(abs)
Help on built-in function abs in module builtins:

abs(...)
    abs(number) -> number

    Return the absolute value of the argument.

Your docstring is written from the point of view of the implementer. This kind of material should be in comments.
You spelled your variable list_ to avoid shadowing the built-in function list. I would prefer to find a better name for the variable rather than arbitrarily respelling it like this. Since your algorithm works on any mutable sequence (not just lists), then seq might be a good name.
Instead of:

else:
    if condition:
        code

write:

elif condition:
    code

You have a special case:

if val == len(list_)-1: val = 0

to ensure that val + 1 does not run off the end of the list. But it would be better to stop the iteration before that happens. So instead of:

for val, item in enumerate(list_):

write:

for val in range(len(list_) - 1):

val is an index into the list: it's conventional to give such variables names like i and j.
Each time around the while not_complete loop, you make a pass over the whole of the sequence. But there is an easy optimization, noted by Wikipedia:

  The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time.

So I would write it like this:

def bubble_sort(seq):
    """Sort the mutable sequence seq in place and return it."""
    for i in reversed(range(len(seq))):
        finished = True
        for j in range(i):
            if seq[j] > seq[j + 1]:
                seq[j], seq[j + 1] = seq[j + 1], seq[j]
                finished = False
        if finished:
            break
    return seq

You have some test code at the end of the script. It is best to organize test code like this into unit tests using the unittest module. For example:

from unittest import TestCase
from random import random

class BubbleSortTest(TestCase):
    def test_bubble_sort(self):
        seq = [random() for _ in range(4000)]
        sorted_seq = sorted(seq)
        self.assertEqual(bubble_sort(seq), sorted_seq)

Note how I've used randomization to get a wider range of test cases. (I've also made the length of the test array large enough to give a noticeable delay and so emphasize how poor an algorithm bubble sort is.)


Invoking API calls with parameters specified using JSON I have an instance of a Java class that I need to call some functions on, using the API exposed by another party. For each call, I need to both check for thrown exceptions, and check the value of the returned boolean. If the boolean is false, I need to read the errorMsg object to see what went wrong. In either error case, I need to throw an exception with a relevant method. Each method takes a different number of String arguments

I think there's a cleaner way to do this using reflection, but I can't figure out how to handle the different numbers of arguments. And there may be a totally different solution I've overlooked. Open to all suggestions. Any thoughts?

Here are two examples so you can see what I'm dealing with:

ClassProvidedWithExposedAPI s;

private void setHttp(JsonObject jo) throws Exception {
    boolean success = true;
    String errorString = null;
    ArrayList<Message> errorMsg = new ArrayList<Message>();
    try {
        JsonObject http = jo.getAsJsonObject("http");
        if (http != null && !http.isJsonNull()) {
            success = s.setHttp(getJsonElementAsString(http, Http.ENABLED_ELEMENT),
                    getJsonElementAsString(http, Http.HTTP_PORT_ELEMENT),
                    getJsonElementAsString(http, Http.HTTPS_PORT_ELEMENT),
                    getJsonElementAsString(http, Http.TIMEOUT_ELEMENT),
                    getJsonElementAsString(http, Http.HTTP_REDIRECT_ELEMENT), errorMsg);
        }

    } catch (Exception e) {
        errorString = e.toString();
    } finally {
        if (!success) {
            if (errorString == null) {
                errorString = errorMsg.toString();
            }
            throw new Exception("Exception in setHttp: " + errorString);
        }
    }
}

private void setSsh(JsonObject jo) throws Exception {
    boolean success = true;
    String errorString = null;
    ArrayList<Message> errorMsg = new ArrayList<Message>();
    try {
        JsonObject ssh = jo.getAsJsonObject("ssh");
        if (ssh != null && !ssh.isJsonNull()) {
            success = s.setSsh(getJsonElementAsString(ssh, Ssh.ENABLED_ELEMENT),
                    getJsonElementAsString(ssh, Ssh.SSH_PORT_ELEMENT),
                    getJsonElementAsString(ssh, Ssh.TIMEOUT_ELEMENT), errorMsg);
        }
    } catch (Exception e) {
        errorString = e.toString();
    } finally {
        if (!success) {
            if (errorString == null) {
                errorString = errorMsg.toString();
            }
            throw new Exception("Exception in setSsh: " + errorString);
        }
    }
}

Sounds like a simple use case for polymorphism:

interface JsonOperation {
    void run();
}

private void setHttp(JsonObject jo) {
    runAndHandleErrors(() -> {
        // ...
    });
}

private void setSsl(JsonObject jo) {
    runAndHandleErrors(() -> {
        // ...
    });
}

private void runAndHandleErrors(JsonOperation op) {
    try {
        op.run();
    } catch (Exception e) {
        // ...
    } finally {
        // ...
    }
}

Explanation: JsonOperation is an interface with one method so it is considered a functional interface, meaning a lambda can be considered an implementation of it. runAndHandleErrors takes a JsonOperation so whenever we call runAndHandleErrors with a lambda, the compiler infers the lambda to implement JsonOperation.

A lambda, like an anonymous inner class, captures final variables in enclosing blocks. That means that a lambda, like an anonymous inner class, can use these variables and sees the values of the variables that were assigned when the lambda / anonymous inner class was created. A lambda also captures variables that are effectively final, meaning their values are never changed whether or not they are declared as final.

When setHttp(x) is called, the following happens:

x is assigned to jo
an implementation of JsonOperation capturing jo is created (but not run)
runAndHandleErrors is called and the JsonOperation from step 2 is assigned to op
runAndHandleErrors calls op.run(), causing the JsonOperation to run
the JsonOperation runs, doing whatever it wants with jo - it sees the same value of jo as was assigned in step 2

However, since you posted to the Code Review Stack Exchange and not Programmers Stack Exchange, I'll critique your code:

catch Exception and throws Exception are code smells - to the greatest degree possible, catch and declare specific Exception types.
The logic regarding success and errorString is convoluted. You could instead separately throw an appropriate subclass of Exception in the try and catch blocks and get rid of the success and errorString variables. Your code reuse isn't actually helping because you need conditional logic in the finally block to account for both cases. Also, the thrown exception in the catch block should properly wrap the original exception by passing the latter directly into the former's constructor.
Make a helper method for getJsonElementAsString that takes a varargs array of attribute keys and returns a list of attributes. This method would make your code much terser.


Workaround for have 2 column with pseudo AUTO INCREMENT This is the situation :
the table order has a column with ID AUTO INCREMENT but (there is always a but)
i can't use it because i don't want number order 1234567 after 5 years but i want 1/2014 , 1/2015 etc etc.
For doing this i have created this columns into the table :

ID AUTO INCREMENT <--- unique ID used for manage the order after the insert
numberorder INT <--- fake number of order showed at the user NOT unique
IDyear YEAR <--- the year for the order e.g. 2014 or 2015

For doing this i write this code before the query for insert a new order
and processed at the submit form :

$query_Recordset4 = "SELECT MAX(IDyear) AS maxyear FROM order";
$Recordset4 = $mysqli->query($query_Recordset4);
$row_Recordset4 = $Recordset4->fetch_assoc();
$maxyear = $row_Recordset4['maxyear'] ;
$thisyear = date("Y") ;

if ($maxyear === $thisyear) {
    $query_Recordset5 = "SELECT MAX(numberorder) FROM order WHERE IDyear=$thisyear ;";
    $Recordset5 = $mysqli->query($query_Recordset5);
    $row_Recordset5 = $Recordset5->fetch_assoc();
    $numberorder = $row_Recordset5['MAX(numberorder)'] + 1 ;
}
else {
    $numberorder = 1 ;
}

And then i use $numberorder for insert them into the table order in his column.

QUESTION REVIEW

Maybe my question was not clear written and now i try to add some elements.

Thit is what i have now into the table order :

|----------|-------------|--------|
|    ID    | numberorder | yearId |
|----------|-------------|--------|
!    1     |     1       |  2014  |
|----------|-------------|--------|
|    "     |     "       |    "   |  <---- more orders
|----------|-------------|--------|
|   500    |    500      |  2014  |  <---- last order year 2014
|----------|-------------|--------|

When the year change what i need is this :

|----------|-------------|--------|
|   501    |     1       |  2015  |  <---- first order year 2015 (2016,2017 etc etc)
|----------|-------------|--------|

Like a suggestion, my code has a concurrency problem.

Have a second table yearid with another AUTO_INCREMENT field
for take to them a unique ID for numberorder field is perfect solution but when the year finish i can't restarting the AUTO_INCREMENT at 1 because for security reason the TRUNCATE and DROP commands are not available for the user created for the connection.

The only way i see is create a new table each year e.g. yearid2015 for have ID = 1.

$query_Recordset4 = "SELECT MAX(IDyear) AS maxyear FROM order";

Whenever you need to postfix the name of a variable, class or anything else with number because you already used that name...you're doing it wrong. Either your function does too much and should be split into smaller functions, or you need to choose better names.

$query_Recordset5 = "SELECT MAX(numberorder) FROM order WHERE IDyear=$thisyear ;";

Even when you declare the variable, you should make a habit out of using parameterized queries.

There's something wrong about your table layout. At the moment I imagine it should look something like this:

TABLE order
    numberorder INT
    IDyear INT

A more sane layout would be this:

TABLE order
    id INT AUTO_INCREMENT
    idYear INT
    orderedAt DATETIME

The main difference is that I rely on an ID field which is managed by the database. It does not matter what the accountant wants or how your boss thinks the billing numbers should look like, you need something unique to identify a record and nothing beats a unique, automatically managed counter for doing that job.

Creating the necessary number you want is as easy as

SELECT CONCAT(idYear, '/', YEAR(orderedAt)) FROM order;

and if you place this in a stored procedure or in a function in your object you never need to think about it again. Incrementing this number is also rather easy:

SELECT IFNULL(MAX(idYear), 0) + 1 FROM order WHERE YEAR(orderedAt) = yourYear;

It can not break and you're free to put the date of the order into the past or the future (which is sometimes needed in accounting). In your method working outside of the current year will break the numbering.

Ideally you would set that number if you insert the record into the database to minimize race-conditions (and possible duplicate numbers).


Finding two consecutive triangular numbers with a given target sum I need to speed up this code so it can handle inputs in the thousands. It adds triangular numbers to a list based on input n, then it loops through to find if any two consecutive numbers squared in that list add up to n. The test cases I've been using are n = 45, which would be true and n = 6, which would be false.

Here is the code:

def Triangular(n):
    lst = []
    for i in range(1, n + 1):
        lst.append((i** 2 + i)//2)

    for i in lst:
        for j in lst:
            if i*i + j*j == n and ((lst.index(i) == lst.index(j)+1)
                               or (lst.index(i) == lst.index(j)-1)):
                return True
            else:
                continue

A few suggestions:

Explicitly return False if the condition fails, i.e., if there aren’t two triangular numbers that sum to n.

As it stands, your function with either return True or None.
Don’t store the first n triangular numbers in a list; check them as you go through.

For large n, you’ll be creating a very large list, which will slow down Python. And the vast majority of the numbers in that list will be greater than n, so cannot possibly sum with a consecutive triangular number squared to give n.

This is much more efficient:

for i in range(1, n + 1):
    # If T_1 = i (i+1) / 2 and T_2 = (i+1) (i+2) / 2 then
    # we have
    # T_1^2 + T_2^2 = (i+1)^2 [i^2 + (i+2)^2] / 4
    result = (i+1)**2 * (i**2 + (i+2)**2) / 4
    if result == n:
        return True
    elif result > n:
        return False

We’re not storing lots of numbers in a list, and we’re only going until it’s impossible to find a working combination.

On my fairly weedy old laptop, this can take O(10^7) input and finish in under a second.
Use a better function name, and write a docstring.

Per PEP 8, function names in Python should be lowercase_with_underscores; your CamelCase function gives the impression of being a class.

And Triangular isn’t a very helpful name – if I saw that being called, I’d probably assume it was returning the nth triangular number. Something like

def is_consecutive_triangular_square_sum(n):

doesn’t roll off the tongue as nicely, but it’s never going to be confused for getting triangular numbers, and the is_ prefix suggests that it probably returns a boolean.

You should also write a docstring, which explains what the function is supposed to do. Useful for interactive help and/or people reading your code.


Speed up large calculation of intersections I have the following data:

trains is a dictionary with 1700 elements. The keys are the IDs of trains and the value for each train is an array with every station ID where that train stops.
departures is a dictionary with the same keys as trains, so also 1700 elements. Each value is the departure time of the train.

Now, I would like to compute intersections between trains. When train A and train B have overlapping stops, I look at the departure time of both trains. When train A departs before train B, then (A, B) is put in the resulting set, otherwise (B, A).

trains = {90: [240, 76, 18, ...], 91: [2, 17, 98, 76, ...], ...}
departures = {90: 1418732160, 91: 1418711580, ...}
intersections = []

for i in trains:
    trA = trains[i]
    for j in trains:
        if i != j:
            trB = trains[j]
            intersect = [val for val in trA if val in trB]
            if intersect:
                if departures[i] < departures[j]:
                    if (i, j) not in intersections:
                        intersections.append((i, j))
                else:
                    if (j, i) not in intersections:
                        intersections.append((j, i))

When finished, the intersections list contains 500.000 elements.

This however takes very long to compute! I'm guessing it is because of the (i, j) not in intersections and (j, i) not in intersections statements.

Is there any way I could alter my code to speed up this calculation?

I would use a somewhat different algorithm to accomplish this task, by instead making a dictionary of all trains that go to each stop, sorting those trains by arrival, and then taking all inorder pairs of trains at each stop.

The basic algorithm is like this:

from collections import defaultdict
from itertools import combinations

trains = {...}
departures = {...}

intersections = set()

stations = defaultdict(list)
for t, train in trains.items():
    for s in train:
        stations[s].append(t)

for station in stations.values():
    intersections.update(combinations(sorted(station, key=lambda t: departures[t]), 2))

(This version of the code vastly improved by @Veedrac)


Scheme: FSM substring search I have been working on a function that return a FSM that searches a specific word based on the argument of the constructor. The idea was to use those routines as means to learn about regular expressions and maybe implement a very basic regexp system, so I thought that matching normal string was a good first step in that direction.

This is actually my first "complex" program in Scheme. I learnt to program in C so it has been a little hard to switch my way of thinking into a functional approach, so any comments in my way of programming in Scheme would also be very useful.

NOTES:

I know that using lists might not be the most efficient thing to do, but they allowed me to program in a more functional way without using vector-set!
If there is something to add or to fix please don't just put the answer, that way I won't learn. Try to use code only if necessary.
Sadly Emacs uses tabs for indentation so formatting may be a little messy.

An automata in my code is represented as a list of states where each one is described as a pair of the form (a . b) where a is the matched character and b is the index of the state it transitions to.
If no pair contains a specific character then it defaults to the invalid state (index = 0).

The run-automata function searches a matching substring and returns its offset or #f if it is not contained inside string.

(define (string-null? s) (= (string-length s) 0))
(define (string-append-c s c) (string-append s (string c)))
(define (string-tail str) (substring str 1 (string-length str)))

;; is s2 a prefix of s1?
;; [TODO] - Use offset instead of string-tail
(define (string-prefix? s1 s2)
  (cond
    [(string-null? s2) #t]
    [(string-null? s1) #f]
    [(not (char=? (string-ref s2 0)
                  (string-ref s1 0))) #f]
    [else (string-prefix? (string-tail s1)
                          (string-tail s2))]))

(define (enumerate start end)
  (define (iter start end acc)
    (if (> start end)
        acc
        (iter start (- end 1) (cons end acc))))

  (iter start end '()))

(define (build-automata needle)
  (define (max-suffix-that-is-prefix str)
    (cond
      [(string-null? str) ""]
      [(not (string-prefix? needle str))
         (max-suffix-that-is-prefix (string-tail str))]
      [else str]))

  (define (build-transitions state-string transitions dictionary)
    (if (null? dictionary)
        transitions
        (let* ([c (car dictionary)]
               [suffix (max-suffix-that-is-prefix (string-append-c state-string c))])
          (build-transitions
            state-string
            (if (string-null? suffix)
                transitions
                (cons (cons c (string-length suffix))
                      transitions))
            (cdr dictionary)))))

  ;; Last state does not require a transition as it is the final state.
  ;; "We are done by that point".
  (let ([dictionary (string->list "abcdefghijkmnopqrstuvwxyz")])
    (map (lambda (n)
           (build-transitions
             (substring needle 0 n)
             '()
             dictionary))
         (enumerate 0 (- (string-length needle) 1)))))

;; Takes an automata and a string and returns the offset of the pattern the
;; automata was built to search
(define (run-automata automata string)
  (define (search-transition c state-transitions)
    (cond
      [(null? state-transitions) 0]
      [(char=? (caar state-transitions) c) (cdar state-transitions)]
      [else (search-transition c (cdr state-transitions))]))

  (define (step state automata-size offset)
    (cond
      [(= state automata-size) (- offset automata-size)]
      [(>= offset (string-length string)) #f]
      [else (step (search-transition (string-ref string offset)
                                     (list-ref automata state))
                  automata-size
                  (+ offset 1))]))

  (step 0 (length automata) 0))

My suggestions are less about your design of the automaton, but rather a few comments on the style and language which I hope you will find useful.

Know your functions
Note that, string-null? is #t if the string has zero length. Thus, if ((string-null? str) "") is the same as if ((string-null? str) str). And that combines well with the else part in max-suffix-that-is-prefix which also returns str.

  (define (max-suffix-that-is-prefix str)
    (if (string-prefix? needle str)
        str
        (max-suffix-that-is-prefix (string-tail str))))

Named let
I noticed that some functions (enumerate and run-automata) define local functions only to then call them with initial values. Scheme provides a syntactic form for that, the named let:

(let proc-id ([id init-expr] ...) body ...+)

More on named let: https://docs.racket-lang.org/reference/let.html

Adhering to the declarative paradigm
The enumerate function could be written in a declarative style. To enumerate from start to end is to cons start to the enumeration from (+ start 1) to end.

(define (enumerate start end)
  (if (= start end)
      `(,end)
      (cons start (enumerate (+ start 1) end))))

Note, however, that this is not an equivalent formulation of the iterative style using an accumulator since the call the enumerate in the call to cons prevents tail-recursion optimisation.

Cleaner syntax using a named let:

(define (enumerate start end)
  (let iter ([start start]
             [end end]
             [acc '()])
    (if (> start end)
        acc
        (iter start (- end 1) (cons end acc)))))


Maximum Width binary tree Here is my code for the LeetCode problem

  For a given binary tree, find the maximum width of the binary tree. The width of one level is defined as the length between the end-nodes even if there are None nodes in between

My code (in PyCharm) passess all the given tests but does not seem to pass on the LeetCode website. I am not sure why this is, so please don't try plugging it into the website as I assume the way I have built a binary tree is different to their method.

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    level_width = {0: [0, 0]}

    def get_width(self, root, level=0, pointer=1):
        if root.left:
            if level + 1 not in self.level_width:
                self.level_width[level + 1] = [pointer * 2, 0]
            self.level_width[level + 1][0] = min(self.level_width[level + 1][0], pointer * 2)
            self.get_width(root.left, level + 1, pointer * 2)
        if root.right:
            if level + 1 not in self.level_width:
                self.level_width[level + 1] = [9999, pointer * 2 + 1]
            self.level_width[level + 1][1] = max(self.level_width[level + 1][1], level + 1, pointer * 2 + 1)
            self.get_width(root.right, level + 1, pointer * 2 + 1)
        return

    def widthOfBinaryTree(self, root):
        """
          :type root: TreeNode
          :rtype: int
          """
        self.get_width(root)
        max_distance = 1
        for k, v in self.level_width.items():
            max_distance = max(max_distance, v[1] - v[0] + 1)
        return max_distance

root = Node(1)
root.left = Node(3)
root.left.left = Node(5)
root.left.left.left = Node(6)
root.right = Node(2)
root.right.right = Node(9)
root.right.right.right = Node(7)

print(root.widthOfBinaryTree(root))

In the above code, you missed counting the in-between null nodes, that is why, the result is wrong for the input [2,1,4,3, null,5].

You approached the problem using DFS(Depth First Search) algorithm which is useful to find the height of a tree.

BFS (Breadth-first search) algorithm would be the best suitable choice for this problem.