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

7 Answers 7

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\$
0
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\$
6
  • \$\begingroup\$ I'd double check this, but I believe it works. 140 characters. \$\endgroup\$ Jul 18, 2017 at 12:35
  • \$\begingroup\$ I goofed and left a space between %1 and for... \$\endgroup\$ Jul 18, 2017 at 12:40
  • \$\begingroup\$ Replacing [[a[0]]] with [a[:1]] will save a byte \$\endgroup\$ Jul 18, 2017 at 12:53
  • \$\begingroup\$ Together we outgolfed Haskell. \$\endgroup\$
    – Leaky Nun
    Jul 18, 2017 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\$ Jul 18, 2017 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\$
3
  • \$\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, 2017 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, 2017 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\$
    – ZaMoC
    Jul 18, 2017 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\$
3
  • 1
    \$\begingroup\$ Can you save a byte by using .5 instead of 0.5? \$\endgroup\$ Jul 18, 2017 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\$ Jul 18, 2017 at 12:44
  • \$\begingroup\$ Nice trick with set comprehension, Arnold. \$\endgroup\$
    – Chas Brown
    Jul 18, 2017 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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