Dado un número entero no negativo o una lista de dígitos, determine de cuántas maneras se puede formar el número concatenando números cuadrados, que pueden tener ceros a la izquierda.
Ejemplos
input -> output # explanation
164 -> 2 # [16, 4], [1, 64]
101 -> 2 # [1, 01], [1, 0, 1]
100 -> 3 # [100], [1, 00], [1, 0, 0]
1 -> 1 # [1]
0 -> 1 # [0]
164900 -> 9 # [1, 64, 9, 0, 0], [1, 64, 9, 00], [1, 64, 900], [16, 4, 900], [16, 4, 9, 0, 0], [16, 4, 9, 00], [16, 49, 0, 0], [16, 49, 00], [16, 4900]
Reglas
- Se aplican lagunas estándar
- Este es el código de golf, por lo que gana la respuesta más corta en bytes
code-golf
math
number
combinatorics
set-partitions
Hiperneutrino
fuente
fuente
Respuestas:
Haskell , 135 bytes
Pruébalo en línea!
Probablemente aún no haya jugado bien, pero este es un problema sorprendentemente difícil
fuente
Jalea , 8 bytes
Un enlace monádico que toma una lista de dígitos y devuelve un entero no negativo.
Pruébalo en línea! o ver el conjunto de pruebas .
¿Cómo?
fuente
Haskell , 88 bytes
Define una función
f
que toma una cadena y devuelve un flotante. Muy lento. Pruébalo en línea!Explicación
Estoy usando mi consejo de Haskell para calcular todas las particiones de una cadena con
mapM
ywords
. El fragmentomapM(\c->[[c],c:" "])x
reemplaza cada carácter'c'
de una cadenax
con la cadena de un elemento"c"
o la cadena de dos elementos"c "
, y devuelve la lista de todas las combinaciones posibles. Si tomo uno de los resultados, loy
concateno y llamowords
al resultado, se dividirá en los espacios insertados pormapM
. De esta manera obtengo todas las particionesx
en subcadenas contiguas. Luego, solo cuento los resultados donde cada elemento de partición es un cuadrado perfecto (al encontrarlo en la lista[0,1,4,9,..,x^2]
). Una advertencia es que cada partición se cuenta dos veces, con y sin espacio final, así que tomo la suma de0.5
s en lugar de1
s; Es por eso que el tipo de resultado es flotante.fuente
Pyth , 16 bytes
Banco de pruebas .
fuente
Python 3 ,
148139135134 bytes10 bytes gracias a Arnold Palmer.
Pruébalo en línea!
fuente
%1
yfor
...[[a[0]]]
con[a[:1]]
ahorrará un byteMathematica, 141 bytes
entrada (una lista de dígitos)
fuente
{1,64,9}
,{16,4,9}
y{16,49}
) pero su función devuelve 4.Table[(function of s[[i]]),{i,Length[s=(stuff)]}]
algunas veces; Por lo general, puede jugar golf a esto(function of #)&/@(stuff)
.Python 2 ,
173163 bytesPruébalo en línea!
Editar: Guardado 10 bytes debido a ArnoldPalmer
fuente
.5
lugar de0.5
?