Bestimmen Sie bei einer nicht negativen Ganzzahl oder einer Liste von Ziffern, auf wie viele Arten die Zahl durch Verketten von Quadratzahlen gebildet werden kann, die führende Nullen haben können.

Beispiele

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]

Regeln

• Es gelten Standardlücken
• Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes

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]

Probieren Sie es online!

Wahrscheinlich noch nicht gut golfen, aber das ist ein überraschend schwieriges Problem

Gelee , 8 Bytes

ŒṖḌƲẠ€S

Ein monadischer Link, der eine Liste von Ziffern aufnimmt und eine nicht negative Ganzzahl zurückgibt.

Probieren Sie es online! oder sehen Sie sich die Testsuite an .

Wie?

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

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]

Definiert eine Funktion f, die eine Zeichenfolge akzeptiert und einen Gleitkommawert zurückgibt. Sehr langsam. Probieren Sie es online!

Erläuterung

Ich verwende meinen Haskell-Tipp zum Berechnen aller Partitionen eines Strings mit mapMund words. Das Snippet mapM(\c->[[c],c:" "])xersetzt jedes Zeichen 'c'einer Zeichenfolge xdurch die Zeichenfolge mit einem "c"oder zwei Elementen "c "und gibt die Liste aller möglichen Kombinationen zurück. Wenn ich eines der Ergebnisse nehme y, es verkette und das Ergebnis aufrufe words, wird es an den von eingefügten Stellen aufgeteilt mapM. Auf diese Weise xerhalte ich alle Partitionen von in zusammenhängende Teilzeichenfolgen. Dann zähle ich nur die Ergebnisse, bei denen jedes Partitionselement ein perfektes Quadrat ist (indem ich es in der Liste finde [0,1,4,9,..,x^2]). Eine Einschränkung ist, dass jede Partition zweimal mit und ohne Leerzeichen gezählt wird, also nehme ich die Summe von0.5s statt 1s; Aus diesem Grund ist der Ergebnistyp ein 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.

Pyth , 16 Bytes

lf!f!sI@sjkY2T./

Testsuite .

Python 3 , 148 139 135 134 Bytes

10 Bytes dank 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)

Probieren Sie es online!

Mathematica, 141 Bytes

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

Eingabe (eine Liste von Ziffern)

[{1,6,4}]

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

Probieren Sie es online!

Bearbeiten: 10 Bytes wegen ArnoldPalmer gespeichert