Here's the link to the problem:

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 pare 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

Here's the link to the problem:

https://codility./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 pare 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

• javascript

• Which test cases? What's the expected output, and the wrong output? – Wooble Commented Feb 16, 2014 at 12:50
• I don't know, because codility doesn't provide the exact test cases. I cannot either create one that fails. – Zoltan.Tamasi Commented Feb 16, 2014 at 12:51
• Here's the codility output: codility./demo/results/demoXRF8PS-JWG – Zoltan.Tamasi Commented Feb 16, 2014 at 12:53
• I think the ones that aren't random give enough information to construct your own tests, if I'm reading the output correctly. – Wooble Commented Feb 16, 2014 at 12:58
• codereview.stackexchange. – Nilzor Commented Feb 16, 2014 at 13:55

3 Answers 3

My answer is similar to TonyWilk's but, like the OP did, I rotate all clocks to find a canonical position that can be pared 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 putation 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 putation, 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 pare_ints (const void * pa, const void * pb) { return *(int*)pa - *(int *)pb ; }

static int pare_clocks_M;
static int pare_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 != pare_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), pare_ints);
    }

    // sort clocks
    pare_clocks_M = num_hands;
    qsort (clocks, num_clocks, sizeof(*clocks), pare_clocks);

    // count duplicates
    repeat = 0;
    for (c = 1 ; c != num_clocks ; c++)
    {
        if (!pare_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.

I think the trickyness in the question revolves around the word 'clock' which kept me thinking about only 2 hands for far too long :)

The similarity between 'clocks' looks like it can be given by the sequence of separation of the 'hands'; in the question's example the differences are 1,2,1,1,2. However, the main problem areas are nicely avoided by this very simple case...

Wrapping: e.g. on a normal time clock hands being at 4,6 and 11,1 are both a distance of 2;

Multiple hands: e.g. a 4-hand clock with 8 points may have hands at 1,2,5,6 and 1,4,5,8 giving separations of 1,3,1 or 3,1,3 but these are rotationally identical!

Thinking of clocks with large numbers of hands, you can imagine that sequences of separations between hands cannot be simply matched or sorted.

So, we measure all the spaces between hands - the above 4-hand example would be 1,3,1,3 and 3,1,3,1 (to do this I simply add the first element on the end of the array) and then try to match that against previous patterns. We only keep unique patterns along with a count for each of them.

The pattern matching tries to pare the arrays, then rotates the array one element and tries again (which eats a lot of time!)

At the end we just sum up the binations for each count.

The current code gets a score of 90, only failing on a couple of tests due to timeout. I'm sure someone with a better grasp of Javascript could shave a few 100 millisecs off that.

Here's the output: https://codility./demo/results/demo9GZ7VW-V63/

and here's the code:

// pare 2 arrays - assumes they are the same length
function pareArrays( a1, a2 )
{
    for( var i=0; i<a1.length; i++)
        if( a1[i] != a2[i] ){
            return false;
        }
    return true;
}

// pare newpos[] with positions[][]
// - rotates newpos[] to attempt match 
// returns: index of match or -1 if no match
//
function parePositions(positions,newpos)
{
    for(var ipos=0; ipos<positions.length; ipos++){
        for( i=0; i<newpos.length; i++){
            if( pareArrays(positions[ipos],newpos))
                return ipos;
            newpos.push(newpos.shift());    //rotate array
        }
    }
    return -1;
}

function solution(A, P) {
    var idx,diff,halfP=P/2;
    var highestCount=0;
    var highestIndex=0;
    var positions = [];
    var counts=[];
    A.forEach(function(clock) {
        var position = [];
        // sort 'hands' in ascending order
        clock.sort(function(a, b) { return a - b });
        // duplicate start point on end
        clock.push(clock[0]);

        // create array of distances between hands, wrapping around clock
        for(idx=1; idx<clock.length;idx++){
            diff= Math.abs(clock[idx] - clock[idx-1]);
            position.push((diff>halfP)?P-diff:diff);
        }

        idx= parePositions(positions,position);
        if( idx < 0 ){
            positions.push(position);   // new pattern
            counts.push(1);
        }else{
            counts[idx]++;  // count old pattern
        }
    });

    // sum the binations of counts for each position type
    var sum=0;
    for(idx=0; idx<counts.length; idx++){
        count=counts[idx];
        sum+= (count > 2) ? (count * (count-1))/2 : count-1;
    }

    return sum;
}

I've found out what the problem is. It is in the rotate function.

I assumed that by rotating the list of distances between the clockhands until the list head is the minimum element transfroms identical hand-positions into the same list but it is not the case.

If there are multiple minimum elements in a hand-distance list, the rotate function can result in different lists for identical hand positions.

For example : [4, 1, 3, 2, 1] and [2, 1, 4, 1, 3] are identical, because they can be rotated into each other but rotate results in [1, 3, 2, 1, 4] for the first, and [1, 4, 1, 3, 2] for the second.