Advent of Code 2023 - Day 19

My approach today:

https://github.com/ibarakaiev/advent-of-code-2023/blob/main/lib/advent_of_code/day_19.ex

Part 1 is basically just a loop navigating over the map.

Part 2 is building a “binary tree”: if a certain condition is true, the next execution is a branch “to the left” with the target workflow; if it’s false, continue with the next step of the current workflow. I maintain a map of ranges (%{x: {1, 4000}, ...}) throughout and adjust the range based on each condition. If the execution is to the “left” of the tree, then I just apply the condition, otherwise I apply the inverse of the condition. When A is reached, I multiply the ranges.

https://github.com/tywhisky/advent-of-code/blob/master/2023/day_19/solution.exs

For part2 I used MapSet.intersection/2, which didn’t perform very well, but the whole coding experience was very smooth, no debugging, and I got the right results in one go. The idea is also very easy to understand.

Here is my solution:

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

I just can’t understand what Part 2 is talking about

Here’s my solution, it went pretty well !

import Input

defmodule Day19 do
  def part1(input) do
    {map, parts} = parse_input(input)

    parts
    |> Enum.map(&walk(map, "in", &1))
    |> Enum.zip(parts)
    |> Enum.map(&score/1)
    |> Enum.sum()
  end

  defp walk(map, wf_name, part) do
    conds = Map.fetch!(map, wf_name)

    conds
    |> Enum.find(fn
      {field, ">", thresh, _} ->
        part
        |> Map.fetch!(field)
        |> Kernel.>(thresh)

      {field, "<", thresh, _} ->
        part
        |> Map.fetch!(field)
        |> Kernel.<(thresh)

      _ ->
        true
    end)
    |> then(fn
      {_, _, _, res} -> res
      default -> default
    end)
    |> case do
      "A" -> "A"
      "R" -> "R"
      new_wf_name -> walk(map, new_wf_name, part)
    end
  end

  defp score({"R", _}), do: 0
  defp score({"A", %{"x" => x, "m" => m, "a" => a, "s" => s}}), do: x + m + a + s

  def part2(input) do
    {map, _} = parse_input(input)

    combs(map, Map.fetch!(map, "in"), %{
      "x" => {1, 4001},
      "m" => {1, 4001},
      "a" => {1, 4001},
      "s" => {1, 4001}
    })
  end

  defp combs(map, [{field, op, thresh, res} | tail], threshs) do
    {new_thresh, rev_thresh} = split_treshs(threshs, field, op, thresh)
    combs(map, res, new_thresh) + combs(map, tail, rev_thresh)
  end

  defp combs(map, [key], threshs), do: combs(map, key, threshs)

  defp combs(map, "A", threshs) do
    threshs
    |> Enum.map(fn {_, {min, max}} -> max - min end)
    |> Enum.map(&max(&1, 0))
    |> Enum.reduce(1, &(&1 * &2))
  end

  defp combs(map, "R", threshs), do: 0
  defp combs(map, key, threshs), do: combs(map, Map.fetch!(map, key), threshs)

  defp split_treshs(threshs, field, "<", thresh) do
    new_threshs =
      Map.update!(threshs, field, fn {min, max} ->
        {min, min(max, thresh)}
      end)

    rev_threshs =
      Map.update!(threshs, field, fn {min, max} ->
        {max(min, thresh), max}
      end)

    {new_threshs, rev_threshs}
  end

  defp split_treshs(threshs, field, ">", thresh) do
    new_threshs =
      Map.update!(threshs, field, fn {min, max} ->
        {max(min, thresh + 1), max}
      end)

    rev_threshs =
      Map.update!(threshs, field, fn {min, max} ->
        {min, min(max, thresh + 1)}
      end)

    {new_threshs, rev_threshs}
  end

  defp parse_input([workflows, parts]) do
    {
      workflows |> Enum.map(&parse_workflow/1) |> Map.new(),
      Enum.map(parts, &parse_part/1)
    }
  end

  defp parse_workflow(input) do
    input
    |> Utils.splitrim(~r/[{},]/)
    |> Enum.map(&Utils.splitrim(&1, ":"))
    |> Enum.map(fn
      [solo] ->
        solo

      [<<field::bytes-size(1), op::bytes-size(1), thresh::binary>>, res] ->
        {field, op, String.to_integer(thresh), res}
    end)
    |> then(fn [name | conds] -> {name, conds} end)
  end

  defp parse_part(input) do
    input
    |> Utils.splitrim(~r/[{},]/)
    |> Enum.map(&Utils.splitrim(&1, "="))
    |> Enum.map(fn [field, value] -> {field, String.to_integer(value)} end)
    |> Map.new()
  end

  def run() do
    part2(~i[19]c)
  end

  def bench() do
    Benchmark.mesure_milliseconds(&run/0)
  end
end

Input is just a collection of sigils (such as ~i) to manipulate inputs (like returning parts separated by an empty line).

Part 2 wants you to count all possible combinations of x, m, a, s (between 1 and 4000) that would be accepted by the workflows.

So basically this:

    for x <- 1..4000, m <- 1..4000, s <- 1..4000, a <- 1..4000, reduce: 0 do
      count ->
        if accepted_part?(%{x: x, m: m, s: s, a: a}, worfklows) do
          count + 1
        else
          count
        end
    end

Thank you for your extremely clear explanation

Finally, I did it!

I just feel today is the GenServer day, so I started a bunch of GenServer processes to handle the situation.

All the variable named xmas in the following code binds to a map that looks like

%{
  "x" => 123..321,
  "m" => 132..213,
  "a" => 321..132,
  "s" => 312..213
}

First, here’s the GenServer module that models one pipe in the workflow.

defmodule Pipe do
  use GenServer

  # `spec` is a string like `"foo{x>123:bar,R}"`
  def start_link(spec) do
    {name, rules} = parse_spec(spec)
    GenServer.start_link(__MODULE__, rules, name: name)
  end

  @impl true
  def init(rules) do
    {:ok, rules}
  end

  @impl true
  def handle_cast({:handle, xmas}, rules) do
    rules
    |> Enum.reduce(xmas, fn rule, xmas ->
      rule.(xmas)
    end)

    {:noreply, rules}
  end

  defp parse_spec(spec) do
    [name, rules] =
      ~r/^(\w+)\{(.*)\}$/
      |> Regex.run(spec, capture: :all_but_first)
    
    name = String.to_atom(name)

    rules =
      rules
      |> String.split(",")
      |> Enum.map(&parse_rule/1)

    {name, rules}
  end

  defp parse_rule(rule) do
    case Regex.split(~r/\W/, rule, trim: true, include_captures: true) do
      [next] ->
        next = String.to_atom(next)
        fn xmas ->
          GenServer.cast(next, {:handle, xmas})
          nil
        end
      
      [key, comp, thres, ":", next] ->
        thres = String.to_integer(thres)
        next = String.to_atom(next)
        fn xmas ->
          range = xmas[key]
          {met, unmet} = split(comp, thres, range)
          GenServer.cast(next, {:handle, %{xmas | key => met}})
          %{xmas | key => unmet}
        end
    end
  end

  defp split("<", thres, a..b), do: {a..(thres - 1), thres..b}
  defp split(">", thres, a..b), do: {(thres + 1)..b, a..thres}
end

Then there’s a GenServer for accumulating the results:

defmodule Acceptor do
  use GenServer

  def start_link() do
    GenServer.start_link(__MODULE__, [], name: :A)
  end

  @impl true
  def init(state) do
    {:ok, state}
  end

  @impl true
  def handle_cast({:handle, xmas}, sum) do
    xmas
    |> Map.values()
    |> Stream.map(fn a..b ->
      b - a + 1
    end)
    |> Stream.map(&max(&1, 0))
    |> Enum.product()
    |> then(&{:noreply, &1 + sum})
  end

  @impl true
  def handle_call(:get, _from, state) do
    {:reply, state, state}
  end
end

And the blackhole

defmodule Rejector do
  use GenServer

  def start_link() do
    GenServer.start_link(__MODULE__, nil, name: :R)
  end

  @impl true
  def init(state) do
    {:ok, state}
  end

  @impl true
  def handle_cast({:handle, _xmas}, state) do
    {:noreply, state}
  end
end

Start all the servers:

Acceptor.start_link()

Rejector.start_link()

for spec <- specs do
  Pipe.start_link(spec)
end

And finally, do the job

GenServer.cast(:in, {:handle, %{
  "x" => 1..4000,
  "m" => 1..4000,
  "a" => 1..4000,
  "s" => 1..4000
}})

# Wait a sec

GenServer.call(:A, :get)

Got to use Agent today, pretty fun day honestly:

https://github.com/woojiahao/aoc/blob/main/lib/aoc/y2023/day_19.ex

Part 1 was relatively straightforward, part 2 was a little more challenging in the data storing front, but the actual calculation was quite straightforward

For Part 2 I first recursively walked the tree from "in" and built up a list of branches that lead to "A". Then I flattened the conditions in each branch into a ranges by category. Lastly I found the number of permutations of each branch using Enum.product and summed all of the permutations for each branch. I probably could have combined the first two steps, but I was thinking about the problem as “find all the acceptance branches, then find the number of permutations in each branch”.

defmodule Part1 do
  def parse(input) do
    [workflows, ratings] = String.split(input, "\n\n")

    workflows =
      for line <- String.split(workflows, "\n", trim: true), into: %{} do
        [name, rules] = String.split(line, ["{", "}"], trim: true)

        rules =
          for rule <- String.split(rules, ",") do
            case Regex.run(~r/(?:(\w)([<>])(\d+):)?(\w+)/, rule, capture: :all_but_first) do
              ["", "", "", output] ->
                output

              [category, op, threshold, output] ->
                threshold = String.to_integer(threshold)
                {category, op, threshold, output}
            end
          end

        {name, rules}
      end

    ratings =
      for line <- String.split(ratings, "\n", trim: true) do
        for field <- String.split(line, ["{", "}", ","], trim: true), into: %{} do
          [key, value] = String.split(field, "=")
          {key, String.to_integer(value)}
        end
      end

    {workflows, ratings}
  end

  def eval(rating, workflows), do: eval(rating, workflows, "in")
  def eval(_, _, "R"), do: false
  def eval(_, _, "A"), do: true
  def eval(rating, workflows, <<name::binary>>), do: eval(rating, workflows, workflows[name])
  def eval(rating, workflows, [<<name::binary>>]), do: eval(rating, workflows, name)

  def eval(rating, workflows, [{category, op, threshold, output} | rules]) do
    fun = if op == "<", do: &Kernel.</2, else: &Kernel.>/2
    next = if fun.(rating[category], threshold), do: output, else: rules
    eval(rating, workflows, next)
  end
end

{workflows, ratings} = Part1.parse(input)

ratings
|> Enum.filter(&Part1.eval(&1, workflows))
|> Enum.flat_map(&Map.values/1)
|> Enum.sum()

defmodule Part2 do
  def acceptance(workflows), do: acceptance("in", workflows) |> Enum.map(&flatten/1)

  def acceptance("R", _), do: false
  def acceptance("A", _), do: true
  def acceptance(<<name::binary>>, workflows), do: acceptance(workflows[name], workflows)
  def acceptance([<<name::binary>>], workflows), do: acceptance(name, workflows)

  def acceptance([{category, op, threshold, output} | rest], workflows) do
    left =
      output
      |> acceptance(workflows)
      |> prepend({category, op, threshold})

    right_op = if op === "<", do: ">=", else: "<="

    right =
      rest
      |> acceptance(workflows)
      |> prepend({category, right_op, threshold})

    left ++ right
  end

  def prepend(false, _), do: []
  def prepend(true, rule), do: [[rule]]
  def prepend(branches, rule), do: Enum.map(branches, &[rule | &1])

  @input "xmas"
         |> String.graphemes()
         |> Enum.map(&{&1, 1..4000})
         |> Map.new()

  def flatten(branch), do: flatten(branch, @input)
  def flatten([], acc), do: acc

  def flatten([{category, op, threshold} | branch], acc) do
    lo..hi = acc[category]

    range =
      case op do
        ">" -> max(threshold + 1, lo)..hi
        ">=" -> max(threshold, lo)..hi
        "<" -> lo..min(threshold - 1, hi)
        "<=" -> lo..min(threshold, hi)
      end

    acc = %{acc | category => range}
    flatten(branch, acc)
  end
end

Part2.acceptance(workflows)
|> Enum.map(fn rating ->
  rating
  |> Map.values()
  |> Enum.map(&Enum.count/1)
  |> Enum.product()
end)
|> Enum.sum()

A crude parser and two simple interpreters.
For part 2 used xmas map holding ranges,
and some simple recursion.

import AOC

aoc 2023, 19 do
  def p1(input) do
    [code, data] = input |> String.split("\n\n")
    code = parse_code(code)
    data
    |> String.split("\n", trim: true)
    |> Enum.map(&parse_data/1)
    |> Enum.map(&process(code, :in, &1))
    |> Enum.sum()
  end

  def process(_, :A, xmas), do: xmas |> Map.values |> Enum.sum
  def process(_, :R, _), do: 0
  def process(code, label, xmas), do: evaluate(code, code[label], xmas)

  def evaluate(code, [label], xmas), do: process(code, label, xmas)
  def evaluate(code, [{pred, label} | rest], xmas), do: if(evaluate_pred(pred, xmas), do: process(code, label, xmas), else: evaluate(code, rest, xmas))

  def evaluate_pred({var, "<", n}, xmas), do: xmas[var] < n
  def evaluate_pred({var, ">", n}, xmas), do: xmas[var] > n

  def parse_data(data) do
    data
    |> String.trim_leading("{")
    |> String.trim_trailing("}")
    |> String.split(",", trim: true)
    |> Enum.map(fn pair -> pair |> String.split("=", trim: true) |> then(fn [var, num] -> {String.to_atom(var), String.to_integer(num)} end) end)
    |> Map.new
  end

  def do_snd({fst, snd}, f), do: {fst, f.(snd)}

  def parse_code(code) do
    code
    |> String.split("\n", trim: true)
    |> Enum.map(
      fn line ->
        [name, rules, _] = String.split(line, ["{", "}"])
        {String.to_atom(name),
        String.split(rules, ",")
        |> Enum.map(
          fn rule ->
            case String.split(rule, ":") do
            [pred, label] -> {compile_op(pred, if(String.contains?(pred, "<"), do: "<", else: ">")), String.to_atom(label)}
            [label] -> String.to_atom(label)
            end
          end
          )}
      end
    )
    |> Map.new
  end

  def ranges_size(ranges) do
    ranges
    |> Map.values()
    |> Enum.map(&Enum.count/1)
    |> Enum.product()
  end

  def compile_op(pred, op) do
    [var, num] = String.split(pred, op)
    {String.to_atom(var), op, String.to_integer(num)}
  end

  def split_ranges(ranges, true), do: ranges
  def split_ranges(ranges, {var, "<", num}) do
    cond do
    num in ranges[var] ->
      {lo, hi} = split_range(ranges[var], num)
      [Map.put(ranges, var, lo), Map.put(ranges, var, hi)]
    ranges[var].last < num -> [ranges, empty_ranges()]
    true -> [empty_ranges(), ranges]
    end
  end
  def split_ranges(ranges, {var, ">", num}) do
    cond do
    num in ranges[var] ->
      {lo, hi} = split_range(ranges[var], num+1)
      [Map.put(ranges, var, hi), Map.put(ranges, var, lo)]
    ranges[var].first > num -> [ranges, empty_ranges()]
    true -> [empty_ranges(), ranges]
    end
  end

  def empty_ranges(), do: %{x: [], m: [], a: [], s: []}

  def split_range(lo..hi, n), do: {lo..(n-1), n..hi}

  def process2(_, :A, ranges), do: ranges_size(ranges)
  def process2(_, :R, _), do: 0
  def process2(code, label, ranges), do: evaluate2(code, code[label], ranges)

  def evaluate2(code, [label], ranges), do: process2(code, label, ranges)
  def evaluate2(code, [{pred, label} | rest], ranges) do
    [true_ranges, false_ranges] = split_ranges(ranges, pred)
    process2(code, label, true_ranges) + evaluate2(code, rest, false_ranges)
  end

  def p2(input) do
    input
    |> String.split("\n\n")
    |> hd()
    |> parse_code()
    |> process2(:in, %{x: 1..4000, m: 1..4000, a: 1..4000, s: 1..4000})
  end
end