gistfile1.java

package cfi;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Write a function that accepts four arguments. The first two arguments are the size of the grid (h x w),
 * filled with ascending integers from left to right, top to bottom, starting from 1. The next two arguments
 * are the starting positions, the row (r) and column (c)
 * @author Bernie Margolis
 */
public class Spiral {
	enum Direction {
		Up,
		Down,
		Left,
		Right
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(Arrays.asList(doSpiral(2,4,1,2)).toString());
		System.out.println(Arrays.asList(doSpiral(5,5,3,3)).toString());
	}
	
	/*
	 * @param h height of the grid
	 * @param w width of the grid
	 * @param r starting row
	 * @param c starting column
	 * @return array of integers obtained by spiraling outward anti-clockwise from the r and c, starting upward.
	 */
	private static Integer [] doSpiral(int h, int w, int r, int c) {
		ArrayList<Integer> results = new ArrayList<Integer>();
		
		int numGridSpots = h * w;
		int discovered = 0;
		int currentArmLength = 1;
		int movesOnCurrentArm = 0;
		boolean incrementArmLengthOnSwitch = false;
		Direction currentDirection = Direction.Up;
		
		while (discovered < numGridSpots) {
			int currentSpot = getGridSpot(h, w, r, c);
			if (currentSpot > 0) {
				// If we discover a spot within the boundaries add it to the results
				discovered++;
				results.add(currentSpot);
			}
			
			switch (currentDirection) {
				case Up:
					r--;
					break;
				case Left:
					c--;
					break;
				case Down:
					r++;
					break;
				case Right:
					c++;
					break;
			}
			
			movesOnCurrentArm++;
			if (movesOnCurrentArm == currentArmLength) {
				// Time to switch directions
				currentDirection = switchDirection(currentDirection);
				
				// Reset the number of moves along the current arm every time we switch
				movesOnCurrentArm = 0;

				// Need to increment the length of the arm every other switch
				if (incrementArmLengthOnSwitch) {
					currentArmLength++;
				}
				
				incrementArmLengthOnSwitch = !incrementArmLengthOnSwitch;
			}
		}
		
		return results.toArray(new Integer[numGridSpots]);
	}
	
	private static Direction switchDirection(Direction currentDirection) {
		Direction newDirection;
		switch (currentDirection) {
			case Up:
				newDirection = Direction.Left;
				break;
			case Left:
				newDirection = Direction.Down;
				break;
			case Down:
				newDirection = Direction.Right;
				break;
			case Right:
				newDirection = Direction.Up;
				break;
			default:
				// Should never happen
				throw new IllegalArgumentException("Unrecognized direction: " + currentDirection);
		}

		return newDirection;
	}
	
	private static int getGridSpot(int h, int w, int r, int c) {
		int gridSpot;
		if (c < 1 || c > w || r < 1 || r > h) {
			// Reject anything outside the boundaries
			gridSpot = -1;
		} else {
			gridSpot = ((r - 1) * w) + c;			
		}

		return gridSpot;
	}

}