Codiality training: find the maximum number of hours with hands that look the same when turning

Question

Here is a link to the problem:

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

The problem is that I can’t get 100 points (42 in total). The running time is fine, but for some test cases the code gives the wrong answers, but I can’t understand what the problem is. Can someone please help me?

Here is 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, but, like in OP, I rotate all the clocks to find a canonical position that can be compared with others.

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

I spent a lot of time trying to find a numerical function that would allow me to generate a unique signature based only on hand position values.

Although this is mathematically possible (using an increasing function defining a dense set for integers), computation time and / or floating point precision always interfere.

I went back to sorting the base array and joined in generating a unique clock signature.
This led me to 95%, with one timeout ( see results ).

Then I spent a little more time optimizing the last timeout until I noticed something strange:
this result scored just 85% with 2 timeouts, but if you look at the timings, it will act faster than what was recorded in my previous 95%.

I suspect that the timings are either a little shaky on this, or maybe they are somehow adjusted based on the expected order of the algorithm.
Strictly speaking, mine is in o (N * M ² ) due to the calculation of the signature, even if you need a watch with many thousands of hands to notice this. With a few hands that can fit into memory, the sorting of arrays is dominant, and the practical order is o (N * M * log ₂ (M))

Here is the latest version with an attempt to optimize pair counting, which 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 simple 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 synchronization criterion a bit severe, since this solution consumes zero additional memory (it uses the clock itself as a signature).
You can go faster by doing the sorted insert manually by the selected signature array, but this will consume temporary N * M integers and slightly inflate the code.

Answer 2

I think that the difficulty in the question revolves around the word “clock”, because of which I have been thinking about two hands for too long :)

The similarity between the “clocks” is similar to the fact that it can be defined by the sequence of separation of the “hands”; in the example question, the differences are 1,2,1,1,2. However, the main problem areas are pleasantly avoided in this very simple case ...

Packing: for example. in normal time, hours located at a distance of 4.6 and 11.1 are 2,

A few hands: for example. A 4-hour watch with 8 points can have hands at 1,2,5,6 and 1,4,5,8 giving a separation of 1,3,1 or 3,1,3, but they are rotationally identical!

When thinking of a watch with a large number of hands, you can imagine that sequences of hand breaks cannot simply be matched or sorted.

So, we measure all the spaces between the hands - the above four-hand example will be 1,3,1,3 and 3,1,3,1 (for this, I just add the first element at the end of the array), and then try to match this with previous patterns. We save unique templates along with an invoice for each of them.

Pattern comparison tries to compare arrays, then rotates the array one element and tries again (which eats a lot of time!)

In the end, we simply summarize the combinations for each account.

The current code gets a score of 90 points, only a failure for a couple of tests due to a timeout. I'm sure someone with a better understanding of Javascript could shave a few hundred milliseconds.

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

and here is the code:

 // compare 2 arrays - assumes they are the same length function compareArrays( a1, a2 ) { for( var i=0; i<a1.length; i++) if( a1[i] != a2[i] ){ return false; } return true; } // compare newpos[] with positions[][] // - rotates newpos[] to attempt match // returns: index of match or -1 if no match // function comparePositions(positions,newpos) { for(var ipos=0; ipos<positions.length; ipos++){ for( i=0; i<newpos.length; i++){ if( compareArrays(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= comparePositions(positions,position); if( idx < 0 ){ positions.push(position); // new pattern counts.push(1); }else{ counts[idx]++; // count old pattern } }); // sum the combinations 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; } 

Answer 3

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

I suggested that rotating the list of distances between the clocks until the head of the list becomes the minimum element translates the same hand positions into the same list, but this is not so.

If there are several minimal elements in the distance list, the rotation function can lead to different lists for the same hand positions.

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