Tugas Anda dalam tantangan ini adalah untuk menganalisis "Persamaan Batang Korek Api" yang diberikan seperti ini ...

... dan untuk mengetahui apakah itu dapat diubah menjadi persamaan yang valid dengan mengatur ulang pertandingan. Jika demikian, Anda akan menghasilkan jumlah gerakan paling sedikit untuk melakukannya dan persamaan yang dihasilkan.

Memasukkan

Input adalah sebuah String yang dapat dibaca dari STDIN, diambil sebagai argumen fungsi atau bahkan disimpan dalam file. Ini adalah persamaan yang mewakili pengaturan batang korek api dan dapat dijelaskan menggunakan EBNF berikut:

input = term, "=", term ;
term = number | (term, ("+" | "-"), term) ;
number = "0" | (numeralExceptZero , {numeral}) ;
numeralExceptZero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
numeral = "0" | numeralExceptZero ;

Contoh untuk input yang valid adalah 3+6-201=0+0+8.

Tugas

Pertimbangkan ilustrasi berikut ini di mana setiap batang korek api memiliki nomor yang ditetapkan:

Kami sekarang memetakan setiap simbol input ke posisi batang korek api yang sesuai sebagai berikut:

0 ↦ 1,2,3,4,5,6
1 ↦ 4,5
2 ↦ 2,3,5,6,8
3 ↦ 3,4,5,6,8
4 ↦ 1,4,5,8
5 ↦ 1,3,4,6,8
6 ↦ 1,2,3,4,6,8
7 ↦ 4,5,6
8 ↦ 1,2,3,4,5,6,8
9 ↦ 1,3,4,5,6,8
- ↦ 8
+ ↦ 8,10
= ↦ 7,9

Setiap formula input dapat diubah menjadi pengaturan batang korek api. Misalnya, persamaan "45 + 6 = 92" menjadi

di mana korek api yang tidak digunakan diklik. Tugas Anda adalah untuk mengetahui jumlah korek api yang paling sedikit yang harus disusun ulang agar persamaannya valid.

Keluaran

Kami membedakan antara tiga kemungkinan kasus:

• Jika input tidak valid (artinya tidak memenuhi EBNF di atas), output apa pun yang Anda inginkan.
• Jika tidak, jika ada cara untuk mengubah persamaan menjadi valid dengan menata ulang korek api, Anda harus output baik jumlah minimum penyusunan ulang dan sesuai persamaan. Sama seperti input, persamaan yang dikeluarkan juga harus memenuhi EBNF yang diberikan. Dalam contoh di atas, output yang benar adalah 1dan 46+6=52. Jika ada beberapa kemungkinan untuk persamaan yang dihasilkan, output salah satunya.
• Kalau tidak (jadi jika inputnya valid tetapi tidak ada cara untuk membuat persamaan itu benar), Anda harus output -1.

Detail

• Anda tidak diizinkan untuk menghapus atau menambahkan kecocokan. Itu berarti, jika input dibuat dari nkorek api, output juga harus terdiri dari nkorek api.
• Batang korek api "Kosong" hanya diperbolehkan di bagian akhir dan awal persamaan, bukan di tengah. Jadi, misalnya, beralih 7-1=6ke 7 =6-1hanya dengan menghapus -1dari sisi kiri dan menambahkannya di sisi kanan hanya dengan 3 pengaturan batang korek api tidak diperbolehkan.

• Karena saya tidak benar-benar melihat pemetaan dari angka ke posisi batang korek api sebagai bagian yang menarik dari tantangan ini, untuk plus 20 byte , Anda dapat

  • mengakses file di mana pemetaan (number/operation ↦ matchstick positions)disimpan dengan cara apa pun yang masuk akal, atau
  • jika bahasa pemrograman Anda mendukung Maptipe data, asumsikan bahwa Anda memiliki akses ke peta yang diinisialisasi dengan (number/operation ↦ matchstick positions)-petakan. Peta ini misalnya terlihat seperti itu:{(0,{1,2,3,4,5,6}),(1,{4,5}),(2,{2,3,5,6,8}),(3,{3,4,5,6,8}), ..., (-,{8}),(+,{8,10}),(=,{7,9})}

Contohnya

Input: 1+1=3 ↦ Output: 1 dan1+1=2

Input: 15+6=21 ↦ Output: 0 dan15+6=21

Input: 1=7 ↦ Output: -1

Input: 950-250=750 ↦ Output: 2 dan990-240=750

Input: 1-2=9 ↦ Output: 1 dan1+2=3

Input: 20 + 3=04 ↦ Output: apa pun

Pemenang

Ini adalah kode-golf , jadi jawaban terpendek yang benar (dalam byte) menang. Pemenang akan dipilih satu minggu setelah jawaban pertama yang benar diposting.

Javascript, 1069 Bytes

Saya sudah mengujinya dengan beberapa persamaan uji dan tampaknya berfungsi sepanjang waktu sekarang ...

function w(t){function B(c,f){d=(c.length>f.length?f:c).split("");e=(c.length>f.length?c:f).split("");longer=Math.max(d.length,e.length);if(0!==d.length&&0!==e.length){c=[];for(x in d)for(y in c[x]=[],e)c[x][y]=1<y-x?-1:function(c,n){r=0;for(j in n)-1<c.indexOf(n[j])&&r++;return c.length+n.length-2*r}(a[d[x]],a[e[y]]);return v=function(f,n){for(var h=f.length-2;0<=h;h--)c[n.length-1][h]+=c[n.length-1][h+1];for(h=f.length-2;0<=h;h--)for(var q=0;q<n.length-1;q++)1>=h-q&&(c[q][h]+=-1==c[q][h+1]?c[q+1][h+1]:Math.min(c[q+1][h+1],c[q][h+1]));return c[0][0]/2}(e,d)}return-1}a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];a["+"]=[8,0];a["-"]=[8];a["="]=[7,9];a[" "]=[];l=0;p=[];u=[];r=/^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;b=/(=.*=|[+=-]{2,}|^[+=-])/;if(!t.match(r))return-1;g=function(c,f,t){if(0===t&&f.match(r)&&eval(f.replace("=","==")))c.push(f);else for(var n in a)t>=a[n].length&&" "!=n&&!(f+n).match(b)&&g(c,f+n,t-a[n].length)};g(p,"",function(c){m=0;for(var f in c)m+=a[c[f]].length;return m}(t.split("")));for(var z in p)k=B(t,p[z]),u[k]||(u[k]=[]),u[k].push(p[z]);for(var A in u)return[A,u[A]];return-1}

Ya, ini pertama kalinya saya mengirimkan jawaban, jadi saya tidak melihat diri saya menang. Ini pada dasarnya adalah metode brute force untuk mencari tahu semua jawaban dan kemudian mengambil dan mengembalikan yang terkecil dalam sebuah array. dengan argumen pertama adalah panjang dan argumen kedua adalah array dengan output.

jika inputnya adalah "1-2 = 9" outputnya [1, ["1 + 2 = 3", "7-2 = 5"]]

dan ini adalah kode yang tidak terkompresi:

function ms(s) {
a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];
a["+"] = [8, 0];
a["-"] = [8];
a["="] = [7, 9];
a[" "] = [];
l = 0;
p = [];
u = [];
r = /^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;
b = /(=.*=|[+=-]{2,}|^[+=-])/;
if (!s.match(r)) return -1;
function f(g,h)
{
    d=(g.length>h.length?h:g).split('');
    e=(g.length>h.length?g:h).split('');
    longer=Math.max(d.length, e.length);
    if(0!==d.length&&0!==e.length)
    {
        g=[];
        for(x in d)
        {
            g[x]=[];
            for(y in e)
            {
                g[x][y]=(y-x>1)?-1:function(g, h){r=0;for(j in h)if(g.indexOf(h[j])>-1)r++;return g.length+h.length-2*r;}(a[d[x]],a[e[y]]);
            }
        }
        v=function(d,e)
        {
        for(var y=d.length-2;y>=0;y--) g[e.length-1][y]+=g[e.length-1][y+1];
        for(var y=d.length-2;y>=0;y--)
            for(var x=0;x<e.length-1;x++)
                if(y-x<=1)
                    g[x][y]+=g[x][y+1]==-1?g[x+1][y+1]:Math.min(g[x+1][y+1], g[x][y+1]);
        return g[0][0]/2}(e,d)
        return v
    }
    return -1;
}
g=function(n, s, i){if (i===0 && s.match(r) && eval(s.replace('=','=='))){n.push(s);return;}for (var c in a) if(i>=a[c].length && c!=" " && !(s+c).match(b)) g(n, s+c, i-a[c].length);};
g(p, "", function(q){m=0;for(var t in q)m+=a[q[t]].length;return m}(s.split('')));
for (var i in p)
{
    k=f(s, p[i]);
    if (!u[k]) u[k] = [];
    u[k].push(p[i]);
}
for (var q in u) return [q, u[q]];
return -1;
}

Peringatan: Jangan lakukan persamaan seperti 950-250 = 750 yang digunakan ~ 45 Matchsticks dan karena kode ini menggunakan brute force maka akan menyebabkan javascript hang.

Perl, 334

Cukup cepat asalkan solusinya dapat dicapai dalam 1 atau 2 gerakan. Ketika tidak ada solusi Anda menunggu lama bahkan dalam kasus terkecil 1=7.

#!perl -p
@y=map{sprintf"%010b",$_}63,24,118,124,89,109,111,56,127,125,64,192,768;
$y{$z{$y[$c++]}=$_}=$y[$c]for 0..9,qw(- + =);
$"="|";$l=s/./$y{$&}/g;$x{$_}=1;for$m(0..y/1//){
last if$_=(map"$m $_",grep{s/@y/$z{$&}/g==$l&&/^\d.*\d$/&!/\D\D/&!/\b0\d/&y/=//==1&&eval s/=/==/r}keys%x)[0];
$_=-1;s/0/"$`1$'"=~s!1!$x{"$`0$'"}=1!ger/eg for keys%x}

Contoh:

$ time perl ~/matchstick.pl <<<950-250=750
2 990-250=740

real    0m39.835s
user    0m39.414s
sys 0m0.380s

Ini tidak akan menemukan solusi yang mengubah panjang persamaan seperti 11=4-> 2 11=11, tapi saya tidak yakin ini akan diizinkan.