COMP 2012H Honors Object-Oriented Programming and Data Structures

Lab 2 Arrays and Functions

Common Errors

  1. Indexing errors when implementing swipe(), copy_grid(), and gridNotEqual() functions.
    • for (int i = 0; i < 3; i++), instead of i < 4.
    • for (int i = 4; i > 0; i--), instead of for (int i = 3; i >= 0; i--)
    • Wrong direction of indexing.

  2. Not properly combining or shifting the numbers based on the rules.
    • Shifting only 1 space instead of through all empty space.
    • Recursive combinations, e.g. (4, 2, 0, 2) becoming (8, 0, 0, 0), the 2's combine into a 4 and then the 4's combine again.
    • Not shifting after combining.

  3. Still generating a random number even on an invalid swipe move (when the grid doesn't change).

End of Common Errors

Interesting Cases

  1. Using a completely random trial-and-error generate().

    bool success = false;
while (!success) {
	int i = rand() % 4;
	int j = rand() % 4;
	if (grid[i][j] == 0) {
		grid[i][j] = getRandomNumber();
		success = true;
	}
	// ...
    • Because the grid is small, even for the worst case situation of only 1 empty space, expected case takes 16 trials, but worst case will take much longer than that, since 16 trials does not guarantee seeing a 1/16 success, and this algorithm doesn't scale to larger problems.

  2. Using matrix inversions and transpositions for the different directions of swipe().
    • One student only implemented swipe_left(), and then implemented inverse() and transpose() functions to implement the other directions. While the code is clean, the efficiency is not, because of all the array copying in the inverse() and transpose() functions.
    • We asked the student to re-implement the four swipe() directions as the lab question instead.

End of Interesting Cases