Codility training: Find the maximal number of clocks with hands that look identical when rotated

Question

Here's the link to the problem:

https://codility.com/demo/take-sample-test/clocks

The problem is that I can't get 100 points (only 42) out of it. Running time is OK, but for some test cases the code gives wrong answers, but I can't figure out what's the problem. Can someone please help me out?

Here's my code:

function rotate(arr) {
    var min = arr.reduce(function(a,b) { return a > b ? b : a });
    while (arr[0] != min) {
        var first = arr.shift();
        arr.push(first);
    }
}

function solution(A, P) {
    var positions = [];
    A.forEach(function(clock) {
        var position = [];
        clock.sort(function(a, b) { return a - b });
        clock.push(clock[0] + P);

        // calculating the distances between clock hands
        clock.forEach(function(hand, idx) {
            if (idx == 0) return;            
            position.push(clock[idx] - clock[idx - 1]);
        });

        // rotating the distances array to start with the minimum element
        rotate(position);
        positions.push(position);
    });

    //lexicographically sort positions array to similar types be consecutive
    positions.sort();

    var sum = 0;   
    // create a string to compare types with each other
    var type = positions[0].join(",");
    var n = 0;

    // counting consecutive positions with same type    
    positions.forEach(function(position, idx) {
        if (type == position.join(",")) {
            n++;
        } else {
            type = position.join(",");
            sum += (n * (n-1)) / 2;
            n = 1;
        }
    });
    sum += (n * (n-1)) / 2;

    return sum;
}

jsFiddle

Answer 1

My answer is similar to TonyWilk's but, like the OP did, I rotate all clocks to find a canonical position that can be compared with others.

The canonical position is the one where the sum of all hand positions is minimal (i.e. all hands are as close as possible to 1).

I spent quite a bit of time trying to find a numeric function that would allow to generate a unique signature based on the hand position values alone.

While this is mathematically possible (using an increasing function defining a dense set for integers), the computation time and/or floating point precision always got in the way.

I reverted to a basic array sort and join to generate a unique clock signature.
That brought me to 95%, with one timeout (see the results).

I then spent another bit of time optimizing the last timeout away until I noticed something strange:
this result scored only 85% with 2 timeouts, but if you look at the timings it's actullay faster than what was recorded on my previous 95% score.

I suspect the timings are either a bit wobbly on this one, or maybe they are adjusted somehow based on the expected order of the algorithm.
Strictly speaking, mine is in o(N*M²) because of the signature computation, even though you would need clocks with many thousands of hands to notice it.
With a number of hands that can fit into memory, the array sorting is dominant and the practical order is o(N*M*log₂(M))

Here is the last version, with an attempt at optimizing the pairs counting that makes the code less readable:

function solution (Clocks, Positions)
{   
    // get dimensions
    var num_clocks = Clocks.length;
    var num_hands = Clocks[0].length;

    // collect canonical signatures
    var signatures = [];
    var pairs = 0;

    for (var c = 0 ; c != num_clocks ; c++)
    {
        var s_min = 1e100, o_min;
        var clock = Clocks[c];
        for (var i = 0 ; i != num_hands ; i++)
        {
            // signature of positions with current hand rotated to 0
            var offset = Positions - clock[i];
            var signature = 0;
            for (var j = 0 ; j != num_hands ; j++)
            {
                signature += (clock[j] + offset) % Positions;
            }

            // retain position with minimal signature
            if (signature < s_min)
            {
                s_min = signature;
                o_min = offset;
            }
        }

        // generate clock canonical signature
        for (i = 0 ; i != num_hands ; i++)
        {
            clock[i] = (clock[i] + o_min) % Positions;
        }
        var sig = clock.sort().join();

        // count more pairs if the canonical form already exists
        pairs += signatures[sig] = 1 + (signatures[sig]||0);
    }

    return pairs - num_clocks; // "pairs" includes singleton pairs
}

Basically the same solution in plain C got me a 90% score :

#include <stdlib.h>

static int compare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }

static int compare_clocks_M;
static int compare_clocks (const void * pa, const void * pb)
{
    int i;
    const int * a = *(const int **)pa;
    const int * b = *(const int **)pb;
    for (i = 0 ; i != compare_clocks_M ; i++)
    {
        if (a[i] != b[i]) return a[i] - b[i];
    }
    return 0;
}

int solution(int **clocks, int num_clocks, int num_hands, int positions)
{
    int c;
    int pairs  = 0; // the result
    int repeat = 0; // clock signature repetition counter

    // put all clocks in canonical position
    for (c = 0 ; c != num_clocks ; c++)
    {
        int i;
        unsigned s_min = (unsigned)-1, o_min=-1;
        int * clock = clocks[c];
        for (i = 0 ; i != num_hands ; i++)
        {
            // signature of positions with current hand rotated to 0
            int j;
            unsigned offset = positions - clock[i];
            unsigned signature = 0;
            for (j = 0 ; j != num_hands ; j++)
            {
                signature += (clock[j] + offset) % positions;
            }

            // retain position with minimal signature
            if (signature < s_min)
            {
                s_min = signature;
                o_min = offset;
            }
        }

        // put clock in its canonical position
        for (i = 0 ; i != num_hands ; i++)
        {
            clock[i] = (clock[i] + o_min) % positions;
        }       
        qsort (clock, num_hands, sizeof(*clock), compare_ints);
    }

    // sort clocks
    compare_clocks_M = num_hands;
    qsort (clocks, num_clocks, sizeof(*clocks), compare_clocks);

    // count duplicates
    repeat = 0;
    for (c = 1 ; c != num_clocks ; c++)
    {
        if (!compare_clocks (&clocks[c-1], &clocks[c]))
        {
            pairs += ++repeat;
        }
        else repeat = 0;
    }

    return pairs;
}

I find the timing criterion a bit harsh, since this solution consumes zero extra memory (it uses the clocks themselves as a signature).
You could go faster by doing a sorted insertion manually on a dedicated signature array, but that would consume N*M temporary integers and bloat the code quite a bit.