Winter 2005 UCLA CS 31 Section 1 (Shinnerl)

Last Update: 6:30pm Tues., 2/22

1. Is there a clever trick to do diagonal wrap-around as concisely as the online traversal example does horizontal and vertical wrap-around? Or do we have to handle each diagonal wrap around case separately, for both kinds of puzzle shapes (nrows > ncols and nrows <= ncols)?

   Using the i+j and i-j invariants described in the spec., consider writing a function which does the following:

   1. Accepts current location i, j and puzzle dimensions nrows, ncols and the search direction as input.
   2. Determines the next location in the puzzle to examine in the given direction, according to the following rules.
   3. Increments, decrements, or leaves unchanged i and j separately according to the values in the increment arrays indexed by the search direction index (as in the given example).
   4. The minimum and maximum legal values of i and j for the given starting location, search direction, and puzzle dimensions are determined.
   5. If the new value of i is less than its minimum value, replace it by its maximum value and update j such the appropriate invariant (i+j or i-j) is preserved.
   6. Similarly, if i is greater than its maximum value, replace it by its minimum value and update j so that the appropriate invariant (i+j or i-j) is preserved.
   Although this solution is not quite as compact as the given example, it does handle all possible cases together in one block of code. I don't know of any way to avoid explicitly checking i > nrows etc. altogether.

   Also, I found out that we can't simply replace i (or j) with its max (or min.) value when it's less than its minimal (or greater than its maximum) value.

   You have to determine its max. or min. value based on the diagonal or antidiagonal it's in. It isn't always the same. E.g. consider the puzzle below:

                          b a c k a
                          t a p m w
                          d i n g e
                          t i f k z
   

   For the diagonal containing the the letter 'd' (position (2,0)), the minimum value of i is 2 and the max is 3. But for the diagonal containing the 'w', the min value of i is 0 and the max value of i is 1.

   The trick is to define a function that can determine these minimum and maximum values for any location (i,j) in any puzzle with dimensions (nrows, ncols). Hint: for diagonals, i-j is invariant, and there is a simple relationship between i-j and the min./max. legal values of i and j. It helps to handle the cases i < j and i > j separately.