태그 보관물: subsequence

subsequence

이진을 번갈아 서브 시퀀스로 분해 3, 1\n2\n3어디서 \n등

이것은 HP CodeWars의 최근 경쟁문제 13-비 반복 바이너리 입니다 .

임의의 십진수를 봅시다.

727429805944311

이진 표현을 살펴보십시오.

10100101011001011111110011001011101010110111110111

이제 이진 표현을 숫자 01번갈아가는 하위 시퀀스로 나눕니다 .

1010 010101 10 0101 1 1 1 1 1 10 01 10 0101 1 1010101 101 1 1 1 101 1 1

각 하위 시퀀스를 다시 십진수로 변환합니다.

10 21 2 5 1 1 1 1 1 2 1 2 5 1 85 5 1 1 1 5 1 1

작업

단일 양의 정수를 입력으로 사용하여 위의 프로세스에서 얻은 양의 정수 시퀀스를 출력하십시오.

세부

  • 입력 및 출력은 10 진수 또는 단항이어야합니다.
  • 출력의 숫자는 사람이 읽을 수있는 현명한 방식으로 분리되어야하며 십진수 또는 단항이어야합니다. 공백에는 제한이 없습니다. 유효 출력 스타일 : [1,2,3], 1 2 3, 1\n2\n3어디서 \n등 문자 뉴 라인이다

테스트 사례

 Input | Output
     0 | 0
     1 | 1
     2 | 2
     3 | 1 1
     4 | 2 0
     5 | 5
     6 | 1 2
     7 | 1 1 1
     8 | 2 0 0
     9 | 2 1
    10 | 10
    50 | 1 2 2
   100 | 1 2 2 0
  1000 | 1 1 1 1 10 0 0
 10000 | 2 1 1 2 0 2 0 0 0
 12914 | 1 2 2 1 1 2 2
371017 | 5 42 10 2 1

추가 사항 : 출력의 모든 숫자는 (2^k-1)/3또는 형식이어야합니다 2*(2^k-1)/3. 즉, 0 1 2 5 10 21, 42, 85, 170, ...,이다 A000975 OEIS한다.



답변

Pyth, 17 16 바이트

Jakube 덕분에 1 바이트

iR2cJ.BQx1qVJ+dJ

데모

훌륭하고 영리한 솔루션. Pyth 같은 일부 덜 알려진 기능 사용 x<int><list>c<str><list>.

iR2cJ.BQx1qVJ+dJ
                    Q = eval(input())
    J.BQ            Store in J the input in binary.
          qV        Vectorize equality function over
            J+dJ    J and J with a leading dummy char, to get the offset right.
                    This calculates whether each element matches its successor.
        x1          Find all of the indexes of 1 (True) in this list.
   cJ                Chop J at those locations.
iR2                  Convert from binary back to base ten and output.


답변

수학, 47 바이트

#+##&~Fold~#&/@#~IntegerDigits~2~Split~Unequal&

언 골프 드 :

FromDigits[#,2]&/@Split[IntegerDigits[#,2],Unequal]&

Split[list,f]사이의 위치에 침입, 여러 목록으로 목록을 분할 a하고 bIFF는 f[a,b]반환하지 않습니다 True.

FromDigits[n,2] => Fold[#+##&,n]alephalpha 의 깔끔한 입니다.


답변

파이썬, 86 바이트

내가 Pyth에서 끔찍하게 능가했기 때문에 파이썬에서 다시 할 수 있습니다.

import re
lambda n:[int(s,2)for s in re.sub("(?<=(.))(?=\\1)"," ",bin(n)[2:]).split()]

여기 사용해보십시오!

설명

입력 번호 n를 이진 문자열로 변환하는 것으로 시작 합니다. bin(n)[2:]처리합니다. bin()문자열을 형식으로 반환 하므로이 문자열의 처음 2자를 버려야 합니다 0b10101.
다음으로 하위 시퀀스의 경계를 식별해야합니다. 이것은 (?<=(.))(?=\1)왼쪽과 오른쪽에 같은 숫자를 갖는 문자열에서 길이가 0 인 위치와 일치 하는 정규 표현식으로 수행 할 수 있습니다 .
모든 하위 시퀀스 목록을 얻는 확실한 방법 re.split()은 특정 정규식에서 문자열을 분할하는 것을 사용 하는 것 입니다. 불행하게도이 함수는 길이가 0 인 일치에는 작동하지 않습니다. 그러나 운 좋게도 re.sub(), 우리는 길이가 0 인 일치 항목을 공백으로 바꾸고 그 후에 문자열을 분할합니다.
그런 다음 각 하위 시퀀스를 10 진수로 다시 구문 분석해야합니다 int(s,2).


답변

젤리, 12 바이트

BI¬-ẋż@BFṣ-Ḅ

온라인으로 사용해보십시오! 또는 모든 테스트 사례를 확인하십시오 .

작동 원리

BI¬-ẋż@BFṣ-Ḅ  Main link. Argument: n

B             Convert n to base 2.
 I            Compute the increments, i.e., the differences of consecutive digits.
  ¬           Apply logical NOT.
   -ẋ         Repeat -1 that many times, for the logical NOT of each difference.
              [0, 0] / [1, 1] ->   0    -> 1 -> [-1]
              [0, 1] / [1, 0] -> 1 / -1 -> 0 -> []
       B      Yield n in base 2.
     ż@       Zip the result to the right with the result to the left.
        F     Flatten the resulting list of pairs.
         ṣ-   Split at occurrences of -1.
           Ḅ  Convert each chunk from base 2 to integer.


답변

배쉬 + GNU 유틸리티, 51

dc -e2o?p|sed -r ':;s/(.)\1/\1 \1/;t'|dc -e2i?f|tac

STDIN에서 가져온 입력.

  • dc -e2o?p STDIN에서 입력 정수를 읽고 기본 2 문자열을 출력합니다.
  • sed -r ':;s/(.)\1/\1 \1/;t' 동일한 연속 자릿수가있는 곳마다 공백으로 기본 2 문자열을 분할합니다.
  • dc -e2i?f분할 바이너리를 한 번에 읽고 스택에 각 부분을 넣은 다음 f전체 dc스택 을 덤프합니다 (출력 번호를 역순으로) …
  • …로 수정됩니다 tac.

답변

자바 스크립트 (ES6) 58 62 63

1 바이트 저장된 thx @ETHproductions 편집

thx @Neil으로 저장된 4 바이트 편집

x=>x.toString(2).replace(/((.)(?!\2))*./g,x=>'0b'+x-0+' ')

f=x=>x.toString(2).replace(/((.)(?!\2))*./g,x=>'0b'+x-0+' ')


console.log=x=>O.textContent+=x+'\n'

;[
[     0,'0'],
[     1,'1'],
[     2,'2'],
[     3,'1 1'],
[     4,'2 0'],
[     5,'5'],
[     6,'1 2'],
[     7,'1 1 1'],
[     8,'2 0 0'],
[     9,'2 1'],
[    10,'10'],
[    50,'1 2 2'],
[   100,'1 2 2 0'],
[  1000,'1 1 1 1 10 0 0'],
[ 10000,'2 1 1 2 0 2 0 0 0'],
[ 12914,'1 2 2 1 1 2 2'],
[371017,'5 42 10 2 1']
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i)
  console.log(i+' -> '+r+(r.trim()==k.trim() ? ' ok':'ko (should be '+k+')'))
})
<pre id=O></pre>


답변

Pyth, 26 바이트

iR2c:.BQ"(?<=(.))(?=\\1)"d

여기 사용해보십시오!

설명

iR2c : .BQ "(? <= (.)) (? = \\ 1)"d # Q = 입력 번호

     .BQ # 입력을 이진수로 변환
    : "(? <= (.)) (? = \\ 1)"d # 하위 시퀀스 사이에 공백을 삽입하십시오
   공백에 c # 분할 문자열
iR2 # 각 하위 시퀀스를 10 진수로 변환

Python의 split () 함수는 길이가 0 인 일치 항목으로 분할되지 않으므로 해당 일치 항목을 공백으로 바꾸고 결과를 분할해야합니다.