Berapa banyak partisi yang hanya berisi kotak yang sempurna?

16

Dengan bilangan bulat non-negatif atau daftar angka, tentukan dalam berapa cara bilangan dapat dibentuk dengan menggabungkan bilangan kuadrat, yang mungkin memiliki angka nol di depan.

Contohnya

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]

Aturan

  • Celah Standar Berlaku
  • Ini adalah sehingga jawaban tersingkat dalam byte menang
HyperNeutrino
sumber
1
Sandbox Post
HyperNeutrino
Bisakah kita mengambil input sebagai daftar digit?
totallyhuman
mengapa 1 -> 1 tetapi 0 -> 0?
Jonah
@Jonah Typo ... xD
HyperNeutrino
1
@totallyhuman Tentu.
HyperNeutrino

Jawaban:

7

Haskell , 135 byte

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]

Cobalah online!

Mungkin belum bermain golf dengan baik, tetapi ini merupakan masalah yang sangat sulit

Posting Rock Garf Hunter
sumber
7

Jelly , 8 byte

ŒṖḌƲẠ€S

Tautan monadik mengambil daftar angka dan mengembalikan bilangan bulat non-negatif

Cobalah online! atau lihat test suite .

Bagaimana?

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

Haskell , 88 byte

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

Menentukan fungsi fyang mengambil string dan mengembalikan float. Sangat lambat. Cobalah online!

Penjelasan

Saya menggunakan tip Haskell saya untuk menghitung semua partisi string dengan mapMdan words. Cuplikan mapM(\c->[[c],c:" "])xmenggantikan setiap karakter 'c'string xdengan string satu elemen "c"atau string dua elemen "c ", dan mengembalikan daftar semua kombinasi yang mungkin. Jika saya mengambil salah satu hasilnya,, ymenyatukannya dan memanggil wordshasilnya, itu akan dibagi pada spasi yang dimasukkan oleh mapM. Dengan cara ini saya mendapatkan semua partisi xmenjadi substring yang berdekatan. Lalu saya hanya menghitung hasil di mana setiap elemen partisi adalah kuadrat sempurna (dengan menemukannya dalam daftar [0,1,4,9,..,x^2]). Sebuah peringatan adalah bahwa setiap partisi dihitung dua kali, dengan dan tanpa spasi tambahan, jadi saya mengambil jumlah0.5s bukannya 1s; inilah mengapa tipe hasil adalah 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.
Zgarb
sumber
4

Pyth , 16 byte

lf!f!sI@sjkY2T./

Suite uji .

bocor Nun
sumber
4

Python 3 , 148 139 135 134 byte

10 byte berkat 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)

Cobalah online!

bocor Nun
sumber
Saya akan mengecek ini, tapi saya yakin itu berhasil. 140 karakter.
Arnold Palmer
Saya melakukan kesalahan dan meninggalkan ruang antara %1dan for...
Arnold Palmer
Mengganti [[a[0]]]dengan [a[:1]]akan menghemat byte
Arnold Palmer
Bersama-sama kami mengalahkan Haskell.
Leaky Nun
Bagian terbaiknya adalah, sebagian, berkat set, yang belum pernah saya gunakan sampai Anda memposting jawaban kura - kura saya kemarin.
Arnold Palmer
2

Mathematica, 141 byte

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


input (daftar digit)

[{1,6,4}]

J42161217
sumber
Saya pikir ini memberikan jawaban yang salah untuk 1649: Saya menghitung tiga partisi yang membuat kuadrat (yaitu {1,64,9}, {16,4,9}dan {16,49}) tetapi fungsi Anda mengembalikan 4.
Bukan pohon
Juga, saya perhatikan Anda menggunakan konstruksi seperti Table[(function of s[[i]]),{i,Length[s=(stuff)]}]beberapa kali; Anda biasanya bisa bermain golf hingga ini (function of #)&/@(stuff).
Bukan pohon
1
@ Tidak, Anda benar! Saya membuat banyak perubahan, mengikuti instruksi Anda dan itu berfungsi seperti pesona! terima kasih
J42161217
2

Python 2 , 173 163 byte

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

Cobalah online!

Sunting: Disimpan 10 byte karena ArnoldPalmer

Chas Brown
sumber
1
Bisakah Anda menyimpan byte dengan menggunakan .5alih-alih 0.5?
numbermaniac
Kamu bisa. Anda juga dapat menyimpan beberapa byte dengan trik yang sama yang saya gunakan pada posting Python 3 Leaky Nun. Juga, jawaban Anda tidak mencetak jumlah elemen, tetapi elemen itu sendiri, jadi saya menambahkannya. Jika Anda ingin menjaga output yang Anda miliki, itu dikurangi tambahan 5 byte. 163 byte
Arnold Palmer
Trik yang bagus dengan pemahaman set, Arnold.
Chas Brown