OfficeEscapeSolver, Action file, Test Cases, and PowerShell Test Script

file.txt

Step

1 stp, 100%, mirror
 o.         o
 |.  -->    |
x#        x#


Climb off

1 stp, 100%, mirror
 =         =
 o.  -->    o
 |.         |
x=        x= 


Shuffle

3 stp, 100%, mirror
 %.         %
x#   -->  x# 


Clamber Up

10 stp, 95%, mirror
 o.         %
 |#  -->    #
x#        x#


Drop

0 stp, 100%
 o         
 |  -->   o
x.       x|


Drop (Stand)

0 stp, 100%
 %        o
x.  -->  x|


Climb Up

2 stp, 100%
 =        o
 o  -->   |
x|       x


Crouch

2 stp, 100%
 o
 |  -->   %
x#       x#


Stand

4 stp, 100%
 .        o
 %  -->   |
x#       x#


Short Jump

4 stp, 95%, mirror
 o..          o
 |..  -->     |
x#         x#


Long Jump

7 stp, 75%, mirror
 o...           o
 |...  -->      |
x#          x#


High Jump

12 stp, 90%, mirror
 ..         o
 o.  -->    |
 |          
x#        x# 


Put your back into it!

20 stp, 80%, mirror
 o!.         _o
 |!.  -->    _|
x#         x#


Punch

8 stp, 90%, mirror
 o!        o_
 |   -->   |
x#        x#


Kick

8 stp, 85%, mirror
 o         o
 |!  -->   |_
x#        x#


Stamp

8 stp, 90%
 o        o
 |  -->   |
x!       x_

OfficeEscapeSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace OfficeEscapeSolver
{
	public struct Vector
	{
		public static Vector Zero = new Vector(0, 0);
		
		public int X {get; private set;}
		public int Y {get; private set;}
		
		public Vector(int x, int y) : this()
		{
			X = x;
			Y = y;
		}
		
		#region Equals and GetHashCode implementation
		public override bool Equals(object obj)
		{
			return (obj is Vector) && Equals((Vector)obj);
		}
		
		public bool Equals(Vector other)
		{
			return this.X == other.X && this.Y == other.Y;
		}
		
		public override int GetHashCode()
		{
			int hashCode = 0;
			unchecked {
				hashCode += 1000000007 * X.GetHashCode();
				hashCode += 1000000009 * Y.GetHashCode();
			}
			return hashCode;
		}
		
		public static bool operator ==(Vector lhs, Vector rhs)
		{
			return lhs.Equals(rhs);
		}
		
		public static bool operator !=(Vector lhs, Vector rhs)
		{
			return !(lhs == rhs);
		}
		#endregion
		
		public Vector Mirror()
		{
			return new Vector(-X, Y);
		}
		
		public static Vector operator +(Vector l, Vector r)
		{
			return new Vector(l.X + r.X, l.Y + r.Y);
		}
		
		public static Vector operator -(Vector l, Vector r)
		{
			return new Vector(l.X - r.X, l.Y - r.Y);
		}
		
		public override string ToString()
		{
			return X + ", " + Y;
		}
	}
	
	public class CellEffect
	{
		public char NewChar {get; private set;}
		public Vector Offset {get; private set;}
		
		public CellEffect(char newChar, Vector offset)
		{
			NewChar = newChar;
			Offset = offset;
		}
	}
	
	public class CellCondition
	{
		public Func<char, bool> Test {get; private set;}
		public Vector Offset {get; private set;}
		
		public CellCondition(Func<char, bool> test, Vector offset)
		{
			Test = test;
			Offset = offset;
		}
		
		public CellCondition(string accept, Vector offset)
		{
			Test = c => accept.Contains(c);
			Offset = offset;
		}
	}
	
	public class Act
	{
		public string Name {get; private set;}
		public bool Mirror {get; private set;}
		public int Effort {get; private set;}
		public decimal Chance {get; private set;}
		public bool StartCrouched {get; private set;}
		public bool EndCrouched {get; private set;}
		public Vector Motion {get; private set;}
		public List<CellCondition> Conditions {get; private set;} // relative to start location
		public List<CellEffect> Effects {get; private set;} // also relative to start location
		
		private Act CreateMirrorClone()
		{
			return new Act(this);
		}
		
		// mirror clone
		private Act(Act right)
		{
			Name = right.Name.Substring(0, right.Name.Length - 5) + "Left";
			Mirror = true;
			Effort = right.Effort;
			Chance = right.Chance;
			StartCrouched = right.StartCrouched;
			EndCrouched = right.EndCrouched;
			Motion = right.Motion.Mirror();
			
			Conditions = new List<CellCondition>();
			Effects = new List<CellEffect>();
			
			foreach (var cc in right.Conditions)
			{
				Conditions.Add(new CellCondition(cc.Test, cc.Offset.Mirror()));
			}
			
			foreach (var ce in right.Effects)
			{
				Effects.Add(new CellEffect(ce.NewChar, ce.Offset.Mirror()));
			}
		}
		
		public static Act[] Parse(string str)
		{
			Act act = new Act(str);
			if (!act.Mirror)
				return new[] { act };
			else
			{
				return new[] { act, act.CreateMirrorClone() };
			}
		}
		
		// parse
		private Act(string str)
		{
			// defaults
			Mirror = false;
			Effort = 0;
			Chance = 1;
			
			str = str.Replace("\r", "");
			string[] lines = str.Split('\n');
			
			Name = lines[0];
			string[] data = lines[2].Split(',');
			foreach (string _s in data)
			{
				string s = _s.ToLowerInvariant().Trim();
				if (s == "mirror")
				{
					Mirror = true;
					Name += " Right";
				}
				else if (s.EndsWith("%"))
				{
					Chance = decimal.Parse(s.Substring(0, s.Length - 1)) / 100M;
				}
				else if (s.EndsWith(" stp"))
				{
					Effort = int.Parse(s.Substring(0, s.Length - 4));
				}
			}
			
			data = lines.Skip(3).ToArray();
			
			int cutPoint = data.Max(d => d.IndexOf('>'));
			
			Vector leftX = Vector.Zero, rightX = Vector.Zero, leftPos = Vector.Zero, rightPos = Vector.Zero;
			bool crouchLeft = false, crouchRight = false;
			
			// first pass (find things of interest)
			for (int i = 0; i < data.Length; i++)
			{
				string s = data[i];
				for (int j = 0; j < s.Length; j++)
				{
					Vector here = new Vector(j, i);
					char c = s[j];
					if (c == 'x')
					{
						if (j > cutPoint)
							rightX = here;
						else
							leftX = here;
					}
					else if (c == '%')
					{
						if (j > cutPoint)
						{
							crouchRight = true;
							rightPos = here;
						}
						else
						{
							crouchLeft = true;
							leftPos = here;
						}
					}
					else if (c == '|')
					{
						if (j > cutPoint)
						{
							crouchRight = false;
							rightPos = here;
						}
						else
						{
							crouchLeft = false;
							leftPos = here;
						}
					}
				}
			}
			
			StartCrouched = crouchLeft;
			EndCrouched = crouchRight;
			
			Motion = rightPos - leftPos - (rightX - leftX);
			
			Dictionary<char, string> conditionMap = new Dictionary<char, string>();
			conditionMap.Add('.', " =");
			conditionMap.Add('#', "#!");
			conditionMap.Add('!', "!");
			conditionMap.Add('=', "=");
			
			Dictionary<char, char> effectMap = new Dictionary<char, char>();
			effectMap.Add('_', ' ');
			
			Conditions = new List<CellCondition>();
			Effects = new List<CellEffect>();
			
			// second pass (find everything else)
			for (int i = 0; i < data.Length; i++)
			{
				string s = data[i];
				for (int j = 0; j < s.Length; j++)
				{
					Vector here = new Vector(j, i);
					char c = s[j];
					
					if (j < cutPoint)
					{
						if (conditionMap.ContainsKey(c))
						{
							Conditions.Add(new CellCondition(conditionMap[c], here - leftPos));
						}
					}
					else
					{
						if (effectMap.ContainsKey(c))
						{
							Effects.Add(new CellEffect(effectMap[c], here - leftPos - (rightX - leftX)));
						}
					}
				}
			}
		}
	}
	
	public class GameState
	{
		public int Width {get; private set;}
		public int Height {get; private set;}
		private char[,] Map;
		
		public Vector EscapeePosition {get; private set;}
		public bool EscapeeCrouching {get; private set;}
		
		public int MapHash {get; private set;}
		
		// clone
		private GameState(GameState gin)
		{
			Width = gin.Width;
			Height = gin.Height;
			Map = gin.Map;
			EscapeePosition = gin.EscapeePosition;
			EscapeeCrouching = gin.EscapeeCrouching;
			MapHash = gin.MapHash;
		}
		
		// parse
		public GameState(string mapStr)
		{
			mapStr = mapStr.Replace("\r", "");
			
			EscapeeCrouching = false;
			
			string[] lines = mapStr.Split('\n');
			Map = new char[Width = lines[0].Length, Height = lines.Length];
			
			for (int i = 0; i < lines.Length; i++)
			{
				string s = lines[i];
				for (int j = 0; j < s.Length; j++)
				{
					char c = s[j];
					
					if (c == 'o' || c == '|')
					{
						EscapeePosition = new Vector(j, i);
						c = ' ';
					}
					
					Map[j, i] = c;
				}
			}
			
			ComputeMapHash();
		}
		
		#region Equals and GetHashCode implementation
		public override bool Equals(object obj)
		{
			GameState other = obj as GameState;
			if (other == null)
				return false;
			return this.Width == other.Width && this.Height == other.Height && this.EscapeePosition == other.EscapeePosition && this.EscapeeCrouching == other.EscapeeCrouching && this.MapHash == other.MapHash && MapEquals(other);
		}
		
		public override int GetHashCode()
		{
			int hashCode = 0;
			unchecked {
				hashCode += 1000000009 * Width.GetHashCode();
				hashCode += 1000000021 * Height.GetHashCode();
				hashCode += 1000000033 * EscapeePosition.GetHashCode();
				hashCode += 1000000087 * EscapeeCrouching.GetHashCode();
				hashCode += 1000000093 * MapHash.GetHashCode();
			}
			return hashCode;
		}
		
		public static bool operator ==(GameState lhs, GameState rhs)
		{
			if (ReferenceEquals(lhs, rhs))
				return true;
			if (ReferenceEquals(lhs, null) || ReferenceEquals(rhs, null))
				return false;
			return lhs.Equals(rhs);
		}
		
		public static bool operator !=(GameState lhs, GameState rhs)
		{
			return !(lhs == rhs);
		}
		#endregion

		private bool MapEquals(GameState other)
		{
			if (MapHash != other.MapHash)
				return false;
			else
			{
				for (int i = 0; i < Height; i++)
				{
					for (int j = 0; j < Width; j++)
					{
						if (Map[j, i] != other.Map[j, i])
							return false;
					}	
				}
			}
			
			return true;
		}
		
		private void ComputeMapHash()
		{
			// wow, so efficient, wow
			MapHash = MakeMapString().GetHashCode();
		}
		
		private char[,] CloneMap()
		{
			var newMap = new char[Width, Height];
			
			for (int i = 0; i < Height; i++)
			{
				for (int j = 0; j < Width; j++)
				{
					newMap[j, i] = Map[j, i];
				}	
			}
			return newMap;
		}
		
		public void Assign(Vector v, char c)
		{
			if (!Inside(v))
				throw new Exception("What is this??");
			else
				Map[v.X, v.Y] = c;
		}
		
		public char Lookup(Vector v)
		{
			if (!Inside(v))
				return ' '; // the world is empty outside
			else
				return Map[v.X, v.Y];
		}
		
		public bool Inside(Vector v)
		{
			return !(v.X >= Width || v.X < 0 || v.Y >= Height || v.Y < 0);
		}
		
		public bool IsWon
		{
			get
			{
				return !Inside(EscapeePosition);
			}
		}
		
		private string MakeMapString()
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder((Width + 1) * Height);
			for (int i = 0; i < Height; i++)
			{
				for (int j = 0; j < Width; j++)
				{
					sb.Append(Map[j, i]);
				}
			}
			return sb.ToString();
		}
		
		public string MakePictureString()
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder((Width + 1) * Height);
			for (int i = 0; i < Height; i++)
			{
				for (int j = 0; j < Width; j++)
				{
					char c = Map[j, i];
					
					if (!EscapeeCrouching && EscapeePosition.X == j && EscapeePosition.Y == i + 1)
						c = 'o';
					else if (EscapeePosition.X == j && EscapeePosition.Y == i)
					{
						c = EscapeeCrouching ? '%' : '|';
					}
						
					sb.Append(c);
				}
				sb.AppendLine();
			}
			return sb.ToString();
		}
		
		public GameState Move(Act act)
		{
			GameState newGameState = new GameState(this);
			
			// effects
			if (act.Effects.Count > 0)
			{
				newGameState.Map = CloneMap();
				
				foreach (var ce in act.Effects)
				{
					newGameState.Assign(EscapeePosition + ce.Offset, ce.NewChar);
				}
				
				newGameState.ComputeMapHash();
			}
			
			// escapee
			newGameState.EscapeePosition += act.Motion;
			newGameState.EscapeeCrouching = act.EndCrouched;
			
			return newGameState;
		}
		
		public bool Allowed(Act act)
		{
			// match crouching
			if (act.StartCrouched != EscapeeCrouching)
				return false;
			
			// check conditions
			foreach (var cc in act.Conditions)
			{
				if (!cc.Test(Lookup(EscapeePosition + cc.Offset)))
					return false;
			}
			
			return true;
		}
	}
	
	public class Program
	{
		private List<Act> ActTable = new List<Act>();
		
		public static void Main(string[] args)
		{
            if (args.Length < 1)
            {
                Console.WriteLine("Usage:");
                Console.WriteLine("OfficeEscapeSolver.exe gameFile chance (userPlan)");
                Console.WriteLine("    gameFile is a text file containing the map");
                Console.WriteLine("    chance is a number between 0 and 100 for probability of success constraint");
                Console.WriteLine("    userPlan is a text file containing a plan to verify");
                Console.WriteLine();
                Console.WriteLine("or");

                Console.WriteLine("OfficeEscapeSolver.exe gameFileWithChance (userPlan)");
                Console.WriteLine("    gameFile is a text file containing the map and probability of success constraint (at the top, as per the spec)");
                Console.WriteLine("    userPlan is a text file containing a plan to verify");
                Console.WriteLine();
                Console.WriteLine("or");

                Console.WriteLine("OfficeEscapeSolver.exe * chance (userPlan)");
                Console.WriteLine("    map piped into standard in");
                Console.WriteLine("    chance is a number between 0 and 100 for probability of success constraint");
                Console.WriteLine("    userPlan is a text file containing a plan to verify");
                Console.WriteLine();
                Console.WriteLine("or");

                Console.WriteLine("OfficeEscapeSolver.exe * (userPlan)");
                Console.WriteLine("    map and probability of success constraint (at the top, as per the spec) are piped into standard in");
                Console.WriteLine("    userPlan is a text file containing a plan to verify");
                Console.WriteLine();

                Console.WriteLine("Expects a valid 'file.txt' in the same directory.");
                Console.WriteLine(".");
                return;
            }

			Program p = new Program("file.txt");
            
            string gameString;
            decimal chanceConstraint;

            if (args[0] == "*") // from STDIN
            {
                // this is just awful, how did I let it come to this
                string l1 = Console.ReadLine();
                if (decimal.TryParse(l1, out chanceConstraint))
                {
                    gameString = Console.In.ReadToEnd();
                    args = args.Length > 1 ? new string[] { null, null, args[1] } : args; // quality code
                }
                else
                {
                    gameString = l1 + "\n" + Console.In.ReadToEnd();
                    chanceConstraint = decimal.Parse(args[1]);
                }
            }
            else
            {
                string fl = System.IO.File.ReadLines(args[0]).First();
                if (decimal.TryParse(fl, out chanceConstraint))
                {
                    gameString = string.Join("\n", System.IO.File.ReadLines(args[0]).Skip(1));
                    args = args.Length > 1 ? new string[] { null, null, args[1] } : args; // quality code
                }
                else
                {
                    gameString = System.IO.File.ReadAllText(args[0]);
                    chanceConstraint = decimal.Parse(args[1]);
                }
            }

            // doesn't like PS cat
            gameString = gameString.TrimEnd('\r', '\n');

            GameState gs = new GameState(gameString);
			
			SearchState sol = p.Solve(chanceConstraint / 100M, gs);

            if (sol == null)
            {
                Console.WriteLine("There is no hope!");

                if (args.Length > 2)
                {
                    Console.WriteLine();
                    // user entry to verify in args[2]
                    Console.WriteLine();
                    Console.WriteLine("Verifying user plan...");

                    string userPlan = System.IO.File.ReadAllText(args[2]).TrimEnd('\r', '\n');
                    bool fine = userPlan == "There is no hope!";
                    if (userPlan != "There is no hope!")
                        Console.WriteLine("Invalid user plan, there is no hope!");
                    else
                        Console.WriteLine("Indeed, there is no hope!");

                    if (fine)
                        Console.WriteLine("PASS");
                    else
                        Console.WriteLine("FAIL");
                }
            }
            else
            {
                Console.WriteLine(sol.RenderPlan(false)); // for test script
                Console.WriteLine();
                Console.WriteLine(sol.RenderPlan(true));
                Console.WriteLine();
                Console.WriteLine(sol.RenderPlan(false));

                // verify
                Console.WriteLine();
                Console.WriteLine("Verifying...");

                int listedEffort;
                decimal chance;
                int effort;
                p.VerifyPlan(gs, p.TranslatePlan(sol.RenderPlan(false), out listedEffort), out chance, out effort, true, false);

                if (args.Length > 2)
                {
                    // user entry to verify in args[2]
                    Console.WriteLine();
                    Console.WriteLine("Verifying user plan...");
                    
                    int userListedEffort;
                    decimal userChance;
                    int userEffort;

                    string userPlan = System.IO.File.ReadAllText(args[2]).TrimEnd('\r', '\n');

                    if (userPlan == "There is no hope!")
                    {
                        Console.WriteLine("But there is hope!");
                        Console.WriteLine("FAIL");
                        return;
                    }
                    
                    bool fine = p.VerifyPlan(gs, p.TranslatePlan(userPlan, out userListedEffort), out userChance, out userEffort, true, true);

                    Console.WriteLine();
                    if (fine)
                        Console.WriteLine("User Plan Action Sequence is Valid");
                    else
                        Console.WriteLine("User Plan Action Sequence is Invalid");

                    if (userEffort != userListedEffort)
                    {
                        fine = false;
                        Console.WriteLine("Required Effort was incorrect (given" + userListedEffort + " should be " + userEffort + ")");
                    }

                    if (userEffort > effort)
                    {
                        fine = false;
                        Console.WriteLine("Required Effort was non-optimal (was " + userEffort + ", solution found with effort " + effort + ")");
                    }

                    if (fine)
                        Console.WriteLine("User plan looks good.");

                    if (fine)
                        Console.WriteLine("PASS");
                    else
                        Console.WriteLine("FAIL");
                }
            }
		}
		
		public Program(string actfile)
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder();
			
			using (var reader = new System.IO.StreamReader(actfile))
			{
				while (true)
				{
					string line = reader.ReadLine();
					
					if (line == null || (line.Length > 0 && line.Substring(0, 1) != line.Substring(0, 1).ToLowerInvariant()))
                    {
                        string s = sb.ToString();
						if (s.Length > 1)
							ActTable.AddRange(Act.Parse(s));
						sb.Clear();

                        if (line == null)
                            break;
                    }

                    sb.AppendLine(line);
				}
			}
		}

        /// <summary>
        /// Verifies a plan
        /// </summary>
        /// <returns>True if the set of actions are valid</returns>
        public bool VerifyPlan(GameState game, IEnumerable<Act> plan, out decimal chance, out int effort, bool printInfo = true, bool printLotsOfInfo = true)
        {
            int actcount = 0;

            // init
            chance = 1;
            effort = 0;

            if (printLotsOfInfo)
            {
                Console.WriteLine("Initial State");
                Console.WriteLine(game.MakePictureString());
                Console.WriteLine();
            }

            foreach (Act a in plan)
            {
                if (printInfo)
                {
                    Console.WriteLine("# Action " + actcount);

                    if (printLotsOfInfo)
                    {
                        Console.WriteLine(a.Name + ": " + a.Effort + "stp " + (a.Chance*100M) + "%");
                    }
                }

                if (game.IsWon)
                {
                    // early win
                    if (printInfo)
                    {
                        Console.WriteLine("Already won after " + actcount + " actions: illegal plan.");
                        return false;
                    }
                }

                if (!game.Allowed(a))
                {
                    if (printInfo)
                    {
                        Console.WriteLine("Action \"" + a.Name + "\" invalid from state:");
                        Console.WriteLine(game.MakePictureString());
                    }

                    chance = 0;
                    effort = -1;
                    return false;
                }

                // apply
                game = game.Move(a);

                effort += a.Effort;
                chance *= a.Chance;

                actcount++;

                if (printLotsOfInfo)
                {
                    Console.WriteLine("Chance of Success: " + chance + " (" + (chance * 100M) + "%)");
                    Console.WriteLine("Required Effort: " + effort);
                    Console.WriteLine("Actions Performed: " + actcount);
                    Console.WriteLine(game.MakePictureString());
                }
            }

            if (printInfo)
            {
                Console.WriteLine();
                Console.WriteLine("Action Sequence Completed Successfully.");
                Console.WriteLine("Chance of Success: " + chance + " (" + (chance * 100M) + "%)");
                Console.WriteLine("Required Effort: " + effort);
                Console.WriteLine("Actions Performed: " + actcount);
            }

            return true;
        }

        public List<Act> TranslatePlan(string plan, out int effort)
        {
            List<Act> actionSequence = new List<Act>();

            effort = -1;

            string[] lines = plan.Replace("\r","").Split('\n');
            
            foreach (string l in lines)
            {
                if (!string.IsNullOrEmpty(l)) // skip Required Effort
                {
                    if (l.StartsWith("Required Effort:"))
                        effort = int.Parse(l.Substring(l.IndexOf(':') + 2));
                    else if (!l.Contains(":"))
                        actionSequence.Add(TranslateAct(l));
                }
            }

            return actionSequence;
        }

        public Act TranslateAct(string str)
        {
            var act = ActTable.FirstOrDefault(a => a.Name == str);
            if (act == null)
            {
                throw new ArgumentException("Unrecognised action \"" + str + "\"", nameof(str));
            }
            return act;
        }
		
		public class SearchState
		{
			public SearchState Previous {get; private set;}
			public Act Act {get; private set;}
			public GameState GameState {get; private set;}
			public int Effort {get; private set;}
			public Decimal Chance {get; private set;}
			
			public bool ObjectivelyBetterThanOrAsGoodAs(SearchState other)
			{
				return GameState == other.GameState && Chance >= other.Chance && Effort <= other.Effort;  
			}
			
			public static SearchState CreateInitial(GameState gameState)
			{
				return new SearchState(null, null, gameState, 0, 1M);
			}
			
			private SearchState(SearchState previous, Act act, GameState gameState, int effort, decimal chance)
			{
				Previous = previous;
				Act = act;
				GameState = gameState;
				Effort = effort;
				Chance = chance;
			}
			
			public SearchState Move(Act act)
			{
				return new SearchState(this, act, GameState.Move(act), Effort + act.Effort, Chance * act.Chance);
			}
			
			public string RenderPlan(bool includeState = false)
			{
				Stack<SearchState> sss = new Stack<Program.SearchState>();
				
				SearchState cur = this;
				
				while (cur != null)
				{
					sss.Push(cur);
					cur = cur.Previous;
				}
				
				System.Text.StringBuilder sb = new System.Text.StringBuilder();
				sb.AppendLine("Required Effort: " + Effort);
				sb.AppendLine("Probability of Success: " + Chance);
				while (sss.Count > 0)
				{
					SearchState s = sss.Pop();
					
					if (s.Act != null) // start
						sb.AppendLine(s.Act.Name);
					
					if (includeState)
						sb.AppendLine(s.GameState.MakePictureString());
				}
				
				return sb.ToString();
			}
		}
		
		public SearchState Solve(decimal minChance, GameState gs)
		{
			SearchState start = SearchState.CreateInitial(gs);
			
			// let's not make this too efficient
			List<SearchState> due = new List<Program.SearchState>();
			
			//List<SearchState>[,] seen = new List<SearchState>[gs.Width, gs.Height];
			Dictionary<GameState, List<SearchState>> seen = new Dictionary<GameState, List<SearchState>>();
			
			Action<SearchState> consider = (nss) =>
			{
				if (nss.Chance < minChance)
					return;
				
				List<SearchState> priors;
				
				if (!seen.TryGetValue(nss.GameState, out priors))
				{
					priors = new List<SearchState>();
					seen.Add(nss.GameState, priors);
				}
				else
				{
					if (priors.Any(pss => pss.ObjectivelyBetterThanOrAsGoodAs(nss)))
						return; // no reason for us to exist
					
					// remove any old inferiors
					priors.RemoveAll(pss => nss.ObjectivelyBetterThanOrAsGoodAs(pss));
				}
				
				// we are good to go
				priors.Add(nss);
				due.Add(nss);
			};
			
			Action<SearchState, Act> tryMove = (prev, act) =>
			{
				if (prev.GameState.Allowed(act))
				{
					SearchState nss = prev.Move(act);
					consider(nss);
				}
			};
			
			consider(start);
			int iters = 0;
			while (due.Count > 0)
			{
				due.Sort(new Comparison<SearchState>((a, b) => -a.Effort.CompareTo(b.Effort)));
				SearchState next = due[due.Count - 1];
				due.RemoveAt(due.Count - 1);
				
				//Console.WriteLine(iters + "\t" + next.Effort + "\t" + next.Chance);
				//Console.WriteLine(next.GameState.MakePictureString());
				
				iters++;
				
				if (next.GameState.IsWon)
				{
					return next;
				}
				
				foreach (Act a in ActTable)
					tryMove(next, a);
			}
			
			return null;
		}
	}
}

test.ps1

# run me like this:
# . .\test.ps1 .\OfficeEscapeSolver.exe
# running that should pass all the test cases, and fail none
# if it does not, then either my code is broken, or one or more test cases are broken
# just substitude your own program for .\OfficeEscapeSolver.exe to test your own program

# $solver is the program ot run
# $mode is how we pass it the testcase
#   "stdin" passes it in through standard input
#   "file" passes the filename as a parameter
# $tmp is a file to use as a temporary file for the submission plan
Param($solver, $mode = "stdin", $tmp = "____tempUserPlan.txt")

$p = 0
$f = 0

ls testcase*.txt | % {$_.Name} | % {
  $tc = $_
  if ($mode -eq "stdin") { $res = iex "cat $tc | $solver" }
  elseif ($mode -eq "file") { $res = iex "$solver $tc" }
  else { "Unrecognised Mode $mode" }

  $s = -1
  $res | % {
    $l = $_
    if ($l.StartsWith("Required Effort: ")) { $s = -$s }
    if ($l -eq $null -or $l -eq "") { $s =0 }
    if ($s -eq 1) { $l }
    if ($l -eq "There is no hope!") { $l }
  } > $tmp

  $pass = 0
  .\OfficeEscapeSolver.exe $tc $tmp | % {
    if ($_ -eq "PASS") { $pass = 1 }
  }

  if ($pass) { "PASS $tc"; $p++ }
  else { "FAIL $tc"; $f++ }
}

"End."
"Passed $p"
"Failed $f"

testcase0.txt

50
#######################
#                =    #
!                =    !
#          !     =    #
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

testcase1.txt

100
o
|

testcase10.txt

1
##   #
#o # #
#|#  #
######

testcase11.txt

30
        ###########
        #==       #
#########==########
#        ==       #
!        ==       !
# o      ==       #
# |               #
######     #####!##
# =  #     #    = #
! =  #######    = !
# =      !      = #
# =      !      = #
##= ############  #
# =            #  #
! =            ####
# =               !
# =               !
##= ###############
# =      #        #
! =      #        #
# =      !        !
# =      !        !
###################

testcase2.txt

5
# =      #
# =      !
# = !  ! !
# =#######
# =  #    
# =   o  #
# = ! |  #
##########

testcase3.txt

60
#########
# ! #   #
! ! ! o #
! # ! | #
#########

testcase4.txt

50
#######################
#          #     =    #
!          #     =    !
#          #     =    #
######  #####!## =### #
#=   ##       #  =    #
#=#############  =    #
#=               =    #
#= o             =    #
#!!|             =    #
#######################

testcase5.txt

66
######
#  ###
#o ! !
#| ! !
### ##
######

testcase6.txt

50
  #     #
  !   o #
  !   | #
#########

testcase7.txt

30
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

testcase8.txt

32
###################
# ## # # #   #  = #
! ## #   #   #  = #
#      #   #    = #
##  ############= #
# ## #         #= #
# =  #         #= #
! =  #         #= #
# =  #         #= #
#o=  !          ==#
#|=  !           =#
#!= # ==########==#
#   #    !   !!  =#
#   #    !!  !  = #
#   # !!!!#########
#   # #           #
#   # #           #
###################

testcase9.txt

80
#########
# ! #   #
! ! ! o #
! # ! | #
#########

You should be able to download this package, and run the following from PowerShell:

csc .\OfficeEscapeSolver.cs
. .\test.ps1 ".\OfficeEscapeSolver.exe *" stdin

If the result doesn't say "Passed 12", then something has gone wrong.

Running OfficeEscapeSolver.exe on it's own presents the Usage. test.ps1 can either pass the testcases as standard input ('stdin' arg as shown) or as a filename parameter ('file').