7457
he game of jump-It consists of a board with n positive integers in a row except for the first column, which always contains zero. These numbers represent the cost to enter each column. Here is a sample game board where n is 6:
0 3 80 6 57 10
The object of the game is to move from the first column to the last column in the lowest total cost. The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, then move to 10 for a total of 80 + 57 + 10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3 + 6 + 10 = 19.
Here is a template code. This template contains some pre-written code and stubs for different functions you will need to complete.
————————————————————————————————–
import time def jumpIt(board): ”’Recursive implementation for the jump it game @board — a list representing a playing board where each cell contains a cost associated with visiting that cell @return the cheapest cost to play the game ”’ return 1 #replace this line by your code costDict = {} # dictionary for caching solutions to use with topDownJumpIt() def topDownJumpIt(board, i): “””Top-down recursive implementation for the jumpIt game board — a list where each cell a cost associated with visiting that cell i — is index of the cell where game stars Function return minimum total cost of playing the game “”” n = len(board) if costDict.get(i, None) == None: # if value has not been calculated # calculate and store it if i == n – 1: #if starting game at last cell costDict[i] = board[n – 1] elif i == n – 2: #your code goes here pass #remove this line else: #board length is at least 3 #your code goes here pass #remove this line return 1 #replace by actuall value to be returned cost = [] #cache table where cost[i] will store the minimum #cost of playing the jump-It game starting at cell i def jumpIt_BottomUp(board): “””BottomUp implementation board – list with cost associated with visiting each cell Function returns minimum total cost to reach last cell starting at 1st cell “”” n = len(board) #your code goes here return 1 #replace by actuall value to be returned path = [] #global table to store path leading to cheapest cost def topDownJumpIt_withPath(board, i): ”’Extended top-down implementation to also find the actual path (i,e, cells visited on a minimin cost path for playing the jump it game) Store the special marker -1 at path[len(board) – 1] to indicate that the last cell has been reached Function returns cheapest cost of playing the game starting at index i ”’ n = len(board) path[n – 1] = -1 # special marker indicating end of path “destination/last cell has been reached” pass def jumpIt_BottomUp_withPath(board): ”’Extended bottom-up implementation to also find the actual path (i,e, cells visited on a cheapest cost path for playing the jump-It game) Store the special marker -1 at path[len(board) – 1] to indicate that the last cell has been reached Function returns cheapest cost of playing the game starting at index 0 ”’ n = len(board) path[n – 1] = -1 # special marker indicating end of path “destination/last cell has been reached” pass def displayPath(board): “”” This function displays the path leading to cheapest cost – function displays indices of cells visited In addition, function displays contents of visited cells board – list with cost associated with visiting each cell path – global list where path[i] indicates the cell to move to from cell i “”” cell = 0 # start path at cell 0 print(“Path showing indices of visited cells:”, end = ” “) print(0, end =””) path_contents = “0” #cost of starting/1st cell is 0 – added for easier tracing while path[cell] != -1: # -1 indicates that destination/last cell has been reached print(” ->”, path[cell], end = “”) cell = path[cell] path_contents += ” -> ” + str(board[cell]) print() print(“Path showing contents of visited cells:”, path_contents) def main(): global cost, costDict, path f = open(“input.txt”, “r”) for line in f: lyst = line.split() # tokenize input line, it also removes EOL marker board = list(map(int, lyst)) cost = [0] * len(board) #create the cache table start = time.time() # store number of seconds since Unix Epoch min_cost = jumpIt(board) #costDict = {} #start with an empty dictionary for every board #min_cost = topDownJumpIt(board, 0) #min_cost = jumpIt_BottomUp(board) #path = cost[:] # create a table for path that is identical to path #min_cost = jumpIt_BottomUp_withPath(board) #displayPath(board) elapsed = time.time() – start #time it took function print(min_cost) f.close() main()
————————————————————————————————–
Also, here is a sample input file, input.txt
————————————————————————————————–
0 5 75 7 43 11 0 3 80 6 57 10 0 98 7 44 25 3 5 85 46 4 0 57 59 83 9 42 70 0 20 49 96 53 7 43 77 0 24 17 15 61 49 61 8 65 43 26 99 7 57 97 50 93 6 82 52 0 6 3 2 14 5 17 3 11 9 4 11 0 24 17 15 61 49 61 8 65 43 26 99 7 57 97 50 93 6 82 52 2 4 7 9 1 59 83 9 42 70
————————————————————————————————–
[50 points] Now, you will write a recursive solution to the jump-It problem by filling in the code for the function jumpIt(board). This function computes and returns the cheapest cost of playing the game for an arbitrary game board represented as a list. Because the function can take long time to run on large boards, you can assume that the board size is at most 50 cells. For this function, your code does not need to compute the actual sequence of jumps, it only needs to compute the cheapest cost of this sequence. (Hint: Think about the special and simple cases. For example, what is the cheapest cost of playing the game when the board has exactly 1, 2, or 3 cells? Alternatively, you can think about what the minimum cost would be if the game starts at the last cell, the cell before the last cell, or at the cell that is two cells away from the last cell. What is the recursive or general case?)
The code provided in the function main() reads input from a text file named input.txt and sends output to stdout (the computer’s screen). The input file consists of a sequence of lines, where each line corresponds to a board. The numbers on a line are the costs to enter the columns on the board. For example, the above board is represented in the input file as
0 3 80 6 57 10
Sample input file is as follows:
0 5 75 7 43 11
0 3 80 6 57 10
0 98 7 44 25 3 5 85 46 4
0 57 59 83 9 42 70
0 20 49 96 53 7 43 77
0 24 17 15 61 49 61 8 65 43 26 99 7 57 97 50 93 6 82 52
0 6 3 2 14 5 17 3 11 9 4 11
0 24 17 15 61 49 61 8 65 43 26 99 7 57 97 50 93 6 82 52 2 4 7 9 1 59 83 9 42 70
The corresponding output is as follows:
23
19
87
138
186
330
33
478
[25 points] Now, you need to provide a top-down recursive implementation for solving the jump-It problem. First, study the corresponding top-down solutions for the provided in slides 34-37 of the PowerPoints and the programs fibonacci.py, topDown_minCost.py and topDown_minCost_v2.py on trace). Then, fill in the code for the function topDownJumpIt(board, i). This function computes and returns the cheapest cost of playing the game when starting the game at cell i. Then comment the line in the function main() that tests the function jumpIt() and uncomment the lines:
costDict = {} #start with an empty dictionary for every board.
min_cost = topDownJumpIt(board, 0)
that test this function by playing the game starting at cell 0.
Add the following line to the end of the input file, input.txt, and run the program:
0 53 98 29 11 64 40 14 3 32 71 35 41 66 56 3 21 54 90 59 18 18 44 5 52 6 40 92 69 87 94 78 64 67 17 60 19 40 58 36 9 59 27 40 90 8 1 84 24 83 10
This represents a board of size 51 cells. You will notice that the program runs fast. Try to test the jumpIt function from part 1 on this board. You will notice that the program takes a very long time on this line. Experiment with different lengths of this new line to get a feeling of the difference in time the different implementaions take to execute to completion. When you are done with the experiment, remove this new line from the input file.
[25 points] Now, you will provide a bottom-up implementation for solving the jump-It game problem. Before you do that, make sure to study the corresponding implementations for the Fibonacci sequence and “minimum cost path” problems (code is provided in the files fibonacci.py and minCost.py on trace). Then, fill in the code for the function jumpIt_BottomUp(board) that provides such implementation. This function computes and returns the minimum cost of playing the jump-It game starting at index 0 on the playing board. Remember that, in the bottom-up approach, you need to fill in the cache table, cost, starting with the basic cases. Then, fill the rest of the cache table in a bottom up fasion until the solution for the whole problem is found. Notice, solution of the whole problem (which corresponds to playing the game starting at index 0) is found when cost[0] is filled.
Comment and uncomment appropriate lines in the function main() to test this function. Finally, perform a similar experiment on a long board similar to what you did in the previos part.
[Extra credit: 20 points] Fill in the code for the function jumpIt_BottomUp_withPath(board), which extends the solution provided by the function jumpIt_BottomUp(board) to also find a path of the actual cells visited in a path leading to playing the jump-It game with the cheapest cost. To do this, maintain an additional list, path, where path[i] contains the index of the next cell visited after cell i.
Comment the call testing the previous funcion, then uncomment the following lines in main()
path = cost[:] # create a table for path that is identical to path
min_cost = jumpIt_BottomUp_withPath(board)
displayPath(board)
Testing this code on the board represented by the list [0, 3, 80, 6, 57, 10] would produce the following output:
Path showing indices of visited cells: 0 -> 1 -> 3 -> 5
Path showing contents of visited cells: 0 -> 3 -> 6 -> 10
