Counting pairs of relatively prime numbers

tl;dr TLE beyond input size 40000 to 50000 (10 seconds for input size 100000)

Conditions (1) and (2) are transitive but independent and one-sided. This means they can only prune half of all candidates on average each, and so their combination only reduces the average candidate set to one fourth (i.e. half of a half). Such a small constant factor is not worth it to invest in (as in 'devising a special data structure'), unless overall performance is already close to a passing grade. Asymptotic performance doesn't change at all, of course. Hence it is best to take the doubling in performance that comes from index pruning (condition (2), which is essentially free) and test condition (1) as pairs are processed.

Condition (3) induces a squarish relation all on its own already, and it is not transitive. This means that there is no efficiency gain from precomputing this relation, and memoisation is likely to be completely ineffective in the face of random inputs.

The evaluation of the GCD for a pair of numbers takes time logarithmic in the smaller of the two inputs. This time can be cut by a considerable constant factor with a bit of precomputation, by computing integer-sized 'bit vectors' representing the presence of a handful of the smallest primes in the (radical) factorisation of a number.

This way a simple binary AND can prove the absence of shared small factors and thus avoid the computation of the actual GCD in about 89% of all cases (assuming factorisation by the first 32 primes, i.e. up to 131). In the remaining 11%, only the factorisation 'remainders' need to be GCDed, i.e. what remains after dividing out the small factors/radicals represented by the bit vectors. This saves some iterations of Euclid's algorithm.

This can give you an overall speed boost of an order of magnitude or more. On top of the factor 2 speed gain from index pruning mentioned by coderodde and some general efficiency tuning this might just be enough to beat the time limit...

Note: one might be tempted to extend the 'bit vectors' from 32 bits to 64 bits to utilise the bigger machine words on 64-bit machines, but this is not worth it. It doubles the up-front factorisation effort but it improves the rejection rate only from 88.7% to 90.3%, i.e. by a completely negligible 1.8%.

Here's a small table with the pass/reject rates for bit masks involving the given number of the first primes:

 8 primes: pass 17,102%, rej. 82,898%                 # up to 4 extra radicals
12 primes: pass 14,872%, rej. 85,128% // boost 2,690% # up to 3 extra radicals
16 primes: pass 13,609%, rej. 86,391% // boost 1.484%
32 primes: pass 11,300%, rej. 88,700% // boost 2,673%
64 primes: pass  9,683%, rej. 90,317% // boost 1,823% # up to 1 extra radical

The 'up to X extra radicals' bit says how many different prime factors can remain in the factorisations of numbers not exceeding 100,000 after the the given number of the first small primes has been factored out.

P.S.: the bounds on the number of numbers is the same as the bound on the size of the numbers, which means that the factorisations can be pre-computed wholesale without any divisions (by borrowing the logic behind the Sieve of Eratosthenes). The partial factoring for the bit vectors takes less than a millisecond, and factoring the input remainders takes less than 10 milliseconds for 100,000 inputs. Hence the stuff can always be computed wholesale and it isn't even worth it to have different code paths for small and big input batches.

--- UPDATE ---

For getting a better handle on the problem I needed a closer fix on some numbers, and so I coded things up in C++. It turned out that computing the gcd of the remainders (after factoring out the small primes used in the 'bit vectors') is orders of magnitude too slow, even though it occurs only for 0.35% of all candidates. This necessitated replacing the partial factorisation remainders with lists of the (up to two) remaining radicals.

'Radical' Optimisation

For numbers less than 107113 = 43 * 47 * 53, factoring out the 13 smallest primes leaves at most two distinct prime factors ('radicals'). Moreover, only factors up to half the limit need be considered since the only numbers with bigger prime factors are the primes, which are coprime to all numbers but themselves and self-pairings get excluded via criteria (1) and (2) both. This means that 2 x 16 bits = 32 bits are sufficient for storing the 'list' of remaining radicals for a number.

This size reduction is beneficial for L1 cache utilisation and it would allow to stuff both radicals into a single 32-bit integer; however, it collides with an important optimisation of the intersection operation. This optimisation is the reduction of branchings to the absolute minimum of two to three comparisons, by always treating the two-element lists as full and by replacing all but one of the remaining non-comparison branches with arithmetic (poor man's CMOV). This makes things easier for the CPU's branch prediction logic and reduces the amount of incurred branch mis-prediction penalties, but it requires the use of sentinel values for 'missing' radicals. With the only safe sentinel for a number a[i] being a[i] itself this means that the slots for the radicals must be able to hold full-sized numbers.

Elimination of one particularly nasty branch required adding a third radical slot (which always holds a sentinel value) but it resulted in a speedup of 10%. Without this explanation it might seem odd that the code uses three slots even though there can be at most two radicals. First, the data:

uint16_t sieve[1 + LIMIT];  // bit masks of partial factorisations of 1 .. LIMIT
uint16_t v[1 + LIMIT];      // v[i] = sieve[a[i]]
uint32_t f[1 + LIMIT][3];   // remaining factors (radicals) for each input (3rd is sentinel)
uint8_t skip[1 + LIMIT];    // for each a[j]: how many successors are not less

The code for generating these tables is elementary and of little interest here (especially as it takes less than 10 milliseconds even in C#). Hence I'm skipping it in the interest of brevity. Here is the meat of the code, the function that does the counting as specified by the task:

uint64_t count_matches (uint32_t const a[], uint32_t count)
{
    uint64_t result = 0;

    prepare_tables(a, count);

    for (uint32_t i = 0; i < count; ++i)
    {
        uint32_t a_i = a[i];
        unsigned v_i = v[i];

        for (uint32_t j = i + 1; j < count; ++j)
        {
            if ((v_i & v[j]) == 0)
            {
                if (a_i > a[j])
                {
                    if (uint32_t d = f[i][0] - f[j][0])
                    {
                        uint32_t di = (d >> 31) & 1;
                        uint32_t ci = di;
                        uint32_t cj = di ^ 1;

                        if ((d = f[i][ci] - f[j][cj]) != 0)
                        {
                            di = (d >> 31) & 1;
                            ci += di;
                            cj += di ^ 1;

                            if ((d = f[i][ci] - f[j][cj]) != 0)
                                ++result;
                        }
                    }
                }
                else j += skip[j];
            }
        }
    }

    return result;
}

On my laptop this clocks a bit less than 19 seconds for random inputs of size 100,000, compared to 22 seconds for a 'branchy' version of the intersection test (which has no use for the third slot):

                    int32_t d = int32_t(f[i][0] - f[j][0]);

                    if (d > 0)
                    {
                        d = int32_t(f[i][0] - f[j][1]);

                        result += d > 0 || d && f[i][1] != f[j][1];
                    }
                    else if (d != 0)
                    {
                        d = int32_t(f[i][1] - f[j][0]);

                        result += d < 0 || d && f[i][1] != f[j][1];
                    }

Of course, in Python the optimisation is bound to get killed by the interpreter overhead, because the code contains a lot of explicit little operations instead of pushing processing into the engine. But in any case it should be beneficial to utilise the fact the 'radical factor set intersection' involves only lists of at most two elements here instead of general sets.

Skip Counts

The skip count thing hasn't been mentioned yet - it's a small optimisation that costs virtually nothing and improves speed by about 10%. It utilises the fact that a[i] <= a[j] && a[j] <= a[j + k] implies a[i] <= a[j + k], and storing/precomputing this is cheap because it involves only a[j] and its context in the input sequence instead of depending on pairings of a[i] and a[j].

Half of all skip counts are 0, of course, and half of the rest is 1. The rest peters off quickly because the probability of a skip count having value k is 1 / ((k+1)*(k+2)), which means that skip counts of four bits or so already realise most of the performance gain that can be gotten this way.

Four bits would probably be optimum if one wanted to stuff several different values - like input number, small factor bit vector and skip count - into a single integer-sized variable, especially in languages where array indexings carry a heavy cost (Python, Java, C#). In my sample code I used a separate array for simplicity, and hence allocated one whole byte for each skip count.

Numbers and Summary

The reason I sat down and got coding was that I wanted to get a fix on some numbers, in order to get a better handle on the problem and a better feeling for the lay of the land. Here are those numbers.

For a random input vector of 100,000 numbers - the limit given in the task description - and enumerating only the 4,999,950,000 pairs of numbers with i < j, it took the following amounts of time to count the following things:

11.0 s for 2512386875 inversions
21.5 s for 3029211382 coprime pairs
17.3 s for 1527936260 candidates (a[i] > a[j] and no common factors among the first 16 primes)
15.7 s for 1527936260 candidates (dito, with byte-sized skip counts)
85.7 s for 1522549277 matches (with gcd applied to remainders)
18.6 s for 1522549277 matches (with list intersection for remainder radicals)

The most important message here is that the number of inversions (i.e. criterion (2) in the task description), the number of coprime pairs (criterion (3)) and the number of results to be counted are all the same order of magnitude as the number of pairs with i < j. The percentages are 50.2%, 60.6% and 30.5% respectively.

Also, just counting the number of inversions takes more than five times as long as the two seconds admissible as per the task description, even though my laptop is likely quite a bit faster than the hardware used by the robot judge.

Even if I found some fiendishly clever algorithm or data structure which can prune everything that doesn't fulfil the task conditions then the time would still be 30.5% * 19 s which is about 6 seconds. In other words, on a maximum input file the code would still take three times as long as the time limit.

For comparison, counting the matches for a vector of 1000 random inputs - as per coderodde's 'lightened' specification - takes less than 2 milliseconds with this code. I'd hate to think how long coderodde's solution would take on a maximum input file as per the actual task description; extrapolation from the given results puts it at more than half an hour.

In the first two paragraphs of this post I argumented why the intersection of the task criteria must leave a number of pairings that is still square in the number of inputs; now we know that the actual number is about 30% of 'j-pruned' pairs or 15% of all input pairs. Moreover, the C++ timings suggest that counting each result pair individually is simply not an option, since the optimisation potential that's still left is far less than an order of magnitude (which is why I didn't bother to create an optimised version).

Any admissible solution must count whole swathes of pairs in one go instead of processing each pair individually, but at the moment I cannot offer any specific advice as to how one might accomplish that. One seedling of an idea might lie in the fact that any prime must a priori be coprime to any input number other than itself, so that only criteria (1) and (2) need be applied for counting it. Similar considerations apply to sets of input numbers that have disjoint sets of prime factors.

I took a peek at the submission table at HackerEarth, and the only successful submissions I could see were in C++ with timings between 3.3 seconds and 12 seconds, with codes sizes ranging from 10KB to several hundred KB. This suggests that real solutions might be quite involved, compared to the simple code that has been discussed in this topic so far. I did not look at any of the code, however, because I intend to have a stab at the problem myself first...

UPDATE #2

250,000,000 factor set intersections per second

For an input vector of 10^5 values the current algorithm has to filter 0.5 * (10^5)^2 pairs of numbers - that's about 5 billion (American-style). Performance can be roughly doubled by looking only at inversions and by removing all branches but one from the set intersection code.

The standard algorithm for inversion counting by merge sorting divides the input into non-inverted and inverted runs and tallies the latter:

long count_inversions_m1 (List<int> values)
{
    long inversions = 0;
    int n = values.Count;
    var a = values.ToArray();
    var b = new int[n];

    for (int w = 1; w < n; w <<= 1)
    {
        for (int beg = 0; beg < n; beg += w + w)
        {
            int mid = Math.Min(beg + w, n);
            int end = Math.Min(mid + w, n);

            for (int i = beg, j = mid, k = beg; k < end; ++k)
            {
                if (i < mid && (j >= end || a[i] <= a[j]))
                {
                    b[k] = a[i++];
                }
                else // a[k] > a[j] for all k in [i .. mid - 1]
                {
                    inversions += mid - i;
                    b[k] = a[j++];
                }
            }
        }

        var t = a;
        a = b;
        b = t;
    }

    return inversions;
}

In the a[i] > a[j] branch, the run from a[i] to a[mid - 1] is inverted with respect to a[j]; all inversions in the input pass that branch eventually. Replacing the line

 inversions += mid - i;

with a small loop that performs factor set intersection on the values involved gives an algorithm that is a tad faster than the earlier one, because it never has to look at any non-inverted pairs. Simply dropping the intersection code from the earlier version in there would work, but it can be made faster by using branch-less comparison.

That is, instead of branching based on the result of comparing factors, a value is computed that is 0 if the two lists of non-bitmapped prime factors (at most two elements each) have some value in common, and 1 if they do not. I chose to abuse the fact that, given a pair of unequal values a and b, either a - b or b - a must be negative but no difference is negative if the values are equal. Hence the high bit of (a - b) | (b - a) is 1 if the values are different, and 0 if they are equal (as long as the difference does not exceed INT32_MAX).

A further speedup comes from ‘compressing’ factors down to 16 bits. This is possible because the factors are only ever compared for equality, and any unique mapping of values will do just as well for that. There are only 9592 primes up to 100000, and so there are many viable schemes for assigning each prime a unique 16-bit proxy value. I chose p < UINT_MAX ? p : (ushort)(p + 3) for simplicity. This ‘compression’ from 32 bits to 16 bits leads to better cache utilisation and reduces register pressure for 32-bit architectures (since a whole pair fits into a single machine word).

Here's the final set intersection code, ready for replacing the inversion branch in the above procedure (C++ version shown, but the C# is similar):

uint32_t a_j = b[k] = a[j++];                // x 815,024
unsigned f_j = factor_bits[a_j];
unsigned bj0 = big_factors[a_j][0];
unsigned bj1 = big_factors[a_j][1];

for (uint32_t l = i; l < mid; ++l)
{
    uint32_t a_i = a[l];                     // x 2,512,386,875

    if ((f_j & factor_bits[a_i]) == 0)
    {
        unsigned bi0 = big_factors[a_i][0];  // x 1,527,936,260
        unsigned di0 = ((bi0 - bj0) | (bj0 - bi0)) & ((bi0 - bj1) | (bj1 - bi0));
        unsigned bi1 = big_factors[a_i][1];
        unsigned di1 = ((bi1 - bj0) | (bj0 - bi1)) & ((bi1 - bj1) | (bj1 - bi1));

        result += (di0 & di1) >> 31;         // 1,522,549,277 x 1 vs 5,386,983 x 0
    }
}

The 16-bit factor bitmaps are kept in a separate array to improve cache efficiency, because the bitmap AND must occur for every inversion pair whereas comparison of the up to two extra factors occurs less often. I've annotated some code lines with execution counts for an input of 100,000 random values, to put things a bit into perspective.

The resulting code comes closer to the goal, but not close enough. The C++ version still needs 10 seconds for a maximum-size (non-degenerate) input, and for the C# edition it's 12.5 seconds. I submitted the C# but, as expected, it failed all (non-degenerate) test cases where the input size exceeded 40,000 significantly. The performance target seems almost within reach, but it seems hopeless to try squeezing another five-fold performance increase out of the current approach.

I've chosen to complete the write-up despite the failure because some of the techniques may be useful for other challenges. Thanks to Kaushal28 for bringing this neat problem to our attention - I had a lot of fun trying to solve it and I learnt a lot along the way.


I'd suggest to change the type signature of randomDots to

randomDots :: [Dot] -> [Double] -> R.RVar [Dot]

as there is nothing IO based there. And then change main to

main = mainWith . dotsToDiagram =<< R.sample (randomDots [] [0.01, 0.02..1.0])

Nitpicks: I'd put tooClose before randomDots so that the functions are in logical order, but that's just a matter of personal preferences.

Otherwise I also quite liked the code.

Update: Some further thoughts: Function randomDots is concise, but it also mixes several concepts together. Namely:

it re-runs generation of a dot (until it fits wrt the previous ones);
it checks each generated dot with all previously generated ones.

So I'd suggest to split the function into even smaller ones, each targeting one of these problems. While the resulting code is larger, I believe it's easier to comprehend and more maintainable in the long run:

-- | Runs a monadic action while its result satisfies a given predicate.
iterateWhile :: (Monad m) => (a -> Bool) -> m a -> m a
iterateWhile pred k = loop
  where
    loop = k >>= \x -> if pred x then loop else return x

This function is also available in monad-loops. Then:

-- | Generates a list of values that are independent wrt a given (commutative)
-- predicate.
-- Each monadic action is repeated until its result is independent with all the
-- previous ones.
genIndependent :: (Monad m) => (a -> a -> Bool) -> [m a] -> m [a]
genIndependent pred = foldM step []
  where
    step rs k = liftM (: rs) $ iterateWhile (\x -> any (pred x) rs) k

Both these functions are polymorphic with no coupling with RVar. The final function is then expressed just as

-- |Recursively generate random dots and check that they do not
-- overlap.
randomDots :: [Double] -> R.RVar [Dot]
randomDots = genIndependent tooClose . map (R.sample . randomDot)


One thing I quickly spot is this:
If your second while loop completes naturally instead of via a break, you will also exit the  first while loop. Thus the last instruction executed, gt--, is unnecessary.

Let's look at the execution paths:

//BEGINLOOPS
while (lt <= gt) {
    if (a[pivot] > a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, does gt--;, then jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                break;//does gt--;, then jumps to BEGINLOOPS
            }
            gt--;
        }
        gt--;
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);

There's only 2 ways the second while loop can end. Either via a break or via gt decrementing until it equalizes with lt.

So we should alter the one execution path where the gt--; is unnecessary.

//BEGINLOOPS
while (lt <= gt) {
    if (a[pivot] > a[lt]) {
        temp = a[pivot];
        a[pivot] = a[lt];
        a[lt] = temp;
        pivot = lt++;
    } else {
        while (gt >= lt)  {//If false, jumps to ENDLOOPS
            if (a[gt] < a[lt]) {
                temp = a[lt];
                a[lt] = a[gt];
                a[gt] = temp;
                gt--;//does gt--;,
                break;//then jumps to BEGINLOOPS
            }
            gt--;
        }
    }
}
//ENDLOOPS
qsort(a, start, pivot - 1);
qsort(a, pivot + 1, end);

That saves you one instruction for each time you end via that one execution path.

Additionally, you know what pivot is already, so I'd split this in a helper function and a recursive function.

public static void quickSort(int[] a, int start, int end) {
    if (start >= end) return;
    qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    while (lt <= gt) {
        if (a[pivot] > a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    gt--;
                    break;
                }
                gt--;
            }
        }
    }
    pivot--;
    if(start < pivot){
        qsort(a, start, pivot);
    }
    if(lt < end){
        qsort(a, lt, end);
    }
}

Whoa, that's different near the end. Yeah, I rushed ahead. Let me explain.

pivot starts at start. lt starts at start + 1, which is pivot + 1. Furthermore, there's only one place where pivot is changed (pivot = lt++) and there's only one place where lt is changed (also pivot = lt++). Looking at that line tells us it does this:
Set pivot to the value of lt (which by definition is pivot + 1), then up lt by one, making lt to be pivot + 1 again. One wonders whether you even need the different variable - if you wanted to conserve memory, I would strip the unneeded variable.

So with that logic, excepting the moment of which that one line is executed in which they are altered, pivot and lt are always 1 apart. Thus I can use lt as a shorthand for pivot + 1.

Examples, with pivot = 12:

qsort(a, start, pivot - 1);//12 - 1 = 11
qsort(a, pivot + 1, end);//12 + 1 = 13

    pivot--;//lt is still 13, 12-- = 11
    if(start < pivot){//only run if start >= end is false, so only run if start < end is true.
        qsort(a, start, pivot);//11
    }
    if(lt < end){//only run if start < end is true.
        qsort(a, lt, end);//lt is still 13, I changed nothing to it.
    }

You should also consider removing the pivot variable and seeing if that makes a difference.

That said, all performance optimizations should be profiled and benchmarked properly. Who knows what optimizations the JVM will make for you. But if you were a human who executed the code by hand, these optimizations would speed the code up for you.

Looking deeper at it (why not?) shows me one more problem: if you made no swaps, you will still split around your pivot, reiterating the entire array except one element. That's really, really bad. You'll basically have \$T_{end-start}\$ iterations, where \$T\$ is a triangular number. In other words: 100 elements sorted gives you 5050 iterations or so. That's bad.
Let's add a boolean for that.

public static void quickSort(int[] a, int start, int end) {
    if (start >= end) return;
    qsort(a, start, end);
}

private static void qsort(int[] a, int start, int end) {
    int pivot = start;
    int lt = start + 1;
    int gt = end;
    int temp;
    boolean swapped = false;
    while (lt <= gt) {
        if (a[pivot] > a[lt]) {
            temp = a[pivot];
            a[pivot] = a[lt];
            a[lt] = temp;
            pivot = lt++;
            swapped = true;
        } else {
            while (gt >= lt)  {
                if (a[gt] < a[lt]) {
                    temp = a[lt];
                    a[lt] = a[gt];
                    a[gt] = temp;
                    swapped = true;
                    gt--;
                    break;
                }
                gt--;
            }
        }
    }
    if(swapped){
        pivot--;
        if(start < pivot){
            qsort(a, start, pivot);
        }
        if(lt < end){
            qsort(a, lt, end);
        }
    }
}


Script to store, search, and delete IPFS data with description in JSON file

I would make an object that acts like a dict and that automatically writes any changes to disk, similar to the one I wrote in this answer.

import os
import json

class PersonalHashTracker(dict):

    def __init__(self, filename):
        self.filename = filename
        if os.path.isfile(filename):
            with open(filename) as f:
                # use super here to avoid unnecessary write
                super(PersonalHashTracker, self).update(json.load(f) or {})

    def write(self):
        with open(self.filename, "w") as f:
            json.dump(self, f)

    def __setitem__(self, key, value):
        super(PersonalHashTracker, self).__setitem__(key, value)
        self.write()

    def __delitem__(self, key):
        super(PersonalHashTracker, self).__delitem__(key)
        self.write()

    def update(self, d, **kwargs):
        super(PersonalHashTracker, self).update(d, **kwargs)
        self.write()

You can then use it like this:

MENU = """What do you want to do?
a)Add a new IPFS hash
s)Seach stored hashes
d)Delete stored hash
q)Quit
>>"""

if __name__ == "__main__":
    hash_store = PersonalHashTracker("/Users/troywilson/testing/pht/hash.json")

    while True:
        choice = raw_input(MENU)
        if choice == 'a':
            # Add a new hash.
            description = raw_input('Enter hash description: ')
            new_hash_val = raw_input('Enter IPFS hash: ')
            new_url_val = raw_input('Enter URL: ')

            if new_hash_val not in hash_store:
                hash_store[new_hash_val] = {'description': description,
                                            'url': new_url_val}
            else:
                print 'Hash exists!'
        elif choice == 's':
            # Search the current descriptions.
            search_term = raw_input('Enter search term: ')
            descriptions = {v['description']: h for h, v in hash_store.items()}
            print descriptions.get(search_term, 'Not Found')
        elif choice == 'd':
            # Search the current descriptions and delete entry.
            del_hash = raw_input('Hash to delete: ')
            del hash_store[del_hash]
            print 'Hash removed'
        else:
            print 'Exiting'
            break


On the whole, the game works and has a solid UI that you've correctly kept basic and mostly out of play as you focus on the game engine logic. It looks like you've gone for a partially-OOP approach by putting focus on the two entities that are drawable and their necessary data but leaving the main game logic outside of a class. I think that's a reasonable fundamental design. I do have a variety of suggestions for tightening up this design and improving code style though.
Tight coupling
Although your classes are potentially useful abstractions, the snake's movement update is done outside of the snake class, breaking encapsulation. A snake.move or snake.change_direction function is the correct delegation of responsibility for this rather than reaching into the class from main and messing with its internals.
The state of code with classes and functions that rely on and mutate global state is difficult to predict. For example, I'd reasonably expect a snake or food class to be able to create multiple instances with separate positions. But in this design, instances are tightly coupled to a single global FOOD_COOR or SNAKE_COMP variable. Creating more than a single instance of either class breaks it.
There are other more subtle violations of modularity, like calling global hit inside of snake.hit_check. This function should return true or false if a hit occurred and let the calling code invoke hit how, when and if they please rather than creating a dependency between the class and exterior code. pygame could be removed or at least injected into the object so the same snake logic could hook to any visual interface.
High cyclomatic complexity
The main while loop that runs the game has very high cyclomatic complexity with over 18 branches and 3 layers of nesting. These giant blocks of conditionals and loops make the code very hard to understand (and by extension, maintain and debug) and should be broken out into functions or otherwise refactored.
Abusing literals
The code abuses hard-coded literal values throughout. If you want to change the size of the grid, for example, you'd need to walk the whole file hunting for all the 10s that happen to be related to the grid size to make them a different number. This is tedious and error-prone even in a tiny program.
Same applies to window size and a few other things. Storing these values as variables in one place and referencing them means everything just works when you need to change a value, helping to eliminate typo bugs and ease refactoring. If classes or functions need to know the window size, this information should be injected in a parameter to the initializer or appropriate method.
d (really direction) has 4 possible values: 1, 2, 3 and 4. The problem is that "1" has no semantic meaning here. It's not obvious whether a "1" entails up, down, left or sideways. The classical way to handle this is an enumeration, but even direction = "up" would increase the expressiveness of the code and reduce bugs (did you type in 2 when you meant 1 somewhere?).
Magical boolean flags
Variables like
s = False
g = False

are unclear. Pick descriptive names and avoid boolean flags in favor of functions that can return true/false to handle control flow. The reason functions are cleaner than flags is because they result in less state for the caller to keep track of and support modularity. Less state means the code is easier to understand. Modularity means it's easier to isolate problems if they occur and handle refactors locally without causing a domino effect throughout the code base.
Complex logic
Much of the logic can be simplified considerably. To pick one example, code that checks whether the head segment is colliding with the tail,
test_l = [[]]
for i in range(0, len(SNAKE_COMP)):
    test_l.append(tuple(SNAKE_COMP[i][0:2]))
for i in range(0, len(test_l)):
    if test_l.count(test_l[i]) > 1:
        hit()

could be something like
if any(SNAKE_COMP[0][:2] == x[:2] for x in SNAKE_COMP[1:]):
    hit()

Even here, it's unusual that SNAKE_COMP needs 3 elements in its coordinates. The slice is a code smell because it's non-obvious. If the third element is direction, it's not necessary. Only the head needs an explicit direction.
Style and naming

Classes should be UpperCamelCase. You don't need the () after the class name unless you're inheriting. Making the class Snake as it should be means you can call the instance snake instead of the awkward intentional typo snek to avoid the alias.

Use ALL_CAPS variable names sparingly, if at all, and only to designate program constants.

Never use single-letter variables unless the purpose is overwhelmingly obvious from context.
f = [random.randint(0, 50)*10, random.randint(0, 50)*10]
d = 2

are not obvious. f is never used in the program which an editor with static analysis should warn you of and d should be called direction.

Alphabetize imports.

Use vertical whitespace more liberally, particularly around functions and blocks.

In addition to confusing single-letter boolean flags, names like SNAKE_COMP are unclear. What's COMP? Something like snake_coordinates, snake_body or snake_tail seems a bit clearer here. Even better in a class like snake.tail.

Follow PEP-8 and your style will sparkle.
UX
After a collision, the game freezes for 3 seconds and dies. As a player, I might feel like the game crashed or is buggy. A message or visual indication of the collision would communicate the snake's death better. Even just exiting instantly feels like a smoother experience.
Efficiency
This is totally premature, but it's worth keeping in mind that nearly all of your snake and apple operations that are O(n) like SNAKE_COMP.insert(0, FOOD_COORS) can be made O(1) using a deque and set. When you move the snake forward, you can rotate the deque. When you check for collision between the head and the body, you can use a set lookup.
Rewrite suggestion, round 1
This requires Python 3.8 because of the whisker assignments, but you can easily move those outside of the blocks.
I'm using __iter__ in both classes. Since I'm doing all of the drawing and pygame interaction in the main (the point is to keep UI and game logic separate), making the snake iterable is a nice way to get all of its body segments, but I cast to a tuple to avoid the caller mutating its position accidentally.
On the other hand, I trust that the caller will abide by the vector input for the turn function since we're all consenting adults. If you don't trust the client to behave, you can validate this coordinate pair and raise an error.
There's still lots of room for improvement: the main code is a bit bloated so this refactor is mostly an exercise in class organization and trying to keep everything loosely coupled. Docstrings are pretty cursory and could better explain the parameters and return values.
I don't really know Pygame so I may have gaffed--I find the key handlers pretty awkward, but I notice you can slice out the arrow keys and make a nice, indexable list of flags that hopefully doesn't break anything.
import pygame
from random import randrange

class Snake:
    def __init__(self, size, direction, body):
        self.size = size
        self.direction = direction
        self.body = list(map(tuple, body))

    def __iter__(self):
        return map(tuple, self.body)

    def in_bounds(self, width, height):
        """ Returns whether the snake's head is in the height/width bounds """
        x, y = self.body[0]
        return x >= 0 and y >= 0 and x < width and y < height

    def move(self):
        """ Moves the snake in the direction it's facing """
        self.body.insert(0, (self.body[0][0] + self.direction[0] * self.size,
                             self.body[0][1] + self.direction[1] * self.size))

    def remove_tail(self):
        """ Destroys the snake's last tail segment """
        del self.body[-1]

    def touching_point(self, point):
        """ Returns whether point is somewhere in the snake's body """
        return point in self.body

    def touching_tail(self):
        """ Returns whether the snake's head point is in the snake's body """
        return self.body[0] in self.body[1:]

    def set_direction(self, x, y):
        """ Sets the snake's direction given a cardinal unit-vector facing
            in a non-opposite direction from the snake's current direction
        """
        if (-x, -y) != self.direction:
            self.direction = x, y

class Food:
    def __init__(self, x=0, y=0):
        self.x, self.y = x, y

    def __iter__(self):
        yield self.x, self.y

    def reposition(self, size, width, height, used_squares):
        """ Repositions the apple on the size grid within the bounds avoiding
            certain used squares. Infinitely loops if no squares are available.
        """
        while point := (randrange(0, width, size), randrange(0, height, size)):
            if point not in used_squares:
                self.x, self.y = point
                break

if __name__ == "__main__":
    class Color:
        white = 255, 255, 255
        red = 255, 0, 0
        black = 0, 0, 0

    width = height = 500
    game_speed = 15
    cell_size = 10
    directions = (0, -1), (0, 1), (1, 0), (-1, 0)
    initial_body = (50, 50), (40, 50), (30, 50), (20, 50), (10, 50)
    initial_direction = (1, 0)
    pyg_arrow_key_loc = slice(273, 277)
    pygame.init()
    pygame.display.set_caption("snake")
    pyg_window = pygame.display.set_mode((width, height))
    pyg_clock = pygame.time.Clock()
    snake = Snake(cell_size, initial_direction, initial_body)
    apple = Food()
    apple.reposition(cell_size, width, height, snake)

    while not any(event.type == pygame.QUIT for event in pygame.event.get()):
        if any(arrows := pygame.key.get_pressed()[pyg_arrow_key_loc]):
            snake.set_direction(*directions[arrows.index(1)])

        snake.move()

        if snake.touching_point(*apple):
            apple.reposition(cell_size, width, height, snake)
        else:
            snake.remove_tail()

        if snake.touching_tail() or not snake.in_bounds(width, height):
            pygame.quit()

        pygame.draw.rect(pyg_window, Color.black, (0, 0, width, height))
        apple_rect = (apple.x, apple.y, cell_size, cell_size)
        pygame.draw.rect(pyg_window, Color.red, apple_rect)

        for x, y in snake:
            pygame.draw.rect(pyg_window, Color.white, (x, y, cell_size, cell_size))

        pyg_clock.tick(game_speed)
        pygame.display.update()

Rewrite suggestion, round 2
I wasn't entirely happy with main in the above rewrite so I gave a shot at cleaning it up a bit. It's still not perfect and adds code but it'd be a likely next step if you wanted to scale up the app. Breaking render into entity-specific functions is a potential next step as the app grows.
Notice that the Snake and Food classes don't need to be touched thanks to the earlier refactor and we can treat them as black boxes. After this refactor, the main function can treat SnakeGame as a black box as well and just specify its configuration. You can see how the abstractions build up: we can tuck these classes into another file like snake.py and use it as a library.
import pygame
from snake import Food, Snake

class SnakeGame:
    class Color:
        white = 255, 255, 255
        red = 255, 0, 0
        black = 0, 0, 0

    def __init__(self, width, height, cell_size,
                 initial_body, initial_direction, game_speed):
        pygame.init()
        pygame.display.set_caption("snake")
        self.pyg_window = pygame.display.set_mode((width, height))
        self.pyg_clock = pygame.time.Clock()
        self.snake = Snake(cell_size, initial_direction, initial_body)
        self.apple = Food()
        self.cell_size = cell_size
        self.width = width
        self.height = height
        self.game_speed = game_speed
        self.apple.reposition(cell_size, width, height, self.snake)

    def run(self):
        pyg_arrow_key_loc = slice(273, 277)
        directions = (0, -1), (0, 1), (1, 0), (-1, 0)

        while not any(event.type == pygame.QUIT for event in pygame.event.get()):
            if any(arrows := pygame.key.get_pressed()[pyg_arrow_key_loc]):
                self.snake.set_direction(*directions[arrows.index(1)])

            self.snake.move()

            if self.snake.touching_point(*self.apple):
                self.apple.reposition(self.cell_size, self.width,
                                      self.height, self.snake)
            else:
                self.snake.remove_tail()

            if (self.snake.touching_tail() or
                not self.snake.in_bounds(self.width, self.height)):
                pygame.quit()

            self.render()

    def render(self):
        pygame.draw.rect(self.pyg_window, SnakeGame.Color.black,
                              (0, 0, self.width, self.height))
        apple_rect = (self.apple.x, self.apple.y, self.cell_size, self.cell_size)
        pygame.draw.rect(self.pyg_window, SnakeGame.Color.red, apple_rect)

        for x, y in self.snake:
            pygame.draw.rect(self.pyg_window, SnakeGame.Color.white,
                                  (x, y, self.cell_size, self.cell_size))

        self.pyg_clock.tick(self.game_speed)
        pygame.display.update()

if __name__ == "__main__":
    SnakeGame(width=500,
              height=500,
              cell_size=10,
              initial_body=((50, 50), (40, 50), (30, 50), (20, 50), (10, 50)),
              initial_direction=(1, 0),
              game_speed=15).run()

Suggested exercises

Add a score.
Improve graphics/UI/messaging/text.
Try making multiple apples.
Make the snake periodically "poop", creating an obstacle that it cannot touch but fades away over time.
Add walls.
Add levels.
Try adding a second snake that uses the wasd keys on the same keyboard.
Use Flask SocketIO to make a real time network game.
Try writing a snake AI.


JavaScript syntax: bucketing based on days (today, yesterday and past)

Doing it without an additional library you could try a custom function that does the same thing
function isSame(a,offset) {
    const b = new Date();
    b.setDate(b.getDate() - offset);
    return a === b
}

const [todayBucket, yesterdayBucket] = [0, 1].map(offset =>
  recordings.filter(({ createdOn }) =>
    isSame(createdOn,offset),
  ),
);
const pastBucket = recordings.filter(
  recording => ![...todayBucket, ...yesterdayBucket].includes(recording),
);


Your code is full of variables named somethingSet — but they aren't actually sets! Why not?

This solution, which takes advantage of Python's built-in set operations, is shorter.  Just being able to write have_nots = all_centers - haves is worth it.

from collections import defaultdict

num_centers = int(raw_input('Number of data centers: '))
print("Input data set information as: x y z")

all_centers = set(xrange(1, num_centers + 1))
centers_with_data = defaultdict(set)

# Grab dataset ID information from stdin
for center in range(1, num_centers + 1):
    for data_set in map(int, raw_input("Data set %s: " % (center)).split()):
        centers_with_data[data_set].add(center)

print "One possible solution:\n"

for data_set, haves in centers_with_data.iteritems():
    have_nots = all_centers - haves
    donor = next(iter(haves))   # Pick an arbitrary source
    for acceptor in have_nots:
        print "%d %d %d" % (data_set, donor, acceptor)


Mapping and sorting lists of Haskell tuples

Mapping over second

It is surprising that you know about &&&, but not second, also from Arrows:

mapOverSnd f = map (second f)

second is of type Arrow a => a b c -> a (d, b) (d, c), which boils down to (b->c) -> (d,b) -> (d,c) here.

Alternatively, you can take advantage that pairs are a Functor instance: `fmap (+1) ("...",10) = ("...",11)

mapOverSnd f = map (fmap f)

Definitions can be infix

You wrote (//) a b =, but definitions can be infix, too:

a // b = fromIntegral a / fromIntegral b

your2TupleOrdering

2-tuples are simply called pairs. sort needs a function like compare, so define yours in terms of compare. Take advantage of Ordering being an instance of Monoid:

myPairOrdering (a1,b1) (a2,b2) = compare a1 a2 `mappend` compare b2 b1

The Monoid instance of Ordering is:

mempty = EQ
EQ `mappend` y = y -- only if left side equals, use right
x  `mappend` _ = x -- shortcut otherwise

ngrams

Any solution to ngrams will be ugly because you don't want the very last elements which are below the minimum length. You are forcing an Eq constraint, which is not necessary. Avoid by comparing the length. Another solution is

ngrams' n = filter ((==n).length) . map (take n) . tails

The filter part here is ugly.

The let-chain

You can condense the let-chain with composition, cutting out freq3grams and my3grams. At some point in you haskell journey, you will do that. When you grow wiser, you will value readability over succinctness. Long story short: This part is OK.


Much too complicated. Use MAPCAR:

(defun group-pairwise (numbers)
  "Returns a list with the elements of NUMBERS grouped in pairs."
  (mapcar #'list numbers (rest numbers)))

Similar:

(defun generate-graph-of-digits (numbers graph)
  (mapc (lambda (a b)
          (add-edge-between-vertexes graph a b))
        numbers
        (rest numbers)))

Such primitive recursion can be replaced with mapping functions. Bonus: mapping functions are not limited by recursion stack.

Style

Also:

(append (list (list a b)) some-list)

is

(cons (list a b) some-list)

Then:

(cond (a (progn b c d))
      ((evenp n) (progn o p q))
      (t (progn e f g)))

is:

(cond (a b c d)
      ((evenp n) o p q)
      (t e f g))

Each cond clause accepts any number of Lisp forms after the condition.


Best structure for a Person in PHP classes (and databse)

First Question: Don't let potential use-cases of your application drive how you model the data. As you experienced, this causes a lot of headache later on.

Extracting the dob & dod for performance reasons is premature in this case. It is absolutely ok to load data even when not sure if it will be required. Every (un-optimized) application has a percentage of data it doesn't load. That's fine until you really experience performance issues. And then this probably is not the bottle neck you are going to optimize first. Loading those two extra values goes almost for free .

If you have larger data-structures (e.g. huge object tress by relations), you can use the lazy-loading pattern for this (which is what many ORM do to avoid joins). This keeps your model intact but avoids loading too much data. Lazy-loading scalars probably is more expensive then just loading them in the first place.

Excursus: What you tried to do is to model two different roles of the same entity. This is a valid approach some times. Yet this doesn't say the information is not loaded, it's just limiting the available interface. To be able to use its full power, generic functions are required though. An example might look like:

interface Person {
    // shared information
}

interface PersonName extends Person {
    // names
}

interface PersonDates extends Person {
    // dob & dob
}

public find<? extends Person>(int id) {
    return PersonImpl();
}

class PersonImpl implements PersonName, PersonDates {
}

repository.find<PersonName>(1);
repository.find<PersonDates>(1);

This is some very expensive pattern though, in terms of complexity and effort to create. You'll rarely use this. Especially as this doesn't make data loading faster. The entity is always loaded completely too.

Second Question: Well, you know my opinion here :). Separate your model from how it is stored. The repository (its mapper) should be the only one to know how to save the model to the database.

Database structure:

I prefer to to name tables in plural (as they represent collections). Other do as you. Some kind a personal, stick to one convention though.
Use InnoDb's foreign keys in your model. They help greatly to enforce data integrity.
Normalization would require to extract city, postcode and county from your address table into a separate one.


Test all properties with single test function

too vague & hiding test cases

[DataRow("Name", "A normal name", "A normal name", new string[] { "Name" })]
[DataRow("Name", null, null, new string[] { "Name" })]
[DataRow("Name", "", "", new string[] { "Name" })]
[DataRow("Name", "A normal name", "A normal name", new string[] { "Name" })]
[DataRow("Name", "A really very super duper long string to test the overall allowed length", "A really very super duper long string to test the overall allowed length", new string[] { "Name" })]

Tests should be testing very specific things. This test however isn't doing that. I looks like it's not simply testing the PropertyChanged event. If it was, then a single DataRow would be enough to tell whether the event fires or not.

It seems to also test some conditions that might prevent it from firering. Such tests should be done separately because here it's not clear what conditions you are testing.

too many hardcoded strings

Technically I find it's ok but to my taste there are too many hardcoded strings. I wouldn't say anything if it was just data but since they are property names I don't like them being strings.

You could use nameof to replace them with something more dynamic but then the test would not be very readable anymore.

extend Assert & use expressions

Instead it'd be a better idea to write an extension for the Assert.That property that you could use for testing the event in this way:

Assert.That.PropertyChanged(
    new Customer(),
    x => x.FirstName = "John",
    x => x.FirstName,
    x => x.FullName
);

where the signature of the method is:

public static void PropertyChanged<T>(
    this Assert assert,
    T obj,
    Action<T> setProperty,
    params Expression<Func<T>>[] changedProperties
)
{
    ...
}

now you can do the reflection magic here.

This is just an idea but you could of course have a couple of such extensions. One very gneric and another one that e.g. assumes that the property being set always fires an event for it.

confusing naming

foreach (var s in propChangedNames)

If you must give variables single letter names then let them at least be derived from the main name. Here p or pcn would be appropriate. s does not stand for anything. The only exception is x in lambda expressions which stands for current-item.

misses the point

  although it could even be generalized with a templated method for all classes

Then do this because otherwise you failed to reach the third goal which is:

  Don't write a ton of very repetitive test code


Visualize Parts of Song as Analyzed by Echonest

This code is really nice, and the output is very good looking! I do have a few nitpicky things that I want to cover.

Why are you storing the usage in a variable named usage? This should be in the file's main docstring. You don't need to print usage under if __name__ == "__main__":.
Is # encoding: utf=8 really needed? It doesn't seem like you're using any special unicode characters anywhere, so remove it.
You should have a docstring in visualize_analysis. Describe what the function does, and how it does that, preferably, in detail.

That's about all I see that should be improved! If there's anything else you want me to cover, mention it in the comments, and I'll see what I can do! Hope this helps!


Replace array element with multiplication of neighbors in Scala

The tricky part of this problem is how to handle the special cases for the start and end of the list, as well as how to handle short lists with fewer than three elements.

The fact that you need to consider up to three elements at a time means that you need a lot of base cases for recursion, though.  It's also undesirable to expose the special cases in the form of the carryOver and useCarryOver parameters.

A better approach would be to take advantage of the List.sliding function.  (Note that .sliding may produce a group with just two elements instead of three, if the input lst has length two.)

def multiplication(lst: List[Int]): List[Int] = lst match {
  case _::_::_ =>
    (lst.head :: lst ++ List(lst.last))
      .sliding(3)
      .map(group => group.head * group.last)
      .toList
  case _ => lst
}


Remove unwanted characters from specified column in all Worksheets

First of all, let me note that your code looks good already. There are only a few things I would change:

It might be a good idea to turn the (Public) Sub into a Private Sub parameterized by FIRST_ROW, TEST_COLUMN, and arrForbidden, which then is called by a new Public Sub passing in your special values. This would separate the configuration from the actual algorithm.
The name of the sub and its parameters could be improved by replacing them with something more expressive, like RemoveAllForbiddenCharacters instead of ReplaceAll, and removalColumn instead of TEST_COLUMN. (Well, the last one is not very good, but nothing better came to my mind immediately.)
I am personally not a fan of declaring multiple variables on one line or initializing on the same line because it often hurts readability. However, here it does not really hurt.

Now, I would like to present a number of different approaches to your problem. Some of these can even be combined for better results.

Using an Array to Query and Write Data

Instead of directly iterating over the cells in the collumn and updating every cell, you can read in the entire range into a two-dimensional (Variant) array using the Value property of the range, or even better the Value2 property, which is faster and usually safer. (See this blog post.)
Then, you can iterate over the array and finally paste it back by assigning to the Value property of the range.

This approach is faster then updating each cell because accessing the cells in a worksheet is rather slow.

Using Regular Expressions

Instead of looping over your array, you could use a regular expression. The VBA support for these is in the library 'Microsoft VBScript Regular Expressions 5.5'. An extensive description on how to use them can be found in the answer to this question on Stack Overflow.

Basically, what you would do is set up the regex matcher with a pattern string—in your case, "[\\/:%'*?<>|"".]". Next, you would use the Replace function of the regex object to replace all occurrences of the forbidden characters in one go.

I do not know whether this is really much faster than the simple loop in your case. That pretty much depends on how well optimized the regex Replace procedure is. But either way, it is a little more expressive and you could reuse the code to do all sorts of more elaborate substitutions.

Using User-Defined Functions

Instead of using a sub, you could write a function just for replacing all forbidden characters in a cell. Then, you could use this in some new column in the worksheets to automatically produce the cleaned-up version of your column in that new column. However, this would probably require you to actually reformat the worksheets before uploading to ALM (assuming ALM requires a fixed sheet layout for the import).

Personally, I do not really like this approach as it pollutes the worksheets with helper columns. However, if the need arises to remove the forbidden characters in more places, writing such a function might be the way to go.

Using Excel Functions

If you do not want to use VBA at all, you can modify the previous approach to use a suitable Excel workbook function. The base function for this approach is SUBSTITUTE, which replaces occurrences of one string in another by a specified value.

A simple approach would be to nest calls to SUBSTITUTE, one for each character to replace. However, this very easily becomes completely unreadable. Moreover, there is an upper limit on how long a formula is allowed to be. (OK, this Microsoft page says the limit is now over 8000 characters, so this should not really be a problem.)

There might be a nicer way to reduce the nested formulas into one array formula, but I personally don't know how to do it.


Arduino Code for Juggling Machine (Stepper Motors)

Inside loop, you're checking if some code should be run before startup. You could simply move the corresponding code to setup, and be sure it's only run once:
#include <AccelStepper.h>
AccelStepper stepper1(AccelStepper::DRIVER, 9, 8);
AccelStepper stepper2(AccelStepper::DRIVER, 4, 3);

int side = 0;
int max_speed = 6000;
int max_acceleration = 12000;
int stepover = 300;
int step_distance = 800;

void setup() {
  stepper1.setMaxSpeed(max_speed);
  stepper2.setMaxSpeed(max_speed);
  stepper1.setAcceleration(1234);
  stepper2.setAcceleration(1234);
  stepper1.moveTo(600);
  stepper2.moveTo(-200);

  while (abs(stepper1.distanceToGo()) > 0) {
    stepper1.run();
  }
  while (abs(stepper2.distanceToGo()) > 0) {
    stepper2.run();
  }
  stepper1.setAcceleration(max_acceleration);
  stepper2.setAcceleration(max_acceleration);
  delay(500);
}

void loop() {
  // This code moves the left arm
  if (abs(stepper1.distanceToGo()) == 0 and abs(stepper2.distanceToGo()) < stepover and side == 0) {
    stepper1.moveTo(step_distance + stepper1.currentPosition());
    side = 1;
  }

  // This code moves the right arm
  if (abs(stepper2.distanceToGo()) == 0 and abs(stepper1.distanceToGo()) < stepover and side == 1) {
    stepper2.setCurrentPosition(0);
    stepper2.moveTo(step_distance);
    side = 0;
  }

  stepper2.run();
  stepper1.run();
}

abs cannot be negative, so it might be clearer to replace abs(...) != 0 by abs(...) > 0
AccelStepper::move(long relative) is defined as moveTo(_currentPos + relative); so you can probably replace your moveTo by move.


The input validation

is_valid_permutation() does not verify if the elements in the two lists
are unique. As an example

is_valid_permutation([[1, 1, 1, 2], [2, 2, 2, 1]])

returns True (and

from_permutation_to_disjoints_cycles([[1, 1, 1, 2], [2, 2, 2, 1]])

aborts later with a ValueError because some index is not found).
This can for example be fixed by checking

len(in_perm[0]) == len(in_perm[1]) == len(set(in_perm[0]))

instead of

len(in_perm[0]) == len(in_perm[1])

Restricting the input to lists of integers seems unnecessary to me,
the conversion from the Cauchy notation to cycles works perfectly with arbitrary values (as long as they are hashable):

>>> print(from_permutation_to_disjoints_cycles([["a", "b", "c", "d"], ["b", "a", "d", "c"]]))
[['a', 'b'], ['c', 'd']]

For invalid input, ValueError seems more
appropriate to me, IOError is meant for I/O related failures, such
as reading or writing data.

From Cauchy notation to cycles

decouple_permutation() can be simplified to

def decouple_permutation(perm):
    """
    from [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    to   [[1,3], [2,4], [3,5], [4,2], [5,1]]
    """
    return [list(a) for a in zip(perm[0], perm[1]) if a[0] != a[1]]

the check for perm[0] != perm[1] is not necessary.

However, I would suggest to use a dictionary instead of a list of lists
to store the mappings. Dictionary lookup is much faster than a (linear)
search in a list (what index() does). This leads to the following
implementation:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) if a != b }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles

For each initial value which has not been handled, we build a complete
cycle by dictionary lookups. pop() retrieves the next element of a
cycle and removes the pair from the dictionary, so that it will not be
handled again. Apart from appending to the cycles, no list modifications
are done.

(Remark: My initial suggestion did not work correctly. This new version
does essentially what the “pseudo code” in Acccumulation's answer
describes. The implementation however is different.)

In my test this was significantly faster for large permutations (benchmark
below).

Finally, your code does not return cycles with a single element:

>>> from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3]]

As a consequence, the reverse conversion gives not the original permutation:

>>> from_disjoint_cycles_to_permutation([[1, 2, 3]])
[[1, 2, 3], [2, 3, 1]]

With the dictionary approach, this can be fixed by removing the if a != b condition:

def from_permutation_to_disjoints_cycles(perm):
    mappings = { a: b for a, b in zip(*perm) }
    cycles = []
    for a in perm[0]:
        b = mappings.pop(a, None)
        if b is None:
            continue # `a` has already been handled
        cycle = [a]
        while a != b:
            cycle.append(b)
            b = mappings.pop(b)
        cycles.append(cycle)
    return cycles

Now

>>> from_permutation_to_disjoints_cycles([[1, 2, 3, 4], [2, 3, 1, 4]])
[[1, 2, 3], [4]]

>>> from_disjoint_cycles_to_permutation([[1, 2, 3], [4]])
[[1, 2, 3, 4], [2, 3, 1, 4]]

Benchmark

A primitive benchmark, for the permutation which reverses the first 1000
integers (without the input validation):

import time

perm = [[x for x in range(1, 1001)], [x for x in reversed(range(1, 1001))]]

start = time.time()
c = from_permutation_to_disjoints_cycles(perm)
end = time.time()
print((end - start) * 1000)

Result (on a 1,2 GHz MacBook):

Your code: 20 milliseconds,
My code: 0.8 milliseconds.

From cycles to Cauchy notation

The conversion from the Cauchy notation to cycles works with arbitrary
(distinct) integers (or even arbitrary values), but the reverse
conversion assumes that the values are consecutive integers starting
at 1:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[1, 2, 3, 4, 5, 6], [0, 3, 2, 0, 6, 5]

An alternative approach would be to zip() each cycle with a rotation
of itself, to get the list of mapping pairs:

def from_disjoint_cycles_to_permutation(dc):
    """
    from [[1, 3, 5], [2, 4]]
    to   [[1, 2, 3, 4, 5], [3, 4, 5, 2, 1]]
    """
    pairs = [(a, b) for cycle in dc for a, b in zip(cycle, cycle[1:] + cycle[:1])]
    return [list(i) for i in zip(*pairs)]

(The transposition method is taken from Transpose list of lists on Stack Overflow.)

Now the reverse conversion works as expected:

>>> from_permutation_to_disjoints_cycles([[2, 3, 5, 6], [3, 2, 6, 5]])
[[2, 3], [5, 6]]

>>> from_disjoint_cycles_to_permutation([[2, 3], [5, 6]]))
[[2, 3, 5, 6], [3, 2, 6, 5]]

and the function is not limited to integers anymore.

Using Sympy

The Permutation
class from Sympy provides functions to convert between the
different representations.

Example (the permutations elements are zero-based integers):

>>> from sympy.combinatorics import Permutation

>>> p1 = Permutation([2, 0, 1, 5, 4, 3])
>>> p1.cyclic_form
[[0, 2, 1], [3, 5]]
>>> p1.full_cyclic_form
[[0, 2, 1], [3, 5], [4]]

>>> p2 = Permutation([[0, 2, 1], [3, 5]])
>>> p2.array_form
[2, 0, 1, 5, 4, 3]


Express.js routes management for large web application

absolutely, you should compose your express application in terms of a hierarchy of routers

instancing all those routers should be negligible in terms of your application's performance
this is the only approach i can imagine feasibly maintaining at scale, it buys you some separation of concerns


Your code looks very good and the type annotation is a really nice touch
Also, your code is well organised and easy to understand. Some documentation could be a good idea (but it's better to have no doc rather than bad doc). Also, you could consider writing unit tests.

Let's try to see what could be improved/made more Pythonic.

Loop like a native

I highly recommand Ned Batchelder's excellent talk "loop like a native". One of the idea is that whenever you are using for i in range(len(iterable)), you are probably doing it wrong. In your case, you could use for i, char in enumerate(word):.

End of word

The end-of-word detection could be done in a single statement: is_end_of_word = i == len(word) - 1. Also, you can get rid of the definition before the loop and even in the loops, sometimes, you could define it only behind the if char in current.children: because you use it only there.

Reorganise the logic

Sometimes, you check if something is empty and then if it contains a particular element. This can be factorised out:

Also, simplifying the code if (cond) return False else return True, you could rewrite contains:

def contains(self, word: str) -> bool:
    current = self.root
    for char in word:
        if char not in current.children:
            return False
        current = current.children[char]
    return current.is_word

Then in _retrieve_all_words, you can get rid of continue by using a simple else which makes things more explicit. Then, you can actually factorise out the common code at the end of the 2 branches and get the more simple:

        if child.is_word:
            words.append(word)
        if child.children:
            self._retrieve_all_words(child, word, words)
        word = word[:-1]

Finally, you can use += to simplify word = word + child.char into word += child.char.

At this stage, the code looks like:

from typing import Optional

class Trie:
    def __init__(self):
        self.root = Node(char=None, is_word=False)

    def add(self, word: str) -> None:
        current = self.root

        for i, char in enumerate(word):
            if char in current.children:
                current = current.children[char]
            else:
                is_end_of_word = i == len(word) - 1
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert

    def contains(self, word: str) -> bool:
        current = self.root
        for char in word:
            if char not in current.children:
                return False
            current = current.children[char]
        return current.is_word

    def remove(self, word: str) -> None:
        current = self.root
        for i, char in enumerate(word):
            if char not in current.children:
                return
            is_end_of_word = i == len(word) - 1
            if current.children[char].is_word and is_end_of_word:
                current.children[char].is_word = False
                return
            current = current.children[char]

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            word += child.char
            if child.is_word:
                words.append(word)
            if child.children:
                self._retrieve_all_words(child, word, words)
            word = word[:-1]
        return words

class Node:
    def __init__(self, char: Optional[str], is_word: bool):
        self.char = char
        self.is_word = is_word
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))

Storing things in a different format

Instead of maintaining a is_word attribute, maybe you could add store a sentinel like None to say that we have a full word here. This could be written like this:

from typing import Optional

class Trie:
    def __init__(self):
        self.root = Node(char=None)

    def add(self, word: str) -> None:
        current = self.root

        for char in list(word) + [None]:
            if char in current.children:
                current = current.children[char]
            else:
                node_to_insert = Node(char)
                current.add_child(node_to_insert)
                current = node_to_insert

    def contains(self, word: str) -> bool:
        current = self.root
        for char in list(word) + [None]:
            if char not in current.children:
                return False
            current = current.children[char]
        return True

    def remove(self, word: str) -> None:
        current = self.root
        for char in list(word) + [None]:
            if char not in current.children:
                return
            elif char is None:
                del current.children[char]
            else:
                current = current.children[char]

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            if child.char is None:
                words.append(word)
            else:
                word += child.char
                if child.children:
                    self._retrieve_all_words(child, word, words)
                word = word[:-1]
        return words

class Node:
    def __init__(self, char: Optional[str]):
        self.char = char
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))
t.remove("toto")
print(t.retrieve_all_words())
print(t.contains("toto"))

Back to word = word + child.char

Something I should have mentionned earlier but spotted on the late.

In _retrieve_all_words, you add a char to word only to remove it afterward. It is much clearer (and more efficient?) to just write word + char in the places where you actually need to word with the added character.

Then, the code becomes:

def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
    for child in current.children.values():
        if child.char is None:
            words.append(word)
        elif child.children:
            self._retrieve_all_words(child, word + child.char, words)
    return words


Use of dictionary for file-saving function

Yes, you could reduce duplication (and make it easier to add new exporters) if you used a dictionary to map extensions to functions. However, you couldn't do it quite as you suggest; you would store the result of the method call in the dictionary, not the method itself. Here is one suggestion, using os.path.splitext to get the extension defined in save_filename and functools.partial to supply the additional argument required for CSVs.

from functools import partial
import os

EXPORTERS = {'.xls': pd.DataFrame.to_excel,
             '.xlsx': pd.DataFrame.to_excel,
             '.csv': partial(pd.DataFrame.to_csv, index=False)}

def save_to_file(data, save_filename, columns_order=None):
    """ Saves data to file

    :param data: data to be saved
    :param save_filename: the filename
    :param columns_order: the order of columns
                          if needed to rearrange

    :return: True if done or None if error

    """
    try:
        df = pd.DataFrame(data)
        if columns_order is not None:  # Rearrange columns if needed
            df = df[columns_order]
        _, ext = os.path.splitext(save_filename)
        if ext in EXPORTERS:
            EXPORTERS[ext](df, save_filename)
            return True
        else:
            print "Not a supported filetype: {}".format(ext)
    except Exception, e:
        print "Save_to_file error:", e

Note the following:

I have stored the methods on the class in the dictionary, allowing it to be defined outside the function, so you need to pass the instance df as well as the first argument save_filename;
Rather than force the user to specify "" if the columns_order isn't required, I have given it a default None value; and
return None is implicit.

Including the list of supported filetypes in the docstring and output message is duplication of the information now stored in the dictionary's keys - if you add another supported type, you now need to change three parts of your code.

Finally, you should review your error handling. For one thing, except Exception as e: is more modern than except Exception, e: (which is retained on;ly for backwards compatibility, and doesn't work at all in 3.x). Secondly, you should use more specific error handling - what could go wrong, and how should it be dealt with? At the very least, I would differentiate between:

The conversion to DataFrame or column rearrangement not working; and
A failure in file operations.

Thirdly, rather than return either True or None, it would be conventional to raise an error from your function in the cases where you currently print a message - if the data hasn't been saved, the calling function should do something about it - and return None (again, implicitly) otherwise.


You could use the build-in Math.Round method:

public static int RoundTo(this int value, int roundTo)
{
    return (int)Math.Round((double)value / roundTo) * roundTo;
}

Using this approach you can round not only ints:

public static double RoundTo(this double value, double roundTo)
{
    return Math.Round(value / roundTo) * roundTo;
}

As for your approach, you don't need midPoint:

public static int RoundTo(this int value, int roundTo)
{
    var remainder = value % roundTo;
    var result = remainder < roundTo - remainder
        ? (value - remainder) //round down
        : (value + (roundTo - remainder)); //round up
    return result;
}


There are a number of things that could be improved here, and none of them have to do with the efficiency of the program.  The problems with this code are more fundamental.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't use #include <bits/stdc++.h>

This is poor programming practice.  Here's why.

Eliminate global variables where possible

The q variable is global but should really be in main or still better, see the next suggestion.

Create a C++ object

Whenever you have some data structure and associated actions (such as push and pop in this case), you should be thinking object.  In this case, it's quite simple to create an object from the code you have.  I'll leave that fun to you.

Use consistent formatting

The code as posted has inconsistent indentation which makes it hard to read and understand. Pick a style and apply it consistently.

Use more whitespace to enhance readability of the code

Instead of crowding things together like this:

 for(int i=0;i<q.size();i++) cout<<q[i]<<" ";

most people find it more easily readable if you use more space:

 for (int i=0; i < q.size(); i++) {
     std::cout << q[i] << " ";
 }

Use standard classes

Finally, there's the obvious: one could use std::queue.  I am assuming that you did not because you are still learning C++ and wanted to try to create a queue yourself.  That's fine as a programming exercise, but of course in real code, it's almost always better to use part of the standard library.


When given 7 letters, find all possible words with length 3 to 7

You are forming each possible combination, and look for it in the dictionary. That indeed takes forever. You'd be in a better shape doing it other way around. Read the dictionary word by word, and for each word check if it is composed by your letters. In pseudocode,

    for letter in word
        if letter not in letters
            return false
    return true


An malformed program (with misbalanced brackets) may cause an UB (e.g. popping back from an empty vector; or running out of program space in scanToEndOfLoops).
I recommend implementing step method:

void run() {
    while (progPointer < program.size()) {
        step();
    }
}

with an intention to reuse it in a debugger.


A service that returns paged Products with optional filtering

I would suggest you to move the pagination settings to your SearchModel

Then you can have an utility/extension method or whatever you whish with this signature

public IQueryable<Product> ApplyFilter(IQueryable<Product> productQuery, SearchModel model)

and you write there ll the filtering business, so you can re use it in more methods and simplify the readability of your main method.

Finally, I would not recommend to rewrite your if statements like this

if (search.CategoryId != 0)
{
    products = products.Where(p => p.CategoryId == search.CategoryId);
}


If you don't want to reinvent the wheel, you can implement a very short and simple solution using java.util:

public class Main {
    public static void main(final String[] args) throws IOException {
        final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        final BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        final String line = bufferedReader.readLine().trim();
        List<String> words = Arrays.asList(line.split("\\s+"));

        String reversedWords = reverseWords(words);

        bufferedWriter.write(reversedWords.toCharArray());

        bufferedReader.close();
        bufferedWriter.close();
    }

    private static String reverseWords(final List<String> words) {
        return words.stream().map(word -> reverseWord(word)).collect(Collectors.joining(" "));
    }

    private static String reverseWord(final String word) {
        return new StringBuilder(word).reverse().toString();
    }
}


A very simple change that replaces the while loop with a for loop (I don't know much about OpenCV, so I can't help too much there):

for count in range(1, 10):
    _, pho = webcam.read()
    gr = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
    images = face_cascade.detectMultiScale(gr, 1.3, 4)
    for (x,y,w,h) in faces:
            cv2.rectangle(pho,(x,y),(x+w,y+h),(0,255,0),2)
            fa = gray[y:y + h, x:x + w]
            e_size = cv2.resize(fa, (100, 100))
            cv2.imwrite('%s/%s.JPEG' % (folder,count), e_size)
    cv2.imshow('OpenCV', pho)
    key = cv2.waitKey(20)

Additionally, in Python 3 especially, the % string formatting syntax is out-of-favor/deprecated -- use the {} and .format syntax instead:

cv2.imwrite('%s/%s.JPEG' % (folder,count), e_size)

becomes

cv2.imwrite('{!s}/{!s}.JPEG'.format(folder, count), e_size)


Synesthesia for the rest of us (i.e. algorithm for unique string colorization)

Code Style

Where does the 32 come from? It seems strange to have AlphabetLength assigned as a constant, but 32 is an unexplained magic number. Especially if its value is actually based on the length of the alphabet, you should make it clear what the significance of that number is.
The method signature is pretty weird. Looking it up, apparently it's from some IValueConverter interface. You'd be better off extracting everything you have here into a private method which takes a string parameter and returns a SolidColorBrush. Then you can call that from Convert, doing any casting or validation you need there.
You have a mix of var and explicit type names. It'd be more consistent to declare your floats as var r = 0f, etc.
Your RGB values seem to be based entirely on the first, second and last characters of the string. That means there's really no reason to loop over it, you can just assign them directly
index is casted to a float everywhere it's used. It'd be cleaner to have it assigned as a float in the first place.

Algorithm

Currently, your names can be any colour at all. That's going to make displaying them hard, because you'll potentially have to modify the background colour to make sure the name reads clearly. You might be better off instead using HSV (Hue, Saturation, Value) colour space with a fixed V, then play with the H and S. It might also be good to use a restricted range of S so you don't end up with lots of washed-out, similar-looking colours
Using only the first, second and last characters in a name means you're going to have a lot of clashes, where different names show as the same colour. A different approach might be to do something like name.GetHashCode() to get an integer representing the string. You could then use that to generate the HSV (or RGB) components a few ways, like passing it as a seed to new Random (which will be consistent each time). Colour space is relatively limited, so you'll never get away from clashes altogether, but I think this will make them far less common.


Is this as inefficient and illogical as it seems?

Yes- as others have pointed out in comments, it seems to be somewhat poorly written. Not only is it difficult to read (as evidenced by your question here), but it isn't as efficient as it could be- each variable (e.g. $acct, $mos) is an array -and each sequential array grows in size! This is quite wasteful - see this playground example for an illustration.

If there are 26 fields per row, that means 376 elements* across 26 arrays. Storing each value as a string (or cast numbers to integer/float values) would dramatically decrease the amount of memory used. While the memory would likely be reclaimed between iterations, it would still make quite a difference.

  If it is indeed an odd way of doing things, what would have been the motivation to do it this way?

That would be difficult for us to answer without knowing the history of the team, code, etc. Perhaps the original implementor(s) didn't know any other technique for abstracting those values.

  My inclination would be to simply explode the string once for each row, and place each value in a variable, {and use list()}

That sounds like a better choice, though if there truly are 26+ values in each row, that line of code would get very lengthy. Perhaps a good choice would be to define a mapping of indexes like below, or just assert (/use error handling) to ensure the expected data exists in each line. Or, as Claudio mentioned in a comment str_getcsv() could also be utilized to simplify things here.

const FIELD_MAPPING = array(
    'acct',
    'mos',
    'f_name',
    'l_name',
    ...
);

It is unclear how the variables are used but presumably they are passed as parameters to a function/method call. If that is the case, then call_user_func_array() could be used, or if PHP 5.6+ is used, then call the function directly and pass the parameters using the spread/splat operator.

*Triangle series sum of 26 (351) + 26 - 1 (since each array except the last one has an extra element (the remaining fields separated by commas)


Check is_permutation on a pair of same sized arrays - follow-up

Genericity

Your algorithm currently only works for std::array and nothing else, which is a little bit sad: you could make it work for other sequence containers as well. You could improve this by making you algorithm take two pairs of iterators like the C++14 version of std::is_permutation:

template <typename ForwardIterator1, typename ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
                    ForwardIterator2 first2, ForwardIterator2 last2);

Note that I used forward iterators since the operations you use do not require anything more specialized to work.

You will have to make some compromises like using std::distance to check whether the sizes are the same, which eventually means that the size comparison will only be \$O(n)\$ for random-access iterators. In a future C++ world with concepts and a standardized std::size, you could have a signature like this:

bool is_permutation(const ForwardIterable& cont1,
                    const ForwardIterable& cont2);

Here, I used the ForwardIterable concept which represents types that have forward iterators. You could then use std::size to compute the size of the container; for std::list, you would have a size in \$O(1)\$ for example while it does not have random-access iterators.

However, we're still stuck in a world without concepts. We can emulate concept constraints but it gets pretty messy, so let's stuck to the iterator version for now even if it means that it won't be optimal.

Smaller concrete things

A few things easy to change that may make you smile:

If you intend to go the genericity way, then use std::begin and std::end instead of the begin and end functions since the former will work on more sequence containers.
These lines could be improved:

if(( myPair.first == first_map.end()) && (myPair.second == second_map.end()))
    return true;
else
    return false;

First, it's better to always use braces with if and other control structures to avoid small and silent errors in the future. But in this case, you can actually get rid of the condition altogether:

return myPair.first == first_map.end()
    && myPair.second == second_map.end();

Having to deal with std::pair whenever you want to use std::map and friends can be bothersome. Fortunately, there are ways to hide them. For example, you can change this line:

temp_unordered_map.insert(std::pair<T1,int>(x,1));

into this one:

temp_unordered_map.emplace(x, 1);

The function make_unordered_map does not tell much more than its return type. The name count_occurrences would probably be more suitable and provide more information.
If you plan to keep your function working only for std::array, then you can actually get rid of this runtime check:

if( N1  != N2)

You can replace it by a compile-time static_assert to warn users that they are doing something bad right from the start:

static_assert(N1 == N2, "is_permutation only accepts arrays of the same size");


Counting characters inside of a textarea using Angular

You don't need to declare an extra reference variable. I would suggest the first approach i.e. using [(ngModel)] for two-way data binding.

However, in the first approach, you must initialize the model value before using it in your template i.e. fruit.description should not be undefined otherwise you'll get the following TypeError:

  Cannot read property 'length' of undefined

Using the second approach, you wont get that error.


Git tag release build files and reset to commit without

It's a very nicely written script.

  It's working great, but is having a tag that refers to an overridden commit a good idea?

It doesn't sound great, but I don't have a better idea either.
In any case, I don't see any harm in doing this.
The content of these commits don't pollute the history because they are not really part of it.

If repository storage becomes a problem later,
you can always wipe out the obsolete tags.
(As you mentioned in a comment, this might not be such a good idea if package managers (like bower) rely on git tags for dependencies...)

Error handling

What if gulp fails? The script will happily go ahead and publish something broken or half-baked.
It would be good to add some error handling here, for example:

if ! gulp; then
    echo "Fatal: gulp failed, aborting..."
    exit 1
fi

Code duplication

This line appears twice:

newver=$(npm --no-git-tag-version version $1)

As it's a non-trivial command,
it would be good to put it in a function, for example:

set_newver() {
    newver=$(npm --no-git-tag-version version $1)
}

Naming

It's good to give command line parameters a proper name early on,
and refer to them by that name throughout the script,
instead of a meaningless $1. For example version.

This may be subjective, but I find newver a bit awkward,
and perhaps npm_version would be better. I leave that up to you.


Koch snowflake in Python with numpy and pygame

This is good code — I only have a couple of minor points.

Since nothing changes or animates, there's no need to have a top-level loop or a clock. You can just draw the snowflake and then wait for the user to quit (calling event.wait instead of event.get so that the program isn't busy doing nothing).
It's clearer to write pygame.Color('white') and pygame.Color('black') instead of [255, 255, 255] and [0, 0, 0].
Instead of:

# find the normal to this line
line_normal = numpy.array([
        line_end[1]-line_start[1],
        line_start[0]-line_end[0] ])

consider using the cross product:

line_normal = numpy.cross(line_end - line_start, [0, 0, 1])

There's repeated code in the computation of the triangle points that could be factored out into a function:

def interpolated(x, start, end):
    """Return vector interpolated between start and end by x."""
    return (1 - x) * start + x * end

and then:

triangle_left  = interpolated(1/3, line_start, line_end)
triangle_right = interpolated(2/3, line_start, line_end)


I could be wrong, but I haven't seen other designs of serialization than :

Serializer with reflection (customizable through attributes/converter/mapper).

This design is more complicated, in a sense that you have to plan ahead every the possible details of serialization. It is also harder to wire everything up, while leaving room for customization.

  it would simply consist of a large if-else/switch branch

This really shouldn't happen unless you plan to do this : switch(element.GetType().Name). You should use reflection to pull every member or property(pick one), and use Attribute to filter amd format them. The only switch you might need to have is opposibly for the premitive types : string, int, enum, etc.

  it would force me to expose private members as internal/protected/public

You don't have to, as you can obtain information on any member of a class, be protected or private.
Serializable by exposing a serialize method

This design is more straight-forward where each element serializes its own stuffs and delegates the rest to the respective element.

I'm going to assume the document is composed of hierarchical elements. If that is case, copying and merging the bytes array could get very costly, more as we get closer to the root element. Since you mentionned that you're working with a "very specific binary representation" and writing to a "stream", it would be best to write directly on the stream, rather than copying and merging the bytes, and holding them around.

public abstract class Element
{
    // Removed for verbosity ...

    protected abstract void Serialize(BinaryWriter writer);
}

public class ElementX : Element
{
    public string Result { get; set; }
    public Element Data { get; set; }

    protected override void Serialize(BinaryWriter writer)
    {
        const string NewLine = "\r\n";
        const string Opening = "begin-elem-x";
        const string Closing = "end-elem-x";

        writer.Write(Opening);
        writer.Write(NewLine);
        writer.Write(Data);
        writer.Write(NewLine);
        writer.Write(Closing);
        writer.Write(Result);
    }
}

internal static class SerializationExtensions
{
    public static void Write(this BinaryWriter writer, Element element)
    {
        element.Serialize(writer);
    }
}


Some minor changes I would recommend:

Replace the magic numbers with symbolic constants. It will be easier to
modify your program when these rates change.

constexpr long double ANNUAL_MORTGAGE_COST = 0.03;
constexpr long double LOAN_PRINCIPAL_PLUS = 0.06;
constexpr long double MARGINAL_TAX_RATE = 0.35;

Instead of doing the calculations inside main() I would suggest
putting it into a function.

long double totalPayment(long double housePrice, long double downPayment){

    long double loanBalance = housePrice - downPayment;
    long double interest = LOAN_PRINCIPAL_PLUS * loanBalance;
    long double annualMortgage = (ANNUAL_MORTGAGE_COST * loanBalance) + interest;
    long double savings = MARGINAL_TAX_RATE * interest;
    long double totalCost = annualMortgage - savings;

    return totalCost;
}


Functional testing issue - Feels like one long test

@depends does not define order

  [@depends] do not define the order in which the test methods are to be executed

Using @depends and not returning/passing arguments is an indicator that @depends isn't appropriate for what you're currently doing. You need to have a consistent application state before running each individual test method so that they do not depend on execution order. Otherwise tests easily become quite unwieldy and ultimately of little value.

If you want to do that via @depends, you need to return  from a test method and the following method should expect it as the first argument (and literally depend on whatever it receives).

Reduce dependencies

In tests you should aim to reduce, not add dependencies, otherwise you can be in quite a fragile position. If for example your register function breaks, it wouldn't affect existing users, or therefore all other tests, at all - but using cascading tests as shown you would be unable to test/demonstrate that.

A broken register function would certainly be a problem - but is it a "100% of the site is broken" problem? It makes test results un-representative, and potentially harder to identify the root cause. If you have one failing test - it's very obvious where to focus your attention just from the test results. If all tests fail, it is not.

Of course anything more than of 0% fails warrants developer attention.

Achieve consistent application state

So, for example, each test should:

Establish a consistent application state (setUp functionality)
Use the concept of fixtures to e.g. populate the session, cookies, db - whatever is required
test what it needs to test
cleanup after itself (tearDown functionality)

In Context, I would say that means:

Create a test user to be able to test logging in without first being forced in the test case to "test" your register function:

public funtion testLogin() {
    // Insert a user directly into the users table - simulate anything else from testRegister
    ...
    $this->assertSame("UserName", $_SESSION['user']['name']);
}

You setup the session/cookie/whatever state for each subsequent test so that you don't need to "test" your login function to be able to test other authorized functions:

public funtion testFillForm1() {
    $this->_login();
    ...
}

public funtion testFillForm2() {
    $this->_login();
    ...
}

public funtion testFillForm3() {
    $this->_login();
    ...
}

protected function _login($user = array()) {
    if (!$user) {
        $user = array('name' => 'Default');
    }
    $_SESSION['user'] = $user;
}

If any of your setup steps are generic enough to apply to all tests, put them in the setUp function. E.g. loading 10 test users, with various permissions - put that in setUp and therefore testing login, registration-"that username already exists" would need no in-test setup at all.

I'm not exactly sure how that applies to using selenium, but hopefully this gives you enough of a hint to remove some of your inter-test dependencies.


ASP.NET account login system implemented via Masterpage and Panels

What you are doing right now is not fundamentally correct. This link http://learn.iis.net/page.aspx/170/developing-a-module-using-net/ explains developing a custom authentication module.

Also you should read about page life cycle while working asp webforms. http://msdn.microsoft.com/en-us/library/ms178472.aspx


This does it in two steps:

Add spaces before each uppercase, which allows the uppercases to be handled by...
The delimiter case.  This is the same regex you already wrote, although I am collapsing multiple delimters down to a single one.

Having two transformation passes, similar to using a unix pipeline, is easier to reason about that breaking it up into two cases with an "if else".

Note the cryptic (?!^) matches "not at the beginning of a line" only

function spinalCase(str) {
  return str.replace(/(?!^)([A-Z])/g, ' $1')
            .replace(/[_\s]+(?=[a-zA-Z])/g, '-').toLowerCase();
}

All of your test cases pass:

this-is-spinal-tap
this-is-spinal-tap
the-andy-griffith-show
teletubbies-say-eh-oh


Reading separate components of 8.3 filename into proper filename in C

Here are some things that may help you improve your code.

Avoid "tricky" loops

There is nothing technically wrong with this line:

for(c=0; c < 8 && filename[c] != '\0'; c++);

However, because one doesn't usually write a for loop with no body, it would probably be useful for your code to call attention to the fact that there's nothing happening within the loop.  You could write it like this:

for(c=0; c < 8 && filename[c] != '\0'; c++) {
    // do nothing
}

Or another way:

for(c=0; c < 8 && filename[c] != '\0'; c++)
    continue;

All will likely compile to the exact same object code.

Don't mix I/O with data operations

Generally speaking having a printf within a data manipulation function such as read_filename is not a good idea.  It makes it harder to reuse the function.  It's OK for diagnostics and for troubleshooting, but it would be better to omit it from the final version.  Similarly, it would be better if the fread would read the entire 8.3 filename into a memory buffer and then pass the memory buffer to code that would do the parsing.  That cleanly separates I/O from data manipulation and is probably more efficient as well.

Return an error code

The read_filename function can detect errors, but summarily exits the entire program rather than returning an error code that would allow the calling function to decide how to handle the error. A more robust design that might allow the code to be reused would return an error code.

Eliminate "magic numbers"

Things like if (argc != 2) are OK, because programmers reading this will know what that code is doing.  However, when you write if(8 != fread(&filename[0], 1, 8, arc)) it's not at all obvious whether 8 is the correct value, or exactly what it represents.  Better would be to use a named const value there such as const size_t FILENAMESIZE = 8;

Be careful with assumptions about argument size

In the fprintf functions, the parameter should be 0x%08lX rather than 0x%08X because ftell() returns a long.

Try this

Here's one way to do this, incorporating all of these suggestions:

// max size of 8.3 filename
const size_t FILENAMELEN = 11u;
const size_t EXTOFFSET = 8u;
const size_t EXTLEN = 3u;

char *read_filename(FILE *arc)
{
    char *filename = malloc(FILENAMELEN+2);
    if (filename == NULL) {
        return filename;
    }
    filename[FILENAMELEN] = '\0';
    if (FILENAMELEN != fread(filename, 1u, FILENAMELEN, arc)) {
        free(filename);
        return NULL;
    }
    return filename;
}

char *parse_filename(char *filename)
{
    if (filename == NULL) {
        return filename;
    }
    // insert the '.'
    memmove(&filename[EXTOFFSET+1], &filename[EXTOFFSET], EXTLEN);
    filename[EXTOFFSET] = '.';
    size_t i;
    for (i=0; filename[i] && i < EXTOFFSET; ++i) {
    }
    if (i < EXTOFFSET) {
        memmove(&filename[i], &filename[EXTOFFSET], EXTLEN+2);
    }
    return filename;
}


Controller with too many parameters with DI

Create a class that will expose the services as properties. That class should also have DI set up. Register that class with interface in the container. Inject the class into your own controller.