포자 번호
Sep 19 2020
배경
이 사이트에있는 다른 사용자의 ID를 기반으로 최소 5 가지 유형 의 번호 를 연구했습니다 . 왜 다른 것을 공부하지 않습니까?
내 사용자 ID는 \$91030_{10}\$. 이진 표현은 \$10110001110010110_2\$, 그 자체로 흥미로운 속성을 가진 표현 :
- 이진수의 가장 긴 회 문학적 실행에 대한 한 가지 옵션은 \입니다.$0011100\$.
- 이 숫자를 제거하면 나머지 숫자 목록 ( \$1011010110\$)는 두 개의 동일한 절반으로 나눌 수 있습니다.
저는 포자 볼 숫자 를 양의 정수로 정의합니다. 여기서 이진 표현에서 가장 긴 회 문형 숫자 실행 옵션 중 하나 이상을 제거하여 나머지 숫자 목록을 두 개의 동일한 반으로 나눌 수 있습니다.
직무
양의 정수를 입력으로 받아 포자 숫자인지 아닌지를 결정하는 프로그램이나 함수를 작성합니다.
명심해야 할 몇 가지 설명 :
- 선행 0은 무시해야합니다.
- 나머지 숫자가 동일한 반으로 분할 될 수 있는지 확인하기 전에 정확히 하나의 회 문형 숫자를 제거해야합니다.
- 가장 긴 회 문식 실행 옵션 중 하나가 여러 번 발생하는 경우 나머지 숫자가 동일한 반으로 분할 될 수 있는지 확인하기 전에 모든 항목 이 아닌 하나의 항목 만 제거하십시오 .
- 한 자리 숫자는 회문입니다.
- 빈 문자열
""은 회문이 아니며 두 개의 동일한 반으로 나눌 수 없습니다.
가장 긴 회 문형 숫자가 두 개 이상있을 수 있습니다.
- \ 의 이진수$12_{10}\$( \$1100\$)에는 가장 긴 회 문식 실행 ( \$11\$및 \$00\$). 어느 것이 제거 되더라도 나머지 숫자는 동일한 반으로 나눌 수 있습니다. 따라서 \$12_{10}\$ 포자 숫자입니다.
- \ 의 이진수$20_{10}\$( \$10100\$)에는 가장 긴 회 문식 실행 ( \$010\$및 \$101\$). \ 제거$010\$자릿수 \$10\$, 동일한 반으로 나눌 수 없습니다. 그러나 \$101\$자릿수 \$00\$, 될 수 있습니다. 따라서 \$20_{10}\$ 포자 숫자입니다.
1,000 개 미만의 포자 볼 수는 153 개입니다.
12 20 23 24 26 28 29 39 48 57 60 68 71 84 87 96 100 106 108 110 111 113 117 123 124 132
135 154 166 178 180 183 192 204 207 210 222 225 237 240 243 252 260 263 277 282 287 295
314 326 334 336 337 340 343 348 351 354 370 372 375 384 392 394 396 399 404 412 418 426
428 431 432 446 449 457 469 476 477 479 480 483 484 490 491 496 497 501 503 508 516 519
533 538 543 562 600 610 612 615 634 646 652 660 663 664 670 673 676 691 700 703 706 718
720 735 742 754 756 759 768 778 780 783 792 804 816 821 826 828 831 834 858 870 874 876
879 894 897 918 921 922 924 927 933 957 960 963 972 978 987 993 999
규칙
- 이것은 code-golf 이므로 바이트 단위의 가장 짧은 답변이 이깁니다.
- 표준 I / O 규칙이 적용됩니다.
답변
9 UnrelatedString Sep 19 2020 at 18:45
Brachylog , 26 바이트
{ḃ~c₃↺{↔?¬Ė}ʰ↻c}ᶠlᵒlᵍh∋~jz
온라인으로 시도하십시오!
큰 가짜 테스트 케이스의 경우 엄청나게 느리지 만 진실한 테스트 케이스는 놀랍도록 빠르게 확인합니다. 내 원래 솔루션 은 xash의 삭제 된 답변과 동일한 거짓 부정에 부딪 혔지만 다행히도 2 바이트를 줄이는 데 도움이되는 수정 프로세스가 있습니다.
{ }ᶠ Find every possible result from:
ḃ take the binary digits of the input,
~c₃ split them into three (possibly empty) partitions,
↺{ }ʰ↻ for the middle partition:
↔ reversed it is
? itself
¬Ė which is not the empty list;
Ė replace it with the empty list.
c and re-concatenate the partitions.
lᵒ Sort the results by length,
lᵍ group them by length,
h and take the first group (that with minimal length).
∋ Some element of that group
~j is something concatenated with itself
z which is not the empty list.
회문 부분 문자열의 길이를 최대화하는 대신 남은 모든 항목의 길이를 최소화 할뿐입니다. 이는 .NET에 의존하는 초기 접근 방식 때문에 실제로 생각해 낸 접근 방식입니다 ≜.
8 Lyxal Sep 19 2020 at 11:24
05AB1E , 47 45 43 42 40 41 40 31 바이트
b©ŒʒÂQ}é.γg}θε®sõ.;D2ä1ìËsgĀ*}à
온라인으로 시도하십시오!
-2 @ovs 덕분에!
-1 @ovs 덕분에!
-1 (웃음) 버그 수정
덕분에 -1 @ovs 덕분에 (다시!)
+1 도전 설명으로 인해 +1 :-(
하지만 @Kevin! 덕분에 -1, @Kevin 덕분에
또 다른 무려 -9!
신경 쓰지 마세요 ... 05AB1E에 경험이 많은 사람 이 골프를 치게 될 또 다른 지나치게 긴 답변을 05AB1E에 게시 했습니다.
ÂQ문자열이 회문가에서 찍은 경우 트릭은 볼 이 케빈에 의해 05AB1E 팁 대답.
설명 됨 (이전)
bDV.œ˜ʒÂQ} ЀgàUʒgXQ}εYsõ:Ðg;ôËsgD0ÊsÈ**}à
bDV # Get the binary representation of the input, and assign variable Y to that value while still keeping a copy on the stack
.œ # Push all partitions of that binary representation
˜ # Flatten said list and
ʒ # Select items where:
ÂQ} # They are a palindrome
Ð # and push three copies of it to the stack.
€g # For one of those copies, push the length of each item
àU # Find the maximum length and assign it to variable Y
ʒgXQ} # From the list of palindromic partitions, select the ones which are of the maximum length
ε # And from that list:
Ysõ: # Replace the occurrence of that number in variable Y with nothing THEN
Ð # Triplicate it THEN
g;ô # Split it in half THEN
Ë # See if all elements are equal AND
sgD0ÊsÈ** # Ensure the length of Y with the item removed isn't 0 and isn't odd
}à # Close the map, and take the maximum of the list and implicitly print the result
5 Jonah Sep 19 2020 at 13:35
J , 80 78 75 66 61 57 바이트
1 e.#\,@((#<.[-:[:,~,~inv)\.*[:(*i.@#=+./"{i:1:)(-:|.)\)]
온라인으로 시도하십시오!
-Marshall 덕분에 3 바이트
xash 덕분에 -9 바이트
내가 생각했던 것보다 더 힘들다.
마침내 J의 경우 여전히 높지만 상당한 크기입니다.
J , 대체 접근 방식, 73 바이트
1 e.1}.((((<:@[,(-:|.)\#(#<.]-:[:,~,~inv)\.)~{.))^:(0<{.@]*1=#@])^:_#)@#:
온라인으로 시도하십시오!
이것은 do..while을 사용합니다. ^:(while)^:_가능한 가장 긴 회문을 검색하는 것으로 시작하여 특정 길이에 대한 항목을 찾으면 즉시 중지하고 해당 회 문의 보완이 두 배 문자열인지 알려주는 부울을 반환합니다.
4 JonathanAllan Sep 19 2020 at 23:15
젤리 , 31 바이트
ḊḢŒḂḤœP⁸F
BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ
온라인으로 시도하십시오! 또는 최대 600 개를 참조하십시오(최대 1000 개는 너무 느림).
어떻게?
BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ - Main Link: n
B - convert (n) to a binary list
Ø2 - [2,2]
j - join ([2,2]) with (B(n))
ŒṖ - partitions (none with empty parts, hence the Ø2j and ḟ€€2)
ḟ€€2 - remove any 2s from each part of each
Ç€ - call Link 1 for each
(removes second part if it's palindromic & flattens)
LÐṂ - keep only those with minimal length
Ƈ - filter keep those for which:
$ - last two links as a monad:
ŒH - split into two
E - all equal?
Ẹ - any truthy?
ḊḢŒḂḤœP⁸F - Link 1: list of parts
Ḋ - deueue
Ḣ - head -> second part
ŒḂ - is palindromic? (1 if so, else 0)
Ḥ - double
⁸ - the list of parts
œP - partition at index
(0œP[4,5,6,7] -> [[4,5,6,7]] while 2œP[4,5,6,7] -> [[4],[6,7]])
F - flatten
4 att Sep 19 2020 at 11:59
Wolfram 언어 (Mathematica) , 128 ... 103 101 바이트
FreeQ[MinimalBy[$@@d~Drop~#&/@SequencePosition[d=#~IntegerDigits~2,_?PalindromeQ],Length],a__~$~a__]&
온라인으로 시도하십시오!
False숫자가 포자 숫자가 아니면 반환 합니다 True.
d=#~IntegerDigits~2 (* get digits of input, base 2. *)
SequencePosition[ % ,_?PalindromeQ] (* get positions of palindromic runs *)
d~Drop~#/@ % (* and remove them, *)
$@@ % (* placing the remaining digits in $ *)
MinimalBy[ % ,Length] (* keep the shortest remaining digit lists *)
FreeQ[ % ,a__~$~a__] (* and check if they have identical halves. *)
$@@\ 와 같은 경우를 처리하는 데 필요합니다.$38=100110_2\$두 최장 회문 하나의 제거, 여기서 1001, 0110동일한 결과를 갖는다 10.
3 Arnauld Sep 19 2020 at 11:29
JavaScript (ES6), 175 바이트
n=>(m=g=(s,p='',q=p)=>s?g(s.slice(1),p+s[0],q,s==[...s].reverse(L=s.length).join``?o=(L<=m?o:!(m=L))|L==m&/^(.+)\1$/.test(p+q):0,g(s.slice(0,-1),p,s[L-1]+q)):o)(n.toString(2))
온라인으로 시도하십시오!
댓글 작성
n => ( // n = input
m = // initialize m to a non-numeric value
g = ( // g is a recursive function taking:
s, // s = middle part of the string (the palindromic one)
p = '', q = p // p = left part, q = right part
) => //
s ? // if s is not empty:
g( // outer recursive call:
s.slice(1), // with the first character of s removed ...
p + s[0], // ... and appended to p
q, // with q unchanged
s == [...s] // split s
.reverse( // reverse it
L = s.length // set L = length of s (argument ignored by reverse)
).join`` ? // join again; if s is a palindrome:
o = // update o:
( L <= m ? // if L is not higher than m:
o // yield o
: // else:
!(m = L) // update m to L and yield 0
) | L == m & // bitwise OR with 1 if L = m (current max.)
/^(.+)\1$/ // and the concatenation of p and q can be
.test(p + q) // split into 2 identical halves
: // else:
0, // abort
g( // inner recursive call:
s.slice(0, -1), // with the last character of s removed
p, // with p unchanged
s[L - 1] + q // with the last character of s prepended to q
) // end of inner recursive call
) // end of outer recursive call
: // else:
o // return o
)(n.toString(2)) // initial call to g with s = binary string for n
3 Neil Sep 19 2020 at 15:45
Retina , 126 바이트
.+
*
+`^(_*)\1(_?)(?!^|_)
$1$.2
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$' N$`
$.& +m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1 0m`^(.+)\1$
온라인으로 시도하십시오! 설명:
.+
*
입력을 단항으로 변환합니다.
+`^(_*)\1(_?)(?!^|_)
$1$.2
바이너리로 변환하십시오.
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$'
회문을 찾아 제거합니다.
N$`
$.&
결과를 길이별로 정렬하여 첫 번째 결과가 가장 긴 회문에 해당하도록합니다.
+m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1
길이가 더 긴 모든 결과를 제거하십시오.
0m`^(.+)\1$
분할 할 수있는 항목이 있는지 확인하십시오.
3 Neil Sep 19 2020 at 17:33
목탄 , 53 바이트
≔⍘Ｎ²θＦ⊕ＬθＦιＦ⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 출력은 Charcoal 부울입니다. 즉 -, 포자 볼 번호에 대해 그렇지 않으면 비어 있습니다. 설명:
≔⍘Ｎ²θ
입력을 밑이 2로 변환합니다.
Ｆ⊕ＬθＦι
입력의 모든 중요하지 않은 부분 문자열을 반복합니다.
Ｆ⁼✂θκι¹⮌✂θκι
이 부분 문자열이 그 반대와 같으면 ...
⊞υ⁺…θκ✂θι
... 그런 다음 나머지 숫자를 미리 정의 된 빈 목록으로 푸시합니다.
¿⌊υ
원래 번호가 회문이 아니었다면 ...
⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
... 그런 다음 결과가 최소 길이이고 길이가 절반으로 줄어들고 다시 두 배가 된 것과 같은지 여부를 출력합니다.
2 GalenIvanov Sep 21 2020 at 14:24
인자 , 209 197 바이트
: s ( n -- ? ) >bin dup all-subseqs [ dup reverse = ] filter
dup [ last length ] dip [ length over = ] filter nip
[ split1 append [ ""= not ] keep dup length 2/ cut = and ]
with [ or ] map-reduce ;
온라인으로 시도하십시오!
2 Zgarb Sep 21 2020 at 15:59
Husk , 28 바이트
▲foE½†!ḋ¹ṠM-ö→kLfoS=↔m!ḋ¹Qŀḋ
온라인으로 시도하십시오! 빈 목록 (허 스크에서는 거짓) 또는 비어 있지 않은 목록 (진실)을 반환합니다.
설명
반복 ḋ되는 것은 아깝지만 어떻게 제거해야할지 모르겠습니다.
Input is a number, say n=357
▲f(E½)†!ḋ¹ṠM-(→kLf(S=↔m!ḋ¹)Q)ŀḋ Parentheses added for clarity.
ḋ Binary digits: D=[1,0,1,1,0,0,1,0,1]
ŀ Indices: I=[1,2,3,4,5,6,7,8,9]
(→kLf(S=↔m!ḋ¹)Q) Get indices of longest palindromic runs.
Q Slices: [[1],[2],[1,2],..,[1,2,..,9]]
f Filter by condition:
(S=↔m!ḋ¹) Is a palindrome in D.
m Map
! indexing into
ḋ¹ D (recomputed).
S= That equals
↔ its reverse.
kL Classify (into separate lists) by length.
→ Get the last one: [[2,3,4,5],[4,5,6,7]]
ṠM- Remove each from I: [[1,6,7,8,9],[1,2,3,8,9]]
† Deep map
!ḋ¹ indexing into D (recomputed again): [[1,0,1,0,1],[1,0,1,0,1]]
f Filter by condition:
(E½) Splits into identical halves.
½ Split into halves (if length is odd, first part is longer): [[1,0,1],[0,1]]
E All elements are equal: 0
Result is []
▲ Maximum, or [] if the argument is empty: []
The final result is nonempty iff the last filter keeps a nonempty list.
2 AZTECCO Sep 21 2020 at 04:56
Japt , 33 42 바이트
s2
ã fêS üÊo
Vc@ðXãjXVÎlîòZÊ/2Ãd_Ê©ZÎ¥Zo
시도 해봐
s2 - convert input to binary string
ã - substrings
fêS - filter palindrome
üÊo - take last group by length
Vc@ðXÃ - find indexes of each palindrome in input
£jXVÎlà - map those indexes by removing n(=palindr.length) characters from input at index
®òZÊ/2Ã - split all results
d_ - return true if any :
Ê© - exists and..
ZÎ¥Zo - are ==
수정 됨 : 이제 2405 => 100101100101과 같이 더 동일한 가장 긴 회문이있는 숫자에 대해 작동합니다.
테스트 : 처음 1000 개의 항을 계산하고 결과가 테스트 케이스와 같은지 확인합니다.
1 ovs Sep 19 2020 at 15:40
Python 3.8 (사전 릴리스) , 154152 바이트
def f(n):s=f'{n:b}';k=len(s);return max((b-a,(r:=s[:a]+s[b:])[:(h:=k-b+a>>1)]==r[h:]>'')for a in range(k)for b in range(a,k+1)if(p:=s[a:b])==p[::-1])[1]
온라인으로 시도하십시오!
댓글 :
s=f'{n:b}' # convert n to a binary string
k=len(s) # and take the length
return max( ... )[1] # the second element from the maximum of
(b-a, # tuples of palindrome length b-a ...
[:(h:=k-b+a>>1)] # ... and is the first half
(r:=s[:a]+s[b:]) # of the binary string without the palindrome
==r[h:] # equal to the second half
>'') # and not equal to the empty string
for a in range(k) # for palindrome starting positions a in [0, 1, ..., k-1]
for b in range(a,k+1) # for palindrome end indices b in [1, 2, ..., k-a]
if(p:=s[a:b])==p[::-1]) # if this is an actual palindrome
최대 길이가 같은 회문이 여러 개 max있는 경우 가장 높은 초 값을 가진 튜플을 선택합니다 True>False. 여기서 .
1 user Sep 20 2020 at 07:00
Dotty, 201 바이트
s=>((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}
온라인으로 시도 (Scastie에서)
입력은 이미 2 진 문자열이어야합니다.
Dotty, 226 바이트
x=>{val s=x.toBinaryString
((for{j<-1 to s.size
i<-0 to j-1
x=s.slice(i,j)if x==x.reverse}yield(i,j))groupBy(_-_)minBy(_._1)_2)exists{(i,j)=>val x=s.slice(0,i)+s.substring(j)
x!=""&&x.slice(0,x.size/2)==x.substring(x.size/2)}}
온라인으로 시도 (Scastie에서)
입력은 Int.