Ekspresikan angka dengan hanya 0-9 dan empat operasi

14

Penjelasan

Befunge adalah program dua dimensi yang menggunakan tumpukan .

Itu berarti, untuk melakukan 5 + 6, Anda menulis 56+, yang berarti:

56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)

Namun, seperti yang diamati oleh kecerdasan Anda, kami tidak dapat mendorong nomornya 56langsung ke tumpukan.

Untuk melakukannya, kita harus menulis 78*sebaliknya, yang mengalikan 7dan 8dan mendorong produk ke dalam stack.

Detail

Input dapat diambil dalam format apa pun, artinya bisa STDIN atau tidak, atas kebijakan programmer.

Input akan berupa bilangan bulat positif (tidak ada bonus untuk menyertakan 0atau bilangan bulat negatif).

Outputnya akan berupa string yang hanya terdiri dari karakter-karakter ini: 0123456789+-*/(Saya tidak akan menggunakan %modulo.)

Tujuannya adalah untuk menemukan string terpendek yang dapat mewakili input, menggunakan format yang dijelaskan di atas.

Misalnya, jika inputnya adalah 123, maka outputnya adalah67*99*+ . Keluaran harus dievaluasi dari kiri ke kanan.

Jika ada lebih dari satu output yang dapat diterima (mis. 99*67*+Juga dapat diterima), ada yang bisa dicetak (tidak ada bonus untuk mencetak semuanya).

Penjelasan lebih lanjut

Jika Anda masih tidak mengerti bagaimana cara 67*99*+mengevaluasi 123, berikut adalah penjelasan terperinci.

stack    |operation|explanation
          67*99*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      9     push 9 to stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack

TL; DR

Program perlu menemukan string terpendek yang dapat mewakili input (angka), menggunakan format yang ditentukan di atas.

Catatan

Ini adalah tantangan , jadi kode terpendek dalam byte menang.

Disambiguasi

The -baik dapat x-yatau y-x, kebijaksanaan programmer. Namun, pilihannya harus konsisten dalam solusi. Demikian juga untuk/ .

Program sampel

Lua, 1862 bytes ( coba online )

Karena saya penulis, saya tidak akan golf sama sekali.

Penjelasan:

This uses the depth-first search method.

Lebih lanjut tentang pencarian mendalam-pertama: di sini .

Program:

local input = (...) or 81

local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, a+b)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        table.insert(temp, s..'0')
        table.insert(temp, s..'1')
        table.insert(temp, s..'2')
        table.insert(temp, s..'3')
        table.insert(temp, s..'4')
        table.insert(temp, s..'5')
        table.insert(temp, s..'6')
        table.insert(temp, s..'7')
        table.insert(temp, s..'8')
        table.insert(temp, s..'9')
        table.insert(temp, s..'+')
        table.insert(temp, s..'-')
        table.insert(temp, s..'*')
        table.insert(temp, s..'/')
    end
    for i=1,#temp do
        if input == eval(temp[i]) then
            print(temp[i])
            return
        end
    end
    samples = temp
end

Bonus

Kue untuk Anda jika Anda menggunakan Befunge (atau varian lainnya) untuk menulis kode.

Biarawati Bocor
sumber
3
Mungkin sulit untuk memutuskan, diberi jawaban, jika selalu menghasilkan string yang paling baik. Satu ide adalah untuk menghasilkan set besar katakanlah 30--50 angka dan skor dengan jumlah semua panjang string output. Namun, saya tidak yakin bagaimana menggabungkan skor itu dengan panjang kode
Luis Mendo
4
Subset dari ini .
Addison Crump
2
Menyalin pikiran saya dari obrolan : "Saya memikirkannya tetapi saya berpendapat bahwa himpunan bagian membuat semuanya lebih sederhana karena 1) tidak ada hex, 2) tidak ada float, 3) tidak ada duplikasi dan 4) hanya positif"
Sp3000
1
@CoolestVeto yang satu ini cukup berbeda untuk membatalkan jawaban lama.
Rɪᴋᴇʀ
1
@ CoolestVeto Saya pikir tantangan lain harus ditutup sebagai duplikat dari yang ini.
mbomb007

Jawaban:

4

Python 2, 278 byte

Solusi terbaik saya, yang setiap saat memberikan jawaban terpendek. (tapi sangat lambat)

def e(c):
 s=[];x,y=s.append,s.pop
 while c:
  d,c=c[0],c[1:]
  if"/"<d<":":x(d)
  else:a,b=y(),y();x(str(eval(b+d+a)))
 return int(y())
def g(v):
 s="0123456789+-*";t=list(s)
 while 1:
  for x in t:
   try:
    if e(x)==v:return x
   except:0
  t=[x+y for x in t for y in s]

Python 2, 437 byte

Solusi ini lebih panjang, tetapi sangat cepat (bukan kekerasan). Dan saya cukup yakin, itu selalu mengembalikan hasil sesingkat mungkin.

r=range;l=len;a=input()
def f(n):
 if n<=9:return str(n)
 for d in r(9,1,-1):
  if n%d==0:return f(n/d)+"%d*"%d
 h=sum(map(int,list(str(n))))%9
 return f(n-h)+"%d+"%h
m={x:f(x) for x in r(a*9)}
for b in m:
 if a-b in m and l(m[b])+l(m[a-b])+1<l(m[a]):m[a]=m[a-b]+m[b]+"+"
 if a+b in m and l(m[b])+l(m[a+b])+1<l(m[a]):m[a]=m[a+b]+m[b]+"-"
 if b!=0 and a%b==0 and a/b in m and l(m[b])+l(m[a/b])+1<l(m[a]):m[a]=m[a/b]+m[b]+"*"
print m[a]
pbochniak
sumber
2
Selamat datang di PPCG ! Semoga Anda bersenang-senang di sini.
Leaky Nun
1
@ pbochinak Saya pikir saya mungkin telah menemukan yang valid. f(6551)mengembalikan 25*8*9*7+9*8+(13 karakter), sedangkan 9999***52*-(11 karakter) adalah yang lebih baik. Diverifikasi dengan evalfungsi saya sendiri di atas (dalam pertanyaan).
Leaky Nun
4
@ pbochniak Seperti komentar sebelum saya tunjukkan, jawaban ini tidak valid dalam kondisi saat ini. Disarankan untuk sementara menghapusnya saat Anda sedang mengerjakan perbaikan (jika tidak ada yang lain, untuk mencegahnya menarik downvotes).
Dennis
1
saat Anda hanya bisawhile c:
Ven
Anda dapat menggunakan ;untuk memisahkan tugas ke variabel (yang menyimpan byte dalam blok indentasi), tip ven, menyingkirkan spasi putih antara simbol dan apa pun, dan tbisa pergi.
CalculatorFeline
4

Perl, 134 133 132 128 byte

Termasuk +5 untuk -Xlp(2 tambahan karena mengandung kode ')

Jalankan dengan nomor target di STDIN:

perl -Xlp befour.pl <<< 123

befour.pl:

@1{1..9}=1..9;$.+=2,map{for$a(%1){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}%1until$\=$1{$_}}{

Ini tidak memiliki batas buatan dan secara konseptual agak efisien tetapi memiliki waktu menjalankan yang mengerikan meskipun saya mengorbankan beberapa byte untuk mempercepatnya. Menghasilkan solusi panjang 11 (mis. Nomor target 6551) membutuhkan waktu sekitar 5 jam pada sistem saya.

Mengorbankan 7 byte lebih banyak membuat kecepatannya lebih tertahankan.

@1{1..9}=1..9;$.+=2,map{for$a(@a){"+-*/"=~s%.%"\$1{\$-=$a$&$_/'$1{$a}$1{$_}$&'=~/^.{$.}\$/}||=\$&"%eegr}}@a=keys%1until$\=$1{$_}}{

17 menit untuk solusi panjang 11, sekitar 5 jam untuk solusi panjang 13. Nomor pertama yang membutuhkan panjang 15 adalah 16622 yang memakan waktu sekitar 2 hari. Angka pertama yang membutuhkan panjang 17 adalah 73319.

Perhatikan bahwa ia mengasumsikan bahwa divisi mengembalikan integer dengan memotong menuju 0 (sesuai spesifikasi befunge 93)

Ton Hospel
sumber
Apa yang dilakukan tanda dolar? (Saya tidak berbicara Perl sama sekali)
Leaky Nun
1
@KennyLau $mengakses nilai skalar. Di mana di sebagian besar bahasa yang Anda tulis a=4, perl akan digunakan $a=4. Tetapi juga digunakan untuk akses skalar dari variabel yang lebih kompleks. Misalnya $a{$b}mengambil dari hash (peta, kamus) %anilai skalar yang dikunci$b
Ton Hospel
2

C, 550 545 byte

#define L strlen
#define y strcpy
#define t strcat
char c[9999][99];i=1,k=3;main(j){for(;i<10;i++)*c[i]=i+'0';for(;k--;){
for(i=1;i<9999;i++)for(j=1;j<=i;j++)*c[i]&&*c[j]&&(i+j>9998||*c[i+j]&&
L(c[i+j])<L(c[i])+L(c[j])+2||t(t(y(c[i+j],c[i]),c[j]),"+"),
i*j>9998||*c[i*j]&&L(c[i*j])<L(c[i])+L(c[j])+2||t(t(y(c[i*j],c[i]),c[j]),"*"));
for(i=9999;--i;)for(j=i;--j;)*c[i]&&*c[j]&&(*c[i/j]&&
L(c[i/j])<L(c[i])+L(c[j])+2||t(t(y(c[i/j],c[i]),c[j]),"/"),
*c[i-j]&&L(c[i-j])<L(c[i])+L(c[j])+2||t(t(y(c[i-j],c[i]),c[j]),"-"));}
scanf("%d",&i);printf("%s",c[i]);}

550 545 byte setelah menghapus baris baru yang tidak perlu (semua kecuali tiga baris baru setelah arahan preprocessing).

@ Kenny Lau - Dapat menerima input integer antara 1 dan 9998, tapi saya pikir rentang input yang solusi optimalnya dihitung lebih kecil dari 9998. Di sisi lain, kedua rentang dapat diperpanjang, jika memori memungkinkan itu.

Program tidak dapat mendorong ke tumpukan nomor lebih tinggi dari 9998. (9998 dapat dimodifikasi.) Saya menjalankan program dalam versi yang berbeda, iterasi di atas loop luar (yang dengan k) selama ada perbaikan untuk nomor apa pun antara 1 dan 9998 (seperti dalam algoritma Dijkstra). Setelah tiga iterasi tidak ada perbaikan. Jadi untuk menghemat byte, saya hardcode k = 3.

Untuk memperluas jangkauan, dua hal diperlukan - memodifikasi konstanta 9999 dan 9998, menjalankannya dengan sejumlah variabel iterasi di atas loop outter selama ada perbaikan, untuk melihat berapa lama waktu sampai tidak ada peningkatan, kemudian ubah konstanta k = 3 ke nilai itu.

mIllIbyte
sumber
Selamat datang di PPCG ! Semoga Anda bersenang-senang di sini.
Leaky Nun
Ini melewati tes 6551 saya dengan sempurna. Apa kisaran efektif program ini?
Leaky Nun
Saya percaya ini adalah 9999. Bisakah Anda menambahkan informasi ini ke solusi Anda?
Leaky Nun
Ini harus 9998. Juga, Anda dapat makan beberapa byte dengan menginisialisasi i, jdan ksebelum main().
Leaky Nun
1
@Kenny Lau - Terima kasih atas hasil editnya. Tentang memperluas jangkauan, saya perhatikan bahwa sebenarnya dibutuhkan sedikit lebih banyak untuk memperluas jangkauan. Saya memasukkan informasi itu dalam jawabannya.
mIllIbyte
2

Python 2, 284 byte

Penafian: Mengalami ketakutan selamanya untuk beberapa nilai ... tetapi harus dijamin untuk selalu mengembalikan string terpendek, dan tidak memiliki batas rentang yang diberlakukan secara artifisial ... bahkan bekerja pada nilai negatif. :)

def f(v):
 i,z=0,'+-*/'
 while 1:
  s=('%x'%i).translate(__import__('string').maketrans('abcd',z),'ef');t=s;q=[];a,p=q.append,q.pop;i+=1
  try:
   while t:
    o,t=t[0],t[1:]
    if o in z:n,m=p(),p();a(eval(`m`+o+`n`))
    else:a(int(o))
   if p()==v and not q:return s
  except:pass

Algoritma:

  • Dimulai dari i = 0
  • Ambil string yang mewakili nilai hex i, dan ganti abcddengan +-*/masing - masing, dan hapusef
  • Mencoba memproses string sebagai notasi postfix (RPN)
  • Jika berhasil, dan hasilnya cocok dengan nilai input, kembalikan string yang digunakan.
  • Jika tidak, tambahkan idan coba lagi.
Ken 'Joey' Mosher
sumber
"[t] lakukan [...] selamanya untuk beberapa nilai" Sudahkah Anda mengujinya? Nilai apa?
Leaky Nun
@ KennyLau Saya baru saja menulis tes yang menghitung f(i)dari 0 <= i <= 6551(untuk menangkap 6551nilai yang Anda gunakan untuk membatalkan pengajuan asli @pbochniak). Saat ini, sudah berjalan hanya beberapa menit, dan inilah output terakhir dari tes ini: 91 : 49+7* 3.020 s (total 108.174 s, worst 89: 5.827 s) Pembaruan - baru saja selesai dengan nilai 92: 92 : 149+7*+ 258.761 s (total 366.935 s, worst 92: 258.761 s)
Ken 'Joey' Mosher
@ KennyLau: Tes telah berjalan lebih dari satu jam, dan hanya sampai dengan nilai 113... lihat hasil tes lengkap di sini (pastebin) jika Anda tertarik ...
Ken 'Joey' Mosher
2

Python 2, 182 byte

n=input()
L=[[[],""]]
while 1:
 s,c=L.pop(0);L+=[[s+[i],c+`i`]for i in range(10)]+(s[1:]and[[s[:-2]+[eval(`s[-2]`+o+`s[-1]`)],c+o]for o in"/+-*"[s[-1]==0:]])
 if[n]==s[-1:]:print c;E

Sangat lambat, saya membiarkannya berjalan selama satu jam pada input 221dan masih belum dihentikan. Sebagian besar kelambatan adalah karena saya menggunakan daftar sebagai antrian untuk pencarian pertama kali, dan .pop(0)memang demikianO(n) untuk daftar.

Lhanyalah sebuah antrian yang berisi (stack, code to reach stack)pasangan. Pada setiap langkah, angka selalu ditambahkan, dan operator dilakukan jika tumpukan memiliki setidaknya dua elemen. Pembagian hanya dilakukan jika elemen terakhir bukan 0, meskipun saya memiliki kecurigaan kuat bahwa pembagian tidak perlu (walaupun saya tidak punya cara untuk membuktikannya, tetapi saya telah memeriksa ini adalah kasus hingga 500).

Program berakhir melalui NameErrorsetelah mencetak hasilnya (akhirnya).

Sp3000
sumber
Apa yang ;Epada akhirnya dilakukan?
Leaky Nun
@ KennyLau Itulah NameErroruntuk penghentian, karena Etidak ditentukan di tempat lain
Sp3000
Wow, kepintarannya seperti itu.
Leaky Nun
1

CJam, 79

ri:M;A,:s:L;{L2m*{s,Y=},{~:A+AS*~!"/+-*">\f{\+}~}%Y2+:Y;_L@+:L;{S*~M=},:R!}gR0=

Cobalah online

Ini sangat tidak efisien, tetapi mengingat ingatan dan waktu yang cukup, akhirnya bekerja. Memori kehabisan 123 dengan 16GB, tetapi 120 dan 125 baik-baik saja.

aditsu berhenti karena SE adalah JAHAT
sumber
1

Pyth - 35 byte

Paksaan. Yang aneh adalah bahwa input implisit baru benar-benar menyakiti skor saya karena tampaknya juga berfungsi untuk .vpyth_eval.

.V1IKfqQ.x.v+jd_T\;N^s+"+-*/"UTbhKB

Cobalah online di sini .

Maltysen
sumber
0

Python 3, 183 byte

e,n=enumerate,input()
v=list('0123456789')+[' '*n]*n*2
for i,s in e(v):
 for j,t in e(v):
  for o,k in zip('+*-',(i+j,i*j,i-j)):
   if 9<k<2*n:v[k]=min(v[k],s+t+o,key=len)
print(v[n])

Kecepatan tidak sepenuhnya tidak masuk akal (123, 221, 1237, 6551 selesai dalam urutan detik atau menit). Mengubah ifpernyataan untuk if j<=i and <k<2*nmempercepatnya lebih banyak, dengan biaya 9 byte lebih banyak. Saya meninggalkan divisi ( /), karena saya tidak dapat melihat bagaimana itu akan diperlukan.

RootTwo
sumber
Petunjuk: diperlukan pembagian.
Leaky Nun