For instructions on how to work on the assignment on Mimir, please review materials in Lab 0. Do not forget to submit your work before the deadline. A Makefile is provided. Run make clean before submitting the folder. Or even better, run make sub and submit the zip file hw2.zip.

Exercise 1. (50 points) Puzzle

In this exercise, we will solve a puzzle using recursion. Specifically, the puzzle involves traversals of an array. We are given a puzzle consisting of a row of squares each containing an integer, like this:

Figure 1: A puzzle configuration.

The circle on the initial square is a marker that can move to other squares along the row. At each step in the puzzle, we 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, we can solve the puzzle by making the following set of moves:

Figure 2: Steps to solve the puzzle.

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, we will need to keep track of which indices have been visited to avoid an infinite traversal (memoization). In our code, we use an array to present the configuration of the puzzle.

1

int a[] = {3, 6, 4, 1, 3, 4, 2, 5, 3, 0}; 

We need to implement the following function.

int puzzle(int a[], int n, int idx, int v[], int p_flag) { 

}

Here a[ ] is the array that configures the puzzle, n is the size of the puzzle, idx is the location of the marker in the array. v[ ] is an array that indicates which indices have already been visited. If the value of v[i] is 1, then the index i has been visited; otherwise, it has not been visited yet. Last, p flag indicates whether to print out a solution to the puzzle.

This function returns 1 if the puzzle is solvable. Otherwise, the functions returns 0. Below is the main() function of the program; note how the above function is used.

int main() {

 int a[] = {1, 2, 3, 4, 5, 6, 7, 0}; int v[8] = {0}; if(puzzle(a, 8, 0, v, 1)) 

 printf(" This puzzle is solvable. "); else 

 printf(" This puzzle is not solvable. "); 

 int b[] = {1, 2, 1, 3, 2, 0, 1, 0}; int v1[8] = {0}; 

 if(puzzle(b, 8, 0, v1, 1)) printf(" This puzzle is solvable. "); 

 else printf(" This puzzle is not solvable. "); 

 int n = 1024; int c[n]; int v2[n]; 

int i, j;

 for(i = 0; i < n; i++) c[i] = i + 1; 

 for(j = 1; j <= n; j++) { 

 for(i = 0; i < n; i++) v2[i] = 0; 

 if(puzzle(c, j, 0, v2, 0)) printf("%d ", j); } 

return 0; }

2

Below output can be used to check correctness of our code.

$ ./puzzle 12345670 7310 This puzzle is solvable. 12132010 76310

This puzzle is solvable. 1 2 4 

8 16 32 64 128 256 512 1024 

Note for the first two puzzles, solutions are shown. The solutions are shown in the reverse order. For example, the solution for the first puzzle is

7310

which indicates that indices 0, 1, 3, and 7 are visited consecutively. Read the rest of the output, and try to figure out why these numbers are printed by reading the code in the

main() function.

Exercise 2. (50 points) Bounded 2D Random Walk

In this problem, we will write a program to simulate a 2D random walk. Imagine a random walker starting at the origin (0, 0) that with equal probabilities goes up, right, down and left. For example, when the walker is at (x,y), with equal probability 1/4, their next location is at (x,y1),(x+1,y),(x,y+1), or (x1,y).

Given a positive integer n, a square is defined by the following four points: (n,n),(n,n),(n,n), and (n,n). We are interested in knowing, on average, what fraction of points within this square the walker visits before they touch one of the edges of the square, given they start their walk from (0, 0).

One extreme example is n = 1. When the walker starts from (0, 0), after one step, they will touch one of the edges of the square. There is only 1 point inside the square, and the walk visits this point before they touch one of the edges. Therefore, this fraction is 1 for n = 1.

In the starter code 2d-walk.c, implement the following function

double two_d_random(int n) 

This function should return the fraction mentioned above. n is the integer mentioned above to define the square boundary.

In the function, we need to use an array to keep track of which coordinates have been visited inside the squared defined by the two coordinates (n,n) and (n,n). When deciding which way to go for the next step, generate a random number as follows.

3

r = rand() % 4;

and treat r = 0, 1, 2, 3 as going up, right, down and left respectively. The random walk should stop once the x coordinate or y coordinate reaches n or n. The function should return the fraction of the visited (x, y) coordinates inside (not including) the square.

Below is the main() function. For each n = 1, 2, 4, . . . , 256, we call the function two_d_random(n) 1, 000 times and calculate and print out the mean of the covered fractions for the given n.

//Do not change the code below int main() { 

 int trials = 1000; 

 srand(12345); for(int n=1; n<=2; n*=2) { 

 double sum = 0.; for(int i=0; i < trials; i++) { 

 double p = two_d_random(n); 

sum += p; }

 printf("%d %.3lf ", n, sum/trials); } 

return 0; }

Below is the desired output. We can use the output to check our code.

$ ./2d-walk 1 1.000 2 0.367 4 0.221 

8 0.154 16 0.122 32 0.101 64 0.085 128 0.077 256 0.071 

4