jzimbel's recent activity

Comment on Day 9: Movie Theater in ~comp.advent_of_code
jzimbel
3 hours, 11 minutes ago
Link Parent
Yeah, I was worried about this and a few other possible pitfalls while working on my solution. I spent a substantial amount of time writing checks to confirm all of the following: perimeter does...
Yeah, I was worried about this and a few other possible pitfalls while working on my solution.

I spent a substantial amount of time writing checks to confirm all of the following:
- perimeter does not cross itself
- every red tile is a corner of the shape--no 3 consecutive red tiles are collinear
- input walks the perimeter in clockwise direction ^{(this didn't end up mattering all that much)}
- perimeter never touches itself--every perimeter tile is adjacent to exactly 2 other perimeter tiles
1 vote
Comment on Day 5: Cafeteria in ~comp.advent_of_code
jzimbel
4 days, 21 hours ago
Link Parent
Oh wow, I did not realize in (which is just a macro that compiles to an Enum.member?/2 call, I believe) had that much overhead for ranges! If I change the anonymous fn passed to Enum.any?/2 in my...
Oh wow, I did not realize in (which is just a macro that compiles to an Enum.member?/2 call, I believe) had that much overhead for ranges!

If I change the anonymous fn passed to Enum.any?/2 in my part 1 solution to this:
```
&(id >= &1.first and id <= &1.last)
```
it has the exact same performance as yours.

Seems like the generalized logic for ranges with steps other than 1 slows things down a lot. (There's also some overhead from dispatching via the Enumerable protocol.)

I wonder why they don't just add a separate clause with the faster logic for the most commonly used step size of 1.

Re: limited type options, OOP concept relations

Yeah, the main composite types available in elixir are much simpler than what you can cook up in most OOP languages. There are also structs, but they're basically just maps with well-defined keys.

The limited inventory of core types is partly due to how deeply pattern matching is baked into the language and even the BEAM VM. Simple types allow for powerful, fast pattern matching.

Also related: a big part of Elixir and the larger OTP ecosystem, which you unfortunately won't get much practice with on AoC puzzles, is stateful message-passing processes like Agents and GenServers. These are conceptually analogous to objects: they bundle some well-defined data structure with functions that act on it and a public/private interface. The big difference is that they behave more like mini-servers internal to your application, running receive-act-respond loops, with strong concurrency guarantees.
1 vote

Comment on Day 5: Cafeteria in ~comp.advent_of_code

jzimbel

5 days, 20 hours ago

Link

Elixir Both parts I figured it would help to merge overlapping ranges for part 1, and it turned out to be necessary for part 2. I went a little overboard trying to squeeze stuff onto single lines,...

Elixir

Both parts

I figured it would help to merge overlapping ranges for part 1, and it turned out to be necessary for part 2.

I went a little overboard trying to squeeze stuff onto single lines, my code was more legible earlier. Ah well.

defmodule AdventOfCode.Solution.Year2025.Day05 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    [ranges, ids] = String.split(input, "\n\n")
    {parse_and_consolidate_ranges(ranges), parse_ids(ids)}
  end

  def part1({ranges, ids}), do: Enum.count(ids, fn id -> Enum.any?(ranges, &(id in &1)) end)
  def part2({ranges, _ids}), do: Enum.sum_by(ranges, &Range.size/1)

  defp consolidate(ranges) do
    [hd_range | ranges] = Enum.sort_by(ranges, & &1.first)

    Enum.chunk_while(
      ranges,
      hd_range,
      fn _..b2//1 = r2, a1..b1//1 = r1 ->
        if Range.disjoint?(r1, r2), do: {:cont, r1, r2}, else: {:cont, a1..max(b1, b2)//1}
      end,
      fn final_range -> {:cont, final_range, nil} end
    )
  end

  defp parse_and_consolidate_ranges(str) do
    str
    |> String.split()
    |> Enum.map(fn line ->
      [first, last] = String.split(line, "-")
      String.to_integer(first)..String.to_integer(last)//1
    end)
    |> consolidate()
  end

  defp parse_ids(str) do
    str
    |> String.split()
    |> Enum.map(&String.to_integer/1)
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Part 2     1401.14 K        0.71 μs   ±888.65%        0.71 μs        0.83 μs
Parse         8.53 K      117.22 μs     ±4.82%      118.33 μs      131.04 μs
Part 1        1.05 K      956.85 μs     ±1.20%      956.63 μs      983.61 μs

3 votes

Comment on Day 4: Printing Department in ~comp.advent_of_code

jzimbel

6 days, 20 hours ago (edited 6 days, 6 hours ago)

Link

Elixir I've built up a pretty robust Grid module over the years—maybe concerningly robust given that it's used solely for a bunch of toy code puzzles—so today's solution was a quick one. No...

Elixir

I've built up a pretty robust Grid module over the years—maybe concerningly robust given that it's used solely for a bunch of toy code puzzles—so today's solution was a quick one.

No special optimizations, I just took the obvious approach.

Both parts

defmodule AdventOfCode.Solution.Year2025.Day04 do
  alias AdventOfCode.Grid, as: G

  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input), do: G.from_input(input)

  def part1(grid), do: map_size(forklift_cells(grid))

  def part2(grid) do
    grid
    |> Stream.unfold(&remove_forkliftable/1)
    |> Enum.sum()
  end

  defp forklift_cells(grid) do
    for {coords, ?@} <- grid, forkliftable?(coords, grid), into: %{}, do: {coords, ?.}
  end

  defp forkliftable?(coords, grid) do
    grid
    |> G.adjacent_values(coords)
    |> Enum.count(&(&1 == ?@))
    |> Kernel.<(4)
  end

  defp remove_forkliftable(grid) do
    removals = forklift_cells(grid)

    case map_size(removals) do
      # End the stream.
      0 -> nil
      n -> {n, G.replace(grid, removals)}
    end
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Parse         526.68        1.90 ms     ±1.87%        1.90 ms        1.97 ms
Part 1        159.39        6.27 ms     ±3.94%        6.27 ms        6.95 ms
Part 2          7.69      130.08 ms     ±0.99%      129.91 ms      134.38 ms

Bonus: Animated passes

I exported an image of the grid after each forklift pass and assembled a looping animation.

3 votes

Comment on Day 3: Lobby in ~comp.advent_of_code

jzimbel

December 3 (edited December 3)

Link

Elixir I'm including my original code for part 1 even though my part 2 solution can be used for both. Because I'm proud of my inscrutable recursive function 🥰 My general max_joltage/2 function...

Elixir

I'm including my original code for part 1 even though my part 2 solution can be used for both. Because I'm proud of my inscrutable recursive function 🥰

My general max_joltage/2 function implements what @Hvv describes better than I could in their "But can we do it faster?" box.
edit: Actually I think I went only halfway with the optimizations. I didn't do as much preprocessing as I could have! (And didn't keep the input rows as strings, and didn't do one of the skip-ahead optimizations)

Parse input

Note: ?<unicode codepoint> is a funky bit of built-in syntax that gives the integer value of a unicode codepoint. For basic ascii characters, it's equivalent to C's '<character>' syntax. For example, ?a == 97.

When the puzzle input string is a bunch of digit characters that need to be parsed into a list of integers, digit_char - ?0 is a little shortcut for parsing each one.

use AdventOfCode.Solution.SharedParse

@impl true
@spec parse(String.t()) :: [[0..9]]
def parse(input) do
  input
  |> String.split()
  |> Enum.map(&for(d <- String.to_charlist(&1), do: d - ?0))
end

Original part 1 solution

def part1(battery_banks) do
  Enum.sum_by(battery_banks, &max_joltage_p1/1)
end

defp max_joltage_p1(batteries, acc \\ {0, 0})

defp max_joltage_p1([], {tens, ones}), do: Integer.undigits([tens, ones])
defp max_joltage_p1([b], {tens, ones}) when b > ones, do: max_joltage_p1([], {tens, b})
defp max_joltage_p1([_b], acc), do: max_joltage_p1([], acc)
defp max_joltage_p1([b | bs], {tens, _ones}) when b > tens, do: max_joltage_p1(bs, {b, 0})
defp max_joltage_p1([b | bs], {tens, ones}) when b > ones, do: max_joltage_p1(bs, {tens, b})
defp max_joltage_p1([_b | bs], acc), do: max_joltage_p1(bs, acc)

General solution for both parts

def part1(battery_banks), do: Enum.sum_by(battery_banks, &max_joltage(&1, 2))
def part2(battery_banks), do: Enum.sum_by(battery_banks, &max_joltage(&1, 12))

defp max_joltage(batteries, num_to_activate) do
  bank_size = length(batteries)
  init_active_group = List.duplicate(0, num_to_activate)

  batteries
  # Annotate batteries with the earliest index they can occupy in the activated group
  |> Enum.with_index(fn b, i -> {b, max(num_to_activate + i - bank_size, 0)} end)
  |> Enum.reduce(init_active_group, &update_active_group/2)
  |> Integer.undigits()
end

defp update_active_group({b, min_i}, active_group) do
  {ineligible, eligible} = Enum.split(active_group, min_i)
  update_active_group(b, eligible, Enum.reverse(ineligible))
end

defp update_active_group(_b, [], acc), do: Enum.reverse(acc)

defp update_active_group(b, [active | actives], acc) when b > active,
  do: update_active_group(b, [], List.duplicate(0, length(actives)) ++ [b | acc])

defp update_active_group(b, [active | actives], acc),
  do: update_active_group(b, actives, [active | acc])

Benchmarks

(Using the general solution--which for part 1 is a few hundred μs slower than the bespoke solution)

Name             ips        average  deviation         median         99th %
Parse         4.18 K      239.18 μs     ±3.65%      235.08 μs      261.13 μs
Part 1        2.68 K      373.56 μs    ±14.17%      370.92 μs      408.97 μs
Part 2        0.84 K     1188.87 μs     ±1.98%     1190.63 μs     1230.33 μs

3 votes

Comment on Day 2: Gift Shop in ~comp.advent_of_code

jzimbel

December 2 (edited December 2)

Link

Elixir I did my best to optimize my part 1 solution by filtering out large chunks of the ID ranges that would not work. (hint: the ID needs to be able to split into two parts with equal numbers of...

Elixir

I did my best to optimize my part 1 solution by filtering out large chunks of the ID ranges that would not work. (hint: the ID needs to be able to split into two parts with equal numbers of digits.)

But none of that optimization really applies to part 2, so I did basically a brute-force approach for it. It took over a second to complete before I tweaked it to process all rows concurrently using Task.async_stream/3. Running concurrently, it takes about half a second.

Parsing the input

use AdventOfCode.Solution.SharedParse

@impl true
def parse(input) do
  input
  |> String.trim()
  |> String.split(",")
  |> Enum.map(&parse_range/1)
end

defp parse_range(str) do
  ~r/(\d+)-(\d+)/
  |> Regex.run(str, capture: :all_but_first)
  |> Enum.map(&String.to_integer/1)
  |> then(fn [first, last] -> first..last//1 end)
end

Part 1

import Integer, only: [is_odd: 1]

def part1(ranges) do
  ranges
  |> Task.async_stream(&(&1 |> invalid_ids_p1() |> Enum.sum()), ordered: false)
  |> Enum.sum_by(fn {:ok, sum} -> sum end)
end

defp invalid_ids_p1(range) do
  range = clamp_range(range)
  exponent = exponent_of_10(range.first)
  splitter = Integer.pow(10, div(exponent, 2) + 1)
  Stream.filter(range, &(div(&1, splitter) == rem(&1, splitter)))
end

# Shrinks the range so that it contains only numbers with even numbers of digits.
defp clamp_range(first..last//1) do
  clamp_up(first)..clamp_down(last)//1
end

# Note: In my input, none of the ranges are so large that they include numbers
# within multiple odd exponents of 10, e.g. 10-1000.
#
# So clamping the single range is enough, ranges never need to be split into
# multiple sub-ranges to remove even exponents of 10 in the middle.

defp clamp_up(n) do
  exponent = exponent_of_10(n)
  if is_odd(exponent), do: n, else: Integer.pow(10, exponent + 1)
end

defp clamp_down(n) do
  exponent = exponent_of_10(n)
  if is_odd(exponent), do: n, else: Integer.pow(10, exponent) - 1
end

defp exponent_of_10(n), do: floor(:math.log10(n))

Part 2

def part2(ranges) do
  ranges
  |> Task.async_stream(&(&1 |> invalid_ids_p2() |> Enum.sum()), ordered: false)
  |> Enum.sum_by(fn {:ok, sum} -> sum end)
end

defp invalid_ids_p2(range) do
  Stream.filter(range, &invalid_p2?/1)
end

defp invalid_p2?(n) do
  digits = Integer.digits(n)
  len = length(digits)

  # Generate chunk sizes to try splitting the digits up into
  1..div(len, 2)//1
  # Chunk size must divide the digits cleanly with no smaller leftover chunk at the end
  |> Stream.filter(&(div(len, &1) == len / &1))
  |> Enum.any?(fn chunk_size ->
    digits
    |> Enum.chunk_every(chunk_size)
    |> Enum.uniq()
    |> length()
    |> Kernel.==(1)
  end)
end

Benchmarks

Without concurrency:

Name             ips        average  deviation         median         99th %
Parse       32028.96      0.00003 s    ±23.95%      0.00003 s      0.00007 s
Part 1        118.94      0.00841 s     ±1.76%      0.00835 s      0.00875 s
Part 2          0.52         1.91 s     ±0.99%         1.92 s         1.92 s

With concurrency:

Name             ips        average  deviation         median         99th %
Parse       32601.48      0.0307 ms    ±21.58%      0.0284 ms      0.0701 ms
Part 1        331.88        3.01 ms     ±6.84%        3.02 ms        3.46 ms
Part 2          2.02      496.24 ms     ±1.39%      495.07 ms      510.70 ms

2 votes

Comment on Day 1: Secret Entrance in ~comp.advent_of_code
jzimbel
December 2
Link Parent
It's a fun language! It's the primary language I use at work as well, so if you have any questions I can probably answer them. (Do note that I don't really prioritize clarity or readability for a...

It's a fun language! It's the primary language I use at work as well, so if you have any questions I can probably answer them.

(Do note that I don't really prioritize clarity or readability for a lot of my AoC puzzle solutions, though. I sometimes go out of my way to solve the puzzles in weird unconventional ways.)

2 votes

Comment on Day 1: Secret Entrance in ~comp.advent_of_code

jzimbel

December 1 (edited December 2)

Link

Elixir If anyone is interested, I have a template repository that helps you set up an elixir project for Advent of Code puzzles with some nice conveniences. That’s what I’ll be using in all of my...

Elixir

If anyone is interested, I have a template repository that helps you set up an elixir project for Advent of Code puzzles with some nice conveniences. That’s what I’ll be using in all of my solutions.

I am so glad he’s shortened the event to 12 days, I always spend way too much time on these puzzles and end up neglecting more important things during an already busy holiday month…

Both parts

I wanted to find a cleaner (i.e. more math-based, less branching-logic-based) approach for counting the number of times a given rotation visited position 0, but this was the best I could come up with.

Summary of my approach: Build a list where each element is a map with :position and :zero_visits keys. Each map gives the position of the dial after one rotation specified by the input, as well as the number of times it moved to 0 on its way to that ending position. Use these computed states of the dial after each rotation to get the answers for both part 1 and part 2.

defmodule AdventOfCode.Solution.Year2025.Day01 do
  use AdventOfCode.Solution.SharedParse

  @start_position 50

  @impl true
  def parse(input) do
    input
    |> String.split()
    |> Enum.map(fn
      "L" <> digits -> -String.to_integer(digits)
      "R" <> digits -> String.to_integer(digits)
    end)
    |> Stream.scan(%{position: @start_position, zero_visits: 0}, &move/2)
    |> Enum.to_list()
  end

  def part1(movements), do: Enum.count(movements, &(&1.position == 0))
  def part2(movements), do: Enum.sum_by(movements, & &1.zero_visits)

  defp move(rotation, %{position: position}) do
    %{
      position: Integer.mod(position + rotation, 100),
      zero_visits: count_zero_visits(position, rotation)
    }
  end

  # Note: Input never contains "L0" or "R0"--magnitude of a rotation is always nonzero.
  defp count_zero_visits(position, rotation) when rotation > 0, do: zv(rotation, 100 - position)
  defp count_zero_visits(position, rotation) when rotation < 0, do: zv(abs(rotation), position)

  defp zv(rot_mag, _zero_dist = 0), do: div(rot_mag, 100)
  defp zv(rot_mag, zero_dist) when rot_mag >= zero_dist, do: 1 + zv(rot_mag - zero_dist, 0)
  defp zv(_rot_mag, _zero_dist), do: 0
end

Benchmarks

Since I put basically all the work in the shared parse function, "part 1" and "part 2" are simply the logic that sums up the results with one final pass through the list.

Name             ips        average  deviation         median         99th %
Part 2       93.12 K       10.74 μs    ±37.65%       10.63 μs       12.08 μs
Part 1       29.50 K       33.90 μs     ±4.94%       33.71 μs       36.13 μs
Parse         2.52 K      396.37 μs    ±30.97%      367.54 μs      546.53 μs

3 votes

Comment on Two signs that Democrats flipped Donald Trump supporters on Tuesday (gifted link) in ~society
jzimbel
November 7
Link Parent
Per tradition

Per tradition

1 vote
Comment on What are some interesting landmarks in your neck of the woods? in ~talk
jzimbel
October 16
Link
Taco bench. Hexagon house. Tree wizard. (Sadly, someone set him on fire a few years ago, but He Is Immortal.)

Taco bench.
Hexagon house.
Tree wizard. (Sadly, someone set him on fire a few years ago, but He Is Immortal.)

1 vote
Comment on iOS 26 is here in ~tech
jzimbel
September 17
Link Parent
Oh wow, that Finder window screenshot is egregious… I can almost sense the resentment coming through from whichever poor dev/design team was tasked with updating the Finder UI

Oh wow, that Finder window screenshot is egregious… I can almost sense the resentment coming through from whichever poor dev/design team was tasked with updating the Finder UI

8 votes
Comment on Norway's capital is known for its green policies and widespread adoption of electric vehicles. Why does the city still struggle with air pollution? in ~enviro
jzimbel
April 17
Link
Now I’m imagining pea-sized dust motes drifting through the air over Oslo (The article is off by a factor of 1000—PM10 is in micrometers, not millimeters)

In February, levels of PM10 pollution — from tiny but harmful airborne particles of less than 10 millimeters diameter

Now I’m imagining pea-sized dust motes drifting through the air over Oslo

(The article is off by a factor of 1000—PM10 is in micrometers, not millimeters)

15 votes
Comment on James Bond shocker! Amazon MGM Studios takes creative control of spy franchise as producers Michael G. Wilson and Barbara Broccoli step back. in ~movies
jzimbel
February 22
Link Parent
Along these same lines, I saw this very funny bluesky post yesterday.

Along these same lines, I saw this very funny bluesky post yesterday.

3 votes
Comment on Are modern iPhones unusable without a case? in ~comp
jzimbel
February 16
Link
As someone who does not use a case, there’s a reason why basically the only thing I check when deciding whether to buy a newer iPhone is the weight and dimensions. I won’t even consider it if it’s...

As someone who does not use a case, there’s a reason why basically the only thing I check when deciding whether to buy a newer iPhone is the weight and dimensions. I won’t even consider it if it’s any heavier or wider/taller than my current phone.

(I missed the boat on the 13 mini, sadly)

1 vote
Comment on What are your favourite things to mix with natural yogurt? in ~food
jzimbel
January 12
Link
For Greek yogurt, this dip you can make in about a half hour is absolutely delicious. Have made many times, goes great with pita (toasted or not), carrots, fennel, etc. Around my area, Fage Total...

For Greek yogurt, this dip you can make in about a half hour is absolutely delicious. Have made many times, goes great with pita (toasted or not), carrots, fennel, etc.

Around my area, Fage Total 5% milkfat is the best plain Greek yogurt for this recipe

Comment on Day 10: Hoof It in ~comp.advent_of_code

jzimbel

December 13, 2024

Link

I'd been avoiding this one because it seemed like it would be a cumbersome pathfinding problem, but it turned out to be... very easy? The only difference between part 1 and part 2 was whether to...

I'd been avoiding this one because it seemed like it would be a cumbersome pathfinding problem, but it turned out to be... very easy?

The only difference between part 1 and part 2 was whether to keep duplicates in my list of in-progress paths. Annoyingly, the for special form (aka comprehensions) has a weird limitation where its :uniq option only accepts boolean literals, so I had to conditionally filter to unique values outside of the comprehension.

Both parts (Elixir)

defmodule AdventOfCode.Solution.Year2024.Day10 do
  use AdventOfCode.Solution.SharedParse

  alias AdventOfCode.Grid, as: G

  @impl true
  def parse(input), do: G.from_input(input)

  def part1(grid), do: solve(grid, true)
  def part2(grid), do: solve(grid, false)

  defp solve(grid, uniq?) do
    for {point, ?0} <- grid, reduce: 0 do
      acc -> acc + count_trailheads([point], ?1, grid, uniq?)
    end
  end

  defp count_trailheads(points, ?9, grid, uniq?) do
    length(next(points, ?9, grid, uniq?))
  end

  defp count_trailheads([], target, _, _) when target < ?9, do: 0

  defp count_trailheads(points, target, grid, uniq?) do
    count_trailheads(next(points, target, grid, uniq?), target + 1, grid, uniq?)
  end

  defp next(points, target, grid, uniq?) do
    next_points =
      for point <- points,
          {p, ^target} <- G.adjacent_cells(grid, point, :cardinal) do
        p
      end

    if uniq?, do: Enum.uniq(next_points), else: next_points
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Parse         4.18 K      239.19 μs    ±10.26%      235.29 μs      318.13 μs
Part 1        1.01 K      991.95 μs     ±6.37%      964.33 μs     1198.67 μs
Part 2        0.84 K     1189.14 μs     ±6.19%     1161.58 μs     1395.33 μs

Comparison: 
Parse         4.18 K
Part 1        1.01 K - 4.15x slower +752.76 μs
Part 2        0.84 K - 4.97x slower +949.95 μs

1 vote

Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code

jzimbel

December 12, 2024

Link Parent

I realized keeping the stones as strings was a silly choice. After switching to integers, my solution is a bit more concise and also runs faster. Both parts, using integers instead of strings...

I realized keeping the stones as strings was a silly choice. After switching to integers, my solution is a bit more concise and also runs faster.

Both parts, using integers instead of strings

defmodule AdventOfCode.Solution.Year2024.Day11 do
  use AdventOfCode.Solution.SharedParse

  import Integer, only: [is_even: 1]

  @impl true
  def parse(input), do: input |> String.split() |> Enum.map(&String.to_integer/1)

  def part1(stones), do: solve(stones, 25)
  def part2(stones), do: solve(stones, 75)

  defp solve(stones, blinks) do
    stones
    |> collect()
    |> Stream.iterate(&blink/1)
    |> Enum.at(blinks)
    |> Enum.map(fn {_stone, n} -> n end)
    |> Enum.sum()
  end

  defp blink(stones, acc \\ [])

  defp blink([], acc), do: collect(acc)

  defp blink([{stone, n} | rest], acc) do
    acc =
      cond do
        stone == 0 ->
          [{1, n} | acc]

        is_even(digits = trunc(:math.log10(stone)) + 1) ->
          divisor = Integer.pow(10, div(digits, 2))
          [{rem(stone, divisor), n}, {div(stone, divisor), n} | acc]

        true ->
          [{stone * 2024, n} | acc]
      end

    blink(rest, acc)
  end

  defp collect([{_stone, _n} | _] = stones) do
    stones
    |> Enum.group_by(fn {stone, _n} -> stone end, fn {_stone, n} -> n end)
    |> Enum.map(fn {stone, ns} -> {stone, Enum.sum(ns)} end)
  end

  defp collect([_stone | _] = stones) do
    stones
    |> Enum.frequencies()
    |> Map.to_list()
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Parse       275.55 K        3.63 μs   ±214.14%        3.50 μs        4.88 μs
Part 1        1.48 K      676.32 μs    ±52.08%      626.25 μs     1302.52 μs
Part 2      0.0263 K    38024.57 μs     ±3.23%    38143.92 μs    41155.89 μs

Comparison: 
Parse       275.55 K
Part 1        1.48 K - 186.36x slower +672.70 μs
Part 2      0.0263 K - 10477.83x slower +38020.94 μs

Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code

jzimbel

December 12, 2024 (edited December 12, 2024)

Link

After I got my efficient part 2 solution working, I tried continuing to 100 iterations and beyond and found something kind of neat! At some point, new unique numbers stop being generated. For my...

After I got my efficient part 2 solution working, I tried continuing to 100 iterations and beyond and found something kind of neat! At some point, new unique numbers stop being generated. For my particular puzzle input, there are 3811 unique numbers that can be generated. The example input 125 17 can generate just 54 different numbers.

Anyway,

Both parts (Elixir)

defmodule AdventOfCode.Solution.Year2024.Day11 do
  use AdventOfCode.Solution.SharedParse

  import Integer, only: [is_even: 1]

  @impl true
  def parse(input), do: String.split(input)

  def part1(stones), do: solve(stones, 25)
  def part2(stones), do: solve(stones, 75)

  defp solve(stones, blinks) do
    stones
    |> collect()
    |> Stream.iterate(&blink/1)
    |> Enum.at(blinks)
    |> Enum.map(fn {_stone, n} -> n end)
    |> Enum.sum()
  end

  defp blink(stones, acc \\ [])

  defp blink([], acc), do: collect(acc)

  defp blink([stone | stones], acc) do
    acc =
      case stone do
        {"0", n} ->
          [{"1", n} | acc]

        {stone, n} when is_even(byte_size(stone)) ->
          {a, b} = split(stone)
          [{b, n}, {a, n} | acc]

        {stone, n} ->
          stone = stone |> String.to_integer() |> Kernel.*(2024) |> Integer.to_string()
          [{stone, n} | acc]
      end

    blink(stones, acc)
  end

  defp split(str) do
    half = str |> byte_size() |> div(2)
    a = str |> binary_part(0, half) |> trim_zeros()
    b = str |> binary_part(half, half) |> trim_zeros()
    {a, b}
  end

  defp trim_zeros(str) do
    case String.trim_leading(str, "0") do
      "" -> "0"
      trimmed -> trimmed
    end
  end

  defp collect([{_stone, _n} | _] = stones) do
    stones
    |> Enum.group_by(fn {stone, _n} -> stone end, fn {_stone, n} -> n end)
    |> Enum.map(fn {stone, ns} -> {stone, Enum.sum(ns)} end)
  end

  defp collect([_stone | _] = stones) do
    stones
    |> Enum.frequencies()
    |> Map.to_list()
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Parse      288130.82     0.00347 ms   ±229.80%     0.00342 ms     0.00471 ms
Part 1        774.97        1.29 ms     ±6.84%        1.28 ms        1.46 ms
Part 2          7.89      126.79 ms     ±1.35%      126.76 ms      134.28 ms

Comparison: 
Parse      288130.82
Part 1        774.97 - 371.80x slower +1.29 ms
Part 2          7.89 - 36531.34x slower +126.78 ms

2 votes

Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code

jzimbel

December 11, 2024

Link

Behold, two abominations of pattern matching: the twin beasts, relocate_file/2 and clear_file/2. Look On My Works And Despair! Both parts (Elixir) (If you think it's incomprehensible now, you...

Behold, two abominations of pattern matching: the twin beasts, relocate_file/2 and clear_file/2.

Look On My Works And Despair!

Both parts (Elixir)

(If you think it's incomprehensible now, you should have how it looked before I defined the hp macro)

defmodule AdventOfCode.Solution.Year2024.Day09 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    input
    |> String.trim()
    |> :binary.bin_to_list()
    # Parse all digits in the string
    |> Enum.map(&(&1 - ?0))
    # Expand each digit to a file or free segment of the corresponding length
    |> Enum.flat_map_reduce({:file, 0}, fn
      n, {:file, i} -> {List.duplicate(i, n), {:free, i + 1}}
      n, {:free, i} -> {List.duplicate(:_, n), {:file, i}}
    end)
    |> then(fn {disk, _acc} -> disk end)
  end

  def part1(disk) do
    disk
    |> shift_files_left_p1()
    |> checksum()
  end

  def part2(disk) do
    disk
    |> shift_files_left_p2()
    |> checksum()
  end

  defp shift_files_left_p1(disk) do
    file_blocks =
      disk
      |> Enum.reject(&(&1 == :_))
      |> Enum.reverse()

    {new_disk, _} =
      disk
      # Since all file blocks are being compacted left,
      # we know the number of blocks needed ahead of time.
      |> Enum.take(length(file_blocks))
      |> Enum.map_reduce(file_blocks, fn
        # See a free block: emit a file block off the end
        :_, [file_block | file_blocks] -> {file_block, file_blocks}
        # See a file block: emit the file block
        file_block, file_blocks -> {file_block, file_blocks}
      end)

    new_disk
  end

  defp shift_files_left_p2(disk) do
    files =
      disk
      |> Enum.reject(&(&1 == :_))
      |> Enum.reverse()
      |> Enum.chunk_by(& &1)

    disk = Enum.chunk_by(disk, & &1)

    files
    |> Enum.reduce(disk, &relocate_file/2)
    |> List.flatten()
  end

  # "Head pattern". Matches a list with pattern `pat` as head and anything as tail.
  # hp(:foo) expands to [:foo | _]
  # hp(my_var) expands to [my_var | _], binding `my_var` to the head of a nonempty list
  defmacrop hp(pat), do: quote(do: [unquote(pat) | _])

  ### Puts file at its new position (if one exists)
  ### and then replaces its old position with free blocks using `clear_file`
  defp relocate_file(file, disk)

  defp relocate_file(file, [hp(:_) = free | rest]) when length(file) <= length(free) do
    # Found a fit
    [file, Enum.drop(free, length(file)) | clear_file(hd(file), rest)]
  end

  defp relocate_file(file, [hp(:_) = free | rest]) do
    # Too small
    [free | relocate_file(file, rest)]
  end

  defp relocate_file(hp(id), hp(hp(id)) = disk) do
    # Reached the original file without finding a fit
    disk
  end

  defp relocate_file(file, [other_file | rest]) do
    # A different file
    [other_file | relocate_file(file, rest)]
  end

  ### Clears moved file after `relocate_file` puts it in new position
  defp clear_file(id, disk)

  defp clear_file(id, [hp(:_) = l_free, hp(id) = file, hp(:_) = r_free | rest]) do
    # Found the file and it has free space both before and after it
    [l_free ++ List.duplicate(:_, length(file)) ++ r_free | rest]
  end

  defp clear_file(id, [hp(:_) = l_free, hp(id) = file | rest]) do
    # Found the file and it has free space before only
    [l_free ++ List.duplicate(:_, length(file)) | rest]
  end

  defp clear_file(id, [hp(id) = file, hp(:_) = r_free | rest]) do
    # Found the file and it has free space after only
    [List.duplicate(:_, length(file)) ++ r_free | rest]
  end

  defp clear_file(id, [hp(id) = file | rest]) do
    # Found the file and it's surrounded by other files
    [List.duplicate(:_, length(file)) | rest]
  end

  defp clear_file(id, [other | rest]) do
    # A free space or a different file
    [other | clear_file(id, rest)]
  end

  defp checksum(disk) do
    disk
    |> Enum.with_index()
    |> Enum.reject(&match?({:_, _i}, &1))
    |> Enum.map(&Tuple.product/1)
    |> Enum.sum()
  end
end

Benchmarks

Name             ips        average  deviation         median         99th %
Parse         659.55        1.52 ms     ±7.23%        1.50 ms        1.87 ms
Part 1        277.49        3.60 ms     ±6.45%        3.53 ms        4.24 ms
Part 2          1.11      897.97 ms     ±2.04%      898.05 ms      916.18 ms

Comparison: 
Parse         659.55
Part 1        277.49 - 2.38x slower +2.09 ms
Part 2          1.11 - 592.26x slower +896.45 ms

2 votes

Comment on Day 7: Bridge Repair in ~comp.advent_of_code

jzimbel

December 9, 2024 (edited December 9, 2024)

Link

I started out on this thinking I could do a little better than brute force by doing the following: sort each list of numbers and start testing with all +'s, so that each attempt would produce a...

I started out on this thinking I could do a little better than brute force by doing the following:

sort each list of numbers and start testing with all +'s, so that each attempt would produce a generally increasing result*
stop testing once the results became greater than the target number, since further tests would produce only more numbers greater than the target.

Buuuuut sorting the list would cause the operations to be applied in the wrong order. That was it for my optimization ideas, so brute force it is!

Both parts (Elixir)

Somewhat out of laziness, I generated the op permutations from an incrementing integer.

E.g. On a line with n numbers, I would need n-1 operators.

For part 1, this would require testing up to 2^(n-1) op combos, so I used an integer starting at 0 and incrementing to that number. When it was say, 6, that would translate to binary 0 1 1, and then I'd translate each digit to an operator: + * *

Part 2 was almost the same, except the combos were 3^(n-1) and I converted the integer to ternary: 6 -> 0 2 0 -> + || +.

defmodule AdventOfCode.Solution.Year2024.Day07 do
  use AdventOfCode.Solution.SharedParse

  @impl true
  def parse(input) do
    for line <- String.split(input, "\n", trim: true) do
      [target, ns] = String.split(line, ":")
      {String.to_integer(target), for(n <- String.split(ns), do: String.to_integer(n))}
    end
  end

  def part1(equations), do: sum_solvable(equations, 2)
  def part2(equations), do: sum_solvable(equations, 3)

  defp sum_solvable(eqs, n_ops) do
    for {target, _ns} = eq <- eqs, solvable?(eq, n_ops), reduce: 0, do: (acc -> acc + target)
  end

  def solvable?({target, ns}, n_ops) do
    ns
    |> stream_calculations(n_ops)
    |> Enum.any?(&(&1 == target))
  end

  def stream_calculations([], _n_ops), do: []
  def stream_calculations([n], _n_ops), do: [n]

  def stream_calculations(ns, n_ops) do
    upper_bound = n_ops ** (length(ns) - 1)

    Stream.unfold(0, fn
      ^upper_bound -> nil
      op_combo -> {apply_ops(op_combo, ns, n_ops), op_combo + 1}
    end)
  end

  defp apply_ops(op_combo, ns, n_ops) do
    op_combo
    |> Integer.digits(n_ops)
    |> zero_pad(length(ns))
    |> Enum.zip_reduce(ns, 0, &eval_op/3)
  end

  defp zero_pad(l, n), do: List.duplicate(0, max(0, n - length(l))) ++ l

  defp eval_op(0, b, a), do: a + b
  defp eval_op(1, b, a), do: a * b
  defp eval_op(2, b, a), do: a * 10 ** (1 + trunc(:math.log10(b))) + b
end

Benchmarks

Is there any way to optimize this? (Besides the obvious parallelization by line)
It almost seems like a cryptography problem.

Running the whole thing in one process:

Name             ips        average  deviation         median         99th %
Parse         302.82        3.30 ms     ±2.25%        3.28 ms        3.53 ms
Part 1         34.66       28.85 ms     ±5.40%       28.69 ms       37.07 ms
Part 2          0.56     1777.75 ms     ±0.59%     1783.57 ms     1783.96 ms

Comparison: 
Parse         302.82
Part 1         34.66 - 8.74x slower +25.55 ms
Part 2          0.56 - 538.34x slower +1774.45 ms

After switching to a Task.async_stream call to check each line concurrently:

Name             ips        average  deviation         median         99th %
Part 1        105.77        9.45 ms     ±2.56%        9.45 ms       10.17 ms
Part 2          3.08      324.21 ms     ±2.38%      324.76 ms      333.83 ms

* (tbh I think this logic was flawed as well. For example, 5 + 1 = 6 and 5 * 1 = 5.)

jzimbel's recent activity

Comment on Day 9: Movie Theater in ~comp.advent_of_code

Comment on Day 5: Cafeteria in ~comp.advent_of_code

Comment on Day 5: Cafeteria in ~comp.advent_of_code

Comment on Day 4: Printing Department in ~comp.advent_of_code

Comment on Day 3: Lobby in ~comp.advent_of_code

Comment on Day 2: Gift Shop in ~comp.advent_of_code

Comment on Day 1: Secret Entrance in ~comp.advent_of_code

Comment on Day 1: Secret Entrance in ~comp.advent_of_code

Comment on Two signs that Democrats flipped Donald Trump supporters on Tuesday (gifted link) in ~society

Comment on What are some interesting landmarks in your neck of the woods? in ~talk

Comment on iOS 26 is here in ~tech

Comment on Norway's capital is known for its green policies and widespread adoption of electric vehicles. Why does the city still struggle with air pollution? in ~enviro

Comment on James Bond shocker! Amazon MGM Studios takes creative control of spy franchise as producers Michael G. Wilson and Barbara Broccoli step back. in ~movies

Comment on Are modern iPhones unusable without a case? in ~comp

Comment on What are your favourite things to mix with natural yogurt? in ~food

Comment on Day 10: Hoof It in ~comp.advent_of_code

Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code

Comment on Day 11: Plutonian Pebbles in ~comp.advent_of_code

Comment on Day 9: Disk Fragmenter in ~comp.advent_of_code

Comment on Day 7: Bridge Repair in ~comp.advent_of_code