diff --git a/python/SlidingBfsReference.py b/python/SlidingBfsReference.py index 49a830d..af19351 100644 --- a/python/SlidingBfsReference.py +++ b/python/SlidingBfsReference.py @@ -4,7 +4,7 @@ from pprint import pprint level_to_pos = {} pos_to_level = {} -def slidingBfsSolver(puzzle, max_level=-1): +def slidingBfsSolver(puzzle, width, height, max_level=-1): """BF visit the entire puzzle graph, build level_to_pos, pos_to_level structures.""" solution = puzzle level = 0 @@ -19,7 +19,7 @@ def slidingBfsSolver(puzzle, max_level=-1): ### For every position on the last level (these farthest-away positions are the "frontier") for position in level_to_pos[level-1]: ### For every child of those frontier positions - for child in Sliding.children(W, H, position): + for child in Sliding.children(width, height, position): ### If it's the first time we've seen this child if child not in pos_to_level: ### Update the mappings to remember it, and it will be part of the new frontier @@ -31,7 +31,6 @@ def slidingBfsSolver(puzzle, max_level=-1): def main(): - global W, H parser = argparse.ArgumentParser( description="Returns back the entire solution graph.") parser.add_argument("-H", "--height", type=int, default=2, @@ -40,11 +39,8 @@ def main(): help="width of the puzzle") args = parser.parse_args() - W = args.width - H = args.height - - p = Sliding.solution(W, H) - slidingBfsSolver(p) + p = Sliding.solution(args.width, args.height) + slidingBfsSolver(p, args.width, args.height) if __name__ == "__main__": diff --git a/python/proj2-1.txt b/python/proj2-1.txt new file mode 100644 index 0000000..00a7d55 --- /dev/null +++ b/python/proj2-1.txt @@ -0,0 +1,15 @@ +Partner 1 Name: +Partner 1 Login: + +Partner 2 Name: +Partner 2 Login: + +1. + + + +2. + + + +3. diff --git a/spec/img/sliding_puzzle.png b/spec/img/sliding_puzzle.png new file mode 100644 index 0000000..49fddd6 Binary files /dev/null and b/spec/img/sliding_puzzle.png differ diff --git a/spec/index.html b/spec/index.html index 8d8e53d..fe36993 100644 --- a/spec/index.html +++ b/spec/index.html @@ -27,6 +27,7 @@ All updates to the project spec will be listed in this section.

Clarifications/Reminders

@@ -258,7 +259,17 @@ pos_to_level = {}

Getting started

-

Copy the files in the directory ~cs61c/proj/02 to your proj2 directory, by entering the + +

As mentioned above, we are going to be solving the generalized Fifteen puzzle, which we call the Sliding puzzle (with input parameters width and height). + +This puzzle consists of numbered tiles in a random ordering with one tile missing. The objective of the game to place the tiles in order as shown in the image below, for the 3x3 case.

+ +

+If you've never played the game before, it might be helpful (and fun!) to try it here. That website allows you to play a 3x3, 4x4, or 5x5 puzzle. +

+ +

Starter Code

+

To get started on the project, copy the files in the directory ~cs61c/proj/02 to your proj2 directory, by entering the following command:

@@ -269,6 +280,8 @@ $ cp -r ~cs61c/proj/02 ~/proj2

You are free (and encouraged) to define and implement additional helper functions, but they must be in SlidingBfsSpark.py. Changes you @@ -290,7 +303,9 @@ $ cp -r ~cs61c/proj/02 ~/proj2

As described above, this MapReduce job will take as input a width and height describing a Sliding puzzle. Using the solution, it will repeatedly expand the BFS tree, and generate a mapping between every position and the level at which it is in the BFS tree.

-

More precisely, we expect your output to be a text file of the following form. (for example, for a 2x2 case):

+

We represent a Sliding puzzle as a Python tuple of strings. Each tile is an alphabetic character and the empty space is represented with a hyphen '-'.

+ +

Therefore, after running your MapReduce job, we expect your program to produce a text file of the following form. (for example, for a 2x2 case):

 0 ('A', 'B', 'C', '-')
 1 ('A', '-', 'C', 'B')
@@ -309,7 +324,7 @@ $ cp -r ~cs61c/proj/02 ~/proj2

Here's a recommended plan of attack:

+

Follow Up Questions to Submit

+

You will submit you and your partners answers to the following questions in proj2-1.txt. +

+1. Some games (e.g., Rush Hour, Klotski, etc.) do not have a single solution, but a set of solution positions (and a single starting position). This is because those puzzles only care about the final position of a particular block, and don't care about the location of the other blocks. In terms of an API change, solution() wouldn't be a no-argument function that returns the single solution position anymore, but instead be a predicate that took in a position and returned whether it was in the solution set or not. Your friend suggests to generate all the permutations of blocks (or whatever else is being moved / rotated / changed in the puzzle), call them all solutions (level = 0), and proceed normally. What is one potential problem with this idea? (Hint: take a look at the number of positions in the 2x2 final solution and compare that with all the ways of permuting four pieces). +

+ +

+2. What's a better algorithm to solve these kinds of puzzles? How would you modify your original solver? +

+ +

+3. On the same note, what needs to be changed to solve loop-free puzzles, like Peg Solitaire. For every position, rather than the distance to the solution, what might you store? What changes would you make to your solver? In the case of Peg Solitaire, would it change the memory requirements of your solver? +

+

Debugging and Testing

You should test your code on one of the following servers. (See below for benchmark information). @@ -380,6 +409,11 @@ $ cp ~cs61c/proj/02/<NAME OF FILE> ~/proj2

  • Be sure to test all (2x2, 3x3, 5x2) puzzle sizes as passing the 3x3 benchmark does not mean you will necessarily reach the 5x2 benchmark as well.
    • +
  • Finally, a portion of your grade will correspond to your answers to the follow up questions in proj2-1.txt + + +

    Other Grading Notes

    +