Ploblem
Blackout Math is a puzzle in which you are given an incorrect arithmetic equation, such as this one:1
288 / 24 × 6 = 18 × 13 × 8
To solve the puzzle, figure out which two squares must be blacked out to create a correct equation. Blacked out squares are simply skipped over when reading the new equation. Note that you can choose to black out an operation — for example, if you black out the last multiplication sign, the right side would read 18 x 138. You are not allowed to black out the equal sign!
In this particular instance of the puzzle, the answer is as follows:1
288 / 4 × 6 = 18 × 3 × 8
as both sides of the equation now evaluate to 432.
Here is another puzzle for you to try:1
168 / 24 + 8 = 11 × 3 - 16
In this project, you will develop a program that reads in Blackout Math puzzles from a file and determines their solutions.
Building your solution
Once your solution is complete, it will work as follows:1
2
3
4
5
6Open up a file of Blackout Math puzzles
For each puzzle:
For each possible pair of characters in the puzzle
Determine the string that results from deleting those characters
Compute the value of each side of the equation
If the two sides have the same value, success!
However, it will be easier to build your solution from the inside out — that is, first create a function that computes the value of one side of one equation, then use that to build a checker for a single puzzle, and so on. Here we will give you some hints for how to complete this process.
Computing the value of an expression
Consider the following string: 5 × 2 + 3 – going from left to right, your program will have to check whether each character represents a digit or an operation, and keep a running total of the current value of the expression. Also note that when you come to a number, you have to remember what the last character was – knowing only that the current character is a 3 only helps if you know that you were supposed to add it to the previous value of the expression! The Python function isdigit will be helpful for this process. To get started, write a skeleton of a compute function that takes a string and goes through it character by character, converting the numbers to ints and printing “add”, “subtract”, “multiply” or “divide” for each operation as they are encountered.
Now, consider the expression 5 + 2 × 3 – if we parse this string from left to right (as we would usually process it in a loop), we will get 21, but according to the standard order of operations, we should do the multiplication first, then the addition, to get 11. In effect, when going left-to-right, we need to delay the addition until the multiplication has been completed. One way to do that is to save the addition on a stack, then pop it off the stack and execute it once the multiplication has finished. You also need to save the numbers themselves on a separate stack until they are needed. Of course, if you have multiple additions or subtractions in a row, then you need to only save the last one, so when you see a second addition or subtraction, you need to compute the result of the first before saving the result and the most recent operation.
If we have parentheses as well, this also can be easily handled with a stack, again essentially forcing the contents of the parentheses to happen first.
The pseudocode for handling order-of-operations (for just the four standard operations plus parentheses) using a pair of stacks is as follows:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16Determine what the next item in the string is, call this X
If X is a number, push it onto the number stack
If X is any of the four arithmetic operations:
While the top of the operation stack is equal or higher precedence to X:
Pop the top two numbers from the number stack and one operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
Push X onto the operation stack
If X is (, push it onto the operation stack
If X is ),
While the top of the operation stack is not '(':
Pop the top two numbers from the number stack and the top operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
Pop off the (
Once you reach the end of the input, while the stacks are not empty:
Pop the top two numbers from the number stack and the top operation from the operation stack
Apply the operation that you just popped, push the result onto the number stack
To get a feel for how and why this works, trace this pseudocode for the input 2 + 5 × (6 - 3) - 6 by noting what is in each stack after reading each character.
Finally, consider the string 5 × 12 + 3 – in this case, when you come to a number, you cannot count on it being immediately used. Instead, you have to continue building up the value of the current number until you read an operation, then you can incorporate that into the expression. Figure out what happens when the 1 is read by your function, then the 2, and finally the +. Modify your compute function to handle the case of multi-digit numbers. As above, trace the correct execution on paper and then test the code on a few different cases.
Error handling
In many cases in this course, we do not worry about handling errors in input as they are not critical to the problem at hand. However, in this case, we can expect “errors” to occur when parsing. This is because we will be deleting arbitrary characters from the puzzle. For example, when trying to solve our first example 288 / 24 × 6=18 × 13 × 8 we might try deleting the 6, leaving a left side of 288 / 24×. We know right away that this is not a possible solution to the puzzle, but our compute function must still handle this gracefully. Luckily, the stack-based algorithm will handle most of these cases easily – if we get to the end of the input and have anything other than one number and no operators left, there was erroneous input. Other error cases that you may discover can also be dealt with via the parsing algorithm itself.
Testing whether an equation is correct
Once we can evaluate a single expression, it is simple to compute whether two sides of an equation are equal. You may find the Python functions find (with slicing) or split useful to locate the equal sign in your equation (if it still has one!). Write a function called test that takes in a string and uses your compute function to decide if the string represents the correct solution to a Blackout Math puzzle.
Computing all possible pairs of characters
To solve a Blackout Math puzzle, you have to find the two squares to black out, or in our case, two characters to remove from the string. For a computer, the simplest thing to do is simply to test all possible pairs of characters. Note that although the two examples in this writeup are the same length, not all Blackout Math puzzles will be.
Write a function solve that takes in a full Blackout Math puzzle as a string and loops through all possible pairs of characters. For each pair of characters, create the string that results when those two characters are removed, and use your evaluate function to see which of those represents the solution! This is a good time to make sure that your error handling works, as this loop will send many malformed equations to your evaluate function – consider how compute will report errors, and how evaluate will handle them. Remember, that the two characters that are removed COULD be on the same side of the equals sign.
Using a binary tree to compute all possible solutions
Now that you have done this for all possible combinations of two blacked out characters, you need to now do it for any arbitrary number of blacked out characters.
To do this you are required to use a binary tree. The tree will be structured such that all leaf nodes of the tree are all possible combinations of blacked out characters.
The left child of the tree will be the equation with the current character blacked out. The right child will be the equation with the current character not blacked out.
To construct the tree you will consider one character at a time in the equation. You will make two children, one with the current value blacked out and one with the value not blacked out. Each level of the tree will represent all possible combinations of a new character character being added to the statement.
Your function for making the tree will be recursive in nature, as recursion is the easiest way to process a binary tree.
Psuedocode for making the tree:1
2
3
4
5
6
7
8
9
10
11
12
13def makeTree( equation, value ):
if the equation is empty, we have reached the leaves of this branch:
set left and right children to None
otherwise:
we need to create the left and right children:
- left will be a recursive call to make tree with:
- the first character removed from the equation
- the same value
- right will be a recursive call to make tree with:
- the equation with the first character removed
- the first character of the equation appended to the value
make a binary tree node with the left, right, and current value
return the binary tree node
In the case of the tree presented above, there are no valid solutions. These trees can get large. There are actually 2 n possible leaf nodes, where n is the length of the equation. For example, the equation 3 + 2 / 5 = 5 + 3 × 2 will have 2 11 possible leaf nodes. That’s 2048 leaf nodes!
Testing
As you develop your solution, make sure to thoroughly test each function as well as the overall solution. For the compute function, it probably makes sense to test simple expressions first, then more complex ones (including parentheses), and finally ones that will cause errors of various kinds.
For the overall solution, you should test some different puzzles including some of your own creation (making a puzzle isn’t that hard!). Make sure that your code works for all the puzzles – but we will not test with any puzzle that does not have a solution. Note that some puzzles, such as the one given at the top of this request, do not rely on order of operations, so can be used for testing whether or not you have implemented that algorithm.