Saatnya menghitung

14

pengantar

Ini adalah salah satu teka-teki matematika favorit saya.

Diberi angka (katakanlah 3) dan berapa kali menggunakan angka itu (katakanlah 5), hasilkan 10 ekspresi yang menghasilkan 1, 2, 3, 4, 5, 6, 7, 8, 9 dan 10 menggunakan just +, -, ×, ÷, ^ dan √ (root) (tanda kurung diperbolehkan untuk operasi grup).

Sebagai contoh:

(3^3 + 3)/(3 + 3) = (33 - 3)/(3 + 3) = 3 + 3/3 + 3/3 = 5

Perhatikan bahwa semua di atas menggunakan lima 3 dan operasi matematika dan hasil ke 5. Anda juga dapat menggunakan 3 sebelum √ untuk menunjukkan akar pangkat tiga. Hal yang sama berlaku untuk menggunakan 4 sebelum √ untuk menunjukkan akar keempat.

Juga perhatikan bahwa dua 3 dapat digunakan untuk membentuk 33, atau tiga 3 dapat digunakan untuk membentuk 333 dan seterusnya.

Tantangan

  • Anda akan diberi dua angka (keduanya mulai dari 1 hingga 5) sebagai argumen fungsi, STDIN atau argumen baris perintah.
  • Angka pertama menunjukkan digit mana yang digunakan dan angka kedua menunjukkan berapa kali digit itu digunakan dalam ekspresi.
  • Program Anda harus menampilkan array ukuran 10 (atau 10 angka yang dipisahkan spasi) di mana setiap elemen menunjukkan apakah ekspresi matematika (hanya menggunakan operator yang diizinkan) yang menghasilkan (index + 1)angka tersebut mungkin atau tidak menggunakan nilai kebenaran / kepalsuan.

Misalnya, jika inputnya adalah

1 3

Maka output seharusnya

[1, 1, 1, 0, 0, 0, 0, 0, 0, 1]

karena hanya 1, 2, 3 dan 10 yang dapat diekspresikan menggunakan tiga 1.

Skor

  • Ini adalah sehingga panjang kode minimum dalam byte menang.

Bonus

Cetak-em-semua [−50]

Kurangi 50 dari skor Anda jika elemen array output sama dengan jumlah total kombinasi yang masuk akal untuk mendapatkan (index + 1)nilai alih-alih nilai jujur ​​atau palsu.

Sebagai contoh, jika hanya ada 3 kemungkinan kombinasi dari lima 3 yang menghasilkan 5, maka entri ke- 4 larik keluaran haruslah 3.

Matematika Ekstrim [−100]

Kurangi 100 dari skor Anda jika elemen array output mengandung setidaknya satu dari ekspresi aktual yang menghasilkan (index + 1)nilai.

Misalnya, jika menggunakan lima 3, entri ke- 4 larik keluaran dapat berupa (3^3 + 3)/(3 + 3), (33 - 3)/(3 + 3)atau3 + 3/3 + 3/3

Berlebihan [−200]

Kurangi 200 dari skor Anda jika elemen array keluaran berisi semua kemungkinan kombinasi (dipisahkan oleh |). Bonus ini ditambahkan di atas bonus Matematika Ekstrim , sehingga Anda mendapatkan total −300.

Misalnya, jika menggunakan lima 3, elemen ke- 4 larik keluaran harus(3^3 + 3)/(3 + 3)|(33 - 3)/(3 + 3)|3 + 3/3 + 3/3

Catatan: Setiap dua ekspresi untuk mencapai hasil yang sama harus berbeda secara logis dengan pendekatan yang berbeda di keduanya.

Misalnya, untuk mendapatkan 5 menggunakan lima 3, 3 + 3/3 + 3/3sama 3/3 + 3 + 3/3atau 3/3 + 3/3 + 3karena pendekatan yang sama diambil untuk masing-masing. (3^3 + 3)/(3 + 3)dan (33 - 3)/(3 + 3)berbeda, karena 30 dalam pembilang dicapai melalui pendekatan yang berbeda.

UPDATE : Setelah melalui semua jawaban, ditemukan bahwa semua jawaban memiliki ketidaksempurnaan karena kasus tepi unary -dan √. Dengan demikian, melewatkan kasus tepi itu dianggap oke sejauh kelengkapan jawaban terlibat.

Ini adalah pertanyaan yang sulit, tetapi yang agak menarik.

Selamat bermain golf!

Pengoptimal
sumber
1
Maaf, ini mungkin bodoh, tapi bagaimana Anda mendapatkan 10 hanya dengan tiga 1s?
FryAmTheEggman
3
@FryAmTheEggman 11-1
Pengoptimal
1
Ah, jadi saya bodoh: p
FryAmTheEggman
4
Itu aturan yang sangat kabur. Saya dapat memutuskan bahwa akar kuadrat dari 1, akar kuadrat dari akar kuadrat dari 1, dll. Semuanya merupakan pendekatan yang berbeda dan saya memiliki jumlah jawaban yang tidak terbatas. Apakah a + b berbeda dari b + a? Apakah (-a) * (-b) berbeda dari b * a?
feersum
2
Saya mengetahui hal ini, tetapi saya tidak dapat mewakili 4 ^ (4 ^ (4 ^ (4 ^ 4)))) dalam format angka biasa - menyimpan 4 ^ (4 ^ (4 ^ 4)) sebagai bilangan bulat membutuhkan lebih banyak bit daripada ada atom di alam semesta). Jadi, kecuali saya menggunakan sistem aljabar komputer yang mampu menangani angka-angka seperti itu (jika ada sama sekali), saya perlu memperlakukan ini sebagai kasus khusus. Namun ini hampir pasti membutuhkan lebih banyak karakter daripada yang saya menangkan dengan berlebihan. Karenanya penghargaan ini tidak ada gunanya kecuali Anda mengecualikan beberapa akar kuadrat.
Wrzlprmft

Jawaban:

1

Python 3 (tidak sempurna), 449 - 300 = 149

Menderita semua kekurangan yang sama dengan solusi KSab : tidak ada operator unary, yang dipasangkan sepenuhnya, mengandung ekspresi yang sama seperti (1+1)+1dan 1+(1+1). Saya menghilangkan duplikat yang tepat dengan meneruskan hasilnya ke set(). Outputnya bisa sedikit lebih buruk untuk menghemat beberapa byte, tapi saya suka cara ini. Saya juga tidak melakukan nth root karena sepertinya mereka tidak banyak memberi Anda masalah ini.

R=range
E=lambda z:eval(z.replace("^","**"))
def m(d,n):_=R(1,11);s={i:[]for i in _};r=R(1,n);n<2 and s[d].append(str(d));d=str(d);t=[[(d*i,i)for i in r]]+[[]]*n;h=[];[(h.append("("+A+o+B+")"),t[l].append((h[0],a+b))if a+b<n else E(*h)in _ and s[E(*h)].append(h[0]),h.pop())for l in r for j in R(l)for A,a in t[j]for k in R(l)for B,b in t[k]if a+b<=n for o in"+-*/^"if(o=="^"and-~-(0<E(B)<9)or 0==E(B)and"/"==o)-1];[print(i,set(s[i])or'')for i in _]

Ini akan memakan waktu beberapa menit untuk dijalankan jika argumen kedua adalah 5. Tes dengan menelepon m(digit, number):

>>> m(1,3)
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/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)'}
2 {'(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)'}
3 {'((1+1)+1)', '(1+(1+1))'}
4 
5 
6 
7 
8 
9 
10 {'(11-1)'}
>>> m(3,3)
1 {'((3/3)^3)'}
2 {'(3-(3/3))', '((3+3)/3)'}
3 {'(3-(3-3))', '((3-3)+3)', '((3/3)*3)', '(3*(3/3))', '(3/(3/3))', '((3+3)-3)', '(3^(3/3))', '(3+(3-3))', '((3*3)/3)'}
4 {'((3/3)+3)', '(3+(3/3))'}
5 
6 {'((3*3)-3)'}
7 
8 
9 {'(3+(3+3))', '((3+3)+3)', '((3^3)/3)'}
10 
DLosc
sumber
4

Python (tidak sempurna) 493 474 - 300 = 174

Ada sejumlah masalah dengan solusi ini, pertama bahwa ia mengabaikan eksponen yang terlalu besar (apa pun di mana eksponen lebih besar dari 100). Saya sebenarnya tidak berpikir ini menghilangkan kemungkinan input kurang dari atau sama dengan 5, tapi saya tidak 100% yakin.

Hal lain adalah bahwa ia tidak mempertimbangkan akar kuadrat apapun, karena akan menjadi rumit (solusi apa pun dengan istilah apa pun yang sama dengan 0 atau 1 akan menghasilkan jumlah solusi yang tak terbatas). Itu juga tidak mempertimbangkan negasi unary (simbol '-') untuk alasan yang sama, dan juga fakta bahwa saya tidak benar-benar yakin jika pertanyaannya diajukan.

Saya juga mempertimbangkan kriteria apa yang harus memutuskan jika dua ekspresi adalah setara, tetapi saya tidak dapat menemukan cara untuk mendefinisikannya secara ketat dengan cara yang saya temukan intuitif, jadi (setidaknya untuk saat ini) saya tidak menerapkan hal seperti itu. Ini berarti bahwa itu menghasilkan beberapa hasil, dan juga menggunakan tanda kurung dengan cara yang cukup naif.

Di samping catatan saya pikir ini mungkin termasuk baris kode terpanjang yang pernah saya tulis, terutama sebelum golf sepenuhnya.

R=range
F=lambda s:lambda a,b:eval(s)
L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)|(b>99)else a**b")),('v',F("b**(1./a)if a and(a>=0 or b)and(b>=0 or int(1./a)==1./a)&(1./a<99)else''"))]if o(u,v)!='']
A=L(*input())
for i in R(11):
 for v,s in A:
    if v==i:print i,s[1:-1]

Contoh: ('v' mewakili '√')

2,3

0 2*(2-2)
0 2v(2-2)
0 (2-2)*2
0 (2-2)/2
0 (2-2)^2
1 2^(2-2)
1 2-(2/2)
1 2v(2/2)
1 (2/2)^2
2 2v(2+2)
2 2+(2-2)
2 2-(2-2)
2 2v(2*2)
2 2*(2/2)
2 2/(2/2)
2 2^(2/2)
2 2v(2^2)
2 (2+2)-2
2 (2+2)/2
2 (2-2)+2
2 (2*2)-2
2 (2*2)/2
2 (2/2)*2
2 (2/2)v2
2 (2^2)-2
2 (2^2)/2
3 2+(2/2)
3 (2/2)+2
6 2+(2+2)
6 2+(2*2)
6 2+(2^2)
6 (2+2)+2
6 (2*2)+2
6 (2^2)+2
8 2*(2+2)
8 2*(2*2)
8 2*(2^2)
8 (2+2)*2
8 (2*2)*2
8 (2^2)*2
KSab
sumber
Saya menemukan beberapa hal yang dapat Anda lakukan untuk mempersingkat L:L=lambda D,N:[(int(str(D)*N),str(D)*N)]+[(o(u,v),"(%s%s%s)"%(s,c,t))for p in R(1,N)for u,s in L(D,p)for v,t in L(D,N-p)for c,o in[('+',F('a+b')),('-',F('a-b')),('*',F('a*b')),('/',F("1.*a/b if b else''")),('^',F("''if(a<0 and int(b)!=b)|(a and b<0)or b>100 else a**b")),('v',F("''if a==0 or(b<0 and int(1./a)!=(1./a))or(b or a<0)or(1./a)>100 else b**(1./a)"))]if o(u,v)!='']
FryAmTheEggman
Maaf, komentar itu terlihat sangat buruk :( Lagi pula, untuk menjelaskan: ketika membandingkan dengan 0, saya mencoba untuk meniadakan pernyataan, kemudian menukar konsekuensinya. Saya juga menemukan beberapa tempat untuk digunakan |dan &bukannya ordan and. Kedua trik ini dapat digunakan untuk mempersingkat panggilan terakhir ke F, tetapi yang satu membutuhkan beberapa Demorgan dan saya kehabisan waktu paruh; p
FryAmTheEggman
@FryAmTheEggman Oh itu bagus, saya sudah memperbarui jawaban saya dengan apa yang Anda posting dan ketika saya punya waktu saya akan melihat yang terakhir. Persyaratan untuk memeriksa validitas input memang lebih kuat daripada yang saya perkirakan: /
Persyaratan
+10 untuk kecemerlangan lambda bersarang dan - evalbutuh waktu cukup lama untuk mencari tahu baris kedua Anda! Saya pikir saya membuat Anda mengalahkan pada "baris tunggal terpanjang," meskipun. ;) Saya setuju untuk mengabaikan eksponen besar; sebenarnya, saya pikir eksponen yang lebih besar dari 9 tidak akan berguna (kecuali sebagai no-op ketika basisnya 1).
DLosc
@ Duposc Yah, satu skenario yang bisa Anda miliki adalah sesuatu seperti 3 = 33 √ (3 ^ 33). Sebenarnya ketika saya menulis ini saya menyadari bahwa dua (mungkin hanya dua?) Kombinasi yang saya lewatkan4 = (4^4) √ (4 ^ (4^4)) dan ekspresi yang setara dengan 5s. Memang root tampaknya tidak menambah banyak masalah, karena sebagian besar dari mereka baik digunakan sebagai no-ops pada 0 atau 1, no-ops ketika root adalah 1, atau hanya untuk membatalkan kekuatan.
KSab
3

Python 3 - 349 346

r=range
l=lambda s:eval("lambda a"+s)
def T(u,f,X,Y):
    try:return u(f(X,Y))
    except:0
c=l(',x:{x}.union(*[{u(int("1"*a)*x)}|{T(u,f,X,Y)for j in r(1,a)for X in c(j,x)for Y in c(a-j,x)for f in[l(",b:a%sb"%o)for o in{"**"}|set("+-*/")]+[l(",b:a**b**-1")]}for u in[l(":-a")]+[l(":a**.5**%i"%k)for k in r(9)]])')
R=l(",i:[{n+1}<c(i,a)for n in r(10)]")

Berikut ini adalah versi yang agak tidak bercabang:

def R(x,i):
    # Unary Operations
    U = [lambda a:-a] + [eval("lambda a:a**(1/2.**%i)" % j) for j in range(9)]
    # Binary Operations
    F = [eval("lambda a,b:a%sb"%o) for o in ["+","-","*","/","**"]] + [lambda a,b:a**(1./b)]

    def combos(i):
        L = {x}
        for u in U:
            # 3, 33, 333, etc.
            L |= {u(int(str(x)*i))}

            for j in range(1,i):
                for X in combos(j):
                    for Y in combos(i-j):
                        for f in F:
                            # To avoid trouble with division by zero, overflows and similar:
                            try:
                                L |= {u(f(X,Y))}
                            except:
                                pass
        return L

    return [n in combos(i) for n in range(1,11)]

Untuk pengujian saya sarankan untuk mengubah (9)ke sesuatu yang lebih kecil, karena ini adalah jumlah dari beberapa akar kuadrat yang diperhitungkan, yang memiliki dampak besar pada kinerja.

Akhirnya, ini membuat saya bertanya-tanya, apakah minus unary sebenarnya diperlukan dalam beberapa kasus ...

Wrzlprmft
sumber
1
Saya pikir Anda benar tentang unary '-' mungkin tidak menambahkan apa pun (setidaknya ke pertanyaan dasar tanpa bonus). Satu-satunya skenario non-sepele yang dapat saya pikirkan adalah sesuatu seperti 1 = 3^3 * 3^(-3), tetapi bahkan mempertimbangkan ini, saya ragu ada angka yang ini merupakan solusi yang mungkin ketika tidak ada yang lain.
KSab
1
Anda dapat menyimpan 3 byte dengan menggunakan a**.5**%ialih-alih a**(1/2**%i)menghitung beberapa akar kuadrat.
DLosc
@Dosc: Memang, terima kasih.
Wrzlprmft
Anda dapat menghemat enam byte dengan mengurangi indentasi empat ruang menjadi satu ruang.
Beta Decay
@BetaDecay: Saya tidak pernah menggunakan indentasi empat ruang (ngeri), saya menggunakan tab. Lihat saja sumber posting saya. Stack Exchange hanya menjadikannya empat ruang.
Wrzlprmft
2

Mathematica - 246 karakter (tidak ada bonus diklaim)

f[x_,y_]:=x-y
g[x_,y_]:=x/y
h[x_,y_]:=x^(1/y)
j[x_,y_]:=FromDigits@Join[IntegerDigits@x,{y}]
z[{r_,n_,L_}]:=z[{L[[1]][r,n],n,Rest@L}]
z[{r_,n_,{}}]:=r
a[n_,t_]:=Union@Select[z[{n,n,#}]&/@Tuples[{Plus,f,Times,g,Power,h,j},t-1],IntegerQ@#&&0<#<11&]

Penjelasan

Fungsi jmenggabungkan dua angka digit-bijaksana.

Fungsi zmengambil hasil r, jumlah n, dan daftar fungsiL , masing-masing yang beroperasi pada dua argumen. Itu kemudian menerapkan daftar fungsi secara berurutan ke argumen [r,n]menggunakan rekursi, sampai daftar kosong, di mana ia mengembalikan hasilnya.

Fungsinya amengambil sejumlah ndan sejumlah salinant . Itu membuat semua tuple panjang (t-1) dari daftar fungsi {Plus, f, Times, g, Power, h, j}dan mengirimkan setiap tuple melalui fungsi z, kemudian mengembalikan daftar semua angka 1 hingga 10 yang telah dibuat.

Contoh eksekusi a[2,3] kembali {1, 2, 3, 6, 8}.

Keterbatasan

Karena daftar fungsi diterapkan secara berurutan, memakan satu salinan nomor setiap kali, itu dapat kehilangan beberapa kombinasi. Misalnya, ketika beroperasi pada empat berpasangan, ia akan kehilangan 22/22 = 1 karena ketidakmampuannya untuk mengevaluasi daftar fungsi yang rusak. Tentu saja, 2/2 * 2/2 = 1 mencakup kasus ini.

fosgen
sumber