Matchstick Equations

Question

Your task in this challenge is to analyize a given "Matchstick Equation" like this one...

... and to find out whether it can be turned into a valid equation by rearranging the matches. If so, you are to output the least number of moves to do so and the resulting equation.

Input

The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. It is an equation that represents a matchstick arrangement and can be described using the following EBNF:

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

An example for a valid input would be 3+6-201=0+0+8.

Task

Consider the following illustration where each matchstick has a number assigned:

We now map each input symbol to the corresponding matchstick positions as follows:

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

Each input formula can be turned into a matchstick arrangement. For example, the equation "45+6=92" becomes

where unused matchsticks are greyed out. Your task is to find out the least number of matchsticks that have to be rearranged in order to make the equation valid.

Output

We distinguish between three possible cases:

• If the input is not valid (i.e. it doesn't satisfy the above EBNF), output whatever you want.
• Otherwise, if there are ways to turn the equation into a valid one by rearranging the matchsticks, you have to output both the minimum number of rearrangements and the corresponding equation. Just as the input, the outputted equation must also satisfy the given EBNF. In the above example, the correct output would be 1 and 46+6=52. If there are multiple possibilities for the resulting equation, output any of them.
• Otherwise (so if the input is valid but there is no way to make the equation true), you have to output -1.

Details

• You are not allowed to remove or to add matches. That means, if the input is built of n matchsticks, the output must also consist of exactly n matchsticks.
• "Empty" matchstick-blocks are only allowed at the end and the beginning of an equation, not in the middle. So, for example, turning 7-1=6 into 7 =6-1 by simply removing -1 from the left side and adding it on the right side with just 3 matchstick rearrangements is not allowed.

• Since I don't really see the mapping from numbers to matchstick positions as an interesting part of this challenge, for a plus of 20 bytes, you may either

  • access a file in which the mapping (number/operation ↦ matchstick positions) is stored in any reasonable way, or
  • if your programming language supports a Map datatype, assume that you have access to a map that is preinitialized with the (number/operation ↦ matchstick positions)-mapping. This map may for example look like that: {(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})}

Examples

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

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

Input: 1=7 ↦ Output: -1

Input: 950-250=750 ↦ Output: 2 and 990-240=750

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

Input: 20 + 3=04 ↦ Output: anything

Winner

This is code-golf, so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

Answer 1

Javascript, 1069 Bytes

I've tested it with quite a few test equations and it seems to work all of the time now...

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}

Well this is my first time ever submitting an answer, so I don't see myself winning. This is basically a brute force method to figure out all answers and then it grabs and returns the smallest ones in an array. with the first argument being the length and the second being an array with the outputs.

if the input is "1-2=9" the output is [1,["1+2=3","7-2=5"]]

and here is the uncompressed 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;
}

Warning: Don't do equations like 950-250=750 it uses ~45 Matchsticks and because this code uses brute force it will cause javascript to hang.

Answer 2

Perl, 334

Fairly fast as long as the solution is reachable in 1 or 2 moves. When there is no solution you are up for a long wait even in the smallest case of 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}

Example:

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

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

This will not find solutions that change the length of the equasion like 11=4 -> 2 11=11, but I am not sure it this would be allowed.