up vote 7 down vote favorite
1

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 # [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]

Rules

  • Standard Loopholes Apply
  • This is so the shortest answer in bytes wins
share|improve this question
1  
Sandbox Post – HyperNeutrino 8 hours ago
    
Can we take input as a list of digits? – totallyhuman 7 hours ago
    
why is 1 -> 1 but 0 -> 0? – Jonah 7 hours ago
    
@Jonah Typo... xD – HyperNeutrino 6 hours ago
1  
@totallyhuman Sure. – HyperNeutrino 6 hours ago
up vote 5 down vote

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]

Try it online!

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

share|improve this answer
up vote 4 down vote

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
share|improve this answer
up vote 3 down vote

Pyth, 16 bytes

lf!f!sI@sjkY2T./

Test suite.

share|improve this answer
up vote 2 down vote

Python 2, 173 bytes

lambda s:[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)-1))]if all(int(int(x)**0.5)**2==int(x)for x in l)]

Try it online!

share|improve this answer
up vote 2 down vote

Python 3, 148 bytes

lambda a:sum(all(int(n**.5)**2==n for n in x)for x in p(a))
p=lambda a:a[1:]and sum([[x+[a[-1]],x[:-1]+[x[-1]*10+a[-1]]]for x in p(a[:-1])],[])or[a]

Try it online!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.