Day 18 - Advent of Code 2015
Mix.install([:kino, :benchee]):ok
Links
Prompt
--- Day 18: Like a GIF For Your Yard ---
After the million lights incident, the fire code has gotten stricter: now, at most ten thousand lights are allowed. You arrange them in a 100x100 grid.
Never one to let you down, Santa again mails you instructions on the ideal lighting configuration. With so few lights, he says, you'll have to resort to animation.
Start by setting your lights to the included initial configuration (your puzzle input). A # means "on", and a . means "off".
Then, animate your grid in steps, where each step decides the next configuration based on the current one. Each light's next state (either on or off) depends on its current state and the current states of the eight lights adjacent to it (including diagonals). Lights on the edge of the grid might have fewer than eight neighbors; the missing ones always count as "off".
For example, in a simplified 6x6 grid, the light marked A has the neighbors numbered 1 through 8, and the light marked B, which is on an edge, only has the neighbors marked 1 through 5:
1B5...
234...
......
..123.
..8A4.
..765.
The state a light should have next is based on its current state (on or off) plus the number of neighbors that are on:
- A light which is on stays on when
2or3neighbors are on, and turns off otherwise. - A light which is off turns on if exactly
3neighbors are on, and stays off otherwise.
All of the lights update simultaneously; they all consider the same current state before moving to the next.
Here's a few steps from an example configuration of another 6x6 grid:
Initial state:
.#.#.#
...##.
#....#
..#...
#.#..#
####..
After 1 step:
..##..
..##.#
...##.
......
#.....
#.##..
After 2 steps:
..###.
......
..###.
......
.#....
.#....
After 3 steps:
...#..
......
...#..
..##..
......
......
After 4 steps:
......
......
..##..
..##..
......
......
After 4 steps, this example has four lights on.
In your grid of 100x100 lights, given your initial configuration, how many lights are on after 100 steps?
To begin, get your puzzle input.
--- Part Two ---
You flip the instructions over; Santa goes on to point out that this is all just an implementation of Conway's Game of Life. At least, it was, until you notice that something's wrong with the grid of lights you bought: four lights, one in each corner, are stuck on and can't be turned off. The example above will actually run like this:
Initial state:
##.#.#
...##.
#....#
..#...
#.#..#
####.#
After 1 step:
#.##.#
####.#
...##.
......
#...#.
#.####
After 2 steps:
#..#.#
#....#
.#.##.
...##.
.#..##
##.###
After 3 steps:
#...##
####.#
..##.#
......
##....
####.#
After 4 steps:
#.####
#....#
...#..
.##...
#.....
#.#..#
After 5 steps:
##.###
.##..#
.##...
.##...
#.#...
##...#
After 5 steps, this example now has 17 lights on.
In your grid of 100x100 lights, given your initial configuration, but with the four corners always in the on state, how many lights are on after 100 steps?
Although it hasn't changed, you can still get your puzzle input.
Input
input = Kino.Input.textarea("Please paste your input file:")input = input |> Kino.Input.read()"#...##......#......##.##..#...##......##.#.#.###.#.#..#..#......####..#......###.#.#....#..##..###..\n####..#.#...#....#.#####.##.##.#..#.......#....#.##...###.###..#.#.#........#..#.#.##...##..#.####.#\n...#..##...#.#.###.#.###..#.##.####.###...#...........#.###..##.#.##.#.###...#.#..###....#.###.#..#.\n.#...##...####.#..#.....#..#...#.#.##...#...##..#.#.###....#..###.....##..#.###..###.....##..###...#\n..##.#####....##..#.#..##.##..######...#..###.######.....#..##...#.#..##..##..#..#..#..##.#.#.#.#...\n.###.###.###...##...##..###..##.###.#.....##..##.#.#########...##..##.#..##.#..##..####..#.#.#.#####\n#.#####..###.###.##.##.#...#.#.#.#..#.###...#..##.###.#...####.#..#.#.....###..#..####..#.#.#...##..\n....#...##.....#....####.##.#.###..#.#.##..#.#...##.###.###..#.##..#.#.##..##..#.##.###..#.#.###.###\n##.##...#.##...#.#..#.#..#...###...###.#..#..#.#####..###.#......#.....###.#####.#.#..#.#.#.##..#.#.\n#.#..#.....#.....##.#..##...###..##...##...###.#.###.#..#.#.###...##..##..#.###...#.#######.#...#.#.\n#.#.....####.#..#.##...#.##....#####.###.#.....#####....###..#........##..####...#...#.###....#..###\n##.#.##..#.#.##.#.....##.#.....###.####.#..######.....####.#.#..##.#.##...#..#.#.....#.####.#.......\n#..#..#.#..#.######.##..##.####.....##.#.##.#.######..#.#....#.#...#.#..#..#.#.###.#..#.#.#..#...###\n####..####.#.#.###.....#.#.#.##..#.##.##.##.#..##..##.#.##.....#.#..#.####.....###.#..#.####.#.#..##\n###.##..##.#.##..#..##...#.#####.##.#....##.####.#.##....#..###.#.#.##...#.....#.#.#.#.#..##.#.#..#.\n......#..####...##.##...#.##.##...##..#..##.###..#...#..##...#.#....###.####...#.##.###.#.##.####.##\n..#...#####.#.#..#.##....#..#...#..####.....###...##.###....#..#.###...#........#.#.##..#..#.#.....#\n#######.#.#.###.###..######.##..#####.##.###.###....####.#..##.##...###.#..############.#.##....##.#\n#.#...##.###.#.###..#.#.#.#.#.#..##..####.#..##.....#.##..#.##...##.#..##..#.#.#....##....##.#..#.#.\n..#.#.####.....###..#######.#.#.#.#...##.#####.....##...##...##.###..######.###..#...####.#..###.###\n.#.##....#.#.##..##.#.##.##..######...#.....#..#.#.#.#.....#.#..##.#.#.......#######....#.......#...\n..###.##.##..##....#.###...#.....##..##......###...##..###.##...##.###.#.#.#.###.###.#.#...###..#...\n.##.#.#...#...##.#.#...#..#..#.#...##.#.##...##..#....#.#..##.#..#.#..#.#.....#..#.#...#######.#.##.\n...####....#.###.#..###..##...##..#.#.#.###...#..##.##.##..##.#...#..#.##.....#.#........#..#.#.####\n.....##..###...#....#.#.#.#...###.###...#.#...#.#.####....#..####...###..#..######..##.##..###.#####\n#####.##..#....###.###....##.....#.#..#....#.#####.##.#.####.#.##...#..###...###..##...#.###.#####..\n###.##..........########.######....####.###.#..##...#.##.####.#.....##..#####..###...#####.....#.#.#\n##..#####.##.#.#####.#.##.##..#.##....########.#####.#...#.###.##...#.###.#.#..#....##.#..#...#.#.#.\n.##.#....#..#...#..#####..#..##.#......#..#....########...#..#...#.....####.#...##...#.###.#.#..##.#\n.##.##.#.##.#.##...#.#.#..##.##.###.#..##..#...###.##.###.#####.#.###..#..###.#...#.###.#...#..#.#.#\n.#..#..#.#..#..###..#....###.####.##.#.###.#.##.###.#.##.###.###...###...###.#...####...#.##.##.#.#.\n###..##...###...#..##.#..#.#...##....###.##.##..#####....###..#..#....#..###.###.#...#.##...#.#.#..#\n#....#.......##.....#.##...#..#.###.#.##..##..#.##..#.###..##.##...#####.#..#####..#####..#####....#\n.####.####....###..###.#.##.####.##.#...####.#.###.#.....#...####..#####.###..#.#.###.##.##...##..#.\n####..##...##.########...##..###..#..###.##.#.#.#........#.#####.#...#.###.####.#..####..#.#.#....##\n###.#..#...###.#..#..#.###...##..###.##.#.#...#..#...####..##....#.#..#..##.#.#...#####.###.#..#.#.#\n...##....#.###.#.#..##...##.###.#..#..#......#...#.#..####.#.##..######.####.#...#..#..#..##.#.#.##.\n##.####.#...#..#.#.##..##.#.#.###..##...####......#..######.#......#.##.#....##...###.#.#..#......##\n#.....#...#######.##.#..#.#...###.#..#.####....#.#.##.#.##...###..#...#.###.##..#.###..#.##...#####.\n#####.##...#..#.#.#.......#.##..#####..#####...###..##.#.#..###.#.#####.####..#.#..##...#.##...#.###\n.##.#..#######.###.#.####.....##...#.##.#.#..#...##....#" <> ...
Solution
defmodule Day18 do
defdelegate parse(input), to: __MODULE__.Input
def part1(input, steps \\ 100) do
1..steps
|> Enum.reduce(parse(input), fn _, grid -> next_step(grid) end)
|> Enum.count(fn {_, v} -> v == "#" end)
end
def part2(input, steps \\ 100) do
grid = parse(input)
max_x = grid |> Map.keys() |> Enum.map(&elem(&1, 0)) |> Enum.max()
max_y = grid |> Map.keys() |> Enum.map(&elem(&1, 1)) |> Enum.max()
always_on = [{0, 0}, {0, max_y}, {max_x, 0}, {max_x, max_y}]
grid = Enum.reduce(always_on, grid, fn xy, acc -> Map.put(acc, xy, "#") end)
1..steps
|> Enum.reduce(grid, fn _, acc -> next_step(acc, always_on) end)
|> Enum.count(fn {_, v} -> v == "#" end)
end
defp next_step(grid, always_on \\ []) do
grid
|> Enum.reduce(grid, fn
{xy, "#"}, acc ->
if xy in always_on do
acc
else
case neighbors_on_count(grid, xy) do
2 -> acc
3 -> acc
_ -> Map.put(acc, xy, ".")
end
end
{xy, "."}, acc ->
case neighbors_on_count(grid, xy) do
3 -> Map.put(acc, xy, "#")
_ -> acc
end
end)
end
defp neighbors_on_count(grid, xy) do
neighbor_xys(xy)
|> Enum.map(&grid[&1])
|> Enum.count(&(&1 == "#"))
end
defp neighbor_xys({x, y}) do
[
{x - 1, y - 1},
{x, y - 1},
{x + 1, y - 1},
{x + 1, y},
{x + 1, y + 1},
{x, y + 1},
{x - 1, y + 1},
{x - 1, y}
]
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.split("\n", trim: true)
|> parse()
end
def parse(input) when is_list(input) do
input
|> Enum.with_index()
|> Enum.reduce(%{}, &parse_line/2)
end
def parse_line({line, y}, grid) do
line
|> String.split("", trim: true)
|> Enum.with_index()
|> Enum.reduce(grid, fn {c, x}, acc ->
Map.put(acc, {x, y}, c)
end)
end
end
end{:module, Day18, <<70, 79, 82, 49, 0, 0, 21, ...>>,
{:module, Day18.Input, <<70, 79, 82, ...>>, {:parse_line, 2}}}
In your grid of 100x100 lights, given your initial configuration, how many lights are on after 100 steps?
Your puzzle answer was 814.
Day18.part1(input)814
In your grid of 100x100 lights, given your initial configuration, but with the four corners always in the on state, how many lights are on after 100 steps?
Your puzzle answer was 924.
Day18.part2(input)924
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should return to your Advent calendar and try another puzzle.
If you still want to see it, you can get your puzzle input.
Tests
ExUnit.start(auto_run: false)
defmodule Day18Test do
use ExUnit.Case, async: false
setup_all do
[
input: ".#.#.#\n...##.\n#....#\n..#...\n#.#..#\n####.."
]
end
describe "part1/1" do
test "returns expected value", %{input: input} do
assert Day18.part1(input, 4) == 4
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day18.part2(input, 5) == 17
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 137484
%{excluded: 0, failures: 0, skipped: 0, total: 2}
Benchmarking
# https://github.com/bencheeorg/benchee
Benchee.run(
%{
"Part 1" => fn -> Day18.part1(input) end,
"Part 2" => fn -> Day18.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nilOperating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 16 GB
Elixir 1.14.2
Erlang 25.1.2
Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 2 s
reduction time: 2 s
parallel: 1
inputs: none specified
Estimated total run time: 22 s
Benchmarking Part 1 ...
Benchmarking Part 2 ...
Name ips average deviation median 99th %
Part 1 1.27 788.09 ms ±1.24% 786.32 ms 809.75 ms
Part 2 1.24 805.25 ms ±2.62% 794.44 ms 849.43 ms
Comparison:
Part 1 1.27
Part 2 1.24 - 1.02x slower +17.16 ms
Memory usage statistics:
Name average deviation median 99th %
Part 1 697.86 MB ±0.00% 697.86 MB 697.86 MB
Part 2 700.59 MB ±0.00% 700.58 MB 700.61 MB
Comparison:
Part 1 697.86 MB
Part 2 700.59 MB - 1.00x memory usage +2.73 MB
Reduction count statistics:
Name average deviation median 99th %
Part 1 108.09 M ±0.00% 108.09 M 108.09 M
Part 2 108.20 M ±0.00% 108.20 M 108.20 M
Comparison:
Part 1 108.09 M
Part 2 108.20 M - 1.00x reduction count +0.114 M
nil
