javascript - Codility 训练 : Find the maximal number of clocks with hands that look identical when rotated

Question

这是问题的链接:

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

问题是我不能从中得到 100 分(只有 42 分)。运行时间还可以，但对于某些测试用例，代码给出了错误的答案，但我无法弄清楚问题出在哪里。有人可以帮帮我吗？

这是我的代码:

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

我的回答与 TonyWilk 的相似，但就像 OP 所做的那样，我旋转所有时钟以找到可以与其他时钟进行比较的规范位置。

规范位置是所有手牌位置总和最小的位置(即所有手牌都尽可能接近 1)。

我花了很多时间试图找到一个数字函数，它可以仅根据手的位置值生成唯一的签名。

虽然这在数学上是可能的(使用递增函数定义整数的密集集)，但计算时间和/或浮点精度总是阻碍。

我恢复到基本的数组排序并连接以生成唯一的时钟签名。
这使我达到了 95%，并且有一次超时 ( see the results )。

然后我又花了一点时间优化最后一个超时直到我注意到一些奇怪的事情:
this result有 2 次暂停，得分仅为 85%，但如果你看一下计时，它实际上更快比我之前 95% 得分的记录。

我怀疑这一次的计时有点不稳定，或者它们可能根据算法的预期顺序以某种方式进行了调整。
严格来说，由于签名计算，我的在 o(N*M²) 中，即使您需要有数千根指针的时钟才能注意到它。
手数能装进内存，数组排序占优，实际顺序为o(N*M*log₂(M))

这是最后一个版本，尝试优化对计数，从而降低代码的可读性:

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
}

在普通 C 中基本上相同的解决方案得到了我 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;
}

我发现计时标准有点苛刻，因为此解决方案消耗零额外内存(它使用时钟本身作为签名)。
您可以通过在专用签名数组上手动执行排序插入来加快速度，但这会消耗 N*M 个临时整数并使代码膨胀很多。