Description
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.
5. Submit your work to Mimir Submit puzzle.py to Mimir after you complete your code. The Mimir will automatically grade your submission based on different unit tests. You can submit your code to Mimir up to 30 times to refresh your existing score before the submission deadline. 6. Due date This lab assignment is worth 4 points in the final grade. It will be due by 11:59pm on Mon. Oct 23rd 2017. A penalty of 10% per day will be deducted from your grade, starting at 12:00am. 7. Getting help Start your project early, because you will probably not be able to get timely help in the last few hours before the assignment is due. • Go to the office hours of instructors and TAs. o Prof. Wei Wei: Mon. 2:30 – 3:15pm, Wed. 2:30 – 3:15pm, Thurs. 2:30 – 3:15pm, Fri. 2:30 – 3:15pm @ITE258 o Jenny Blessing: Fri. 12pm – 2pm @ITE140 o Param Bidja: Tues. 2pm – 3pm @ITE140 o Yamuna Rajan: Tues. 11am – 12pm, Wed. 9:30am – 10:30am @ITE140 o Zigeng Wang: Mon. 3pm – 4pm @ITE140 • Post your questions on Piazza. TAs and many of your classmates may answer your questions. • Search the answer of your unknown questions on the Internet. Many questions asked by you might have been asked and answered many times online already.