Codility 교육 :

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

내가 너무 오래 만이 손에 대해 생각 :)

날을 유지하는 질문에 trickyness 단어 '시계'를 중심으로 돌아 가지 생각 : 여기

내 코드입니다

'시계'사이의 유사성은 '손'을 분리하는 순서로 나타낼 수있는 것처럼 보입니다. 질문의 예에서 차이점은 1,2,1,1,2입니다. 그러나 주요 문제 영역은이 매우 단순한 경우 피하는 것이 좋습니다. ...

감싸기 : 예 : 정상적인 시간에 4,6,11에있는 시계 바늘은 모두 2의 거리이다;

여러 손 : 예 : 8 포인트를 가진 4 핸드 시계는 1,2,5,6 및 1,4,5,8 에 손을 가지고 1,3,1 또는 3,1,3의 간격을 둘 수 있지만 회전이 동일합니다!

손이 많은 시계를 생각하면 손 사이의 일련의 분리를 단순히 일치 시키거나 정렬 할 수 없다고 상상할 수 있습니다.

우리는 손 사이의 모든 공간을 측정합니다. 위의 4 개 손잡이 예는 1,3,1,3 및 3,1,3,1이 될 것입니다. 이렇게하려면 끝 부분에 첫 번째 요소를 추가하기 만하면됩니다 그 배열을 이전 패턴과 비교해보십시오. 우리는 고유 한 패턴과 각 패턴의 수를 유지합니다.

패턴 매칭은 다시 배열 한 요소를 회전하고 시도, 배열을 비교하는 시도 (많은 시간을 먹고있는!)

을 우리가 각 카운트 조합을 요약 끝에서.

현재 코드의 점수는 90이며, 시간 초과로 인해 몇 가지 테스트에서 실패합니다. Javascript를 더 잘 이해하면 누군가 100 밀리 초를 줄일 수있을 것이라고 확신합니다.

다음은 출력입니다 : https://codility.com/demo/results/demo9GZ7VW-V63/

여기에 코드입니다 : 나는 문제가 무엇인지 발견했습니다

// 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 2

. rotate 함수에 있습니다.

나는 목록 헤드가 동일한 손 위치에서 동일한 목록으로 이동하는 최소 요소가 될 때까지 클럭 간 거리 사이의 목록을 회전 시키지만 그럴 수 없다고 가정했다.

손 - 거리 목록에 여러 개의 최소 요소가있는 경우 회전 기능은 동일한 손 위치에 대해 다른 목록을 만들 수 있습니다.

예 : [4,1,3,2,1] 및 [2,1,4,1,3]은 서로 회전 할 수 있기 때문에 동일하지만 rotate의 결과는 [1, 3, 2, 1, 4] 및 두 번째에 대한 [1,4,1,3,2]로 구성됩니다.

Answer 3

내 대답은 TonyWilk 's와 비슷하지만 OP와 마찬가지로 모든 시계를 회전하여 다른 시계와 비교할 수있는 표준 위치를 찾습니다.

정규 위치는 모든 손 위치의 합이 최소 인 위치입니다 (즉, 모든 손이 가능한 한 1에 가깝습니다).

저는 손 위치 값만을 기준으로 고유 한 서명을 생성 할 수있는 수치 함수를 찾으려고 꽤 많은 시간을 보냈습니다.

이것은 수학적으로 가능하지만 (정수에 대한 밀도 집합을 정의하는 증가 함수를 사용) 계산 시간 및/또는 부동 소수점 정밀도가 항상 방해가됩니다.

기본 배열 정렬 및 조인으로 되돌아가 고유 한 시계 서명을 생성했습니다.
이로 인해 나를 95 %까지 데려 왔고, 하나의 타임 아웃 (see the results)이있었습니다.

그때 내가 뭔가 이상한 눈치까지 떨어져 마지막 타임 아웃을 최적화하는 시간의 또 다른 비트를 보냈다 :
this result 2 시간 제한이 만 85 %을 기록,하지만 당신은 타이밍 보면 그것은 무엇보다 actullay 빠르다 내 이전 95 % 점수에 기록됩니다.

타이밍이 약간 흔들리는 것 같거나 알고리즘의 예상 순서에 따라 어떻게 든 조정됩니다.
엄밀히 말하면, 수천 개의 시계가있는 시계가 필요함에도 불구하고 서명 계산 때문에 내 것이 o (N * M)입니다. 메모리에 적합 손 다수
는 배열 정렬 지배적이며 실제 순서는 O이다 (* 로그 N의 *의 M ₂ (M)) 여기서

는 시도로, 마지막 버전 덜 읽을 수있는 코드를 만드는 쌍 계산 최적화에 : 나는 TI를 찾을

#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; 
} 

:

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있어 이 솔루션은 추가 메모리를 사용하지 않으므로 (시계 자체를 서명으로 사용하기 때문에) 약간 가혹한 기준을 적용해야합니다.
전용 서명 배열에서 정렬 된 삽입을 수동으로 수행하면 더 빨리 처리 할 수 ​​있지만 N * M 임시 정수를 사용하고 코드를 상당히 부 풀리게됩니다.