Install gnome-nibbles
on your VM
sudo apt-get install gnome-nibblesand run it. You don't have to play much, just enough to get the gist. Notice that you have this "worm" that lives on a grid. It's body is made up of a bunch of contiguous cells on that grid. (NOTE: The worm body cannot cross itself! So a worm of length n consists of n distinct cells.) This problem concerns such a worm.
Problem: WormContains
Input: Given arrays X and Y containing the coordinates of the blocks comprising the body of a worm of length n [assume the head is at coordinate (X[0],Y[0]) and remember, no repeated blocks in a worm body!] and a grid coordinate (x,y)
Solution: true if the worm "contains" (x,y), and false otherwise. I.e. true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwiseExample: if n = 5, X : [ 4 4 3 2 1 ], x = 2 ----> return true Y : [ 5 6 6 6 6 ], y = 6 if n = 5, X : [ 4 4 3 2 1 ], x = 2 ----> return false Y : [ 5 6 6 6 6 ], y = 5
Algorithm: onWormEZ(X,Y,n,x,y) Input: arrays X and Y of n integers that represent a worm body, and grid coordinate (x,y) Output: true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwise res1 = (X[n-1] == x and Y[n-1] == y) if res1 == true or n == 1 return res1 else return onWormEZ(X,Y,n-1,x,y)Your Job: Prove that this algorithm is correct.
Algorithm: onWormSPD(X,Y,n,x,y) Input: arrays X and Y of n integers that represent a worm body, and grid coordinate (x,y) Output: true if (X[i],Y[i]) = (x,y) for some i in {0,...,n-1}, false otherwise i = 0, d = 0 do { i = i + d // d = 0 first time through, so this has no effect. // Afterwards, this skip over the next d entries of X & Y d = |X[i] - x| + |Y[i] - y| // d is the "Manhattan distance" of (x,y) from (X[i],Y[i]), i.e. the # of // steps to adjacent squares you'd need to take to get from one to the other. } while (i+d < n and d > 0 ) return d == 0
j = -1, k = -1 while k ≠ NOTFOUND and j < n-1 do j = j + 1 k = search(A,0,n-1,B[j]) ← we assume "search" is an algorithm for the search problem, we if k = NOTFOUND could equally well use linearSearch, binarySearch or gallopSearch. return j else return NOTFOUNDI recommend tracing through this algorithm on example input. For instance, with n=8 and A and B given below you should return 5.
A: | |
B: |