12

2

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.

This needs to be clarified to specify whether the program needs to be able to solve any solvable map, or whether it only has to work for one map. I'd definitely encourage the former; in the case of one map, it'll be easier to hardcode the solution than to calculate it. – None – 2016-11-22T12:55:32.887

Edited for clarity. Yes you win if you have more than zero water, and yes your program must solve all solvable inputs. – spraff – 2016-11-22T13:07:05.520

What's stopping you to use an algorithm such as A* and dropping a path of 5 units on each tile you successively go to and go back to the start if you step onto a tile without 5 water? – Blue – 2016-11-22T15:19:39.013

Nothing. Go ahead. – spraff – 2016-11-22T15:57:44.710

The 'carry all water from S' strategy should work, although it will be terribly tedious. Consider S.,.,.,.,.e....E where , and e are really dots. The commas are where you keep your stashes along the way, and 'e' is where you need to have 5 water to make a run for E. 4 steps to move 1 water to the first comma (E+0 E-1 W+0 W+4). 16 steps to move 1 water to the second comma. 52 to the third, 160 to the fourth, 484 to drop 1 water to e and get back to S. 1926 steps and you're at e carrying 5 water, 5 more to run to E, 1931 steps. Every two steps of path effectively triples your solution length. – Sparr – 2016-11-23T00:57:43.803

@Sparr: My solution's actually even more inefficient, because the goal is to write a short program to generate the output rather than a short output. "Clever" algorithms to generate a more optimal output are unlikely to win a [tag:code-golf]. – None – 2016-11-23T04:03:29.600

@ais523 I did see that. I have ideas for an even less efficient solution :) – Sparr – 2016-11-23T20:03:35.720