Python代写：CSCI141 Blackout Math

发表于   |   分类于

Introduction

这次需要代写的Python作业是解Blackout Math问题，也就是算数挖空，类似于九宫格游戏，不过多了运算符号，而且是挖数字而不是填数字。

Ploblem

Blackout Math is a puzzle in which you are given an incorrect arithmetic equation, such as this one:

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:

288 / 4 × 6 = 18 × 3 × 8

as both sides of the equation now evaluate to 432.
Here is another puzzle for you to try:

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
6
Open 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
16
Determine 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

The final value of the expression will be on 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
13
def 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!
To process the equations for a given number of blacked out squares, supplied by the user, you will be required to traverse the tree looking for leaf nodes. These are the steps to find valid blacked out equations:

  1. Traverse the tree to find all leaf nodes
  2. When you find a leaf node, check to see if it has the proper number of blacked out characters:
    (a) If it does, determine if it is a valid equation:
    i. If it is, evaluate the equation and print the result
    ii. If it is not, ignore the equation
    (b) If it does not, ignore the node

You will use your work from prior sections to evaluate the equations when you reach them.

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 assignment, do not rely on order of operations, so can be used for testing whether or not you have implemented that algorithm.

Implementation details

You must follow the following naming conventions. This will make the testing and grading of your project more efficient. Points will be deducted if this naming convention is not followed.
You may make any helper functions that you wish, but these must be present.
Each file must also contain:

1
2
if __name__ == "__main__":
  main()

This will run the main when the given file is run and not when others are run.

Blackout

Your code should read in a series of Blackout Math puzzles from a file. Your main file should be named blackout.py and should take in the following input:

  • the name of the file with the puzzles in it.
    It should then read in the lines of this file (one puzzle per line) and print the puzzle and its solution for each one.
    Overall structure of your solution:
  1. blackout.py: This file should contain the following methods:
    (a) compute(s): This function computes the value of the string ‘s’, which represents either the left or right side of an equation. It takes a string as a parameter and returns a numeric value, or None if the equation is not valid.”
    (b) evaluate(s): This function will test a string representing an entire equation to determine if it is valid. If the equation is syntactically valid, and the left and right sides are equal, then this function will return True. Otherwise, it returns False.”
    (c) solve(s): This function will solve a given puzzle, represented by the string s. It will black out two squares at a time, passing each possible combination to the evaluate function. It should return the first valid solution it finds, or None if not valid solution exists.
    (d) main(): This function is the main function for the first part of blackout. It should prompt for and read the file one line at a time and submit each line, or puzzle, to be solved one at a time. It should print out the puzzle and the solution when it is found.
    (e) compute tests(): This function will test your compute function. Ensure you have enough tests to cover the various possible cases you can encounter. Printing the test results in a verbose manner is sufficient.
    (f) evaluate tests(): This function will test your test function. Ensure you have enough tests to cover the various possible cases you can encounter. Printing the test results in a verbose manner is sufficient.
    (g) solve tests(): This function will test your solve function. Ensure you have enough tests to cover the various possible cases you can encounter. Printing test results in a verbose manner is sufficient.

Blackout Tree

Your code should read in a series of Blackout Math puzzles from a file. Your main file for this section should be named blackout tree.py and should take in the following input:

  • The name of the file with the puzzles in it.
  • The number of squares to black out.

It should then read in the lines of this file (one puzzle per line) and print the puzzle and its solution(s) for each one.

  1. blackout tree.py: This file should contain the following methods:
    (a) make tree(s): This function makes the binary tree from the string s, s is a puzzle string. It must use the BinaryTree and BnaryTreeNode classes from lecture. It takes in a string representing a puzzle, and returns a binary tree who’s leaf nodes are all of the possible blacked out combinations.
    (b) solve tree(bt, number): This function will solve the given binary tree puzzle, bt, with the given number of blacked out square, number. It will find all leaf nodes and call evaluate(s) from blackout.py on any leaf node value that has the requested blacked out squares. It will print any solutions it finds, similar to solve(s) in blackout.py. If there are no valid solutions you should output a message stating that fact.
    (c) main(): This function is the main function for the blackout tree section of the project. It should prompt the user for the file containing the puzzles and the number of blacked out squares to look for. It should print the puzzle and call make tree to create the tree. Then solve tree to print the valid solutions for the tree.
    (d) test make tree(): This function should test your make tree function. Ensure you test various different kind of trees.You will have to create expected Binary Trees using the BinaryTree and BinaryTreeNode classes to compare to.