The game of jumpIt consists of a board with n positive integ

The 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:

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.

For this homework assignment, you will write different solutions to this problem. First, you need to download the file hw2_template by following this link (is in most bottom). This template contains some pre-written code and stubs for different functions you will need to complete. Also download a sample input file from here.

[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 or 52 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

(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) file for downloading.

Solution

As mentioned in the question, there is no link found here.So, upto the level I understood the rules of games, i have done basic java programming to implement the game rules. In the code, there are two functions defined, one is to take the input costs for the board and the other function is to traverse the board and to find the lowest cost in treversing the board.

class JumpItGame
{
public static void main(String args[])
{
enter_board();
}
void enter_board()
{
int arr[] = new int [52];
   arr[0] = 0;
Scanner scanner=new Scanner(System.in);
   System.out.println(\"Enter the costs in the board:\");
for ( i=1; i<arr.length; i++){
arr[i]=scanner.nextInt();
   System.out.println(arr[i]);
}
     
   jumpIt(arr);
  
     
}
  
void jumpIt(int arr[])
{
int cost =0;
   int i=1;
   System.out.println(\"the costs traversed are:\");
       while(i<arr.length){
if(arr[i] < arr[i+1])
       {
               cost += arr[i];
               i++;
   System.out.print(\" \"+arr[i]);
}  
else
{
               cost += arr[i+1];
               i += 2;
   System.out.print(\" \"+arr[i]);
}          
}
   System.out.println(\"The total cost of jumping the board:\"+cost);
}
}