Office Escape: Plan your way out!

Question

It's the final sprint... and half your team is off ill. You're working late, just making your last commit for the day, looking forward to... why have the lights turned off? I don't remember the security guy coming around... oh no! I left my keys at home!

As the horror of the situation sinks in, you decide that you are going to escape.

Task Summary

To effect your escape, you need a plan! However, you know that any plan has a chance of failing, and different plans require different amounts of effort.

Being hungry, tired, and an engineer, you decide to write a short program to determine the best way to escape the complex, balancing the concerns of probability of success and the effort it will require.

You make a map of the building:

#######################
#                =    #
!                =    !    <-- window
#          !     =    #        (freedom!)
#################=    #
#    #           =    #
#    #           =    #
#    #           =    #
# o  !   # #  !  =    #
##|  !  ## #  !  =    #
#######################

  ^  ^           ^
  me my door     ludicrously high shelves
     (locked)    (climbable)

To escape the office, you will have to move yourself off the map. Here you see there are 2 windows (!), either one would lead you to freedom, but only one of them accessible. We define 'off the map' as having your feet outside the bounds of the map

Cell types

  - empty, you can be here (i.e. the escapee can consume this cell)
# - solid (your desk, your in-tray), you can't be here, but you can stand on it
! - destructible, (co-worker's desk, door, window), you can't be here until you smash it first (turning it into an empty cell)
= - climbable, (fire ladder, filing cabinet, etc.), you can be here

The cells originally consumed by the escapee taken to be empty.

Action Specifications

You have a number of possible actions at your disposable. These are defined by simple state transitions with some integer success probability. For example, for walking, you move the escapee one cell, which we represent with this transition:

Step

1 stp, 100%, mirror

 o.            o
 |.   -->      |
 #            #

The dots show cells that must be empty (or climbable, but not solid or destructible) either because we move into it or through it. The 100% means you have an 100% chance of not hurting yourself and ending your daring escape. All probabilities will be integer percentages between 1% and 100% inclusive. The first diagram shows the initial state (standing on something solid, standing next to some empty space). The second diagram shows the terminal state (moved into the empty space). There is no requirements for any unspecified cells (spaces, ) on the left (initial state) to be anything in particular. Unspecified cells (space, ) on the right (terminal state) should be the same as they were prior (e.g whatever was behind the escapee, or whatever I happen to be walking onto (be it empty space or otherwise). Note that all right-hand (terminal state) diagrams will only change cells from destructible to empty, no other changes can occur. "1 stp" means it costs 1 stp: we define the "stp" as the amount of energy required to take a step.

"mirror" means this action has two forms. The "right" action is shown, the "left" action is an exact mirror, for example:

.o
.|
 # 

is the mirror (Left) form of

o.
|.
# 

The right action is called " Right" (e.g. "Step Right") The left action is called " Left" (e.g. "Step Left")

In these diagrams, the escapee is show by

o
|

when standing (2 units tall) and

%

when crouching (1 unit tall). Cells that must be solid or destructible are indicated by a hash, #. Cells that must not be solid or destructible are indicated by a dot .. Cells that must be destructible are indicated by a bang !. A newly created empty space is shown by an underscore _. x is a reference point that doesn't move (it doesn't exist, no constraint on what that cell must be (like a space )).

Note: we ignore the issue of rapid deceleration when you hit the floor, and yes, in this game you can do totally epic jumps onto ladders)

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_

Plans

A plan is a sequence of the actions defined above. For example:

Step Left
High Jump Left
Crouch
Shuffle Left
Shuffle Left
Stand
Long Jump Left
Put your back into it! Left
Step Left

Note the inclusion of the drops. The rules should be set up to stop you doing anything but dropping, but you still have to plan for it!

Any plan has a required effort, which is the sum of the efforts for each step. There is also a success probability, which is the product of the success probabilities of each action. Simple example:

Step Right:          1stp,  100%
Long Jump Right:     7stp,  75%
Step Right:          1stp,  100%
Stamp:               8stp,  90%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Drop:                0stp,  100%
Step Left:           1stp,  100%
Step Left:           1stp,  100%
High Jump Left:      12stp, 90%

Effort = 1+7+1+8+1+1+12 = 31
Success Probability = 75%*90*90% = 60.75%

A 'worked example' for the map at the top of page can be found as a gist.

Input

The input comes in two parts, an integer, and an array or string of characters.

The integer is your minimum acceptable (percent) probability of success. It is to be interpreted as a percentage, so 80 means your plan must succeed with probability no less than 80%.

A valid map is a rectangle that includes the standing escapee (minimum size of 1x2) and no unspecified symbols. All rows will be the same length. You may accept input as a 1-dimensional delimitated string (delimiter must be a single consistent character, or one of CRLF and LFCR pair), as a similar 1-dimensional array, or a 2-dimensional array. If your chosen input format does not indicate the width or height of the map in some way, you may accept additional arguments for these (you must clearly state this in your answer). You may mix command line arguments and standard input if it suits you (e.g. map from stdin, minimum success probability from argv). The following are example valid and invalid maps.

Valid:

o
|

Valid:

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

Invalid (no escapee):

  #     #
  !     #
  !     #
#########

Invalid (escapee always starts standing):

  #     #
  !     #
  !   % #
#########

Invalid (invalid symbol):

  #     #
  !  ~  #
  !     #
#########

Invalid (not a rectangle/different length rows):

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

You may assume your input is valid (I don't care what your program does if it is handed invalid input).

Output

Output is text (ASCII). May be returned as a string, or printed to standard output. The plan must be delimitated by a LF, CRLF, or LFCR. Similarly, there must be another LF, CRLF, or LFCR after the Required Effort. A trailing line break is optional.

You must output an optimal plan along with the effort it requires, or "There is no hope!" if no such plan exists. You do not need to output the probability of success. This text may or may not have trailing line break.

An optimal plan is defined as a plan (see above) requiring the minimum effort with at least the given probability of success. Note that you probability calculations must be exact, you may not assume that floating point is good enough (This is why I don't expect you to output them). I will try to design test cases to fairly test this (if you pass them and don't make any daft assumptions then you may consider your submission valid).

Format:

Required Effort: <effort>
<plan>

For example, for the input

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

An appropriate output would be:

Required Effort: 23
Step Left
Step Left
Step Left
Kick Left
Punch Left
Step Left
Step Left
Step Left
Step Left

The probability of success here is 76.5%.

For the same map, but a minimum probability of success of 80%, you would have to "Put your back into it", which would require more effort but fulfil the success probability criteria. If the minimum probability of success were greater than 80%, you'd need to think a bit harder (either punch or kick through part of the door and shuffle out). If the minimum probability of success were 100%, you'd have to print out "There is no hope!"

Examples

It is possible that there are more than one valid plans for an input, you're output doesn't need to be these exactly, but it must have the correct required effort, and be a valid plan. You can use the verifier to check your solutions (see below)

Input:

100
o
|

Output:

Required Effort: 0
Drop

Input:

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

Output:

Required Effort: 57
Step Left
Kick Left
Step Left
Step Left
Step Left
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
High Jump Right
Long Jump Right
Step Right
Drop
Kick Right
Crouch
Shuffle Right
Shuffle Right

Input:

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

Output:

Required Effort: 58
Step Left
Kick Left
Crouch
Shuffle Left
Shuffle Left
Stand
Punch Left
Clamber Up Left
Shuffle Left
Drop (Stand)
Kick Left
Crouch
Shuffle Left
Shuffle Left

For the same map, but 80%, the output should be:

There is no hope!

For the same map, but 50%, the Required effort becomes 56 with a different plan)

Input:

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

Output:

Required Effort: 121
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Step Right
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb Up
Climb off Right
Long Jump Left
Step Left
Step Left
Stamp
Drop
Drop
Crouch
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Shuffle Left
Stand
Clamber Up Left
Stand
Clamber Up Left
Stand
Step Left
Step Left
Step Left
Step Left
Punch Left
Clamber Up Left
Shuffle Left

Input:

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

Output:

Required Effort: 37
Step Right
Put your back into it! Right
Kick Right
Crouch
Shuffle Right
Shuffle Right

Input:

This one is designed to check a number of false assumptions one may fall victim to, and consequently may look a bit odd

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

Output with chance of success constraint 30:

Required Effort: 199
Long Jump Right
Put your back into it! Right
<snip>

Output with chance of success constraint 32:

Required Effort: 200
Long Jump Right
Punch Right
<snip>

Using the map at the top as an input, with probability of success constraint 1%, you should get a Required Effort of 116 (chance of success ~32%, this took about 20seconds to run in my test program).

Victory Criteria

This is code-golf, may the shortest code win.

To be eligible, your function or program must work and be able to solve each of the above testcases in under 30minutes on a reasonable machine. My solver does them each in under 30seconds. If the test script (below) runs in under 30minutes, you're certainly good to go.

Example Solver, Verifier, Test Script, and TestCases (with solutions)

C# code for a solver, and solution verifier, is available here as a gist. The gist also contains file.txt, which is a machine readable (enough) form of the actions described above, and is required for the program to run. Any discrepancy between that file and spec is not intentional.

The gist also contains a number of test cases (including all the examples above), and a PowerShell script to automatically run a submission against them. If the script tells you that a particular test has failed, you can run OfficeEscapeSolver.exe testcase<n>.txt outputFromYourProgram.txt to see more details. Example solutions for these test cases are in another Gist.

All the code is a complete mess (though ungolfed), but you shouldn't need to stray far from the static void Main(...) to change the amount of output (feel free to use this information, I've provided it for your benefit!).

Passing a test-case does not necessarily mean that your output is well formed, as the script and verifier are very generous. Your output must match the specification above for your submission to be valid.

If you think you've found a bug with the solver or testscript, an error in file.txt, or a dodgy testcase, then please comment on this post or otherwise ping me on SE Chat; I probably won't notice any other attempt to communicate.

I won't provide the test script in Bash or Batch, because I don't know them, but I'm happy to include a translation and will write a C# version if people want one.

Post Amble

Got questions? Don't delay, ask them today!

This task is meant to require effort, to give serious golfers something to sink their teeth into.

My thanks to ais523 for his feedback on Input/Output.

I can provide more testcases in the gist file if people want more (don't want this post to become any longer), or want to provide some of their own.

Answer 1

---

Perl 5, 1425 1464 1481 1469 1485 1438 bytes

That was a fun challenge! And, shockingly, it looks like I have the shortest code so far at a little under 1.5kB! :)

Pretty sure I finally got this working. The delimiter used is :, and there is extra padding of two rows on top and one column on either side. So for your input of:

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

my program would take: (NB: there must be a colon at the end, but not at the beginning!)

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

I use regexes to translate from one map to another and solve by brute force. However, I don't add maps to the list if that map has already been reached with less effort and greater or equal probability. Maps are removed from the list once all possible movements from that point have been exhausted. The program ends successfully when it matches a regex that shows I have reached the side or the bottom and ends with "There is no hope!" when the list of maps is exhausted.

Unfortunately, there was a great deal of efficiency traded away to take off a few bytes, so the golfed version is rather slow ;) Perl seems to find the evals in particular to be quite painful.

Without further adieu,

chop($P=<>,$_=<>);s/:/ : /g;$w++until/:.{$w}:/;$z=$"x$w;$_="(.{".$w--."})"for($c,$h,$i,$j);$_="$z:$z: $_$z";$n="[ =]";$d="([!#])";@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp';@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15);sub M{$_=join":",map{join'',reverse split//}split/:/};push@M,[$_,0,100,$P];$B{$_}=100;@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8);@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10);$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/';do{sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}};die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M));$e=-1;while(++$e<@M){@t=@{$M[$e]};$m=$_=$t[0];die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/);for$x(0..15){$_=$m;$t=$t[2]*$P[$x];if($G==$E[$x]+$t[1]and$t>=$t[3]*100){&$x;eval"$z Right/";A;$_=$m;M;&$x;M;eval"$z Left/";A;}}}}

For the sake of sanity, here's the same thing with newlines and a few comments:

chop($P=<>,$_=<>); #Take input
s/:/ : /g; #Pad columns on either side so escapee can leave that way
$w++until/:.{$w}:/; #Find width
$z=$"x$w;#Setup a blank line for use in padding later
$_="(.{".$w--."})"for($c,$h,$i,$j); #Set up some generic capturing regexes for reuse
$_="$z:$z: $_$z"; #Pad the top and bottom so the escapee can leave those ways
$n="[ =]"; #Regex for nonsolid block
$d="([!#])"; #Regex for solid block
@s=split/,/,'Drop,Drop (Stand),Stepx,Climb offx,Shufflex,Clamber Upx,Put your back into it!x,Punchx,Kickx,Short Jumpx,Long Jumpx,High Jumpx,Crouch,Stand,Climb Up,Stamp'; #Movement names
@c=split/,/,"o$c\\|$c$n/ \$1o\$2|,%$c$n/o\$1|,o$n$h\\|$n$h${d}/ o\$1 |\$2\$3,=${c}o$n$h\\|$n$h=/=\$1=o\$2=|\$3=,%$n$h$d/ %\$1\$2,o$n$h\\|${d}$h${d}/ %".'$1 $2$3$4,'."o!$n$i\\|!$n$i${d}/  o\$1  |\$2\$3,o!$h\\|$c$d/o \$1|\$2\$3,\\|!$h$d/| \$1\$2,o$n$n$i\\|$n$n$i${d}/  o\$1  |\$2\$3,o$n$n$n$j\\|$n$n$n$j${d}/   o\$1   |\$2\$3,$n$n${h}o$n$h\\|$c$d/ o".'$1 |$2 $3$4,'."o$c\\|$c${d}/ \$1%\$2\$3,$n$c%$c${d}/o\$1|\$2\$3,=${c}o$c\\|/o\$1|\$2=,\\|$c!/|\$1 ";#Movement regexes
eval"*$_=sub{\$Q=\"$s[$_]\";s/$c[$_]/}"for(0..15); #Setup methods to apply regexes. Name of these methods are 0,1,2,3, etc, so we can easily call them in a loop
sub M{$_=join":",map{join'',reverse split//}split/:/}; #Method to mirror the map. All the regexes are right-moving, so the mirror effects are achieved by M;&$x;M
push@M,[$_,0,100,$P]; #Array for initial map position. Encodes: [Map,Effort value,Probability value 1,Probability value 2,Movements(initially undef)]. Two integers are used for the probability to avoid floating point (although after enough steps they overflow and are automatically converted to f.p.)
$B{$_}=100; #Hash map to hold best probability of reaching a map. A new map is never added if it requires at least as much effort and doesn't give a better probability.
@E=(0,0,1,1,3,10,20,8,8,4,7,12,2,4,2,8); #Effort values
@P=map{100-$_}(0,0,0,0,0,5,20,10,15,5,25,10,0,0,0,10); #Probability values
$z='$N=[$_,$G+0,$t,$t[3]*100,"$t[4]$Q\n"];$N->[4]=~s/x/'; #Setup map values
do{ #Loop over all efforts. Do-while loop starts at undef, which is converted to zero automatically when used in a numeric context
    sub A{@N=@$N;if($N[2]/$N[3]>$B{$N[0]}){push@M,$N;$B{$N[0]}=$N[2]/$N[3]}}; #Method to add a map to list.
    die"There is no hope!\n"if(!(@M=grep$G-$_->[1]<21,@M)); #Pares away maps that no longer can produce new maps, and prints "There is no hope!" to stderr if there are no maps left.
    $e=-1;
    while(++$e<@M){ #Loop over all maps. Note that this loops over even maps that are created during the loop
        @t=@{$M[$e]}; #Dereference info about each map
        $m=$_=$t[0]; $Setup map variables
        die"Required Effort: $t[1]\n$t[4]"if(/([|%]:|:[|%])/||/[|%][^:]*$/||/^$c:[^:]*[%|]/); #Checks if escaped, and gives message if so.
        for$x(0..15){
            $_=$m; #Put map into $_
            $t=$t[2]*$P[$x]; #Probability calculation
            if($G==$E[$x]+$t[1]and$t>=$t[3]*100){ #If effort values are right and probability is over threshold
                &$x; #Run regex
                eval"$z Right/"; #Set up map info
                A; #Add map to list @M (only if probability works out right)
                $_=$m;
                M;&$x;M; #Same thing, but mirrored now (generates movement left)
                eval"$z Left/";
                A;
            }
        }
    }
}while(++$G)

I can already see a couple places to pare away a few more bytes, but I don't want to go through all the testing again yet. Later! :)

Edit: Added some padding below as well to fit your output more exactly when escaping through the floor. Removed some of the evals, so the code might run faster now, too!

Edit: Wasn't handling ladders and drops quite right. Still doesn't handle ladders quite right... Trying to fix that now.

Answer 2

C#, 1814 1481 1395 bytes

What a slog!! I'm really rather pleased with this now!

using C=System.Console;using System.Linq;class S{string M,N="";int x,y,E,c;decimal P=1;static void Main(){int W=0,H=0,x,i,j,k,X,Y,f,m,P=int.Parse(C.ReadLine());string l,M="",B,R="There is no hope!";for(;(l=C.ReadLine())!=null;H++,M+=l)W=l.Length;x=M.IndexOf("|");var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();for(var N=D.ToDictionary(s=>R,s=>D);D.Count>0;D.Sort((z,w)=>z.E-w.E)){S s=D[f=0];D.Remove(s);var n=N[l=s.x+s.M+s.y+s.c]=N.ContainsKey(l)?N[l]:new S[0].ToList();if(n.All(o=>o.P<s.P|o.E>s.E)){n.Add(s);X=s.x;Y=s.y;if((X|Y|-X/W-Y/H)<0){R="Required Effort: "+s.E+s.N;break;}for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(',');f<26;){l=A[k=f*3%48];B=A[++k]+(f>15?" Right":f>9?"":" Left");M=A[++k];m=f++/16*2-1;var Q=s.M.ToArray();var K=s.P*l[4]>=P&s.c==l[k=0]%2;for(j=Y-3;j++<=Y;)for(i=X;i!=X+m*M.Length/4;i+=m)if((K&="==  *!!##*!*=*|*| o*o ".Contains(""+((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ')+M[k]))&M[k++]==33)Q[x]=' ';if(K)D.Add(new S{M=new string(Q),N=s.N+"\n"+B,x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100});}}}C.Write(R);}}

Try It Online

Complete program, takes input to STDIN, output's to STDOUT. Essentially a re-write of my original solver, using a simple and inefficiently implemented BFS to find the optimal path. It's reasonably fast, can't be much slower than my other implementation (I've not really timed it though), certainly runs within the time limit. Much of the cost is the Action table, which is encoded as comma separate values which record the name, 'match/smash' map, and other properties of each available action.

It starts by reading in the minimum probability of success and the map. Then it locates the escapee, removes him from the map, and creates a 'search state' containing this information. Then, it performs the BFS, which repeatedly looks at the next due state with the least effort (ensuring it finds an optimal solution). Before expanding the node, it compares it's effort and probability of success to previous nodes with the same map and escapee location, and rejects itself if a better route has been found to this state already. If it survives this, it adds itself to the 'seen' table so it can reject state later on. This is all for performance, and without it the branching factor would be huge. Then it checks if the escapee is off the map. If it is, then it wins! It back-tracks the state (each prior state is recorded with each state) and builds the plan (in reverse) before exiting the BFS loop. Otherwise, it tries to apply every action, and adds any that can be applied to the due queue, before sorthing this queue so that we get the least effort state next iteration.

Formatted and commented code:

using C=System.Console;
using System.Linq;

// ascii
//   32
// ! 33
// = 61
// . 46
// * 42
// # 35
// | 124
// 0 48

class S // SearchState
{
    string M, // map
        N=""; // plan
    int x, // pos x
        y, // pos y
        E, // effort
        c; // crouching?
    decimal P=1; // chance (Probability)

    static void Main()
    {
        int W=0, // map width
            H=0, // map height
            x, // various temps
            i, // local x
            j, // local y
            k, // position in match/smash map
            X, // s.x
            Y, // s.y

            // action loop
            f, // T idx
            m, // A idx, action mirror (direction)

            P=int.Parse(C.ReadLine()); // probability of success constraint

        string l, // line, Act 'block' params, map hash, match pairs; all sorts!
            M="", // initial map
            B, // name of action
            R="There is no hope!"; // result string

        // read map
        for(;(l=C.ReadLine())!=null; // while there is input to read
            H++,M+=l) // increment height, and append to M
            W=l.Length; // record width

        // detect the escapee
        x=M.IndexOf("|");

        // create first state, and add it to Due list
        var D=new[]{new S{M=M,x=x%W,y=x/W}}.ToList();

        // 'seen' table, stores all the states we've been in which looked similar
        for(var N=D.ToDictionary(s=>R,s=>D); // these values are meaningless (and necessarily can't interfere), we just use it to save having to spec the type
            D.Count>0; // keep going until we run out of states to expand (-> no escape)
            D.Sort((z,w)=>z.E-w.E)) // enforce Breadth First Search
        {
            // get next State to expand, and remove it from Due
            S s=D[f=0];
            D.Remove(s);

            // retrieve or create seen list
            var n=N[l=s.x+s.M+s.y+s.c]= // store it, and cache it, l is 'hash', containing map and escapee state
                N.ContainsKey(l)? // already got a seen list for ths map?
                N[l]: // then use it!
                new S[0].ToList(); // otherwise create a new (empty) one

            // perf: only proceed if we havn't seen this map with better Effort and Chance yet
            if(n.All(o=>o.P<s.P|o.E>s.E))
            {
                // record that we have been seen
                n.Add(s);
                X=s.x;
                Y=s.y;

                if((X|Y|-X/W-Y/H)<0) // check if we our outside the bounds - this took 2.5hour to write. 1 byte.
                { // quit if both are positive or both are negative
                    // freedom
                    R="Required Effort: "+s.E+s.N;

                    // finished
                    break;
                }

                // [Crouch,Effort,dx,dy,Probability],Name,MatchSmash (first 10 are mirrors)
                // 0110d,Step,*** * #*,
                // 0110d,Climb off,=** * =*,
                // 3310d,Shuffle,***** #*,
                // 2:1/_,Clamber Up,*** *##*,
                // 0420_,Short Jump,****  *  #**,
                // 0730K,Long Jump,*****   *   #***,
                // 0<1/Z,High Jump,  * **#*,
                // 0D20P,Put your back into it!,****! *! #**,
                // 0800Z,Punch,***!**#*,
                // 0800U,Kick,*****!#*,
                // 0001d,Drop,*** ,
                // 1001d,Drop (Stand),*** ,
                // 2200d,Crouch,***#,
                // 1400d,Stand,* *#,
                // 020/d,Climb Up,=***,
                // 0800Z,Stamp,***!

                // attempt to expand this node with every action
                for(var A="0110d,Step,*** * #*,0110d,Climb off,=** * =*,3310d,Shuffle,***** #*,2:1/_,Clamber Up,*** *##*,0420_,Short Jump,****  *  #**,0730K,Long Jump,*****   *   #***,0<1/Z,High Jump,  * **#*,0D20P,Put your back into it!,****! *! #**,0800Z,Punch,***!**#*,0800U,Kick,*****!#*,0001d,Drop,*** ,1001d,Drop (Stand),*** ,2200d,Crouch,***#,1400d,Stand,* *#,020/d,Climb Up,=***,0800Z,Stamp,***!".Split(','); // Act string
                    f<26;) // read A into T // (cycle over first 10 twice, making them mirrors)  (very convieniently, 3*16==48=='0'==x!)
                {
                    // 'parse' next action
                    l=A[k=f*3%48]; // [Effort,Crouch,dx,dy,Probability]
                    B=A[++k]+(f>15?" Right":f>9?"":" Left"); // action name
                    M=A[++k]; // Match and Smash table (4x?, escapee at 0,2, #: solid, !: smashable (and is smashed), .: empty,  : don't care, =: climable)
                    //c=l[1]-48; // crouching transition (0: standing -> standing, 1: crouching -> standing, 2: standing -> crouching, 3: crouching -> crouching)
                    m=f++/16*2-1;

                    // this will be the new map
                    var Q=s.M.ToArray();

                    // K is whether we are allowed to apply this action
                    var K=s.P*l[4]>=P& // within chance limit
                        s.c==l[k=0]%2; // crouching matches

                    // compare the map to the Match/Smash map, to make sure we can apply this transform (and smash any ! we meet)
                    for(j=Y-3;j++<=Y;) // for the 4 rows
                        for(i=X;i!=X+m*M.Length/4;i+=m) // for each column (a.M has height 4, but variable width)
                            if((K&= // K still true?
                                "==  *!!##*!*=*|*| o*o ".Contains(""+ // check for an allowed pairing (cache pairing in M) (this includes the escapee, much cheaper to do this than remove him)
                                    ((i|j)>=0&j<H&i<W?Q[x=j*W+i]:' ') // we are within bounds and match, we are out of bounds (empty)
                                    +M[k])) // char from MatchSmash map
                                &M[k++]==33) // if it is destructible ('!' == 33)
                                Q[x]=' '; // then blank it out (x is necessarily set by the cell check)

                    if(K) // if K holds
                        D.Add(new S{M=new string(Q),N=s.N+"\n"+B, // assemble plan as we go (this will chew up memory, but none of the problems are big enough for it to matter)
                            x=X+l[2]%48*m,y=Y+l[3]-48,c=l[0]/50,E=s.E+l[1]-48,P=s.P*l[4]/100}); // add the resulting state to Due
                }
            }
        }

        C.Write(R);
    }
}