Day 1 - Advent of Code 2024

Mix.install([:kino, :benchee])

Links

• Advent of Code (AoC)
• AoC Puzzle Input
• tylerj GitHub - Livebook

Prompt

— Day 1: Historian Hysteria —

The Chief Historian is always present for the big Christmas sleigh launch, but nobody has seen him in months! Last anyone heard, he was visiting locations that are historically significant to the North Pole; a group of Senior Historians has asked you to accompany them as they check the places they think he was most likely to visit.

As each location is checked, they will mark it on their list with a star. They figure the Chief Historian must be in one of the first fifty places they’ll look, so in order to save Christmas, you need to help them get fifty stars on their list before Santa takes off on December 25th.

Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

You haven’t even left yet and the group of Elvish Senior Historians has already hit a problem: their list of locations to check is currently empty. Eventually, someone decides that the best place to check first would be the Chief Historian’s office.

Upon pouring into the office, everyone confirms that the Chief Historian is indeed nowhere to be found. Instead, the Elves discover an assortment of notes and lists of historically significant locations! This seems to be the planning the Chief Historian was doing before he left. Perhaps these notes can be used to determine which locations to search?

Throughout the Chief’s office, the historically significant locations are listed not by name but by a unique number called the location ID. To make sure they don’t miss anything, The Historians split into two groups, each searching the office and trying to create their own complete list of location IDs.

There’s just one problem: by holding the two lists up side by side (your puzzle input), it quickly becomes clear that the lists aren’t very similar. Maybe you can help The Historians reconcile their lists?

For example:

3   4
4   3
2   5
1   3
3   9
3   3

Maybe the lists are only off by a small amount! To find out, pair up the numbers and measure how far apart they are. Pair up the smallest number in the left list with the smallest number in the right list, then the second-smallest left number with the second-smallest right number, and so on.

Within each pair, figure out how far apart the two numbers are; you’ll need to add up all of those distances. For example, if you pair up a 3 from the left list with a 7 from the right list, the distance apart is 4; if you pair up a 9 with a 3, the distance apart is 6.

In the example list above, the pairs and distances would be as follows:

• The smallest number in the left list is 1, and the smallest number in the right list is 3. The distance between them is 2.
• The second-smallest number in the left list is 2, and the second-smallest number in the right list is another 3. The distance between them is 1.
• The third-smallest number in both lists is 3, so the distance between them is 0.
• The next numbers to pair up are 3 and 4, a distance of 1.
• The fifth-smallest numbers in each list are 3 and 5, a distance of 2.
• Finally, the largest number in the left list is 4, while the largest number in the right list is 9; these are a distance 5 apart. To find the total distance between the left list and the right list, add up the distances between all of the pairs you found. In the example above, this is 2 + 1 + 0 + 1 + 2 + 5, a total distance of 11!

Your actual left and right lists contain many location IDs. What is the total distance between your lists?

To begin, get your puzzle input.

Your puzzle answer was 1970720.

— Part Two —

Your analysis only confirmed what everyone feared: the two lists of location IDs are indeed very different.

Or are they?

The Historians can’t agree on which group made the mistakes or how to read most of the Chief’s handwriting, but in the commotion you notice an interesting detail: a lot of location IDs appear in both lists! Maybe the other numbers aren’t location IDs at all but rather misinterpreted handwriting.

This time, you’ll need to figure out exactly how often each number from the left list appears in the right list. Calculate a total similarity score by adding up each number in the left list after multiplying it by the number of times that number appears in the right list.

Here are the same example lists again:

3   4
4   3
2   5
1   3
3   9
3   3

For these example lists, here is the process of finding the similarity score:

• The first number in the left list is 3. It appears in the right list three times, so the similarity score increases by 3 * 3 = 9.
• The second number in the left list is 4. It appears in the right list once, so the similarity score increases by 4 * 1 = 4.
• The third number in the left list is 2. It does not appear in the right list, so the similarity score does not increase (2 * 0 = 0).
• The fourth number, 1, also does not appear in the right list.
• The fifth number, 3, appears in the right list three times; the similarity score increases by 9.
• The last number, 3, appears in the right list three times; the similarity score again increases by 9. So, for these example lists, the similarity score at the end of this process is 31 (9 + 4 + 0 + 0 + 9 + 9).

Once again consider your left and right lists. What is their similarity score?

Although it hasn’t changed, you can still get your puzzle input.

Your puzzle answer was 17191599.

Input

input = Kino.Input.textarea("Please paste your input file:")

input = input |> Kino.Input.read()

"88276   66757\n66898   13714\n58877   87487\n69396   12997\n53434   62485\n69841   67231\n51135   99904\n75350   18379\n87528   59461\n33533   35866\n88767   25688\n70018   18379\n25424   37382\n46726   68550\n41136   44070\n81001   57100\n48800   20883\n68425   87909\n32161   69003\n18867   53216\n58177   19563\n67114   46700\n48598   90768\n49215   39678\n50571   65700\n57798   56585\n87680   69003\n81941   15557\n25776   32379\n61540   58056\n30036   13872\n72011   69003\n74083   56426\n87228   81833\n49402   73309\n20185   37731\n79992   61292\n83744   53216\n51270   88596\n65194   46832\n83619   84894\n61729   48656\n22798   27189\n17489   88767\n72632   85830\n20376   74164\n14663   10793\n75764   18838\n42214   79141\n73812   70018\n77490   16156\n58694   13273\n84894   57554\n89172   61675\n26728   10793\n38031   20716\n42918   72362\n71012   67914\n54495   54567\n46702   63623\n43028   14772\n35521   30594\n67868   67268\n34274   24937\n20784   48924\n35595   84894\n34154   24579\n44840   59881\n36669   56576\n41986   66757\n46387   17065\n44020   21738\n84238   17801\n36022   30633\n71031   18379\n64368   17801\n10793   84894\n20169   34934\n18550   70811\n88728   62854\n66508   64049\n18159   54705\n39451   58284\n42664   38958\n23446   75653\n97584   43691\n78504   58006\n26535   53216\n15557   21045\n28271   47020\n36597   50514\n46447   13273\n95598   22815\n93731   81772\n32397   42899\n52807   58056\n26220   59055\n95837   54705\n67607   97159\n37466   45429\n43058   45549\n26473   38665\n68777   98333\n22436   91327\n88573   18379\n61259   13273\n38254   22391\n93975   44919\n57986   86639\n77318   62161\n84495   36775\n81381   69003\n57739   16156\n60598   40116\n33182   57284\n93710   40019\n37609   19836\n78984   38227\n22162   87784\n55715   79073\n63919   45370\n90630   87468\n25719   18379\n94542   80660\n46758   65583\n81729   67887\n38275   92261\n98915   65294\n56501   83143\n26391   18379\n20345   88767\n90235   72889\n76165   65757\n34771   17801\n11831   85257\n17735   15601\n82093   80861\n74646   34915\n18879   15331\n62123   90282\n76704   10793\n35340   46892\n17626   57504\n73828   23294\n60131   44363\n93584   10793\n62201   44764\n19005   87646\n35018   42747\n47795   36954\n41800   78433\n80773   85010\n80820   34934\n22857   81640\n37449   10995\n82183   24232\n45864   46505\n36815   48985\n54020   13273\n81545   88831\n62572   18336\n44708   64739\n66801   97842\n59501   12794\n67098   75382\n21266   53216\n58508   43409\n84719   20883\n45950   65647\n70627   47730\n94298   87646\n11607   88003\n99117   20883\n17953   13714\n31425   86162\n85902   88767\n88524   97877\n63952   35026\n19191   38958\n79802   15331\n57866   56895\n62302   46538\n78098   95481\n20698   43965\n84629   80543\n41677   21616\n27485   27525\n75935   45791\n31977   16820\n10336   78794\n38958   13714\n84834   61769\n96511   44057\n12736   28591\n89758   59184\n53646   54868\n15153   91337\n32060   34232\n27908   45791\n16393   78168\n25261   52734\n60760   38227\n25775   20883\n16904   29227\n62346   53147\n47080   42526\n93255   70760\n89013   13714\n43284   69177\n65144   93383\n48707   87646\n57437   58056\n11138   75483\n24856   38227\n29683   60040\n98693   55209\n77263   69834\n30391   66757\n33113   47463\n65000   34934\n31396   62769\n46020   54868\n99476   85419\n11386   68175\n13977   58056\n86041   38227\n62608   84894\n80461   68879\n42619   35285\n18929   71805\n91858   28002\n19069   58965\n61625   39986\n13273   26273\n58290   17801\n31333   73406\n95844   13714\n29334   65412\n24222   38958\n76497   34934\n47981   89514\n81211   34934\n43664   54868\n74273   56326\n45398   62234\n98433   24775\n26920   45683\n27584   53650\n63319   34934\n54868   94619\n43366   21445\n71718   67268\n83801   64077\n61400   87482\n61109   73784\n95577   95495\n27710   62470\n68618   60416\n14815   48005\n99140   22460\n19676   93554\n66372   67268\n44319   54705\n73785   38227\n67363   93256\n37981   18379\n64109   73147\n38227   20524\n50207   32773\n15814   34934\n35531   51496\n87819   40501\n77349   59926\n53298   53216\n93233   89273\n39520   53090\n12419   18379\n60177   30633\n75199   20883\n56305   61815\n32449   20883\n34934   92261\n27633   70811\n41294   76937\n34059   83935\n55758   53216\n95114   20883\n73343   17801\n58117   34990\n10949   96230\n50109   62234\n83134   69003\n42282   " <> ...

Solution

defmodule Day01 do
  defdelegate parse(input), to: __MODULE__.Input

  def part1(input) do
    input
    |> parse()
    |> Enum.map(&Enum.sort/1)
    |> Enum.zip()
    |> Enum.map(fn {a, b} -> abs(a - b) end)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> parse()
    |> then(fn [left, right] ->
      count_in_right = fn x -> Enum.count(right, &(&1 == x)) end

      Enum.reduce(left, 0, fn x, sum ->
        sum + x * count_in_right.(x)
      end)
    end)
  end

  defmodule Input do
    def parse(input) when is_binary(input) do
      input
      |> String.splitter("\n", trim: true)
      |> parse()
    end

    def parse(input) do
      input
      |> Stream.map(&parse_line/1)
      |> Stream.zip()
      |> Enum.map(&Tuple.to_list/1)
    end

    def parse_line(line) do
      line
      |> String.splitter(" ", trim: true)
      |> Enum.map(&String.to_integer/1)
    end
  end
end

{:module, Day01, <<70, 79, 82, 49, 0, 0, 11, ...>>,
 {:module, Day01.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}

Your actual left and right lists contain many location IDs. What is the total distance between your lists?

Your puzzle answer was 1970720.

Day01.part1(input)

1970720

Once again consider your left and right lists. What is their similarity score?

Your puzzle answer was 17191599.

Day01.part2(input)

17191599

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 Day01Test do
  use ExUnit.Case, async: false

  setup_all do
    [
      input: "3   4\n4   3\n2   5\n1   3\n3   9\n3   3"
    ]
  end

  describe "part1/1" do
    test "returns expected value", %{input: input} do
      assert Day01.part1(input) == 11
    end
  end

  describe "part2/1" do
    test "returns expected value", %{input: input} do
      assert Day01.part2(input) == 31
    end
  end
end

ExUnit.run()

..
Finished in 0.00 seconds (0.00s async, 0.00s sync)
2 tests, 0 failures

Randomized with seed 669974

%{total: 2, failures: 0, excluded: 0, skipped: 0}

Benchmarking

defmodule Benchmarking do
  # https://github.com/bencheeorg/benchee
  def run(input) do
    Benchee.run(
      %{
        "Part 1" => fn -> Day01.part1(input) end,
        "Part 2" => fn -> Day01.part2(input) end
      },
      memory_time: 2,
      reduction_time: 2
    )

    nil
  end
end

{:module, Benchmarking, <<70, 79, 82, 49, 0, 0, 7, ...>>, {:run, 1}}

Benchmarking.run(input)

Operating System: macOS
CPU Information: Apple M1
Number of Available Cores: 8
Available memory: 8 GB
Elixir 1.15.7
Erlang 26.1.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        1.10 K        0.91 ms    ±17.02%        0.89 ms        1.05 ms
Part 2       0.103 K        9.67 ms    ±25.98%        8.62 ms       15.48 ms

Comparison: 
Part 1        1.10 K
Part 2       0.103 K - 10.66x slower +8.76 ms

Memory usage statistics:

Name           average  deviation         median         99th %
Part 1         2.22 MB     ±0.00%        2.22 MB        2.22 MB
Part 2         1.85 MB     ±0.00%        1.85 MB        1.85 MB

Comparison: 
Part 1         2.22 MB
Part 2         1.85 MB - 0.84x memory usage -0.36359 MB

Reduction count statistics:

Name   Reduction count
Part 1         0.143 M
Part 2          5.12 M - 35.72x reduction count +4.97 M

**All measurements for reduction count were the same**

nil