README
¶
--- Dia 23: Difusão Instável ---
Você entra em uma grande cratera de terra cinzenta onde o arvoredo deveria estar. Ao seu redor, as plantas que você imagina que deveriam estar cheias de frutos estão murchas e quebradas. Um grande grupo de Elfos se formou no meio do arvoredo.
"... mas este vulcão está adormecido há meses. Sem cinzas, os frutos não podem crescer!"
Você olha para cima e vê uma enorme montanha coberta de neve elevando-se acima de você.
"Não é como se houvesse outros vulcões ativos aqui; procuramos em todos os lugares."
"Mas nossos scanners mostram fluxos de magma ativos; claramente está indo para algum lugar."
Eles finalmente reparam em você na beira do arvoredo, sua mochila quase transbordando de frutos estrela aleatórios que você tem coletado. Atrás de você, elefantes e macacos exploram o arvoredo, parecendo preocupados. Então, os Elfos reconhecem a nuvem de cinzas se espalhando lentamente sobre seu desvio recente.
"Por que você..." "Como é que..." "Você acabou de..."
Antes que qualquer um deles possa formular uma pergunta completa, outro Elfo toma a palavra: "Ok, novo plano. Já quase temos frutos suficientes, e as cinzas da nuvem devem se espalhar aqui eventualmente. Se plantarmos rapidamente as novas mudas agora, ainda podemos chegar no ponto de extração. Espalhem!"
Cada um dos elfos enfia a mão em sua mochila e tira uma plantinha. As plantas dependem de nutrientes importantes das cinzas, por isso não podem ser plantadas demasiado próximas umas das outras.
Não há tempo suficiente para deixar os elfos descobrirem onde plantar as mudas; você examina rapidamente o arvoredo (sua entrada do puzzle) e observa suas posições.
Por exemplo:
....#..
..###.#
#...#.#
.#...##
#.###..
##.#.##
.#..#..
A varredura mostra Elfos # e terreno vazio .; fora de sua varredura, mais terreno vazio se estende por um longo caminho em todas as direções. A varredura é orientada de modo que norte fique para cima; as direções ortogonais são escritas N (norte), S (sul), W (oeste) e E (leste), enquanto as direções diagonais são escritas NE, NW, SE, SW.
Os Elfos seguem um processo demorado para descobrir para onde cada um deve ir; você pode acelerar consideravelmente esse processo. O processo consiste em um certo número de rodadas durante as quais os Elfos alternam entre considerar para onde se mover e realmente se mover.
Durante a primeira metade de cada rodada, cada Elfo considera as oito posições adjacentes a si mesmo. Se nenhum outro elfo estiver em uma dessas oito posições, o elfo não fará nada durante esta rodada. Caso contrário, o Elfo olha em cada uma das quatro direções na seguinte ordem e propõe mover um passo na primeira direção válida:
-
Se não houver elfo nas posições N, NE ou NW adjacentes, o elfo propõe mover para norte um passo.
-
Se não houver Elfo nas posições adjacentes S, SE ou SW, o Elfo propõe mover para sul um passo.
-
Se não houver um Elfo nas posições adjacentes W, NW ou SW, o Elfo propõe mover para oeste um passo.
-
Se não houver elfo nas posições adjacentes E, NE ou SE, o elfo propõe mover leste um passo.
Depois que cada Elfo teve a chance de propor um movimento, a segunda metade da rodada pode começar. Simultaneamente, cada elfo move-se para seu quadrado de destino proposto se ele for o único elfo a propor mover-se para aquela posição. Se dois ou mais Elfos propõem mover-se para a mesma posição, nenhum desses Elfos se move.
Finalmente, no final da rodada, a primeira direção que os Elfos consideraram é movida para o final da lista de direções. Por exemplo, durante a segunda rodada, os Elfos tentariam propor um movimento primeiro para o sul, depois para o oeste, depois para o leste e depois para o norte. Na terceira rodada, os elfos considerariam primeiro o oeste, depois o leste, depois o norte e depois o sul.
Como um exemplo menor, considere apenas estes cinco Elfos:
.....
..##.
..#..
.....
..##.
.....
Os dois elfos mais ao norte e os dois elfos mais ao sul propõem mover-se para o norte, enquanto o elfo do meio não pode se mover para o norte e propõe mover-se para o sul. O elfo do meio propõe o mesmo destino que o elfo do sudoeste, então nenhum deles se move, mas os outros três o fazem:
..##.
.....
..#..
...#.
..#..
.....
Em seguida, os dois elfos mais ao norte e o elfo mais ao sul propõem se mudar para o sul. Dos dois Elfos do meio restantes, o do oeste não pode se mover para o sul e propõe mover-se para o oeste, enquanto o leste não pode mover-se para o sul nem oeste e propõe mover-se para o leste. Todos os cinco Elfos conseguem se mover para suas posições propostas:
.....
..##.
.#...
....#
.....
..#..
Finalmente, os dois elfos mais ao sul optam por não se mover. Dos três Elfos restantes, o do oeste propõe mover-se para o oeste, o do leste propõe mover-se para o leste e o do meio propõe mover-se para o norte; todos os três conseguem se mover:
..#..
....#
#....
....#
.....
..#..
Neste ponto, nenhum Elfo precisa se mover, e assim o processo termina.
O exemplo maior acima procede da seguinte forma:
== Estado inicial ==
..............
..............
.......#......
.....###.#....
...#...#.#....
....#...##....
...#.###......
...##.#.##....
....#..#......
..............
..............
..............
== Final da rodada 1 ==
..............
.......#......
.....#...#....
...#..#.#.....
.......#..#...
....#.#.##....
..#..#.#......
..#.#.#.##....
..............
....#..#......
..............
..............
== Final da rodada 2 ==
..............
.......#......
....#.....#...
...#..#.#.....
.......#...#..
...#..#.#.....
.#...#.#.#....
..............
..#.#.#.##....
....#..#......
..............
..............
== Final da rodada 3 ==
..............
.......#......
.....#....#...
..#..#...#....
.......#...#..
...#..#.#.....
.#..#.....#...
.......##.....
..##.#....#...
...#..........
.......#......
..............
== Final da rodada 4 ==
..............
.......#......
......#....#..
..#...##......
...#.....#.#..
.........#....
.#...###..#...
..#......#....
....##....#...
....#.........
.......#......
..............
== Final da rodada 5 ==
.......#......
..............
..#..#.....#..
.........#....
......##...#..
.#.#.####.....
...........#..
....##..#.....
..#...........
..........#...
....#..#......
..............
Depois de mais algumas rodadas...
== Final da rodada 10 ==
.......#......
...........#..
..#.#..#......
......#.......
...#.....#..#.
.#......##....
.....##.......
..#........#..
....#.#..#....
..............
....#..#..#...
..............
Para ter certeza de que estão no caminho certo, os Elfos gostam de verificar após a rodada 10 se estão fazendo um bom progresso para cobrir terreno suficiente. Para fazer isso, conte o número de quadrados de chão vazios contidos no menor retângulo que contém cada Elfo. (As bordas do retângulo devem estar alinhadas nas direções N/S/E/W; os Elfos não têm paciência para calcular retângulos arbitrários.) No exemplo acima, esse retângulo é:
......#.....
..........#.
.#.#..#.....
.....#......
..#.....#..#
#......##...
....##......
.#........#.
...#.#..#...
............
...#..#..#..
Nesta região, o número de quadrados vazios é 110.
Simule o processo dos Elfos e encontre o menor retângulo que contenha os Elfos após 10 rodadas. Quantos quadrados de chão vazios esse retângulo contém?
--- Parte Dois ---
Parece que você está no caminho certo. Termine de simular o processo e descubra onde os Elfos precisam ir. Quantas rodadas você lhes poupou?
No exemplo acima, a primeira rodada em que nenhum elfo se moveu foi a rodada 20:
.......#......
....#......#..
..#.....#.....
......#.......
...#....#.#..#
#.............
....#.....#...
..#.....#.....
....#.#....#..
.........#....
....#......#..
.......#......
Descubra onde os elfos precisam ir. Qual é o número da primeira rodada em que nenhum elfo se move?
Documentation
Source Files