lud

lud

This one was scary at first.

I loved how part one directs you into an obvious optimization, and then part 2 kicks your butt by asking to not do that very specific optimization :smiley:

My solution for part 2 runs in between 150ms and 380ms. I guess it’s because of the async streams, but it’s always fast (around 150, rarely even 120) when I run it once, but then with benchee for 10 seconds it averages between 170 and 380 depending on the runs …) Anyways, is fast enough.

defmodule AdventOfCode.Solutions.Y24.Day19 do
  alias AoC.Input

  def parse(input, _part) do
    [towels, targets] = input |> Input.read!() |> String.trim() |> String.split("\n\n")

    towels = towels |> String.split([",", " "], trim: true) |> Enum.map(&{&1, byte_size(&1)})
    targets = String.split(targets, "\n", trim: true)
    {towels, targets}
  end

  def part_one({towels, targets}) do
    primitives = reduce_towels(towels)
    targets = filter_possible_targets(targets, primitives)
    length(targets)
  end

  # remove towels that can be constructed with other towels
  defp reduce_towels(towels) do
    case Enum.split_with(towels, fn {text, _} = t -> possible_target?(text, towels -- [t]) end) do
      {[], all_primitives} -> all_primitives
      {_composable, primitives} -> reduce_towels(primitives)
    end
  end

  defp filter_possible_targets(targets, towels) do
    targets
    |> Task.async_stream(&{possible_target?(&1, towels), &1}, ordered: false, timeout: :infinity)
    |> Enum.flat_map(fn
      {:ok, {true, t}} -> [t]
      {:ok, {false, _}} -> []
    end)
  end

  defp possible_target?(target, towels) do
    possible_target?(target, towels, towels)
  end

  defp possible_target?("", _, _), do: true
  defp possible_target?(_, [], _), do: false

  defp possible_target?(target, [{h, b} | t], towels) do
    sub_match? =
      case target do
        <<^h::binary-size(b), rest::binary>> -> possible_target?(rest, towels, towels)
        _ -> false
      end

    sub_match? || possible_target?(target, t, towels)
  end

  def part_two({towels, targets}) do
    primitives = reduce_towels(towels)

    targets
    |> filter_possible_targets(primitives)
    |> Task.async_stream(&count_combinations(&1, towels), ordered: false, timeout: :infinity)
    |> Enum.reduce(0, fn {:ok, n}, acc -> acc + n end)
  end

  defp count_combinations(target, towels) do
    possible_towels = Enum.filter(towels, fn {text, _} -> String.contains?(target, text) end)
    do_count(%{target => 1}, possible_towels, 0)
  end

  defp do_count(target_suffixes, _towels, count) when map_size(target_suffixes) == 0 do
    count
  end

  defp do_count(target_suffixes, towels, count) do
    new_suffixes =
      for {t, count} <- target_suffixes, {h, b} <- towels, reduce: [] do
        sufxs ->
          case t do
            <<^h::binary-size(b), rest::binary>> -> [{rest, count} | sufxs]
            _ -> sufxs
          end
      end

    {target_suffixes, finished_count} =
      Enum.reduce(new_suffixes, {%{}, 0}, fn
        {"", cpt}, {map, finished_count} -> {map, finished_count + cpt}
        {sufx, cpt}, {map, finished_count} -> {Map.update(map, sufx, cpt, &(&1 + cpt)), finished_count}
      end)

    do_count(target_suffixes, towels, count + finished_count)
  end
end

Most Liked

bjorng

bjorng

Erlang Core Team

My straightforward solution for part 1 didn’t terminate for my real input.

I then implemented a trie (prefix tree). That took me a while, but it still didn’t terminate.

I then added memoization using the process dictionary. That worked.

After solving part 2, I cleaned up my code. I tried to use Memoize for memoization but the time increased to 31 seconds. I did some attempts to make Memoize use only the first argument of my count function, but I couldn’t make it work. In the end, I rewrote my count function to take an explicit memo argument.

The combined runtime for both parts and the examples is 0.4 seconds.

https://github.com/bjorng/advent-of-code/blob/main/2024/day19/lib/day19.ex

lkuty

lkuty

I compiled a big regex for part 1. It is slow and does not work for part 2 but it was trivial to implement. Now I have to find another kind of solution to be able to do part 2 and probably part 1 faster.

{towels, designs} = puzzle_input
|> String.split("\n")
|> then(fn [towels, _ | designs] -> {String.split(towels, ", "), designs} end)

{:ok, regex} = towels |> Enum.join("|") |> then(fn x -> "^(#{x})+$" end) |> Regex.compile()

designs
|> Enum.reduce(0, fn design, n -> if String.match?(design, regex), do: n+1, else: n end)
|> IO.inspect(label: "Part 1")

igorb

igorb

I started with a straightforward solution I coded up in a few minutes, but it was taking too long on the real input, so I spent a while to rewrite it with a prefix tree (trie) instead. It ended up being too slow too, at which point I realized that, of course, I just needed to use memoization. So then I added it and was able to get the final answer. Ironically, it turned out that my original solution just lacked memoization as well so after adding it it ended up being even faster. Though both are slow compared to your runtime—definitely takes a few seconds for me. I didn’t parallelize, though.

With prefix tree and custom memoization: advent-of-code-2024/lib/advent_of_code2024/day19_trie.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

Straightforward, using a nice memoization library: advent-of-code-2024/lib/advent_of_code2024/day19.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

Last Post!

seeplusplus

seeplusplus

I have never written a macro before, but part one inspired me to give it a go. In hindsight, it was a bad idea, but it worked for part one.

defmodule LinenLayout do
  defmacro __using__(_opts) do
    quote do
      import LinenLayout

      # safeq (resp. safer) is needed, because I wanted a clause like:
     # def q(_), do: 0
     # but Idk how to make sure that clause comes _after_ all the def's
     # that would be expanded from macros, so instead I use try/rescue to
     # catch invocations that don't have matching defs (e.g., patterns s.t. no
     # towel exists for.
      def safeq(x) do
        try do
          q(x)
        rescue _ -> nil
        end
      end
  
      def safer(x) do
        try do
          r(x)
        rescue _ -> nil
        end
      end

      # these two stop the recursive steps below
      def qq(nil) do
        0
      end
      # using `raise` for control flow. I don't like it, but I was desperate
      # will be rescued in `count_makeable`
      def qq(1) do
        raise "yes"
      end
      
      def qq(x) do
          (safeq(x) |> qq()) + (safer(x) |> qq())
      end

      # invoked when there is no pattern left - we had all the towels we needed
      def q(""), do: 1
      def r(""), do: 1
      def count_makeable(towels) do
        towels 
        |> String.split("\n", trim: true)
        |> Stream.map(&
          try do
            qq(&1)
          # qq throws when `safeq` (resp. `safer`) finished completing a patttern
          rescue _ in RuntimeError -> 1
          end) 
        |> Enum.sum()
      end
    end
  end

  # I didn't need `f` _and_ `h`, but I wanted
  # the macro to expand out to functions with different names.
  # there is a way to do this as an arg to the macro, but  i was lazy.
  # these are exactly the same, to understand why they exist, read `g/1`
  # 
  # The basic idea of the approach is that we will use Elixir's binary
  # pattern matching to do all of the work. Each towel in our
  # inventory will get its own `def q(color <> rest)`. We will recursively call on `q(rest)` 
  # until either:
  # (a) We exhaust the pattern (yay, we had all the towels we needed!) 
  # (b) we throw an error for no clause matching input params (the pattern began 
  # with color  we don't have a towel for).
  defmacro f(i) do
    quote do
      def q(unquote(i) <> rest), do: rest
    end
  end
  
 defmacro h(i) do
    quote do
      def r(unquote(i) <> rest), do: rest
    end
  end

  # takes a list of towels and expands out to two sets of functions:
  # one set where the clauses are ordered longest towel first, e.g.,
  # if `bgr` and `b` are both towels `q("bgr" <> rest)` will appear before
  # `q("b" <> rest)`.
  # the other set is reversed - these are the `r` functions, expanded from `h`, above.
  # 
  # why did I do this? because just one of these directions will miss some patterns
 # because they will be greedy in either using the towels with more stripes first or
 # using the towels with the least stripes first. Doing both was my attempt to fix the
 # issue where either of these under counted. This doesn't _really_ fix the real issue.
 # There could be a towel `"bg"` that is "between" `"bgr"` and `"b"` that would never be
# accounted for if the pattern began with `"bgr"`. In fact, this exact issue is probably why
# this approach will not work for pt. 2.
  defmacro g(u) do
   # `u` is the list of towels we have 
   u = u
    |> String.split(", ")
    

   # expand out `f` for all the towels
    (u 
      |> Enum.sort_by(fn l -> -String.length(l) end) 
      |> Enum.map(fn o ->
        quote do
          f(unquote(o))
        end  
        end)
    )
    ++
    (
     # then expand out `h`
      u 
      |> Enum.sort_by(&(String.length(&1))) 
      |> Enum.map(&(quote do h(unquote(&1)) end))
    )
  end
end

Now actually solving part 1:

defmodule Foo do
  use LinenLayout

  g "r, wr, b, g, bwu, rb, gb, br"
end
"""
brwrr
bggr
gbbr
rrbgbr
ubwu
bwurrg
brgr
bbrgwb
"""
|> Foo.count_makeable()

Where Next? Top

Trending in Challenges Top

Other Trending Topics Top

GenericJam
Edit: 2026 May 15 - This post is archived. Mob is alive!! Main docs: mob v0.7.11 — Documentation A bit of explanation for the slightly c...
New
JesseHerrick
Hey, I’m Jesse and I’m the main contributor behind Dexter, a full-featured, lightning-fast Elixir LSP optimized for large codebases. It s...
New
mudasobwa
I am happy to introduce the very α version of the new programming language compiled to BEAM. Welcome Cure. It has literally three kille...
New
marciok
Hi there! We created Gust: A task orchestrator inspired by Airflow. For those who have never heard about Aiflow, it’s a Python-based wor...
New
mhanberg
Hi everyone! The first release candidate for the Expert language server project is now available! We’ve published a press release detai...
New
jimsynz
Beam Bots (or just BB for short) is a framework for building fault-tolerant robotics applications in Elixir using familiar OTP patterns. ...
New

We're in Beta

About us Mission Statement

Options

Thread Display Mode




Thread Preview

Skip Thread Previews