Vous êtes un voyageur traversant le désert entre deux villes. Vous ne pouvez pas transporter suffisamment d'eau pour traverser sans vous arrêter. Ceci est une variation d'un puzzle classique.

Les règles

Un désert ressemble à ceci: une grille WxH d'espace principalement vide. L'espace marqué Sest l'endroit où vous commencez, Ec'est l'endroit où vous voulez finir, et un carré marqué du nombre N contient N unités d'eau. Carrés marqués d'une .retenue d'eau nulle.

.....................................
........S............................
.....................................
.........7...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

Vous commencez en S avec 5 unités d'eau.

Vous pouvez transporter au maximum 5 unités d'eau.

À chaque tour

1. déplacer un carré vers le haut, le bas, la gauche ou la droite,
2. consommez 1 unité d'eau que vous transportez,
3. ramasser ou déposer un certain nombre d'unités d'eau.

Un tour est transcrite ainsi: (direction)(+|-)(units of water), +vous indique ramassez l' eau, -que vous laisser tomber.

Exemple tourne:

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.

Si vous effectuez ces mouvements en commençant par S dans l'exemple ci-dessus, le désert ressemble à ceci après.

.....................................
........S............................
.........1...........................
.........5...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................

Vous ne pouvez pas prendre plus d'eau que ce qui est déjà sur votre place. Lorsque vous récupérez l'eau, déduisez ce nombre d'unités du nombre de tuiles.

Vous ne pouvez ramasser de l'eau que pour un maximum de 5 unités.

Aucune tuile ne peut contenir plus de 9 unités, sauf S qui détient des unités à l'infini.

Vous ne pouvez laisser tomber autant d'eau que vous en avez actuellement.

L'eau au sol reste inchangée jusqu'à ce que vous la récupériez.

Si vous revenez à S, vous pouvez ramasser n'importe quelle quantité d'eau sans l'appauvrir.

Si vous atteignez E, vous gagnez . Vous gagnez toujours si vous consommez votre dernière unité d'eau sur E.

Si, après votre tour, vous n'avez plus d'eau et que vous n'êtes pas sur E, vous mourrez .

Entrée et sortie

Votre programme recevra une carte de départ de taille arbitraire en STDINtant qu'art ASCII dans le format ci-dessus. Vous pouvez supposer qu'il est rectangulaire, c'est-à-dire toutes les lignes de la même longueur, qu'il y a exactement un Set un Ecarré, toutes les lignes se terminent par \n, et l'ensemble de STDIN sera conforme à cette expression régulière:/^[SE1-9\.\n]+$/

Votre programme écrira la sortie suivante dans STDOUT:

1. la liste des coups,
2. l'état final de la carte.

Vous pouvez afficher la liste des mouvements dans n'importe quel format pratique.

L'état final de la carte sera imprimé dans le même format que l'entrée, sauf qu'il montrera en plus l'itinéraire que vous avez suivi à travers le désert en marquant toutes les tuiles visitées #, si cette tuile ne contient pas d'eau et n'est pas S ou E (c'est-à-dire c'est .).

EXEMPLE d' entrée:

.....S.
.......
.......
E......
....8..

EXEMPLE sortie gagnante:

D+0
D+0
D+0
D+0
L+5
L+0
L+0
L+0
L+0
U+0
.....S.
.....#.
.....#.
E....#.
####3#.

Non-trivialité

Lorsque vous publiez votre code, publiez un exemple d'entrée de carte pour lequel votre code trouve une solution qui satisfait aux conditions de non-trivialité suivantes:

• S et E sont séparés d'au moins 10 mouvements.
• Tout carré qui contient initialement N unités d'eau doit être entouré d'une bordure de largeur N dans laquelle se trouvent tous les carrés .(pas d'eau, pas S ou E)

EXEMPLE

........2.
..........
..........
S.1..2....
..........
..........
........1.
..3.......
.........E

Si vous augmentez la quantité d'eau sur n'importe quelle tuile, ce qui précède devient trivial.

Exigences

Vraisemblablement, votre programme rencontrera un certain nombre de tentatives infructueuses avant de trouver une solution, le cas échéant.

1. Votre programme doit éventuellement résoudre tout apport résoluble.
2. Je veux vous regarder mourir - votre programme affichera les mouvements et la carte finale de l'itinéraire vers la mort pour chaque tentative infructueuse de trouver une solution.
3. Si vous rencontrez une solution gagnante, imprimez la sortie complète pour cela et terminez.
4. Exécutez jusqu'à ce qu'une solution soit trouvée, mais n'essayez pas la même solution deux fois - tous les décès doivent se faire par des voies distinctes.
5. Utilisez ceci une entrée de test:

(il faut au moins un coup pour déposer une cache d'eau à un certain point médian).

 S........
 .........
 .........
 ........E

Le code le plus court qui est publié avec une entrée de démonstration non triviale qu'il résout gagne.

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

Cela sera presque certainement battu par l'un des langages de golf lorsque les gens verront mon algorithme :-)

Exécutez avec -n(1 octet de pénalité).

La version précédente n'était pas tout à fait conforme aux spécifications car elle laissait de l'eau supplémentaire sur la carte et ne la montrait pas dans la version finale de la carte; tout en changeant l'algorithme pour faire face à cette situation, j'ai réussi à le jouer un peu plus petit dans le processus.

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

Exemple (j'ai ajouté des sauts de ligne à la sortie pour éviter d'avoir à faire défiler et d'afficher la 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

Dans la notation utilisée par le programme, le mouvement est représenté par L, R, Uet Dpour la gauche, haut, droite, bas , respectivement. Par défaut, vous ramassez 1 unité d'eau après chaque mouvement, mais cela peut être modifié en ajoutant un personnage:

• X: laissez tomber 2 unités d'eau, plutôt que d'en ramasser 1
• Y: laissez tomber 1 unité d'eau, plutôt que d'en ramasser 1
• (c.-à-d. espace): recharger complètement sur l'eau (sortie uniquement après un déplacement vers S; le programme est également sorti avec un espace de tête, ce qui est logique parce que vous commencez complètement sur l'eau)

Comme vous pouvez le voir, il est possible de traverser cette carte (plutôt stérile) sans aucune réserve supplémentaire. En fait, il est possible d'obtenir n'importe quelle distance selon ces règles, sur n'importe quelle carte, sans l'aide d'une eau pré-placée. En tant que tel, cet algorithme ignore simplement toute eau pré-placée, ce qui signifie que je n'ai pas à gaspiller d'octets pour le gérer. Cela signifie également que vous n'allez pas voir le robot mourir, désolé. Il ne dépasse jamais la plage dans laquelle il sait qu'il est garanti de survivre.

La raison pour laquelle nous avons besoin des deux Xet Y(et d'un peu de code supplémentaire pour nous assurer que nous avons Xtout au long de la plupart de la stratégie, mais occasionnellement Yà la fin) est que la spécification nécessite la sortie de la version finale de la carte. La façon la plus simple de mettre en œuvre cela est de laisser la carte entièrement intacte (en dehors de notre chemin à travers des carrés initialement vides), d'autant plus qu'un carré qui a commencé avec de l' 9eau finirait par 10(briser l'art ASCII) s'il se trouvait sur le chemin et nous avons seulement utiliséX, et donc nous devons trouver une solution qui évite de laisser tomber de l'eau supplémentaire sur la carte. L'algorithme ici laisserait «naturellement» 1 unité d'eau supplémentaire sur chaque carré du parcours; en tant que tel, l'avant-dernière fois que nous visitons chaque carré, nous réduisons la quantité d'eau tombée de 1 via l'utilisation de Y plutôt que de X, de sorte que lors de notre dernière visite, nous drainons le carré à sa quantité d'eau d'origine, plutôt que le laissant légèrement plus humide que lorsque nous avons commencé.

Je déconseille de l'exécuter sur une grande carte, car il a des performances O (2 ^ n) (bien que le bot ne meure jamais de soif, il est plausible de penser qu'il mourrait de faim en utilisant une stratégie comme celle-ci.)

Version lisible:

# 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).