Seguindo a sequência do AoC desse outro post: https://www.tabnews.com.br/DeividBraian/advent-of-code-2023-desafios-de-programacao

---

Dia 11: Expansão Cósmica

https://adventofcode.com/2023/day/11

Descrição

Parte Um

Você continua seguindo as placas para "Hot Springs" e eventualmente se depara com um observatório. O Elfo dentro dele é um pesquisador que estuda a expansão cósmica usando o telescópio gigante aqui.

Ele não sabe nada sobre as peças perdidas da máquina; ele está apenas visitando para este projeto de pesquisa. No entanto, ele confirma que as fontes termais são a área mais próxima que provavelmente tem pessoas; ele até o levará diretamente lá assim que terminar a análise de observação de hoje.

Talvez você possa ajudá-lo com a análise para acelerar as coisas?

O pesquisador coletou muitos dados e compilou os dados em uma única imagem gigante (sua entrada para o quebra-cabeça). A imagem inclui espaço vazio (.) e galáxias (#). Por exemplo:

...#......
.......#..
#.........
..........
......#...
.#........
.........#
..........
.......#..
#...#.....

O pesquisador está tentando descobrir a soma dos comprimentos do caminho mais curto entre cada par de galáxias. No entanto, há um detalhe: o universo se expandiu no tempo que levou a luz daquelas galáxias para chegar ao observatório.

Devido a algo relacionado a efeitos gravitacionais, apenas alguns espaços se expandem. Na verdade, o resultado é que qualquer linha ou coluna que não contenha galáxias deve ser na verdade o dobro do tamanho.

No exemplo acima, três colunas e duas linhas não contêm galáxias:

   v  v  v
 ...#......
 .......#..
 #.........
>..........<
 ......#...
 .#........
 .........#
>..........<
 .......#..
 #...#.....
   ^  ^  ^

Essas linhas e colunas precisam ser duas vezes maiores; o resultado da expansão cósmica parece assim:

....#........
.........#...
#............
.............
.............
........#....
.#...........
............#
.............
.............
.........#...
#....#.......

Equipado com este universo expandido, é possível encontrar o caminho mais curto entre cada par de galáxias. Pode ser útil atribuir um número único a cada galáxia:

....1........
.........2...
3............
.............
.............
........4....
.5...........
............6
.............
.............
.........7...
8....9.......

Nestas 9 galáxias, existem 36 pares. Conte cada par apenas uma vez; a ordem dentro do par não importa. Para cada par, encontre qualquer caminho mais curto entre as duas galáxias usando apenas passos que se movam para cima, para baixo, para a esquerda ou para a direita exatamente um . ou # por vez. (O caminho mais curto entre duas galáxias pode passar por outra galáxia.)

Por exemplo, aqui está um dos caminhos mais curtos entre as galáxias 5 e 9:

....1........
.........2...
3............
.............
.............
........4....
.5...........
.##.........6
..##.........
...##........
....##...7...
8....9.......

Este caminho tem comprimento 9 porque leva um mínimo de nove passos para ir da galáxia 5 para a galáxia 9 (as oito localizações marcadas # mais o passo para a própria galáxia 9). Aqui estão alguns outros comprimentos de exemplo de caminhos mais curtos:

• Entre a galáxia 1 e a galáxia 7: 15
• Entre a galáxia 3 e a galáxia 6: 17
• Entre a galáxia 8 e a galáxia 9: 5

Neste exemplo, após expandir o universo, a soma do caminho mais curto entre todos os 36 pares de galáxias é 374.

Expanda o universo e, em seguida, encontre o comprimento do caminho mais curto entre cada par de galáxias. Qual é a soma desses comprimentos?

Comunidade

Compartilhe suas ideias e se junte ao nosso Private Leaderboard! Utilize o código 3564351-c120ec27