胞子球数
Sep 19 2020
バックグラウンド
私たちは、少なくとも研究してきた5 異なる 種類 の 数字をこのサイト上の別のユーザーのIDに基づいて。別の勉強をしてみませんか？
私のユーザーIDは\です$91030_{10}\$。そのバイナリ表現は\$10110001110010110_2\$、独自の興味深いプロパティを持つ表現：
- 2進数の最長の回文実行の1つのオプションは\です。$0011100\$。
- この一連の数字を削除すると、残りの数字のリスト（\$1011010110\$）は、2つの同一の半分に分割できます。
私は、胞子球数を任意の正の整数として定義します。この整数では、バイナリ表現で最も長い回文の数字の実行のオプションの少なくとも1つを削除して、残りの数字のリストを2つの同一の半分に分割できます。
仕事
正の整数を入力として受け取り、それが胞子球の数であるかどうかを判別するプログラムまたは関数を作成します。
覚えておくべきいくつかの説明：
- 先行ゼロは無視する必要があります。
- 残りの数字を同じ半分に分割できるかどうかを確認する前に、正確に1つの回文数字を削除する必要があります。
- 最長のパリンドローム実行のオプションの1つが複数回発生する場合は、残りの数字を同じ半分に分割できるかどうかを確認する前に、すべてではなく1つの発生のみを削除してください。
- 一桁は回文です。
- 空の文字列
""は回文配列ではなく、2つの同一の半分に分割することはできません。
数字の最も長い回文の実行が複数ある可能性があることに注意してください。
- \の2進数$12_{10}\$（\$1100\$）最長のパリンドローム実行のための2つのオプションが含まれています（\$11\$および\$00\$）。どちらを削除しても、残りの数字は同じ半分に分割できます。したがって、\$12_{10}\$ は胞子の数です。
- \の2進数$20_{10}\$（\$10100\$）最長のパリンドローム実行のための2つのオプションが含まれています（\$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
ルール
- これはコードゴルフなので、バイト単位の最短の答えが優先されます。
- 標準の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.
回文部分文字列の長さを最大化するのではなく、残っているすべての長さを最小化するだけです。これは、に依存するという最初のアプローチのために私が実際に思いついたアプローチです≜。
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（lol）バグ修正の
おかげで-1 @ovsのおかげで（再び！）
+ 1はチャレンジの明確化のためです:-(
しかし-1は@Kevin！のおかげで
、もう1つはなんと-9の@Kevin！のおかげです！
ただ05AB1E内の別の過度に長いの答え投稿...私を気にしないでしょう して05AB1Eで経験した誰もがgolfedを。
ÂQ文字列が回文であるかどうかを確認するためのトリックは、Kevinによるこの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 6157バイト
1 e.#\,@((#<.[-:[:,~,~inv)\.*[:(*i.@#=+./"{i:1:)(-:|.)\)]
オンラインでお試しください！
-マーシャルのおかげで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 ... 103101バイト
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\$ここで、いずれか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
網膜、126バイト
.+
*
+`^(_*)\1(_?)(?!^|_)
$1$.2
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$' N$`
$.& +m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1 0m`^(.+)\1$
オンラインでお試しください！説明：
.+
*
入力を1進数に変換します。
+`^(_*)\1(_?)(?!^|_)
$1$.2
バイナリに変換します。
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$'
回文を見つけて削除します。
N$`
$.&
結果を長さで並べ替えて、最初の結果が最長の回文に対応するようにします。
+m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1
長さが長い結果をすべて削除します。
0m`^(.+)\1$
それらのいずれかを分割できるかどうかを確認します。
3 Neil Sep 19 2020 at 17:33
チャコール、53バイト
≔⍘Ｎ²θＦ⊕ＬθＦιＦ⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
オンラインでお試しください！リンクは、コードの詳細バージョンへのリンクです。出力はチャコールブール値です。つまり-、胞子球番号の場合、そうでない場合は空です。説明：
≔⍘Ｎ²θ
入力を基数2に変換します。
Ｆ⊕ＬθＦι
入力の重要な部分文字列をすべてループします。
Ｆ⁼✂θκι¹⮌✂θκι
この部分文字列がその逆に等しい場合...
⊞υ⁺…θκ✂θι
...次に、残りの桁を事前定義された空のリストにプッシュします。
¿⌊υ
元の番号が回文ではなかった場合、...
⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
...次に、結果のいずれかが最小の長さであり、長さが半分になり、再び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
ハスク、28バイト
▲foE½†!ḋ¹ṠM-ö→kLfoS=↔m!ḋ¹Qŀḋ
オンラインでお試しください！空のリスト（Huskでは偽物）または空でないリスト（真実）を返します。
説明
繰り返されるのḋはもったいない気がしますが、どうやってそれを取り除くのかわかりません。
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は、2番目の値が最も高いタプルを選択し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で）
入力はすでにバイナリ文字列である必要があります。
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です。