Votre tâche dans ce défi est d'analyser une "équation de matchstick" comme celle-ci ...

... et pour savoir si elle peut être transformée en une équation valide en réorganisant les correspondances. Si c'est le cas, vous devez générer le moins de mouvements pour le faire et l'équation résultante.

Contribution

L'entrée est une chaîne qui peut être lue depuis STDIN, prise comme argument de fonction ou même stockée dans un fichier. C'est une équation qui représente un arrangement d'allumettes et peut être décrite à l'aide de l'EBNF suivant:

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

Un exemple pour une entrée valide serait 3+6-201=0+0+8.

Tâche

Considérez l'illustration suivante où chaque allumette a un numéro attribué:

Nous mappons maintenant chaque symbole d'entrée aux positions d'allumettes correspondantes comme suit:

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

Chaque formule d'entrée peut être transformée en un arrangement d'allumettes. Par exemple, l'équation "45 + 6 = 92" devient

où les allumettes inutilisées sont grisées. Votre tâche consiste à trouver le moins de allumettes qui doivent être réorganisées afin de rendre l'équation valide.

Production

On distingue trois cas possibles:

• Si l'entrée n'est pas valide (c'est-à-dire qu'elle ne satisfait pas à l'EBNF ci-dessus), sortez ce que vous voulez.
• Sinon, s'il existe des moyens de transformer l'équation en une équation valide en réorganisant les allumettes, vous devez générer à la fois le nombre minimum de réarrangements et l'équation correspondante. Tout comme l'entrée, l'équation sortie doit également satisfaire l'EBNF donné. Dans l'exemple ci-dessus, la sortie correcte serait 1et 46+6=52. S'il existe plusieurs possibilités pour l'équation résultante, sortez l'une d'entre elles.
• Sinon (donc si l'entrée est valide mais qu'il n'y a aucun moyen de rendre l'équation vraie), vous devez sortir -1.

Détails

• Vous n'êtes pas autorisé à supprimer ou à ajouter des correspondances. Cela signifie que si l'entrée est constituée d' nallumettes, la sortie doit également être constituée exactement d' nallumettes.
• Les blocs d'allumettes "vides" ne sont autorisés qu'à la fin et au début d'une équation, pas au milieu. Ainsi, par exemple, le transformer 7-1=6en 7 =6-1le supprimant simplement -1du côté gauche et en l'ajoutant du côté droit avec seulement 3 réarrangements d'allumettes n'est pas autorisé.

• Comme je ne vois pas vraiment le mappage des nombres aux positions des allumettes comme une partie intéressante de ce défi, pour un plus de 20 octets , vous pouvez soit

  • accéder à un fichier dans lequel le mappage (number/operation ↦ matchstick positions)est stocké de manière raisonnable, ou
  • si votre langage de programmation prend en charge un Maptype de données, supposez que vous avez accès à une carte préinitialisée avec le (number/operation ↦ matchstick positions)mappage. Cette carte peut par exemple ressembler à ça:{(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})}

Exemples

Entrée: 1+1=3 ↦ Sortie: 1 et1+1=2

Entrée: 15+6=21 ↦ Sortie: 0 et15+6=21

Entrée: 1=7 ↦ Sortie: -1

Entrée: 950-250=750 ↦ Sortie: 2 et990-240=750

Entrée: 1-2=9 ↦ Sortie: 1 et1+2=3

Entrée: 20 + 3=04 ↦ Sortie: n'importe quoi

Gagnant

Il s'agit de code-golf , donc la réponse correcte la plus courte (en octets) l'emporte. Le gagnant sera choisi une semaine après la publication de la première bonne réponse.

Javascript, 1069 octets

Je l'ai testé avec pas mal d'équations de test et cela semble fonctionner tout le temps maintenant ...

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}

Eh bien, c'est la première fois que je soumets une réponse, donc je ne me vois pas gagner. Il s'agit essentiellement d'une méthode de force brute pour trouver toutes les réponses, puis elle saisit et renvoie les plus petites d'un tableau. avec le premier argument étant la longueur et le second étant un tableau avec les sorties.

si l'entrée est "1-2 = 9", la sortie est [1, ["1 + 2 = 3", "7-2 = 5"]]

et voici le code non compressé:

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

Avertissement: ne faites pas d'équations comme 950-250 = 750, il utilise ~ 45 allumettes et, car ce code utilise la force brute, il entraînera le blocage de javascript.

Perl, 334

Assez rapide tant que la solution est accessible en 1 ou 2 mouvements. Quand il n'y a pas de solution, vous attendez longtemps, même dans le plus petit des cas 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}

Exemple:

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

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

Cela ne trouvera pas de solutions qui modifient la durée de l'équasion comme 11=4-> 2 11=11, mais je ne suis pas sûr que ce soit autorisé.