¿Cuántas particiones contienen solo cuadrados perfectos?

16

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 por lo que gana la respuesta más corta en bytes
Hiperneutrino
fuente
1
Sandbox Post
HyperNeutrino
¿Podemos tomar la entrada como una lista de dígitos?
totalmente humano
¿Por qué es 1 -> 1 pero 0 -> 0?
Jonás
@Jonah Typo ... xD
HyperNeutrino
1
@totallyhuman Claro.
HyperNeutrino

Respuestas:

7

Haskell , 135 bytes

s x=any((x==).(^2))[0..x]
c(a:b:x)=a*10+b:x
c x=x
h[x]=1>0
h x=(s.head)x
f x@(_:_:_)|y<-until h c x=f(tail y)+f(c y)
f x=sum[1|any s x]

Pruébalo en línea!

Probablemente aún no haya jugado bien, pero este es un problema sorprendentemente difícil

Post Rock Garf Hunter
fuente
7

Jalea , 8 bytes

ŒṖḌƲẠ€S

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?

ŒṖḌƲẠ€S - Link: list of digits              e.g. [4,0,0,4]
ŒṖ       - all partitions                         [[4,0,0,4],[4,0,[0,4]],[4,[0,0],4],[4,[0,0,4]],[[4,0],0,4],[[4,0],[0,4]],[[4,0,0],4],[4,0,0,4]]
  Ḍ      - convert from decimal list (vectorises) [[4,0,0,4],[4,0,   4 ],[4,    0,4],[4,      4],[   40,0,4],[   40,    4],[    400,4],     4004]
   Ʋ    - is square? (vectorises)                [[1,1,1,1],[1,1,   1 ],[1,    1,1],[1,      1],[    0,1,1],[    0,    1],[      1,1],        0]
     Ạ€  - all truthy? for €ach                   [        1,          1,          1,          1           0,            0,          1,        0]
       S - sum                                    5
Jonathan Allan
fuente
6

Haskell , 88 bytes

f x=sum[0.5|y<-mapM(\c->[[c],c:" "])x,all((`elem`map(^2)[0..read x]).read).words$id=<<y]

Define una función fque 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 mapMy words. El fragmento mapM(\c->[[c],c:" "])xreemplaza cada carácter 'c'de una cadena xcon 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, lo yconcateno y llamo wordsal resultado, se dividirá en los espacios insertados por mapM. De esta manera obtengo todas las particiones xen 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.5s en lugar de 1s; Es por eso que el tipo de resultado es flotante.

f x=                       -- Define f x as
 sum[0.5|                  -- the sum of 0.5 for
  y<-                      -- every y drawn from
  mapM(\c->[[c],c:" "])x,  -- this list (explained above)
                           -- (y is a list of one- and two-element strings)
  all(...)                 -- such that every element of
                 id=<<y]   -- concatenated y
          .words$          -- split at spaces satisfies this:
                           -- (the element is a string)
   (...).read              -- if we convert it to integer
    `elem`                 -- it is an element of
    map(^2)                -- the squares of
    [0..read x]            -- the numbers in this list.
Zgarb
fuente
4

Python 3 , 148 139 135 134 bytes

10 bytes gracias a Arnold Palmer.

def f(a):
 s=[a[:1]]
 for i in a[1:]:s=sum([[x+[i],x[:-1]+[x[-1]*10+i]]for x in s],[])
 return sum({n**.5%1for n in x}=={0}for x in s)

Pruébalo en línea!

Monja permeable
fuente
Verificaría esto dos veces, pero creo que funciona. 140 caracteres
Arnold Palmer
Me burlé y dejé un espacio entre %1y for...
Arnold Palmer
Reemplazar [[a[0]]]con [a[:1]]ahorrará un byte
Arnold Palmer
Juntos superamos a Haskell.
Leaky Nun
La mejor parte es que fue, en parte, gracias a conjuntos, que nunca había usado hasta que publicaste ayer en mi respuesta de tortuga .
Arnold Palmer
2

Mathematica, 141 bytes

Count[FreeQ[IntegerQ/@Sqrt[FromDigits/@#],1<0]&/@(FoldPairList[TakeDrop,s,#]&/@Flatten[Permutations/@IntegerPartitions[Length[s=#]],1]),1>0]&


entrada (una lista de dígitos)

[{1,6,4}]

J42161217
fuente
Creo que esto da la respuesta incorrecta para 1649: cuento tres particiones que hacen cuadrados (a saber {1,64,9}, {16,4,9}y {16,49}) pero su función devuelve 4.
No es un árbol
Además, he notado que usas construcciones como Table[(function of s[[i]]),{i,Length[s=(stuff)]}]algunas veces; Por lo general, puede jugar golf a esto (function of #)&/@(stuff).
No es un árbol
1
@Notatree tienes toda la razón! Hice muchos cambios, seguí tus instrucciones y ¡funciona de maravilla! gracias
J42161217
2

Python 2 , 173 163 bytes

lambda s:len([l for l in[''.join(sum(zip(s,[','*(n>>i&1)for i in range(len(s))]+['']),())).split(',')for n in range(2**~-len(s))]if {int(x)**.5%1for x in l}=={0}])

Pruébalo en línea!

Editar: Guardado 10 bytes debido a ArnoldPalmer

Chas Brown
fuente
1
¿Se puede guardar un byte usando en .5lugar de 0.5?
numbermaniac
Usted puede. También puede guardar algunos bytes con el mismo truco que hice en la publicación Python 3 de Leaky Nun. Además, su respuesta no imprimió la cantidad de elementos, sino los elementos en sí, así que agregué eso. Si desea mantener la salida que tiene, es menos 5 bytes adicionales. 163 bytes
Arnold Palmer
Buen truco con comprensión, Arnold.
Chas Brown