Day 3 - Advent of Code 2020
# Mix.install([:kino, :benchee])Links
Prompt
--- Day 3: Toboggan Trajectory ---
With the toboggan login problems resolved, you set off toward the airport. While travel by toboggan might be easy, it's certainly not safe: there's very minimal steering and the area is covered in trees. You'll need to see which angles will take you near the fewest trees.
Due to the local geology, trees in this area only grow on exact integer coordinates in a grid. You make a map (your puzzle input) of the open squares (.) and trees (#) you can see. For example:
..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#
These aren't the only trees, though; due to something you read about once involving arboreal genetics and biome stability, the same pattern repeats to the right many times:
..##.........##.........##.........##.........##.........##....... --->
#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....#..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..#...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.##.......#.##.......#.##.......#.##.......#.##..... --->
.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........#.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...##....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.#.#..#...#.# --->
You start on the open square (.) in the top-left corner and need to reach the bottom (below the bottom-most row on your map).
The toboggan can only follow a few specific slopes (you opted for a cheaper model that prefers rational numbers); start by counting all the trees you would encounter for the slope right 3, down 1:
From your starting position at the top-left, check the position that is right 3 and down 1. Then, check the position that is right 3 and down 1 from there, and so on until you go past the bottom of the map.
The locations you'd check in the above example are marked here with O where there was an open square and X where there was a tree:
..##.........##.........##.........##.........##.........##....... --->
#..O#...#..#...#...#..#...#...#..#...#...#..#...#...#..#...#...#..
.#....X..#..#....#..#..#....#..#..#....#..#..#....#..#..#....#..#.
..#.#...#O#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#..#.#...#.#
.#...##..#..X...##..#..#...##..#..#...##..#..#...##..#..#...##..#.
..#.##.......#.X#.......#.##.......#.##.......#.##.......#.##..... --->
.#.#.#....#.#.#.#.O..#.#.#.#....#.#.#.#....#.#.#.#....#.#.#.#....#
.#........#.#........X.#........#.#........#.#........#.#........#
#.##...#...#.##...#...#.X#...#...#.##...#...#.##...#...#.##...#...
#...##....##...##....##...#X....##...##....##...##....##...##....#
.#..#...#.#.#..#...#.#.#..#...X.#.#..#...#.#.#..#...#.#.#..#...#.# --->
In this example, traversing the map using this slope would cause you to encounter 7 trees.
Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?
To begin, get your puzzle input.
--- Part Two ---
Time to check the rest of the slopes - you need to minimize the probability of a sudden arboreal stop, after all.
Determine the number of trees you would encounter if, for each of the following slopes, you start at the top-left corner and traverse the map all the way to the bottom:
- Right 1, down 1.
- Right 3, down 1. (This is the slope you already checked.)
- Right 5, down 1.
- Right 7, down 1.
- Right 1, down 2.
In the above example, these slopes would find 2, 7, 3, 4, and 2 tree(s) respectively; multiplied together, these produce the answer 336.
What do you get if you multiply together the number of trees encountered on each of the listed slopes?
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()
input = AdventOfCode.Input.get!("3", "2020")".#...#.......#...#...#.#.#.....\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......##..#.....##..#...####...\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.....#....#..#..##.....#.......\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..#....##....#.....#...........\n..#.....#......#..#.###.##....#\n.#.......#...........#...#....#\n#............##...#...#.....#..\n##...#.....#.........##...##...\n...#...........#....##.........\n#.##..#..........##..#......#..\n.......#.#.......##.......#....\n" <> ...
Solution
defmodule Day03 do
alias AdventOfCode.CharGrid
def part1(input) do
grid = CharGrid.from_input(input)
count_trees(grid, {0, 0}, {3, 1})
end
def part2(input) do
grid = CharGrid.from_input(input)
[
{1, 1},
{3, 1},
{5, 1},
{7, 1},
{1, 2}
]
|> Enum.map(&count_trees(grid, {0, 0}, &1))
|> Enum.product()
end
defp count_trees(grid, xy, rd, count \\ 0)
defp count_trees(grid, {_, y}, {_r, _d}, count) when y >= grid.height, do: count
defp count_trees(grid, {x, y}, {r, d}, count) do
incr =
case CharGrid.at(grid, {rem(x, grid.width), y}) do
?. -> 0
?# -> 1
end
count_trees(grid, {x + r, y + d}, {r, d}, count + incr)
end
end{:module, Day03, <<70, 79, 82, 49, 0, 0, 11, ...>>, {:count_trees, 4}}
Starting at the top-left corner of your map and following a slope of right 3 and down 1, how many trees would you encounter?
Your puzzle answer was 272.
Day03.part1(input)272
What do you get if you multiply together the number of trees encountered on each of the listed slopes?
Your puzzle answer was 3898725600.
Day03.part2(input)3898725600
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 Day03Test do
use ExUnit.Case, async: false
setup_all do
[
input:
"..##.......\n#...#...#..\n.#....#..#.\n..#.#...#.#\n.#...##..#.\n..#.##.....\n.#.#.#....#\n.#........#\n#.##...#...\n#...##....#\n.#..#...#.#"
]
end
describe "part1/1" do
test "returns expected value", %{input: input} do
assert Day03.part1(input) == 7
end
end
describe "part2/1" do
test "returns expected value", %{input: input} do
assert Day03.part2(input) == 336
end
end
end
ExUnit.run()..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures
Randomized with seed 831415
%{total: 2, failures: 0, excluded: 0, skipped: 0}
Benchmarking
# https://github.com/bencheeorg/benchee
Benchee.run(
%{
"Part 1" => fn -> Day03.part1(input) end,
"Part 2" => fn -> Day03.part2(input) end
},
memory_time: 2,
reduction_time: 2
)
nilWarning: the benchmark Part 1 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
Warning: the benchmark Part 2 is using an evaluated function.
Evaluated functions perform slower than compiled functions.
You can move the Benchee caller to a function in a module and invoke `Mod.fun()` instead.
Alternatively, you can move the benchmark into a benchmark.exs file and run mix run benchmark.exs
Operating System: macOS
CPU Information: Apple M1 Pro
Number of Available Cores: 10
Available memory: 32 GB
Elixir 1.15.6
Erlang 26.1
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 652.47 1.53 ms ±9.19% 1.56 ms 1.83 ms
Part 2 628.03 1.59 ms ±9.24% 1.63 ms 1.88 ms
Comparison:
Part 1 652.47
Part 2 628.03 - 1.04x slower +0.0596 ms
Memory usage statistics:
Name Memory usage
Part 1 1.60 MB
Part 2 1.65 MB - 1.03x memory usage +0.0519 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name average deviation median 99th %
Part 1 86.32 K ±0.18% 86.30 K 86.79 K
Part 2 92.02 K ±0.18% 92.00 K 92.49 K
Comparison:
Part 1 86.30 K
Part 2 92.02 K - 1.07x reduction count +5.70 K
nil
