You are a traveller crossing the desert between two towns. You cannot carry enough water to get across without stopping. This is a variation of a classic puzzle.
The Rules
A desert looks like this: a WxH grid of mostly empty space. The space marked S is where you start, E is where you want to end, and a square marked with the number N holds N units of water. Squares marked with a . hold zero water.
.....................................
........S............................
.....................................
.........7...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................
You start at S with 5 units of water.
You can carry at most 5 units of water.
Each turn you
- move one square Up, Down, Left, or Right,
- consume 1 unit of water that you are carrying,
- pick up or drop some number of units of water.
A turn is notated thus: (direction)(+|-)(units of water), + indicates you are picking up water, - that you are dropping it.
Example turns:
D+0 Move Down
R+0 Move Right
D+2 Move Down, pick up two units of water.
U-1 Move Up, drop one unit of water.
If you perform these moves starting at S in the example above, the desert looks like this afterwards.
.....................................
........S............................
.........1...........................
.........5...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................
You can pick up no more water than is already on your square. When you pick up the water, deduct that number of units from the tile's count.
You can only pick up water to hold a maximum of 5 units.
No tile can hold more than 9 units, except S which holds infinity units.
You can only drop as much water as you are currently holding.
Water on the ground remains unchanged until you pick it up again.
If you return to S you can pick up any quantity of water without depleting it.
If you reach E then you win. You still win if you consume your last unit of water on E.
If, after your turn, you have zero water and you are not on E, you die.
Input and Output
Your program will receive a starting map of arbitrary size on STDIN as ASCII art in the format above. You can assume it is rectangular i.e. all lines the same length, that there is exactly one S and one E square, all lines are terminated with \n, and the whole of STDIN will conform to this regex: /^[SE1-9\.\n]+$/
Your program will write the following output to STDOUT:
- the list of moves,
- the final state of the map.
You may output the list of moves in any convenient format.
The final state of the map will be printed in the same format as the input except that it will additionally show the route you took through the desert by marking all visited tiles with #, if that tile contains no water and is not S or E (i.e. it is .).
EXAMPLE input:
.....S.
.......
.......
E......
....8..
EXAMPLE winning output:
D+0
D+0
D+0
D+0
L+5
L+0
L+0
L+0
L+0
U+0
.....S.
.....#.
.....#.
E....#.
####3#.
Nontriviality
When you post your code, post a sample map input which your code finds a solution for which satisfies the following non-triviality conditions:
- S and E are at least 10 moves apart.
- Any square which initially contains N units of water must be surrounded by a N-width border in which all squares are
.(no water, not S or E)
EXAMPLE
........2.
..........
..........
S.1..2....
..........
..........
........1.
..3.......
.........E
If you increase the amount of water on any tile, the above becomes trivial.
Requirements
Presumably your program will encounter a number of failed attempts before it finds a solution, if any.
- Your program must eventually solve any solvable input.
- I want to watch you die -- your program will output the moves and final map of the route to death for each and every failed attempt to find a solution.
- If you encounter a winning solution, print the full output for that and terminate.
- Run until a solution is found, but do not attempt the same solution twice -- all deaths should be by distinct routes.
- Use this a test input:
(it requires at least one move to drop a water cache at some midpoint).
S........
.........
.........
........E
Shortest code which is posted with a non-trivial demonstration input which it solves wins.
