How many partitions contain only perfect squares?

Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes.

Examples

input -> output # explanation
164 -> 2 # [16, 4], [1, 64]
101 -> 2 # [1, 01], [1, 0, 1]
100 -> 3 # , [1, 00], [1, 0, 0]
1 -> 1 # 
0 -> 1 # 
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]

Rules

• Standard Loopholes Apply
• This is so the shortest answer in bytes wins
• Sandbox Post – HyperNeutrino Jul 17 '17 at 23:43
• Can we take input as a list of digits? – totallyhuman Jul 18 '17 at 0:31
• why is 1 -> 1 but 0 -> 0? – Jonah Jul 18 '17 at 0:52
• @Jonah Typo... xD – HyperNeutrino Jul 18 '17 at 1:31
• @totallyhuman Sure. – HyperNeutrino Jul 18 '17 at 1:31

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

Try it online!

Probably not well golfed yet but this is a surprisingly difficult problem

Jelly, 8 bytes

ŒṖḌÆ²Ạ€S

A monadic link taking a list of digits and returning a non-negative integer.

Try it online! or see the test suite.

How?

ŒṖḌÆ²Ạ€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

f x=sum[0.5|y<-mapM(\c->[[c],c:" "])x,all((elemmap(^2)[0..read x]).read).words$id=<<y] Defines a function f that takes a string and returns a float. Very slow. Try it online! Explanation I'm using my Haskell tip for computing all partitions of a string with mapM and words. The snippet mapM(\c->[[c],c:" "])x replaces every character 'c' of a string x with either the one-element string "c" or the two-element string "c ", and returns the list of all possible combinations. If I take one of the results, y, concatenate it and call words on the result, it will be split at the spaces inserted by mapM. In this way I obtain all partitions of x into contiguous substrings. Then I just count those results where each partition element is a perfect square (by finding it in the list [0,1,4,9,..,x^2]). A caveat is that each partition is counted twice, with and without a trailing space, so I take the sum of 0.5s instead of 1s; this is why the result type is a float. 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.

lf!f!sI@sjkY2T./

Python 3, 148139135 134 bytes

10 bytes thanks to 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)

Try it online!

• I'd double check this, but I believe it works. 140 characters. – Arnold Palmer Jul 18 '17 at 12:35
• I goofed and left a space between %1 and for... – Arnold Palmer Jul 18 '17 at 12:40
• Replacing [[a]] with [a[:1]] will save a byte – Arnold Palmer Jul 18 '17 at 12:53
• Together we outgolfed Haskell. – Leaky Nun Jul 18 '17 at 13:07
• Best part is that it was, in part, thanks to sets, which I had never used until you posted on my turtle answer yesterday. – Arnold Palmer Jul 18 '17 at 13:16

Mathematica, 141 bytes

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

input (a list of digits)

[{1,6,4}]

• I think this gives the wrong answer for 1649: I count three partitions that make squares (namely {1,64,9}, {16,4,9} and {16,49}) but your function returns 4. – Not a tree Jul 18 '17 at 12:17
• Also, I've noticed you using constructions like Table[(function of s[[i]]),{i,Length[s=(stuff)]}] a few times; you can usually golf this down to (function of #)&/@(stuff). – Not a tree Jul 18 '17 at 12:20
• @Notatree you are absolutely right! I made many changes, followed your instructions and it works like a charm! thanks – J42161217 Jul 18 '17 at 17:35

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}])

Try it online!

Edit: Saved 10 bytes due to ArnoldPalmer

• Can you save a byte by using .5 instead of 0.5? – numbermaniac Jul 18 '17 at 8:22
• You can. You can also save some bytes with the same trick I pulled on Leaky Nun's Python 3 post. Also, your answer didn't print the number of elements, but the elements themselves, so I added that in. If you want to keep the output you have, it's minus an extra 5 bytes. 163 bytes – Arnold Palmer Jul 18 '17 at 12:44
• Nice trick with set comprehension, Arnold. – Chas Brown Jul 18 '17 at 20:20