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.