seq.php

<?php

/*

	Find the length of the longest increasing sequence through adjacent numbers
	(including diagonals) in a rectangular grid of numbers in a language of your
	choice. The solution should handle grids of arbitrary width and height.

	For example, in the following grid, one legal path (though not the longest)
	that could be traced is  0->3->7->9 and its length would be 4.

	8 2 4
	0 7 1
	3 7 9

	The path can only connect adjacent locations (you could not connect 8 -> 9),
	and cannot connect equal numbers (you could not connect 7 -> 7).  The longest
	possible sequence for this example would be of length 5 by tracing the
	path 0->2->4->7->9 or 1->2->4->7->8.

	Write a method, in a language of your choice, that takes a rectangular grid
	of numbers as input, and returns the length of the longest such sequence
	as output.

*/

class Grid
{

	/** protected property grid
	 *
	 *	The grid
	 *
	 * @var multi-dimensional array
	 */
	protected $grid = array( );


	/** public property paths
	 *
	 *	The paths taken
	 *	indexes between this array and $sequences are equivalent
	 *
	 * @var multi-dimensional array
	 */
	public $paths = array( );


	/** public property sequences
	 *
	 *	The sequences followed
	 *	indexes between this array and $paths are equivalent
	 *
	 * @var multi-dimensional array
	 */
	public $sequences = array( );


	/** public property longest_sequence
	 *
	 *	The length of the current longest sequence found
	 *
	 * @var int
	 */
	public $longest_sequence = 0;


	/** public function __construct
	 *
	 *	Class constructor
	 *
	 * @param multi-dimensional array number grid or int size of grid
	 * @return void
	 */
	public function __construct($grid = null) {
		if ( ! empty($grid)) {
			try {
				if (is_array($grid)) {
					$this->set_grid($grid);
				}
				elseif (is_int($grid)) {
					$this->generate_grid($grid, true);
				}

				if ($this->grid) {
					$this->sequence( );
				}
			}
			catch (Exception $e) {
				echo $e->getMessage( );
			}
		}
	}


	/** public function set_grid
	 *
	 *	Setter method for grid property
	 *
	 * @param multi-dimensional array number grid
	 * @return void
	 */
	public function set_grid($grid = null) {
		if ( ! is_array($grid)) {
			throw new Exception(__METHOD__.': grid is not an array');
		}

		if ( ! is_array($grid[0])) {
			throw new Exception(__METHOD__.': grid element is not an array');
		}

		// reset any passed indexes to numeric values
		$grid = array_values($grid);

		$size = count($grid[0]);
		foreach ($grid as & $col) { // mind the reference
			if ($size !== count($col)) {
				throw new Exception(__METHOD__.': grid contains row of unequal size');
			}

			// reset any passed indexes to numeric values
			$col = array_values($col);

			foreach ($col as $elem) {
				if ( ! is_numeric($elem)) {
					throw new Exception(__METHOD__.': grid element is not a number');
				}
			}
		}
		unset($col); // kill the reference

		$this->grid = $grid;
	}


	/** public function get_grid
	 *
	 *	Getter method for grid property
	 *
	 * @param multi-dimensional array number grid
	 * @return void
	 */
	public function get_grid( ) {
		return $this->grid;
	}


	/** public function find_path
	 *
	 *	Find the longest path through the grid from the given point
	 *	returned as an array of paths
	 *
	 * @note this function is recursive
	 *
	 * @param int start x-value
	 * @param int start y-value
	 * @param array current sequence
	 * @return void
	 */
	public function find_path($x_start, $y_start, $cur_sequence = array( ), $cur_path = array( )) {
		if (empty($this->grid)) {
			throw new Exception(__METHOD__.': grid not set');
		}

		$x = (int) $x_start;
		$y = (int) $y_start;

		$here = $this->grid[$y][$x];

		$cur_sequence[] = $here;
		$cur_path[] = '['.$x.', '.$y.']';

		// look around the current point and find possible paths
		foreach (array(-1, 0, 1) as $y_i) {
			foreach (array(-1, 0, 1) as $x_i) {
				if ( ! isset($this->grid[$y + $y_i][$x + $x_i]) || ($this->grid[$y + $y_i][$x + $x_i] <= $here)) {
					continue;
				}

				$this->find_path($x + $x_i, $y + $y_i, $cur_sequence, $cur_path);
			}
		}

		// the sequence may not be complete at this point
		// but the data will get stored in case the sequence goes no further
		// any additional sequence values will have been added to the path
		// when the function recursed through itself above

		if (count($cur_sequence) >= $this->longest_sequence) {
			$this->longest_sequence = count($cur_sequence);
		}

		$this->sequences[count($cur_sequence)][] = $cur_sequence;
		$this->paths[count($cur_sequence)][] = $cur_path;
	}


	/** public function sequence
	 *
	 *	Find the length of the longest increasing sequence through adjacent numbers
	 *	(including diagonals) in a rectangular grid of numbers.
	 *
	 * @param void
	 * @return array of solution paths and solutions (multiples possible) or false on failure
	 */
	public function sequence( ) {
		if (empty($this->grid)) {
			throw new Exception(__METHOD__.': grid not set');
		}

		$height = count($this->grid);
		$width = count($this->grid[0]);

		if ( ! $height || ! $width) {
			return false;
		}

		// parse the grid looking for paths
		for ($y = 0; $y < $height; ++$y) {
			for ($x = 0; $x < $width; ++$x) {
				$paths[] = array($x, $y, $this->grid[$y][$x], $this->find_path($x, $y));
			}
		}

		return $this->sequences[$this->longest_sequence];
	}


	/** public function generate_grid
	 *
	 *	Generates a square grid of random numbers of given $size, with
	 *	min-value of 0 and max-value of $size^2.
	 *
	 * @param integer grid size
	 * @param bool save grid to class
	 * @return multi-dimensional array integer grid
	 */
	public function generate_grid($size, $save = false) {
		$grid = array( );
		$max_val = $size * $size;

		for ($i = 0; $i < $size; ++$i) {
			for ($j = 0; $j < $size; ++$j) {
				$grid[$i][$j] = mt_rand(0, $max_val);
			}
		}

		if ($save) {
			$this->set_grid($grid);
		}

		return $grid;
	}

}



//* ---------------------- //

	$grid = array(
		array(8, 2, 4),
		array(0, 7, 1),
		array(3, 7, 9),
	);
	print_grid($grid);

	$Grid = new Grid( );
	$Grid->set_grid($grid);
	$path = $Grid->sequence( );
	g($path);
	g($Grid);

/*/

	$Grid = new Grid(10);
	print_grid($Grid->get_grid( ));
	g($Grid->sequences[$Grid->longest_sequence]);
	g($Grid->paths[$Grid->longest_sequence]);

// ---------------------- */


	// replacement function for my auto-included debug function
	if ( ! function_exists('g')) {
		function g($var) {
			echo '<pre>';
			print_r($var);
			echo '</pre>';
		}
	}


	/** function print_grid
	 *
	 *	Prints the grid out in an easy to see format
	 *
	 * @param array grid
	 * @action outputs the grid to the screen
	 * @return void
	 */
	function print_grid($grid) {
		// adjust the column size based on number size
		$sized = array( );
		$iter = new RecursiveIteratorIterator(new RecursiveArrayIterator($grid));
		foreach ($iter as $val) {
			$sized[] = $val;
		}

		rsort($sized);
		$size = strlen((string) $sized[0]);

		echo '<pre>';

		foreach ($grid as $col) {
			echo "\t";

			foreach ($col as $elem) {
				echo sprintf("%{$size}d", $elem).'  ';
			}

			echo "\n\n";
		}

		echo '</pre>';
	}