Advent of Code 2024 - Day 24

Learning Questions & Discussions Coding Challenges
,
21

Just thinking, I wonder if anyone tried to build an AST out of the input and just execute it as a function call to simulate the machine. That might be fun for me to learn how to do that.

1 Like
22

Not an AST, but a graph and a function to execute that graph with given x and y.

Graph building (with libgraph)

graph =
  exprs
  |> String.split(~r/\W+/, trim: true)
  |> Enum.chunk_every(4)
  |> Enum.reduce(Graph.new(), fn [lhs, op, rhs, out], graph ->
    op = :"b#{String.downcase(op)}"
    
    graph
    |> Graph.add_edge(lhs, out, label: op)
    |> Graph.add_edge(rhs, out, label: op)
  end)

Evaluate the graph:

eval = fn graph, x, y ->
  x_bits =
    x
    |> Integer.to_string(2)
    |> String.pad_leading(45, "0")
    |> String.reverse()
    |> String.to_charlist()
    |> Enum.with_index()
    |> Enum.map(fn {bit, i} ->
      n = i |> to_string() |> String.pad_leading(2, "0")
      {"x#{n}", bit - ?0}
    end)
    |> Map.new()

  y_bits =
    y
    |> Integer.to_string(2)
    |> String.pad_leading(45, "0")
    |> String.reverse()
    |> String.to_charlist()
    |> Enum.with_index()
    |> Enum.map(fn {bit, i} ->
      n = i |> to_string() |> String.pad_leading(2, "0")
      {"y#{n}", bit - ?0}
    end)
    |> Map.new()

  context = Map.merge(x_bits, y_bits)

  sorted = Graph.topsort(graph)

  Enum.reduce(sorted, context, fn vertex, context ->
    case Graph.in_edges(graph, vertex) do
      [] ->
        context
        
      [%Graph.Edge{v1: var1, label: op}, %Graph.Edge{v1: var2, label: op}] ->
        arg1 = context[var1]
        arg2 = context[var2]
        Map.put(context, vertex, apply(Bitwise, op, [arg1, arg2]))
    end
  end)
  |> Enum.filter(fn {k, _} ->
    String.starts_with?(k, "z")
  end)
  |> Enum.sort(:desc)
  |> Enum.map(&elem(&1, 1))
  |> Integer.undigits(2)
end

Example:

eval.(graph, _x = 123, _y = 456)
1 Like