Você é um viajante atravessando o deserto entre duas cidades. Você não pode carregar água suficiente para atravessar sem parar. Esta é uma variação de um quebra-cabeça clássico.

As regras

Um deserto se parece com isso: uma grade WxH da maior parte do espaço vazio. O espaço marcado Sé onde você começa, Eé onde deseja terminar e um quadrado marcado com o número N contém N unidades de água. Quadrados marcados com um ponto .zero de água.

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

Você começa em S com 5 unidades de água.

Você pode transportar no máximo 5 unidades de água.

Cada vez que você

1. mova um quadrado para cima, baixo, esquerda ou direita,
2. consuma 1 unidade de água que você está carregando,
3. pegar ou soltar um número de unidades de água.

A sua vez, está anotado assim: (direction)(+|-)(units of water), +indica que você está pegando água, -que está a deixá-la cair.

Exemplo de turnos:

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.

Se você executar esses movimentos começando em S no exemplo acima, o deserto será assim depois.

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

Você não pode pegar mais água do que já está na sua praça. Quando você pegar a água, deduza esse número de unidades da contagem do ladrilho.

Você só pode pegar água para armazenar no máximo 5 unidades.

Nenhum bloco pode conter mais de 9 unidades, exceto S, que contém unidades infinitas.

Você só pode deixar cair tanta água quanto está segurando no momento.

A água no solo permanece inalterada até você recuperá-la.

Se você retornar a S, poderá coletar qualquer quantidade de água sem esgotá-la.

Se você alcançar E, então você vence . Você ainda ganha se consumir sua última unidade de água em E.

Se, após o seu turno, você tiver zero água e não estiver em E, você morre .

Entrada e saída

Seu programa receberá um mapa inicial de tamanho arbitrário STDINcomo arte ASCII no formato acima. Você pode assumir que é retangular, ou seja, todas as linhas têm o mesmo comprimento, que há exatamente um Se um Equadrado, todas as linhas são terminadas com \ne todo o STDIN estará em conformidade com este regex:/^[SE1-9\.\n]+$/

Seu programa gravará a seguinte saída em STDOUT:

1. a lista de movimentos,
2. o estado final do mapa.

Você pode imprimir a lista de movimentos em qualquer formato conveniente.

O estado final do mapa será impresso no mesmo formato da entrada, exceto que mostrará adicionalmente a rota que você percorreu pelo deserto , marcando todos os ladrilhos visitados com #, se esse ladrilho não contiver água e não for S ou E (por exemplo, é .).

Entrada EXEMPLO :

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

Exemplo de resultado vencedor:

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

Não trivialidade

Ao publicar seu código, publique uma entrada de mapa de amostra na qual seu código encontre uma solução para a qual atenda às seguintes condições de não trivialidade:

• S e E são pelo menos 10 movimentos separados.
• Qualquer quadrado que contenha inicialmente N unidades de água deve ser cercado por uma borda de largura N na qual todos os quadrados estejam .(sem água, não S ou E)

EXEMPLO

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

Se você aumentar a quantidade de água em qualquer peça, o item acima se torna trivial.

Exigências

Presumivelmente, seu programa encontrará várias tentativas com falha antes de encontrar uma solução, se houver.

1. Seu programa deve eventualmente resolver qualquer entrada solucionável.
2. Quero ver você morrer - seu programa exibirá os movimentos e o mapa final da rota para a morte para cada tentativa frustrada de encontrar uma solução.
3. Se você encontrar uma solução vencedora, imprima a saída completa e finalize.
4. Execute até encontrar uma solução, mas não tente a mesma solução duas vezes - todas as mortes devem ocorrer por rotas distintas.
5. Use esta entrada de teste:

(requer pelo menos um movimento para descartar um cache de água em algum ponto intermediário).

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

O código mais curto que é publicado com uma entrada de demonstração não trivial que ele resolve ganha.

Perl, 299 + 1 = 300254 + 1 = 255 bytes

Isso quase certamente será derrotado por uma das linguagens do golfe quando as pessoas virem meu algoritmo :-)

Corra com -n(penalidade de 1 byte).

A versão anterior não estava de acordo com as especificações, porque deixava água extra no mapa e não a mostrava na versão final do mapa; ao mudar o algoritmo para lidar com essa situação, consegui jogar um pouco menor no processo.

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

Exemplo (adicionei quebras de linha à saída para evitar a necessidade de rolar e mostrar a estrutura):

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

Na notação usada pelo programa, o movimento é representado através de L, R, U, e Dpara a esquerda, para cima, direita, para baixo, respectivamente. Por padrão, você coleta 1 unidade de água após cada movimento, mas isso pode ser modificado anexando um caractere:

• X: jogue 2 unidades de água em vez de pegar 1
• Y: solte 1 unidade de água em vez de coletar 1
• (ou seja, espaço): reabasteça completamente a água (somente a saída após a mudança para S; o programa também é liberado com um espaço à esquerda, o que faz sentido porque você começa a ficar cheio na água)

Como você pode ver, é possível cruzar esse mapa (bastante estéril) usando nenhum pool extra. De fato, é possível obter qualquer distância sob essas regras, em qualquer mapa, sem a ajuda de água pré-colocada. Como tal, esse algoritmo simplesmente ignora qualquer água pré-colocada, o que significa que não preciso desperdiçar bytes tentando lidar com isso. Isso também significa que você não verá o bot morrer, desculpe. Ele nunca ultrapassa o limite em que sabe que é garantido que sobreviverá.

A razão precisamos de ambos Xe Y(e um pouco de código extra para garantir que temos Xem quase toda a estratégia, mas o ocasional Yno final) é que a especificação requer a versão final do mapa para ser emitido. A maneira mais fácil de implementar isso é deixar o mapa completamente intocado (além do caminho através de quadrados inicialmente vazios), especialmente porque um quadrado que começou com 9água acabaria com 10(quebrando a arte ASCII) se ele estivesse no caminho e nós usamos apenasX, e, portanto, precisamos encontrar uma solução que evite a queda de água extra no mapa. O algoritmo aqui "naturalmente" jogaria 1 unidade extra de água em cada quadrado da rota; como tal, no penúltimo momento em que visitamos cada quadrado, reduzimos a quantidade de água deixada cair 1 por meio do uso de Y em vez de X, para que, em nossa visita final, drenemos o quadrado de volta à sua quantidade original de água, em vez de deixando-o um pouco mais úmido do que quando começamos.

Eu recomendaria não executar isso em um mapa grande, porque ele tem desempenho O (2 ^ n) (embora o bot nunca morra de sede, é plausível pensar que morreria de fome usando uma estratégia como essa).

Versão legível:

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