Ile partycji zawiera tylko idealne kwadraty?

16

Biorąc pod uwagę nieujemną liczbę całkowitą lub listę cyfr, określ, na ile sposobów można utworzyć liczbę, łącząc liczby kwadratowe, które mogą mieć zera wiodące.

Przykłady

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]

Zasady

  • Obowiązują standardowe luki
  • To jest więc wygrywa najkrótsza odpowiedź w bajtach
HyperNeutrino
źródło
1
Piaskownica
HyperNeutrino,
Czy możemy przyjmować dane wejściowe jako listę cyfr?
całkowicie ludzki,
dlaczego 1 -> 1, ale 0 -> 0?
Jonah
@Jonah Typo ... xD
HyperNeutrino
1
@totallyhuman Sure.
HyperNeutrino,

Odpowiedzi:

7

Haskell , 135 bajtów

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]

Wypróbuj online!

Prawdopodobnie jeszcze nie dobrze grał w golfa, ale jest to zaskakująco trudny problem

Post Rock Garf Hunter
źródło
7

Galaretka , 8 bajtów

ŒṖḌƲẠ€S

Monadyczny link pobierający listę cyfr i zwracający nieujemną liczbę całkowitą.

Wypróbuj online! lub zobacz pakiet testowy .

W jaki sposób?

ŒṖḌƲẠ€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
Jonathan Allan
źródło
6

Haskell , 88 bajtów

f x=sum[0.5|y<-mapM(\c->[[c],c:" "])x,all((`elem`map(^2)[0..read x]).read).words$id=<<y]

Definiuje funkcję, fktóra pobiera ciąg i zwraca liczbę zmiennoprzecinkową. Bardzo wolno. Wypróbuj online!

Wyjaśnienie

Używam mojej wskazówki Haskell do obliczania wszystkich partycji ciągu za pomocą mapMi words. Fragment kodu mapM(\c->[[c],c:" "])xzastępuje każdy znak 'c'ciągu łańcuchem xjednoelementowym "c"lub dwuelementowym "c "i zwraca listę wszystkich możliwych kombinacji. Jeśli wezmę jeden z wyników, ypołącz go i wywołam words, zostanie on podzielony na wstawione spacje mapM. W ten sposób uzyskuję wszystkie partycje xciągłych podciągów. Następnie liczę te wyniki, w których każdy element partycji jest kwadratem idealnym (znajdując go na liście [0,1,4,9,..,x^2]). Zastrzeżeniem jest to, że każda partycja jest liczona dwukrotnie, z końcem spacji i bez, więc biorę sumę0.5 s zamiast 1s; właśnie dlatego typ wyniku jest liczbą zmiennoprzecinkową.

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.
Zgarb
źródło
4

Python 3 , 148 139 135 134 bajtów

10 bajtów dzięki Arnoldowi Palmerowi.

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)

Wypróbuj online!

Leaky Nun
źródło
Chciałbym dokładnie to sprawdzić, ale uważam, że to działa. 140 znaków.
Arnold Palmer
I goofed i pozostawia przestrzeń między %1i for...
Arnold Palmer
Zastąpienie [[a[0]]]go [a[:1]]uratuje bajt
Arnold Palmer
Razem rozgromiliśmy Haskella.
Leaky Nun
Najlepsze jest to, że częściowo było to możliwe dzięki zestawom, których nigdy nie użyłem, dopóki nie napisałeś wczoraj na mojej żółwie .
Arnold Palmer
2

Mathematica, 141 bajtów

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


wejście (lista cyfr)

[{1,6,4}]

J42161217
źródło
Myślę, że to daje złą odpowiedź dla 1649: liczę trzy partycje, które czynią kwadratów (czyli {1,64,9}, {16,4,9}i {16,49}), ale przywracany funkcyjne 4.
Nie drzewie
Zauważyłem też, że Table[(function of s[[i]]),{i,Length[s=(stuff)]}]kilka razy używasz konstrukcji ; zazwyczaj możesz to zagrać w golfa (function of #)&/@(stuff).
Nie drzewo,
1
@Notatree masz absolutną rację! Wprowadziłem wiele zmian, postępowałem zgodnie z instrukcjami i działa to jak urok! dzięki
J42161217,
2

Python 2 , 173 163 bajty

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

Wypróbuj online!

Edycja: Zapisano 10 bajtów dzięki ArnoldPalmer

Chas Brown
źródło
1
Czy możesz zapisać bajt, używając .5zamiast 0.5?
numbermaniac
Możesz. Możesz także zapisać niektóre bajty za pomocą tej samej sztuczki, którą podjąłem w poście napisanym przez Leaky Nun w Python 3. Ponadto twoja odpowiedź nie wypisała liczby elementów, ale same elementy, więc dodałem to. Jeśli chcesz zachować otrzymane dane wyjściowe, jest to minus 5 dodatkowych bajtów. 163 bajty
Arnold Palmer
Niezła sztuczka ze zrozumieniem, Arnold.
Chas Brown