Deine Aufgabe bei dieser Herausforderung ist es, eine gegebene "Matchstick-Gleichung" wie diese zu analysieren ...

... und um herauszufinden, ob es sich durch Umordnen der Übereinstimmungen in eine gültige Gleichung verwandeln lässt. In diesem Fall müssen Sie die geringste Anzahl von Zügen und die resultierende Gleichung ausgeben.

Eingang

Die Eingabe ist eine Zeichenfolge, die aus STDIN gelesen, als Funktionsargument verwendet oder sogar in einer Datei gespeichert werden kann. Es ist eine Gleichung, die eine Streichholzanordnung darstellt und mit dem folgenden EBNF beschrieben werden kann:

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

Ein Beispiel für eine gültige Eingabe wäre 3+6-201=0+0+8.

Aufgabe

Betrachten Sie die folgende Abbildung, in der jedem Streichholz eine Nummer zugewiesen ist:

Wir ordnen nun jedes Eingabesymbol den entsprechenden Streichholzpositionen wie folgt zu:

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

Jede Eingabeformel kann in eine Streichholzanordnung umgewandelt werden. Zum Beispiel wird die Gleichung "45 + 6 = 92"

wo unbenutzte Streichhölzer ausgegraut sind. Ihre Aufgabe ist es, die geringste Anzahl von Streichhölzern herauszufinden, die neu angeordnet werden müssen, um die Gleichung gültig zu machen.

Ausgabe

Wir unterscheiden drei mögliche Fälle:

• Wenn die Eingabe ungültig ist (dh die oben angegebene EBNF nicht erfüllt), geben Sie alles aus, was Sie möchten.
• Andernfalls müssen Sie, wenn es Möglichkeiten gibt, die Gleichung durch Umordnen der Streichhölzer in eine gültige umzuwandeln, sowohl die minimale Anzahl von Umordnungen als auch die entsprechende Gleichung ausgeben . Ebenso wie die Eingabe muss auch die ausgegebene Gleichung die angegebene EBNF erfüllen. Im obigen Beispiel wäre 1und die richtige Ausgabe 46+6=52. Wenn es für die resultierende Gleichung mehrere Möglichkeiten gibt, geben Sie eine davon aus.
• Andernfalls (wenn die Eingabe gültig ist, die Gleichung jedoch nicht wahr ist) müssen Sie eine Ausgabe vornehmen -1.

Einzelheiten

• Sie dürfen keine Übereinstimmungen entfernen oder hinzufügen. Das heißt, wenn die Eingabe aus nStreichhölzern besteht, muss die Ausgabe auch genau aus nStreichhölzern bestehen.
• "Leere" Streichholzblöcke sind nur am Ende und am Anfang einer Gleichung erlaubt, nicht in der Mitte. So zum Beispiel Drehen 7-1=6in 7 =6-1durch einfaches Entfernen -1von der linken Seite und das Hinzufügen es auf der rechten Seite mit nur 3 Zündholz Umlagerungen ist nicht erlaubt.

• Da ich die Zuordnung von Zahlen zu Matchstick-Positionen nicht wirklich als einen interessanten Teil dieser Herausforderung sehe , können Sie dies auch für ein Plus von 20 Byte tun

  • auf eine Datei zugreifen, in der die Zuordnung (number/operation ↦ matchstick positions)in angemessener Weise gespeichert ist, oder
  • Wenn Ihre Programmiersprache einen MapDatentyp unterstützt , nehmen Sie an, dass Sie Zugriff auf eine Map haben, die mit dem (number/operation ↦ matchstick positions)-mapping vorinitialisiert wurde. Diese Map kann zum Beispiel so aussehen:{(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})}

Beispiele

Eingabe: 1+1=3 ↦ Ausgabe: 1 und1+1=2

Eingabe: 15+6=21 ↦ Ausgabe: 0 und15+6=21

Eingabe: 1=7 ↦ Ausgabe: -1

Eingabe: 950-250=750 ↦ Ausgabe: 2 und990-240=750

Eingabe: 1-2=9 ↦ Ausgabe: 1 und1+2=3

Eingabe: 20 + 3=04 ↦ Ausgabe: alles

Gewinner

Das ist Code-Golf , also gewinnt die kürzeste richtige Antwort (in Bytes). Der Gewinner wird eine Woche nach dem Absenden der ersten richtigen Antwort ermittelt.

Javascript, 1069 Bytes

Ich habe es mit einigen Testgleichungen getestet und es scheint jetzt die ganze Zeit zu funktionieren ...

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}

Nun, es ist das erste Mal, dass ich eine Antwort abschicke, also sehe ich mich selbst nicht als Sieger. Dies ist im Grunde eine Brute-Force-Methode, um alle Antworten herauszufinden, und dann werden die kleinsten in einem Array erfasst und zurückgegeben. wobei das erste Argument die Länge und das zweite ein Array mit den Ausgängen ist.

Wenn die Eingabe "1-2 = 9" ist, ist die Ausgabe [1, ["1 + 2 = 3", "7-2 = 5"].

und hier ist der unkomprimierte Code:

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;
}

Warnung: Verwenden Sie keine Gleichungen wie 950-250 = 750, es werden ~ 45 Matchsticks verwendet. Da dieser Code Brute Force verwendet, hängt Javascript.

Perl, 334

Ziemlich schnell, solange die Lösung in 1 oder 2 Zügen erreichbar ist. Wenn es keine Lösung gibt, müssen Sie auch im kleinsten Fall lange warten 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}

Beispiel:

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

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

Dies wird keine Lösungen finden, die die Länge der Equasion wie 11=4-> verändern 2 11=11, aber ich bin nicht sicher, ob dies erlaubt wäre.