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
and46+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 exactlyn
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
into7 =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})}
- access a file in which the mapping
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.
0: 1, 2, 3, 4, 5, 6
for consistency \$\endgroup\$=
(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. \$\endgroup\$1+1+2=3-6+10
? And same question about output. \$\endgroup\$