I want to watch you die of thirst

Question

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

1. move one square Up, Down, Left, or Right,
2. consume 1 unit of water that you are carrying,
3. 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:

1. the list of moves,
2. 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.

1. Your program must eventually solve any solvable input.
2. 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.
3. If you encounter a winning solution, print the full output for that and terminate.
4. Run until a solution is found, but do not attempt the same solution twice -- all deaths should be by distinct routes.
5. 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.

Answer 1

Perl, 299 + 1 = 300 254 + 1 = 255 bytes

This will almost certainly be beaten by one of the golfing languages when people see my algorithm :-)

Run with -n (1 byte penalty).

The previous version didn't quite comply with the spec because it left extra water on the map and didn't show it in the final version of the map; while changing the algorithm to deal with that situation, I managed to golf it a bit smaller in the process.

push@a,[split//];($s,$t)=(length$`,$.)if/S/;($e,$f)=(length$`,$.)if/E/}{$_.=$s<$e?($s++,R):$s>$e?($s--,L):$t<$f?($t++,D):($t--,U);$\=reverse$";$".=y/LRUD/RLDU/r.Y.reverse.($"=~y/Y/X/r);$a[$t-1][$s]=~y/./#/;$\.=$s-$e||$t-$f?redo:$_;print map{join'',@$_}@a

Example (I've added line-breaks to the output to avoid the need to scroll and to show the structure):

E.....
#.....
#.....
#.....
#####S
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUXDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUUYDDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUXDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUUYDDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLXRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLUYDRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLXRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLLYRRRRR
 LXR LLXRR LXR LLLXRRR LXR LLXRR LXR LLLLYRRRR
 LXR LLXRR LXR LLLYRRR LXR LLYRR LYR LLLLLUUUU

In the notation used by the program, movement is represented via L, R, U, and D for left, up, right, down respectively. By default, you pick up 1 unit of water after every move, but this can be modified by appending a character:

• X: drop 2 units of water, rather than picking 1 up
• Y: drop 1 unit of water, rather than picking 1 up
• (i.e. space): completely refill on water (only output after a move to S; the program is also output with a leading space, which makes sense because you start full on water)

As you can see, it's possible to cross this (rather barren) map using no extra pools at all. In fact, it's possible to get any distance under these rules, on any map, without the help of any preplaced water. As such, this algorithm just ignores any preplaced water, meaning I don't have to waste bytes trying to handle it. This also means that you're not going to see the bot die, sorry. It never moves beyond the range in which it knows it's guaranteed to survive.

The reason we need both X and Y (and a bit of extra code to ensure we have X throughout most of the strategy but the occasional Y at the end) is that the spec requires the final version of the map to be output. The easiest way to implement this is to leave the map entirely untouched (apart from our path through initially empty squares), especially as a square which started with 9 water would end up with 10 (breaking the ASCII art) if it happened to be on the path and we only used X, and thus we need to find some solution that avoids dropping extra water on the map. The algorithm here would "naturally" drop 1 extra unit of water on each square on the route; as such, the penultimate time we visit each square, we reduce the amount of water dropped by 1 via the use of Y rather than X, so that on our final visit, we drain the square back to its original quantity of water, rather than leaving it slightly wetter than when we started.

I'd recommend against running this on a large map, because it has O(2^n) performance (although the bot never dies of thirst, it's plausible to think it would die of hunger using a strategy like this.)

Readable version:

# implicit with -n: read a line of input into $_
push @a, [split //]; #/ split $_ into characters, store at the end of @a
($s,$t) = (length$`,$.) if /S/; # if we see S, store its coordinates
($e,$f) = (length$`,$.) if /E/  # if we see E, store its coordinates
}{ # Due to -n, loop back to start if there are more lines.

# From here onwards, $" stores the partial solution this iteration;
#                    $\ stores the partial solution last iteration;
#                    $_ stores the path from ($s,$t) to S.
# At the start of the program, $" is a space, $\ and $_ are empty.

$_ .=  # Work out the next step on the path:
  $s < $e ? ($s++,R) # if too far left, move right, record that in $_;
: $s > $e ? ($s--,L) # if too far right, move left, record that in $_;
: $t < $f ? ($t++,D) # if too far up,    move down, record that in $_;
: ($t--,U);          # in other cases we must be too far down.
$\ = reverse $";     # Store last iteration; $" is constructed backwards.
$" .=                # Extend $" by appending
  y/LRUD/RLDU/r .    # the path from ($s, $t) back to S;
  Y .                # a literal 'Y';
  reverse .          # $/ backwards (i.e. the path from S to ($s, $t);
  ($"=~y/Y/X/r);     # a copy of $" with all 'Y' changed to 'X'.
$a[$t-1][$s] =~      # At the current path coordinate,
  y/./#/;            # replace any '.' with '#'.
$\ .=                # Start appending to $\;
  $s-$e||$t-$f?redo  # if we're not at E, abort that and jump back to {{,
: $_;                # otherwise append $_ (the path from S to E).
print map            # For each element of some array
  {join'',@$_}       # output its concatenated elements
  @a                 # specifying that array as @a.
# Implicitly: print $\ (which specifies the sort of newline print uses).