Latar belakang meta

Ini ditetapkan sebagai pertanyaan pada membingungkan , dan reaksi instan adalah "baik, seseorang hanya akan menyelesaikannya dengan komputer". Ada perdebatan tentang betapa rumitnya sebuah program untuk menyelesaikannya. Nah, "seberapa kompleks program ini harus" cukup banyak definisi kode-golf , jadi mungkin PPCG dapat menyelesaikan masalah ini?

Latar Belakang

Sebuah persamaan batang korek api pada dasarnya adalah sebuah persamaan matematika yang normal, tetapi di mana angka dan operator dibangun secara fisik dengan menempatkan korek api ke meja. (Fitur utama yang relevan dari korek api di sini adalah bahwa mereka cukup kaku dan memiliki panjang yang konstan; kadang-kadang orang menggunakan benda lain, seperti penyeka kapas.)

Untuk tantangan ini, kita tidak perlu mendefinisikan aturan khusus tentang bagaimana mengatur korek api (seperti halnya tantangan terkait); alih-alih, kami hanya peduli tentang berapa banyak korek api yang kami perlukan untuk mewakili ekspresi yang mengevaluasi ke nomor tertentu.

Tugas

Berikut adalah alfabet digit dan operator matematika yang dapat Anda gunakan, masing-masing memiliki biaya dalam korek api:

• 0, seharga 6 batang korek api
• 1, seharga 2 batang korek api
• 2, seharga 5 batang korek api
• 3, seharga 5 batang korek api
• 4, seharga 4 batang korek api
• 5, seharga 5 batang korek api
• 6, seharga 6 batang korek api
• 7, seharga 3 batang korek api
• 8, seharga 7 batang korek api
• 9, seharga 6 batang korek api
• +, seharga 2 batang korek api
• -, seharga 1 batang korek api
• ×, seharga 2 batang korek api

(Anda dapat mewakili ×sebagai *dalam output program Anda jika Anda ingin, untuk menghindari perlu menggunakan karakter non-ASCII. Dalam kebanyakan pengkodean, ×membutuhkan lebih banyak byte daripada *, dan jadi saya membayangkan bahwa sebagian besar program akan ingin memanfaatkan kelonggaran ini .)

Anda perlu menulis sebuah program yang menggunakan integer nonnegatif sebagai input (melalui cara yang masuk akal ), dan menghasilkan ekspresi yang mengevaluasi integer sebagai output (sekali lagi melalui cara yang masuk akal). Selain itu, ekspresi harus trivial: itu harus mengandung setidaknya satu operator +, -atau× . Akhirnya, ekspresi yang Anda hasilkan harus yang termurah (atau terikat untuk yang termurah) dalam hal total biaya batang korek api, di antara semua output yang memenuhi spesifikasi.

Klarifikasi

• Anda dapat membentuk angka beberapa digit melalui mengeluarkan beberapa digit dalam satu baris (mis. 11-1Adalah output yang valid untuk diproduksi 10). Untuk lebih tepatnya, angka yang dihasilkan ditafsirkan dalam desimal. Rangkaian semacam ini bukan operasi yang bekerja pada hasil antara; hanya pada digit literal yang muncul dalam ekspresi asli.
• Untuk tujuan tantangan ini. +,, -dan ×merupakan operator infiks; mereka membutuhkan pertengkaran di sebelah kiri dan ke kanan. Anda tidak diizinkan menggunakannya dalam posisi awalan seperti +5atau -8.
• Anda tidak memiliki tanda kurung (atau cara lain untuk mengontrol prioritas). Ekspresi mengevaluasi menurut aturan presedensi default tipikal (perkalian terjadi pertama kali, dan kemudian penambahan dan pengurangan dievaluasi dari kiri ke kanan).
• Anda tidak memiliki akses ke operator matematika atau konstanta selain yang tercantum di atas; solusi "berpikir lateral" sering diterima di Puzzling, tetapi tidak masuk akal untuk meminta komputer untuk membuatnya sendiri, dan di sini di PPCG, kami ingin bersikap objektif apakah solusi itu benar atau tidak.
• Aturan bilangan bulat bilangan bulat yang biasa berlaku: solusi Anda harus dapat bekerja untuk bilangan bulat besar yang sewenang-wenang dalam versi hipotetis (atau mungkin nyata) bahasa Anda di mana semua bilangan bulat tidak terikat secara default, tetapi jika program Anda gagal dalam praktik karena implementasi tidak mendukung bilangan bulat yang besar, itu tidak membatalkan solusi.
• Jika Anda menggunakan angka atau operator yang sama lebih dari sekali, Anda harus membayar biaya batang korek api setiap kali Anda menggunakannya (karena, jelas, Anda tidak dapat menggunakan kembali korek api fisik yang sama di dua lokasi berbeda di tabel).
• Tidak ada batasan waktu; solusi brute-force dapat diterima. (Meskipun jika Anda memiliki solusi yang lebih cepat daripada brute force, jangan ragu untuk mempostingnya bahkan jika itu lebih lama; melihat bagaimana pendekatan alternatif membandingkan selalu menarik.)
• Meskipun menulis penjelasan tentang kode Anda tidak pernah diperlukan , ini mungkin merupakan ide yang bagus; solusi kode-golf seringkali sangat sulit dibaca (terutama bagi orang yang tidak terbiasa dengan bahasa yang mereka tulis), dan mungkin sulit untuk mengevaluasi (dan dengan demikian memilih) sebuah solusi kecuali Anda mengerti cara kerjanya.

Kondisi kemenangan

Sebagai tantangan kode-golf , jawaban dengan byte lebih sedikit dianggap lebih baik. Namun, seperti biasa, jangan ragu untuk mengirim jawaban dengan pendekatan yang berbeda, atau dalam bahasa tertentu bahkan jika mereka lebih bertele-tele daripada bahasa lain; tujuan golf adalah untuk melihat seberapa jauh Anda dapat mengoptimalkan program tertentu, dan melakukan hal-hal seperti ini memberi kami banyak program potensial untuk dioptimalkan. Jadi jangan berkecil hati jika seseorang mengajukan solusi menggunakan pendekatan yang sama sekali berbeda, atau bahasa yang sama sekali berbeda, dan mendapat jawaban yang jauh lebih pendek; mungkin saja jawaban Anda dioptimalkan dengan lebih baik dan menunjukkan lebih banyak keterampilan, dan pemilih di PPCG sering menghargai itu.

Python2, 1̶9̶8̶ ̶b̶y̶t̶e̶s̶ 182 bytes berkat math_junkie

def f(n,c=dict(zip('0123456789+-*',map(int,'6255456376212'))),e=[(0,'')]):
 while 1:
    v=(m,s)=min(e);e.remove(v)
    try:
     if eval(s)==n:return s
    except:0
    e+=[(m+c[x],s+x)for x in c]

Algoritma ini tidak melakukan apa pun untuk mengecualikan versi awalan +dan -, tetapi mereka akan lebih buruk daripada, atau sama dengan dan muncul kemudian dalam pencarian, rekan-rekan infiks mereka. Karena menggunakan argumen kata kunci secara ebergantian, itu akan memberikan hasil yang tidak valid jika dipanggil beberapa kali per sesi. Untuk memperbaikinya, gunakan f(n, e=[(0,'')])bukan hanya f(n). Perhatikan bahwa indentasi empat spasi mewakili tab, jadi ini hanya akan bekerja dengan Python 2.

Saya juga memiliki versi tidak dioptimalkan dan dioptimalkan yang berjalan cepat bahkan untuk jumlah yang cukup besar:

from heapq import heappop, heappush

def f(n):
    digits = list('0123456789')
    ops =['+','-','*','']
    costs = dict(zip(digits + ops, [6,2,5,5,4,5,6,3,7,6,2,1,2,0]))
    expressions = [(costs[d], abs(n - int(d)), int(d), d) for d in digits[1:]]
    seen = set()
    while 1:
        cost, d, k, expression = heappop(expressions)
        if d == 0:
            return expression
        for op in ops:
            if op in '+-' and k in seen:
                continue
            for digit in digits:
                if op and digit == '0':
                    continue
                expression1 = expression + op + digit
                k1 = eval(expression1)
                d1 = abs(n - k1)
                if d1 == 0:
                    return expression1
                heappush(expressions, (cost+costs[op]+costs[digit], d1, k1, expression1))
        seen.add(k)

PHP, 241 Bytes

Versi Online

function m($i){for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e;}foreach($r=range(0,2*$a=$argv[1])as$v)foreach($r as$w)$x[$v+$w]["$v+$w"]=$x[$v*$w]["$v*$w"]=1+$x[$v-$w]["$v-$w"]=m("$v")+m("$w")+1;echo array_search(min($x[$a]),$x[$a]);

Kerusakan

function m($i){
    for(;$s<strlen($i);)$e+="6255456376"[$i[$s++]];return$e; #return the count of the matchstick for an integer
}

foreach($r=range(0,2*$a=$argv[1])as$v) # limit to an input to 300 in the online version
foreach($r as$w)
       $x[$v+$w]["$v+$w"]=  #fill the 2D array in the form [result][expression] = count matchsticks
       $x[$v*$w]["$v*$w"]=
       1+$x[$v-$w]["$v-$w"]=
       m("$v")+m("$w")+1;
echo $k=array_search(min($x[$a]),$x[$a]); # Output expression with a minium of matchsticks
echo"\t".$x[$a][$k]; #optional Output of the count of the matchsticks

Cara dengan kinerja sedikit lebih baik

function m($i){
for(;$s<strlen($i);)
$e+="6255456376"[$i[$s++]];return$e;} #return the count of the matchstick for an integer
foreach($r=range(0,2*$a=$argv[1])as$v)
foreach($r as$w){$c=m("$v")+m("$w")+1;
if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
if($a==$v*$w)$x["$v*$w"]=1+$c;
if($a==$v-$w)$x["$v-$w"]=$c;}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
    echo"\t".$x[$k]; #optional Output of the count of the matchsticks

Dukungan bilangan bulat negatif

Versi dengan bilangan bulat negatif

function m($i){
    $e=$i<0?1:0; # raise count for negative integers
    for($s=0;$s<strlen($i);)$e+=[6,2,5,5,4,5,6,3,7,6][$i[$s++]];return$e; #return the count of the matchstick for an integer
}
$q=sqrt(abs($argv[1]));
$l=max(177,$q);
$j=range(-$l,$l); # for second loop for better performance
foreach($r=range(min(0,($a=$argv[1])-177),177+$a)as$v) 
foreach($j as$w){$c=m("$v")+m("$w")+1;  
    if($a==$v+$w)$x["$v+$w"]=1+$c; # fill array if value equal input
    if($a==$v*$w)$x["$v*$w"]=1+$c;
    if($a==$v-$w)$x["$v-$w"]=$c;
    if($a==$w-$v)$x["$w-$v"]=$c; # added for integers <0
}
echo $k=array_search(min($x),$x); # Output expression with a minium of matchsticks
echo"\t".$x[$k]; #optional Output of the count of the matchsticks