Advent of Code 2022 - Dia 12

No contexto deste outro conteúdo: https://www.tabnews.com.br/tcarreira/advent-of-code-2022-desafios-de-programacao (se gostarem deste conteúdo, votem no original, para que ele fique visível durante o tempo do AoC)

--- Dia 12: Algoritmo de Escalada ---

Você tenta entrar em contato com os Elfos usando seu dispositivo portátil, mas o rio que você está seguindo deve estar muito baixo para obter um sinal decente.

Você pede ao dispositivo um mapa de altura da área circundante (sua entrada do puzzle). O mapa de altura mostra a área local de cima em forma de uma grelha; a elevação de cada quadrado da grelha é dada por uma única letra minúscula, onde a é a elevação mais baixa, b é a próxima mais baixa, e assim por diante até a elevação mais alta, z.

Também estão incluídas no mapa de altura as marcas para sua posição atual (S) e o local que deve obter o melhor sinal (E). Sua posição atual (S) tem elevação a, e o local que deve receber o melhor sinal (E) tem elevação z.

Você gostaria de chegar a E, mas para economizar energia, você deve fazê-lo no menor número de passos possível. Durante cada passo, você pode mover exatamente um quadrado para cima, para baixo, para a esquerda ou para a direita. Para evitar a necessidade de retirar seu equipamento de escalada, a elevação do quadrado de destino pode ser no máximo um ponto mais alto do que a elevação do seu quadrado atual; ou seja, se a sua elevação atual for m, você pode ir para a elevação n, mas não para a elevação o. (Isso também significa que a elevação do quadrado de destino pode ser muito menor do que a elevação do seu quadrado atual.)

Por exemplo:

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

Aqui, você começa no canto superior esquerdo; seu objetivo está perto do meio. Você pode começar movendo para baixo ou para a direita, mas eventualmente precisará ir em direção ao e na parte inferior. A partir daí, você pode espiralar até o objetivo:

v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^

No diagrama acima, os símbolos indicam se o caminho sai de cada quadrado movendo-se para cima (^), para baixo (v), para a esquerda (<) ou para a direita (>). O local que deve obter o melhor sinal ainda é E, e . marca os quadrados não visitados.

Este caminho atinge a meta em 31 passos, o menor possível.

Qual é o menor número de passos necessários para mover desde a sua posição atual até o local que deve receber o melhor sinal?

--- Parte dois ---

https://github.com/tcarreira/aoc2022/tree/main/day12#----parte-dois----

(saber a parte 2 antes de fazer a parte 1 não é tão divertido. Então vou deixar apenas o link para o Github 😉)

Outros links: