números de sporeball
fundo
Estudamos pelo menos cinco tipos diferentes de números com base nas IDs de diferentes usuários neste site. Por que não estudar outro?
Meu ID de usuário é \$91030_{10}\$. Sua representação binária é \$10110001110010110_2\$, uma representação que possui uma propriedade interessante própria:
- Uma opção para a execução palíndrômica mais longa de dígitos binários é \$0011100\$.
- Se você remover esta sequência de dígitos, a lista de dígitos restantes ( \$1011010110\$) pode ser dividido em duas metades idênticas.
Eu defino um número sporeball como qualquer inteiro positivo em que pelo menos uma das opções para a mais longa sequência palíndrômica de dígitos em sua representação binária pode ser removida de modo que a lista de dígitos restante pode ser dividida em duas metades idênticas.
Tarefa
Escreva um programa ou função que tenha um número inteiro positivo como entrada e determine se é ou não um número de bola de esporo.
Alguns esclarecimentos a ter em conta:
- Zeros à esquerda devem ser ignorados.
- Exatamente uma série de dígitos palindrômicos deve ser removida antes de verificar se os dígitos restantes podem ser divididos em metades idênticas.
- Se uma das opções para a execução palíndrômica mais longa ocorrer várias vezes, remova apenas uma ocorrência , em vez de todas, antes de verificar se os dígitos restantes podem ser divididos em metades idênticas.
- Os dígitos únicos são palindrômicos.
- A string vazia
""não é palíndrômica e não pode ser dividida em duas metades idênticas.
Lembre-se de que pode haver mais de uma sequência palindrômica mais longa de dígitos:
- Os dígitos binários de \$12_{10}\$( \$1100\$) contém duas opções para a execução palíndromica mais longa ( \$11\$e \$00\$) Não importa qual seja removido, os dígitos restantes poderão ser divididos em metades idênticas. Assim, \$12_{10}\$ é um número de sporeball.
- Os dígitos binários de \$20_{10}\$( \$10100\$) contém duas opções para a execução palíndromica mais longa ( \$010\$e \$101\$) Removendo \$010\$deixa os dígitos \$10\$, que não pode ser dividido em metades idênticas; no entanto, removendo \$101\$deixa os dígitos \$00\$, que pode ser. Assim, \$20_{10}\$ é um número de sporeball.
Existem 153 números de sporeball abaixo de 1.000:
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
Regras
- Este é o código-golfe , então a resposta mais curta em bytes ganha.
- Aplicam-se as regras de E / S padrão.
Respostas
Brachylog , 26 bytes
{ḃ~c₃↺{↔?¬Ė}ʰ↻c}ᶠlᵒlᵍh∋~jz
Experimente online!
Terrivelmente lento para grandes casos de teste falsos, mas verifica os verdadeiros surpreendentemente rápido. Minha solução original encontrou os mesmos falsos negativos que a resposta excluída de xash, mas felizmente o processo de correção que me ajudou a cortar 2 bytes.
{ }ᶠ 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.
Em vez de maximizar o comprimento da substring palindrômica, ele apenas minimiza o comprimento de tudo o que resta, que é uma abordagem que eu realmente só criei por causa da minha abordagem inicial de confiar ≜.
05AB1E , 47 45 43 42 40 41 40 31 bytes
b©ŒʒÂQ}é.γg}θε®sõ.;D2ä1ìËsgĀ*}à
Experimente online!
-2 graças a @ovs!
-1 obrigado a @ovs!
-1 (risos) graças a uma correção de bug
-1 graças a @ovs (de novo!)
+1 devido ao esclarecimento do desafio :-(
mas -1 graças a @Kevin!
E outro colossal -9 graças a @Kevin!
Não se importe comigo ... apenas postando outra resposta excessivamente longa em 05AB1E que provavelmente foi considerada por qualquer pessoa experiente em 05AB1E.
O ÂQtruque para ver se uma string é um palíndromo foi extraído desta dica 05AB1E de resposta de Kevin.
Explicado (antigo)
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
J , 80 78 75 66 61 57 bytes
1 e.#\,@((#<.[-:[:,~,~inv)\.*[:(*i.@#=+./"{i:1:)(-:|.)\)]
Experimente online!
-3 bytes graças ao Marshall
-9 bytes graças ao xash
Mais resistente do que pensei que seria.
Finalmente, um tamanho respeitável, embora ainda alto para J.
J , abordagem alternativa, 73 bytes
1 e.1}.((((<:@[,(-:|.)\#(#<.]-:[:,~,~inv)\.)~{.))^:(0<{.@]*1=#@])^:_#)@#:
Experimente online!
Este usa do..while ^:(while)^:_, começando por pesquisar o palíndromo de comprimento mais longo possível e parando assim que encontrar algum para um certo comprimento, retornando o booleano informando se o complemento para aquele palíndromo é uma string dupla.
Jelly , 31 bytes
ḊḢŒḂḤœP⁸F
BØ2jŒṖḟ€€2Ç€LÐṂŒHE$ƇẸ
Experimente online! Ou veja aqueles até 600 (até 1000 é muito lento).
Quão?
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
Wolfram Language (Mathematica) , 128 ... 103 101 bytes
FreeQ[MinimalBy[$@@d~Drop~#&/@SequencePosition[d=#~IntegerDigits~2,_?PalindromeQ],Length],a__~$~a__]&
Experimente online!
Retorna Falsese o número não for um número sporeball e, Truecaso contrário.
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. *)
$@@é necessário para lidar com casos como \$38=100110_2\$, Onde a remoção de qualquer um dos dois mais longos-paldromas 1001, 0110tem o mesmo resultado 10.
JavaScript (ES6), 175 bytes
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))
Experimente online!
Comentou
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
Retina , 126 bytes
.+
*
+`^(_*)\1(_?)(?!^|_)
$1$.2
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$' N$`
$.& +m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1 0m`^(.+)\1$
Experimente online! Explicação:
.+
*
Converta a entrada em unário.
+`^(_*)\1(_?)(?!^|_)
$1$.2
Converta em binário.
Lv$`(.)+.?(?<-1>\1)+(?(1)(?!))|. $`$'
Encontre e remova palíndromos.
N$`
$.&
Classifique os resultados por comprimento, de forma que o primeiro resultado corresponda ao palíndromo mais longo.
+m`^((.)*)¶(?<-2>.)*(?(2)(?!)).+$
$1
Remova todos os resultados de comprimento maior.
0m`^(.+)\1$
Verifique se algum deles pode ser dividido.
Carvão , 53 bytes
≔⍘Ｎ²θＦ⊕ＬθＦιＦ⁼✂θκι¹⮌✂θκι⊞υ⁺…θκ✂θι¿⌊υ⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
Experimente online! O link é para a versão detalhada do código. A saída é um booleano Charcoal, ou seja, -para um número de sporeball, vazio se não for. Explicação:
≔⍘Ｎ²θ
Converta a entrada para a base 2.
Ｆ⊕ＬθＦι
Faça um loop em todas as substrings não triviais da entrada.
Ｆ⁼✂θκι¹⮌✂θκι
Se esta substring for igual ao reverso ...
⊞υ⁺…θκ✂θι
... em seguida, empurre os dígitos restantes para a lista vazia predefinida.
¿⌊υ
Se o número original não era palíndromo, ...
⊙υ∧⁼Ｌι⌊ＥυＬλ⁼ιײ∕ι²
... em seguida, imprima se algum dos resultados tem comprimento mínimo e se iguala a eles, dividido pela metade e dobrado novamente.
Fator , 209 197 bytes
: 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 ;
Experimente online!
Husk , 28 bytes
▲foE½†!ḋ¹ṠM-ö→kLfoS=↔m!ḋ¹Qŀḋ
Experimente online! Retorna uma lista vazia (que é falsa no Husk) ou uma lista não vazia (que é verdadeira).
Explicação
A repetição ḋparece um desperdício, mas não tenho certeza de como me livrar disso.
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.
Japt , 33 42 bytes
s2
ã fêS üÊo
Vc@ðXãjXVÎlîòZÊ/2Ãd_Ê©ZÎ¥Zo
Tente
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 ==
Corrigido: agora funciona para números com execuções palindrômicas mais longas idênticas como 2405 => 100101100101
Teste : calcula os primeiros 1000 termos e verifica se o resultado é o mesmo dos casos de teste.
Python 3.8 (pré-lançamento) , 154 152 bytes
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]
Experimente online!
Comentado:
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
Se houver vários palíndromos de mesmo comprimento máximo, maxseleciona a tupla com o segundo valor mais alto, onde True>False.
Dotty, 201 bytes
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)}
Experimente online (em Scastie)
A entrada já deve ser uma string binária.
Dotty, 226 bytes
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)}}
Experimente online (em Scastie)
A entrada é um Int.