16
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Sandbox Post \$\endgroup\$ – HyperNeutrino Jul 17 '17 at 23:43
  • \$\begingroup\$ Can we take input as a list of digits? \$\endgroup\$ – totallyhuman Jul 18 '17 at 0:31
  • \$\begingroup\$ why is 1 -> 1 but 0 -> 0? \$\endgroup\$ – Jonah Jul 18 '17 at 0:52
  • \$\begingroup\$ @Jonah Typo... xD \$\endgroup\$ – HyperNeutrino Jul 18 '17 at 1:31
  • 1
    \$\begingroup\$ @totallyhuman Sure. \$\endgroup\$ – HyperNeutrino Jul 18 '17 at 1:31
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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]

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.
\$\endgroup\$
4
\$\begingroup\$

Pyth, 16 bytes

lf!f!sI@sjkY2T./

Test suite.

\$\endgroup\$
4
\$\begingroup\$

Python 3, 148 139 135 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!

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

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Not a tree Jul 18 '17 at 12:17
  • \$\begingroup\$ 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). \$\endgroup\$ – Not a tree Jul 18 '17 at 12:20
  • 1
    \$\begingroup\$ @Notatree you are absolutely right! I made many changes, followed your instructions and it works like a charm! thanks \$\endgroup\$ – J42161217 Jul 18 '17 at 17:35
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you save a byte by using .5 instead of 0.5? \$\endgroup\$ – numbermaniac Jul 18 '17 at 8:22
  • \$\begingroup\$ 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 \$\endgroup\$ – Arnold Palmer Jul 18 '17 at 12:44
  • \$\begingroup\$ Nice trick with set comprehension, Arnold. \$\endgroup\$ – Chas Brown Jul 18 '17 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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