Starting from:
$29.99
HW4: Recursive Puzzle
HW4: Recursive Puzzle
1. Introduction In this exercise, we will solve a puzzle using recursion. Specifically, the puzzle involves traversals of a list.
2. Objectives The purpose of this assignment is to help you: • Sharpen your knowledge on recursion • Refine your ability to translate real-world scenarios into code Note: Before you start, if you are not familiar with recursion you are recommended to review the sample code we covered in lecture first.
3. Background You have been given a puzzle consisting of a row of squares each containing an integer, like this:
The circle on the initial square is a marker that can move to other squares along the row. At each step in the puzzle, you may move the marker the number of squares indicated by the integer in the square it currently occupies. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker three squares to the right because there is no room to move three spaces to the left.
The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves:
Even though this puzzle is solvable—and indeed has more than one solution—some puzzles of this form may be impossible, such as the following one:
In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares.
4. Assignment Write a recursive function that takes a starting position of the marker along with the list representing the squares and a set of all the previously visited indices (this set will always start off as empty). The function should return True if it is possible to solve the puzzle from the starting configuration and False if it is impossible.
You may assume all the integers in the list are positive (or zero) and the last entry, the goal square, is always zero. The values of the elements in the list must be the same after calling your function as they are beforehand, (which is to say if you change them during processing, you need to change them back!)
Additional Examples:
4 0 0 0 0
True - simply move right 4
1 2 1 3 2 0 0
True - move right 1, right 2, right 3
0 1 1 0
False - stuck at index 0
1 0 1 0
False - stuck at index 1
4.1 Approach This problem should be solved recursively. Recursion involves calling a function within itself with input that is ‘closer’ to its base case. The first step is to define your base case (i.e. when have I solved the problem to the point where there are no more subproblems?). The next step
is to determine your recursive call - the key to this step is to ensure your recursive call is getting ‘closer’ to your base case to avoid infinite recursion.
Specifically for this puzzle, you’ll need to keep track of which indices you’ve visited to avoid an infinite traversal (like the [3,1,2,3,0] example). You should use a Set to keep track of where you’ve been, and only move on to check the next destination if it is not in that set and if that destination is in the bounds of the list
1. Introduction In this exercise, we will solve a puzzle using recursion. Specifically, the puzzle involves traversals of a list.
2. Objectives The purpose of this assignment is to help you: • Sharpen your knowledge on recursion • Refine your ability to translate real-world scenarios into code Note: Before you start, if you are not familiar with recursion you are recommended to review the sample code we covered in lecture first.
3. Background You have been given a puzzle consisting of a row of squares each containing an integer, like this:
The circle on the initial square is a marker that can move to other squares along the row. At each step in the puzzle, you may move the marker the number of squares indicated by the integer in the square it currently occupies. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker three squares to the right because there is no room to move three spaces to the left.
The goal of the puzzle is to move the marker to the 0 at the far end of the row. In this configuration, you can solve the puzzle by making the following set of moves:
Even though this puzzle is solvable—and indeed has more than one solution—some puzzles of this form may be impossible, such as the following one:
In this puzzle, you can bounce between the two 3’s, but you cannot reach any other squares.
4. Assignment Write a recursive function that takes a starting position of the marker along with the list representing the squares and a set of all the previously visited indices (this set will always start off as empty). The function should return True if it is possible to solve the puzzle from the starting configuration and False if it is impossible.
You may assume all the integers in the list are positive (or zero) and the last entry, the goal square, is always zero. The values of the elements in the list must be the same after calling your function as they are beforehand, (which is to say if you change them during processing, you need to change them back!)
Additional Examples:
4 0 0 0 0
True - simply move right 4
1 2 1 3 2 0 0
True - move right 1, right 2, right 3
0 1 1 0
False - stuck at index 0
1 0 1 0
False - stuck at index 1
4.1 Approach This problem should be solved recursively. Recursion involves calling a function within itself with input that is ‘closer’ to its base case. The first step is to define your base case (i.e. when have I solved the problem to the point where there are no more subproblems?). The next step
is to determine your recursive call - the key to this step is to ensure your recursive call is getting ‘closer’ to your base case to avoid infinite recursion.
Specifically for this puzzle, you’ll need to keep track of which indices you’ve visited to avoid an infinite traversal (like the [3,1,2,3,0] example). You should use a Set to keep track of where you’ve been, and only move on to check the next destination if it is not in that set and if that destination is in the bounds of the list
1 file (234.8KB)
