Kompleksitas Integer

29

Tugas Anda adalah menulis sebuah program yang, pada input n, mengeluarkan ekspresi minimal setiap angka 1 hingga n secara berurutan. Program terpendek dalam byte menang.

Ekspresi minimal menggabungkan 1's dengan penjumlahan dan perkalian untuk menghasilkan angka yang diberikan, menggunakan sesedikit mungkin 1's. Misalnya, 23dinyatakan 23=((1+1+1)(1+1)+1)(1+1+1)+1+1dengan sebelas, yang minimal.

Persyaratan:

  1. Program harus mengambil sebagai input bilangan asli positif n.
  2. Output harus dalam format ini: 20 = ((1+1+1)(1+1+1)+1)(1+1)
  3. Output Anda mungkin tidak memiliki tanda kurung yang tidak perlu, misalnya 8 = ((1+1)(1+1))(1+1).
  4. Tanda multiplikasi *adalah opsional.
  5. Spasi adalah opsional.
  6. Anda tidak harus mengeluarkan semua persamaan yang mungkin untuk nilai yang diberikan: Misalnya, Anda memiliki pilihan untuk menghasilkan 4=1+1+1+1atau 4=(1+1)(1+1). Anda tidak harus mengeluarkan keduanya.
  7. Program terpendek (dalam byte) di setiap bahasa menang.
1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1
6 = (1 + 1 + 1) (1 + 1)
7 = (1 + 1 + 1) (1 + 1) +1
8 = (1 + 1 + 1 + 1) (1 + 1)
9 = (1 + 1 + 1) (1 + 1 + 1)
10 = (1 + 1 + 1) (1 + 1 + 1) +1
11 = (1 + 1 + 1) (1 + 1 + 1) + 1 + 1
12 = (1 + 1 + 1) (1 + 1) (1 + 1)
13 = (1 + 1 + 1) (1 + 1) (1 + 1) +1
14 = ((1 + 1 + 1) (1 + 1) +1) (1 + 1)
15 = (1 + 1 + 1 + 1 + 1) (1 + 1 + 1)
16 = (1 + 1 + 1 + 1) (1 + 1) (1 + 1)
17 = (1 + 1 + 1 + 1) (1 + 1) (1 + 1) +1
18 = (1 + 1 + 1) (1 + 1 + 1) (1 + 1)
19 = (1 + 1 + 1) (1 + 1 + 1) (1 + 1) +1
20 = ((1 + 1 + 1) (1 + 1 + 1) +1) (1 + 1)

Berikut adalah beberapa kasus uji lagi: (ingat, bahwa ekspresi lain dengan angka 1 yang sama juga diperbolehkan)

157=((1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1

444=((1+1+1)(1+1+1)(1+1)(1+1)+1)(1+1+1)(1+1)(1+1)

1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1

15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1

45197=((((1+1+1)(1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1)+1)(1+1+1)(1+1)(1+1)+1)(1+1+1+1+1)(1+1+1)+1+1

Semoga berhasil! - The Turtle 🐢

code-golf math arithmetic Kura-kura
sumber
1
1) Bullet # 6 Anda belum selesai (tidak ada contoh output untuk n=20) dan 2) Anda katakan di awal bahwa kompleksitas integer, yang berbeda dari persamaan, harus berupa output, tetapi Anda tidak memasukkannya dalam salah satu contoh kecuali yang pertama.
El'endia Starman
Saya masih belum jelas. Apakah Anda hanya menampilkan persamaan?
xnor
Iya nih. Kompleksitas integer tidak boleh di-output. Saya juga akan mengklarifikasi itu. Maaf atas kesalahannya. :(
The Turtle
Ups, saya katakan bullet # 6 ketika saya seharusnya mengatakan bullet # 5, dalam daftar persyaratan Anda. Adapun masalah lainnya, terima kasih telah memperbaikinya. :)
El'endia Starman
1
Terkait: oeis.org/A005245 oeis.org/A061373 dan akhirnya oeis.org/A091333
flawr

Jawaban:

10

Pyth, 60 byte

LjWqeb\1b`()L?tbho/N\1++'tb"+1"m+y'/bdy'df!%bTr2b1VSQ++N\='N

Demonstrasi

Kompiler online dapat mencapai 1223 sebelum waktu habis, berkat memoisasi fungsi otomatis Pyth.

1223=((1+1+1)(1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)(1+1+1+1+1)+1+1+1

Dalam abbrieviated notaion,

1223=(3^5+1)*5+3

Ini menggunakan fungsi rekursif ', yang menghitung semua produk possum dan jumlah yang dapat memberikan output yang diinginkan, menemukan string terpendek dengan setiap operasi akhir, kemudian membandingkannya dengan 1menghitung dan mengembalikan yang pertama.

Ini menggunakan fungsi helper y, yang mengurung ekspresi hanya jika perlu di-kurung.

Offline, saya menjalankan program dengan input 15535, dan itu hampir selesai. Hasil dicetak secara bertahap, sehingga mudah untuk melihat perkembangannya.

Baris terakhir dari output:

15535=((((1+1+1)(1+1+1)(1+1+1)(1+1+1)+1)((1+1+1)(1+1)+1)+1)(1+1+1)+1)(1+1+1)(1+1+1)+1

real    7m8.430s
user    7m7.158s
sys 0m0.945s

Dalam notasi singkat,

15535=(((3^4+1)*(3*2+1)+1)*3+1)*3^2+1
isaacg
sumber
7

CJam, 105 102 98 96 byte

q~{)'=1$2,{:I{I1$-'+}%3/1>Imf'*+aImp!*+{)\{j}%\+}:F%{e_"+*"-:+}$0=}j2,{F)_'*={;{'(\')}%1}&*}jN}/

Cobalah online di juru bahasa CJam .

Uji coba

Penerjemah online terlalu lambat untuk kasus uji yang lebih besar. Bahkan dengan Java interpreter, test case yang lebih besar akan memakan waktu yang lama dan membutuhkan memori yang signifikan.

$ time cjam integer-complexity.cjam <<< 157
1=1
2=1+1
3=1+1+1
4=1+1+1+1
5=1+1+1+1+1
6=(1+1)(1+1+1)
7=1+(1+1)(1+1+1)
8=(1+1)(1+1)(1+1)
9=(1+1+1)(1+1+1)
10=1+(1+1+1)(1+1+1)
11=1+1+(1+1+1)(1+1+1)
12=(1+1)(1+1)(1+1+1)
13=1+(1+1)(1+1)(1+1+1)
14=(1+1)(1+(1+1)(1+1+1))
15=(1+1+1)(1+1+1+1+1)
16=(1+1)(1+1)(1+1)(1+1)
17=1+(1+1)(1+1)(1+1)(1+1)
18=(1+1)(1+1+1)(1+1+1)
19=1+(1+1)(1+1+1)(1+1+1)
20=(1+1)(1+1)(1+1+1+1+1)
21=(1+1+1)(1+(1+1)(1+1+1))
22=1+(1+1+1)(1+(1+1)(1+1+1))
23=1+1+(1+1+1)(1+(1+1)(1+1+1))
24=(1+1)(1+1)(1+1)(1+1+1)
25=1+(1+1)(1+1)(1+1)(1+1+1)
26=(1+1)(1+(1+1)(1+1)(1+1+1))
27=(1+1+1)(1+1+1)(1+1+1)
28=1+(1+1+1)(1+1+1)(1+1+1)
29=1+1+(1+1+1)(1+1+1)(1+1+1)
30=(1+1)(1+1+1)(1+1+1+1+1)
31=1+(1+1)(1+1+1)(1+1+1+1+1)
32=(1+1)(1+1)(1+1)(1+1)(1+1)
33=1+(1+1)(1+1)(1+1)(1+1)(1+1)
34=(1+1)(1+(1+1)(1+1)(1+1)(1+1))
35=(1+1+1+1+1)(1+(1+1)(1+1+1))
36=(1+1)(1+1)(1+1+1)(1+1+1)
37=1+(1+1)(1+1)(1+1+1)(1+1+1)
38=(1+1)(1+(1+1)(1+1+1)(1+1+1))
39=(1+1+1)(1+(1+1)(1+1)(1+1+1))
40=(1+1)(1+1)(1+1)(1+1+1+1+1)
41=1+(1+1)(1+1)(1+1)(1+1+1+1+1)
42=(1+1)(1+1+1)(1+(1+1)(1+1+1))
43=1+(1+1)(1+1+1)(1+(1+1)(1+1+1))
44=(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
45=(1+1+1)(1+1+1)(1+1+1+1+1)
46=1+(1+1+1)(1+1+1)(1+1+1+1+1)
47=1+1+(1+1+1)(1+1+1)(1+1+1+1+1)
48=(1+1)(1+1)(1+1)(1+1)(1+1+1)
49=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)
50=(1+1)(1+1+1+1+1)(1+1+1+1+1)
51=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
52=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
53=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
54=(1+1)(1+1+1)(1+1+1)(1+1+1)
55=1+(1+1)(1+1+1)(1+1+1)(1+1+1)
56=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
57=(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
58=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
59=1+1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
60=(1+1)(1+1)(1+1+1)(1+1+1+1+1)
61=1+(1+1)(1+1)(1+1+1)(1+1+1+1+1)
62=(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
63=(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
64=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
65=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
66=(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
67=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
68=(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
69=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1)(1+1))
70=(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
71=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
72=(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
73=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
74=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
75=(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
76=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
77=1+(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
78=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
79=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
80=(1+1)(1+1)(1+1)(1+1)(1+1+1+1+1)
81=(1+1+1)(1+1+1)(1+1+1)(1+1+1)
82=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
83=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1)
84=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
85=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1))
86=(1+1)(1+(1+1)(1+1+1)(1+(1+1)(1+1+1)))
87=(1+1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
88=(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
89=1+(1+1)(1+1)(1+1)(1+1+(1+1+1)(1+1+1))
90=(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
91=1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
92=1+1+(1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
93=(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
94=1+(1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
95=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1))
96=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
97=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1+1)
98=(1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
99=(1+1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
100=(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
101=1+(1+1)(1+1)(1+1+1+1+1)(1+1+1+1+1)
102=(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
103=1+(1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
104=(1+1)(1+1)(1+1)(1+(1+1)(1+1)(1+1+1))
105=(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
106=1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
107=1+1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
108=(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
109=1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
110=1+1+(1+1)(1+1)(1+1+1)(1+1+1)(1+1+1)
111=(1+1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
112=(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
113=1+(1+1)(1+1)(1+1)(1+1)(1+(1+1)(1+1+1))
114=(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
115=1+(1+1)(1+1+1)(1+(1+1)(1+1+1)(1+1+1))
116=(1+1)(1+1)(1+1+(1+1+1)(1+1+1)(1+1+1))
117=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
118=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
119=(1+(1+1)(1+1+1))(1+(1+1)(1+1)(1+1)(1+1))
120=(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
121=1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1+1+1)
122=(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1+1+1))
123=(1+1+1)(1+(1+1)(1+1)(1+1)(1+1+1+1+1))
124=(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
125=(1+1+1+1+1)(1+1+1+1+1)(1+1+1+1+1)
126=(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
127=1+(1+1)(1+1+1)(1+1+1)(1+(1+1)(1+1+1))
128=(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
129=1+(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)(1+1)
130=(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
131=1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1))
132=(1+1)(1+1)(1+1+1)(1+1+(1+1+1)(1+1+1))
133=(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
134=1+(1+(1+1)(1+1+1))(1+(1+1)(1+1+1)(1+1+1))
135=(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
136=1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
137=1+1+(1+1+1)(1+1+1)(1+1+1)(1+1+1+1+1)
138=(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
139=1+(1+1)(1+1+1)(1+1+(1+1+1)(1+(1+1)(1+1+1)))
140=(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
141=1+(1+1)(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1))
142=(1+1)(1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1+1)))
143=(1+1+(1+1+1)(1+1+1))(1+(1+1)(1+1)(1+1+1))
144=(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
145=1+(1+1)(1+1)(1+1)(1+1)(1+1+1)(1+1+1)
146=(1+1)(1+(1+1)(1+1)(1+1)(1+1+1)(1+1+1))
147=(1+1+1)(1+(1+1)(1+1+1))(1+(1+1)(1+1+1))
148=(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
149=1+(1+1)(1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
150=(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
151=1+(1+1)(1+1+1)(1+1+1+1+1)(1+1+1+1+1)
152=(1+1)(1+1)(1+1)(1+(1+1)(1+1+1)(1+1+1))
153=(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
154=1+(1+1+1)(1+1+1)(1+(1+1)(1+1)(1+1)(1+1))
155=(1+1+1+1+1)(1+(1+1)(1+1+1)(1+1+1+1+1))
156=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))
157=1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1))

real    0m3.896s
user    0m4.892s
sys     0m0.066s

Dengan waktu yang cukup, itu akan menghasilkan solusi ini untuk kasus uji berikutnya:

444=(1+1)(1+1)(1+1+1)(1+(1+1)(1+1)(1+1+1)(1+1+1))
1223=1+1+(1+1+1)(1+1+(1+1+1)(1+1+1))(1+(1+1)(1+1)(1+1+1)(1+1+1))
Dennis
sumber
Bagaimana cara kerjanya?
flawr
@ flawr Saya masih berharap untuk bermain golf ini sedikit lebih. Saya akan menambahkan penjelasan ketika saya selesai / menyerah.
Dennis
4

Julia, 229 byte

n->(F=i->K[i]>0?E[i]:"("E[i]")";C=[1;3:n+1];K=0C;E=fill("1",n);for s=1:n for i=1:s÷2 (D=C[i]+C[s-i])<C[s]?(C[s]=D;E[s]=E[i]"+"E[s-i];K[s]=0):s%i>0||(D=C[i]+C[j=s÷i])<C[s]&&(C[s]=D;E[s]=F(i)F(j);K[s]=1)end;println("$s="E[s])end)

Ini sebenarnya cukup cepat. Menetapkan fungsi fdan menjalankan @time f(15535)memberikan output (hanya dua baris terakhir)

15535=1+(1+1+1)(1+1+1)(1+(1+1+1)(1+(1+(1+1)(1+1+1))(1+(1+1+1)(1+1+1)(1+1+1)(1+1+1))))
32.211583 seconds (263.30 M allocations: 4.839 GB, 4.81% gc time)

dan untuk @time f(45197), itu memberi

45197=1+1+(1+1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1+1)(1+(1+1)(1+1+1+1+1)(1+(1+1)(1+1)(1+1)(1+1+1))))
289.749564 seconds (2.42 G allocations: 43.660 GB, 4.91% gc time)

Jadi, apa yang dilakukan kodenya? Sederhana - Cmemegang nomor satu saat ini Cuntuk nomor tersebut, Kadalah susunan indikator yang melacak apakah ekspresi itu, pada dasarnya, jumlah atau produk, untuk tujuan berurusan dengan tanda kurung, dan Emenahan Epenekanan itu sendiri. Bekerja terus dari awal s=1hingga n, kode mencari representasi minimal angka sdalam hal nilai yang lebih rendah, dengan mencari jumlah atau produk. Jika produk, maka memeriksa dua komponen dan menempatkan tanda kurung di sekitar mereka jika jumlahnya. Pemeriksaan itu dilakukan dalam fungsi F, untuk menghemat byte (karena harus dilakukan dua kali, untuk dua faktor).

Glen O
sumber