배열 늘리기 패스 2,2,4로

앞에서 나는 배열을 분쇄하는 과정을 정의했다

호감에서 우리는 배열을 왼쪽에서 오른쪽으로 읽습니다. 한 지점에서 같은 요소 중 두 개가 연속으로 나타나면 첫 번째 요소를 제거하고 두 번째 요소를 두 배로 늘립니다.

예를 들어 다음은 다음 배열을 분쇄하는 과정입니다

[5,2,2,4]
 ^
[5,2,2,4]
   ^
[5,2,2,4]
     ^
[5,4,4]
   ^
[5,4,4]
     ^
[5,8]
   ^

동일한 요소가 여러 번 축소 될 수 있습니다. 이 예에서는 단일 패스 2,2,4로 축소되었습니다 8.

이제 배열을 분쇄하는 것은 쉽지만 어려운 것은 배열을 분쇄하는 것입니다. 당신의 임무는 입력으로 양의 정수의 배열을 취하고 반복적으로 분쇄 될 때 입력을 형성 할 수있는 가장 큰 배열을 출력하는 것입니다. 예를 들어, 어레이 [4]는 분쇄에 의해 형성되고 ,이어서 분쇄에 [2,2]의해 형성된다 [1,1,1,1]. 정수가 아닌 값을 [1,1,1,1]가질 수 없으므로 더 이상 압축을 풀 수 없으므로 답이됩니다.

0이러한 배열은 무기한으로 확장 될 수 있으므로 입력 배열 에서을받지 않습니다 . 또한 동일한 홀수의 두 개가 나란히있는 케이스는 절대받지 않으며, 그러한 경우는 파쇄의 결과 일 수 없습니다.

이것은 이므로 소스의 크기를 바이트 단위로 측정하여 바이트 수가 적을수록 점수가 매겨집니다.

대답을 시작하기 전에이 도전이 생각보다 훨씬 어렵다고 말하고 싶습니다. 진행하면서 직감을 확인하고 답이 모든 테스트 사례를 통과하는지 확인하십시오.

테스트 사례

[] -> []
[5] -> [5]
[6] -> [3,3]
[8] -> [1,1,1,1,1,1,1,1]
[4,8] -> [1,1,1,1,1,1,1,1,1,1,2]
[2,8] -> [1, 1, 1, 1, 2, 1, 1, 1, 1]
[4,4] -> [1,1,1,1,1,1,1,1]


답변

자바 스크립트 (Node.js를) , 237 (221) 213 186 바이트

f=a=>a.map(b=>{for(i=1;~b%2;b/=2)i*=2;return Array(i).fill(b)}).reduce((t,c,i,s)=>{b=c.slice();if(i)r=2*s[--i].length,b.length>=r&&b[0]==s[i][0]?b[r-2]+=b.pop():b;return t.concat(b)},[])

온라인으로 사용해보십시오!

이 알고리즘은 각 숫자를 최대로 늘려서 최적의 확장 배열을 계산 한 다음 필요한 경우 올바른 위치에서 한 쌍의 숫자를 분쇄하여 효과적으로 “충돌 차단제”를 생성하여 이전 숫자의 분쇄 순서를 방해합니다.

예를 들어 :

[1, 1, 1, 1, 1, 1]제공 [4,2]분쇄 한 번,하지만 [1, 1, 1, 1, 2]결과[2, 4]

결과 배열을 분쇄하면 올바른 결과를 얻을 수 있도록 정확히 분쇄 블록을 배치해야하는 위치를 결정해야합니다.

  • 크러쉬 블로커는 이전의 스트레치 수가 현재의 것과 같고 현재의 스트레치 된 순서가 이전의 것보다 큰 경우에만 배치해야합니다. 예를 들어, [2, 4]호감 차단제가 필요합니다 (뻗어 수있다 1, 반복, 그리고 [1, 1]보다 짧은 [1,1,1,1]), 그러나 [4, 2][2, 6]하나를 필요로하지 않는다
  • n이전의 확장 된 시퀀스를 호출 하고 위의 조건이 확인되면 현재 시퀀스는 시퀀스의 반복입니다 n. 이전 번호의 크러시 시퀀스를 중단하려면 n현재 번호 의 두 번째 시퀀스 끝에 크러시 차단기를 배치해야합니다 . 예 : [2, 8] => [(1, 1)=n, (1, 1) + (2) + (1, 1) + ...]또는[4, 8] => [(1, 1, 1, 1)=n, (1, 1, 1, 1) + (1, 1, 2) + ...]

답변

젤리 , 42 바이트

ṪḤ,⁼?⁹⁸;µ/Ḋ$¹L’$?ÐĿċ³
ṗЀ⁸ẎS⁼¥Ðfµ€ŒpẎ€ÇÐfṪ

온라인으로 사용해보십시오!

전체 프로그램. 매우 비효율적이지만 작동합니다.


답변

파이썬 2 , 230 228 226 바이트

가능한 모든 목록을 입력 목록과 동일한 합계로 반복하여 작동합니다. 분쇄 상태에서 입력 어레이와 같지 않은 것을 제거하고 가장 긴 것을 선택하십시오.

편집 :if 주 함수에서 -2 바이트를 제거하여

편집 : 두 개의 불필요한 대괄호를 제거하여 -2 바이트

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]
def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)
b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

온라인으로 사용해보십시오!

설명

가능한 모든 솔루션을 찾고 가장 긴 솔루션을 선택하는 주요 기능

lambda x:max((c(z[:],x),len(z),z)for z in b(sum(x)))[2]

크러쉬 기능 : y가 크러쉬 중 하나와 같은지 확인합니다.

def c(x,y):
 i=e=1
 while x[i:]:
	if x[~-i]==x[i]:del x[i];i-=1;x[i]*=2;e=2
	i+=1
 return x==y or~-e and c(x,y)

주어진 합으로 가능한 모든 순열을 생성

b=lambda s:[z+[-~i]for i in range(s)for z in b(s+~i)]+[[]]

답변

05AB1E , 41 37 바이트

vy[DÉ#2÷]DYQX©NoDU‹&sDV¸X∍sić·®·Íǝ}»,

온라인으로 사용해보십시오!

내 Javascript 솔루션의 포트.

설명 :

vy                   for each member of the list
[DÉ#2÷]              divide by 2 until odd: stack = stretched value, N = iterations
DYQ                  stetched value equal to the previous one?
X©NoDU‹              previous size < current one? (+store the new size in X)
&                    AND on the 2 previous tests
sDV¸X∍s              build a list of the new stretched value repeated X times
                      (+store the new stetched value in Y)
ić·®·Íǝ}             if the previous tests are true:
                       reduce the result list size by 1
                       multiply by 2 the number at the crush block position
»,                   join by newline + print the list