using System;
using System.Collections;

namespace MouseMaze
{
	#region Supplied Interface

	public interface IMouse 
	{
		bool Move(Direction d);
		bool IsCheeseHere();
	}

	public enum Direction 
	{
		North,
		East,
		South,
		West
	}

	#endregion

	class CheeseAppropriator
	{
		private CheeseAppropriator()
		{
		}

		internal struct MouseState
		{
			internal IMouse mouse;
			internal int currentX;
			internal int currentY;
			internal bool gotCheese;
			internal Hashtable visitedLocations;
			internal Stack backtrackStack;
		}

		public const int Y_NORTH = -1;
		public const int Y_SOUTH = 1;
		public const int X_WEST = -1;
		public const int X_EAST = 1;

		private static bool MoveIfAppropriate(Direction d, ref MouseState ms)
		{
			Direction btdir;
			int destX = ms.currentX;
			int destY = ms.currentY;

			switch (d)
			{
				case Direction.North:
					btdir = Direction.South;
					destY += Y_NORTH;
					break;
				case Direction.South:
					btdir = Direction.North;
					destY += Y_SOUTH;
					break;
				case Direction.East:
					btdir = Direction.West;
					destX += X_EAST;
					break;
				case Direction.West:
					btdir = Direction.East;
					destX += X_WEST;
					break;
				default:
					throw new Exception("Tried to move in invalid Direction.");
			}

			string targetKey = String.Format("{0}.{1}", destX, destY);

			// Short circuiting will only call Move() if we haven't been to the
			// target square already.
			if ( !ms.visitedLocations.ContainsKey(targetKey) && ms.mouse.Move(d) )
			{
				// Move succeeded, the mouse is now in the new location, so
				// update the MouseState data.
				ms.currentX = destX;
				ms.currentY = destY;
				ms.backtrackStack.Push(btdir);
				ms.visitedLocations[targetKey] = true;
				ms.gotCheese = ms.mouse.IsCheeseHere();
				return true;
			}
			// Either we've been there already, or Move() failed. We're still
			// in the same location we started in and the MouseState hasn't
			// been changed.
			return false;
		}

		public static bool FindCheese(IMouse mouse)
		{
			// First off, handle the pathological case where we start
			// directly on top of the cheese.
			if (mouse.IsCheeseHere())
				return true;

			MouseState ms;

			ms.mouse = mouse;
			ms.currentX = 0;
			ms.currentY = 0;
			ms.gotCheese = false;

			// We'll just use a Hashtable in lieu of a more appropriate
			// multidimensional array or similar because the size of the maze
			// is not known, other than it's "some reasonable size".
			// Keys of this Hashtable will be strings in the format x+"."+y
			// for clarity's sake -- non-string keys obviously provide better
			// performance (no String.Format calls) and memory usage.
			// If a key exists in this Hashtable, we know we've visited that
			// square so we'll never try to walk into it again unless we're
			// backtracking.
			ms.visitedLocations = new Hashtable();
			ms.visitedLocations["0.0"] = true;

			// So we can backtrack when we hit dead ends.
			ms.backtrackStack = new Stack();

			// Some mice might give up; those mice don't belong at Microsoft.
			while (!ms.gotCheese)
			{
				// Expression short-circuiting will move us only in the first
				// appropriate direction, where appropriate is defined as to
				// a square we haven't been in before, and that we can successfully
				// move to.
				if ( !MoveIfAppropriate(Direction.West, ref ms) &&
					!MoveIfAppropriate(Direction.North, ref ms) &&
					!MoveIfAppropriate(Direction.South, ref ms) &&
					!MoveIfAppropriate(Direction.East, ref ms))
				{
					// Nowhere to go. Backtrack.
					if ( ms.backtrackStack.Count > 0 )
					{
						Direction btdir = (Direction)ms.backtrackStack.Pop();
						bool moveRes = ms.mouse.Move(btdir);
						if (!moveRes)
							throw new Exception("Inconsistent maze state.");
						switch (btdir)
						{
							case Direction.North:
								ms.currentY += Y_NORTH;
								break;
							case Direction.South:
								ms.currentY += Y_SOUTH;
								break;
							case Direction.East:
								ms.currentX += X_EAST;
								break;
							case Direction.West:
								ms.currentX += X_WEST;
								break;
							default:
								throw new Exception("Backtrack stack corrupt.");
						}
					}
					else
					{
						// No more backtracking to do! No path to cheese.
						return false;
					}
				}
			}

			// Cheese found.
			return true;
		}
	}
}