Day 14 - Advent of Code 2015
Mix.install([:kino, :benchee]):okLinks
Prompt
— Day 14: Reindeer Olympics —
This year is the Reindeer Olympics! Reindeer can fly at high speeds, but must rest occasionally to recover their energy. Santa would like to know which of his reindeer is fastest, and so he has them race.
Reindeer can only either be flying (always at their top speed) or resting (not moving at all), and always spend whole seconds in either state.
For example, suppose you have the following Reindeer:
- Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.
- Dancer can fly 16 km/s for 11 seconds, but then must rest for 162 seconds.
After one second, Comet has gone 14 km, while Dancer has gone 16 km. After ten seconds, Comet has gone 140 km, while Dancer has gone 160 km. On the eleventh second, Comet begins resting (staying at 140 km), and Dancer continues on for a total distance of 176 km. On the 12th second, both reindeer are resting. They continue to rest until the 138th second, when Comet flies for another ten seconds. On the 174th second, Dancer flies for another 11 seconds.
In this example, after the 1000th second, both reindeer are resting, and Comet is in the lead at 1120 km (poor Dancer has only gotten 1056 km by that point). So, in this situation, Comet would win (if the race ended at 1000 seconds).
Given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, what distance has the winning reindeer traveled?
To begin, get your puzzle input.
— Part Two —
Seeing how reindeer move in bursts, Santa decides he’s not pleased with the old scoring system.
Instead, at the end of each second, he awards one point to the reindeer currently in the lead. (If there are multiple reindeer tied for the lead, they each get one point.) He keeps the traditional 2503 second time limit, of course, as doing otherwise would be entirely ridiculous.
Given the example reindeer from above, after the first second, Dancer is in the lead and gets one point. He stays in the lead until several seconds into Comet’s second burst: after the 140th second, Comet pulls into the lead and gets his first point. Of course, since Dancer had been in the lead for the 139 seconds before that, he has accumulated 139 points by the 140th second.
After the 1000th second, Dancer has accumulated 689 points, while poor Comet, our old champion, only has 312. So, with the new scoring system, Dancer would win (if the race ended at 1000 seconds).
Again given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, how many points does the winning reindeer have?
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()"Rudolph can fly 22 km/s for 8 seconds, but then must rest for 165 seconds.\nCupid can fly 8 km/s for 17 seconds, but then must rest for 114 seconds.\nPrancer can fly 18 km/s for 6 seconds, but then must rest for 103 seconds.\nDonner can fly 25 km/s for 6 seconds, but then must rest for 145 seconds.\nDasher can fly 11 km/s for 12 seconds, but then must rest for 125 seconds.\nComet can fly 21 km/s for 6 seconds, but then must rest for 121 seconds.\nBlitzen can fly 18 km/s for 3 seconds, but then must rest for 50 seconds.\nVixen can fly 20 km/s for 4 seconds, but then must rest for 75 seconds.\nDancer can fly 7 km/s for 20 seconds, but then must rest for 119 seconds."Solution
defmodule Day14 do
defdelegate parse(input), to: __MODULE__.Input
@total_time 2503
def part1(input) do
input
|> parse()
|> Enum.map(&calc_distance(&1, 0, @total_time))
|> Enum.max_by(&elem(&1, 1))
|> elem(1)
end
def part2(input) do
normalized_input =
input
|> parse()
|> Enum.map(fn {n, s, t, r} ->
{0, 0, n, s, t, r, t, r}
end)
Enum.reduce(
1..@total_time,
normalized_input,
fn _, i -> move_one_second(i) end
)
|> Enum.map(&elem(&1, 0))
|> Enum.max()
end
defp move_one_second(list) when is_list(list) do
new_list = Enum.map(list, &move_one_second/1)
lead_distance = new_list |> Enum.map(&elem(&1, 1)) |> Enum.max()
Enum.map(new_list, &add_point_if_leader(&1, lead_distance))
end
# start flying again
defp move_one_second({p, d, n, s, t, r, 0, 0}),
do: {p, d + s, n, s, t, r, t - 1, r}
# rest
defp move_one_second({p, d, n, s, t, r, 0, rr}),
do: {p, d, n, s, t, r, 0, rr - 1}
# fly
defp move_one_second({p, d, n, s, t, r, tr, rr}),
do: {p, d + s, n, s, t, r, tr - 1, rr}
defp add_point_if_leader({p, d, n, s, t, r, tr, rr}, d),
do: {p + 1, d, n, s, t, r, tr, rr}
defp add_point_if_leader(reindeer_tuple, _),
do: reindeer_tuple
defp calc_distance({name, _, _, _}, distance, seconds) when seconds <= 0,
do: {name, distance}
defp calc_distance({n, s, t, r}, d, seconds) do
calc_distance(
{n, s, t, r},
d + s * min(t, seconds),
seconds - t - r
)
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.split("\n")
|> parse()
end
def parse(input) when is_list(input) do
Stream.map(input, &parse_line/1)
end
def parse_line(line) do
speeds =
Regex.scan(~r{\d+}, line, capture: :first)
|> List.flatten()
|> Enum.map(&String.to_integer/1)
name = String.split(line) |> List.first()
List.to_tuple([name | speeds])
end
end
end{:module, Day14, <<70, 79, 82, 49, 0, 0, 18, ...>>,
{:module, Day14.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}
Given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, what distance has the winning reindeer traveled?
Your puzzle answer was 2696.
Day14.part1(input)2696Again given the descriptions of each reindeer (in your puzzle input), after exactly 2503 seconds, how many points does the winning reindeer have?
Your puzzle answer was 1084.
Day14.part2(input)1084Both 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.
Benchmarking
# https://github.com/bencheeorg/benchee
Benchee.run(
%{
"Part 1" => fn -> Day14.part1(input) end,
"Part 2" => fn -> Day14.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 13.28 K 75.30 μs ±3.54% 74.75 μs 83.67 μs
Part 2 1.68 K 594.57 μs ±3.46% 590.12 μs 669.58 μs
Comparison:
Part 1 13.28 K
Part 2 1.68 K - 7.90x slower +519.27 μs
Memory usage statistics:
Name Memory usage
Part 1 0.0176 MB
Part 2 3.08 MB - 174.38x memory usage +3.06 MB
**All measurements for memory usage were the same**
Reduction count statistics:
Name Reduction count
Part 1 2.22 K
Part 2 356.84 K - 160.96x reduction count +354.63 K
**All measurements for reduction count were the same**nil
