Matchstick Equations

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.

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=3Output: 1 and 1+1=2

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

Input: 1=7Output: -1

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

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

Input: 20 + 3=04Output: anything

Winner

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

• Please add 0: 1, 2, 3, 4, 5, 6 for consistency – Not that Charles Jun 2 '15 at 2:26
• Oh thanks, totally forgot about that somehow! – vauge Jun 2 '15 at 7:16
• @vauge Hey should '2=1-1' -> '2-1=1' return 3 or 14 moves since the 2 technically has to be moved left? – Cieric Jun 2 '15 at 13:03
• @Cieric it should return 3, simply because you can switch the position of = (2 matchsticks) and - (1 matchstick) and leave all the numbers where they are. If, however, the 2 had to be moved left, you would also have to count the required moves. – vauge Jun 2 '15 at 14:30
• Is there a limitation on number of operations? Can the input be like 1+1+2=3-6+10? And same question about output. – Qwertiy Jun 2 '15 at 17:36

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.

• I believe you can declare the variables you use such as var k in the loops as unused parameters to the function, saving 3 bytes for each declaration. – rorlork Jun 2 '15 at 0:34
• I think I'm going to go learn a few more programming languages and figure out a not so brute force way to try and really knock that byte count down. – Cieric Jun 2 '15 at 12:14
• I think your solution is not correct, as when you are calculating the distance you always align the equals characters. In some cases it is not the optimal way. For example '2=1-1' can be transformed in 3 moves into '2-1=1', while aligning the '=' signs gives 14 moves. Also I don't see how you avoid leading zeroes. For example 08=8 for 80=8 is incorrect. – nutki Jun 2 '15 at 12:44
• @nutki Yeah, I think I can change that. I was thinking that'd be wrong though due to you technically having to move over the 2 to make room for the -1 – Cieric Jun 2 '15 at 12:53
• @nutki okay, yeah. Sorry I see what you mean now. Well I'm going to fix the regex and see if I can change the code around for the edit distance. – Cieric Jun 2 '15 at 14:41

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.

• Solutions that change the length of the equation are allowed as long as they follow the EBNF mentioned in the question. Therefore, they should also be found by your function. – vauge Jun 2 '15 at 14:32
• @vauge, yeah I can see that it could be inferred from "empty machsticks blocks" section in the details. I will not add it to this solution though as while it could work, it would make it even slower. – nutki Jun 2 '15 at 15:02
• @vauge I don't want to sound rude, but if the code isn't fixed will it still count? – Cieric Jun 3 '15 at 21:12
• @Cieric If there is no other solution that handles all those cases then yes, it will count. However, if there are any fully working answers by the end of this challenge, I will accept the shortest of them. – vauge Jun 4 '15 at 13:27
• @vauge okay just checking I only have to make sure the number of move is correct so far it always displays the correct output equation. – Cieric Jun 4 '15 at 14:33