Advent of Code 2022 - Day 5

I spent more time than I would have only if I hadn’t updated the “initial state” instead of “accumulator” inside that reducer. It was silly of me and thanks to dbg, copying the example data, and 10 minutes of exploration, I got back on track. Cute of me to think I could get away with a _ in lieu of acc lol.

Here’s the outcome: advent_of_code/lib/2022/day_05.ex at main · code-shoily/advent_of_code · GitHub

Biggest challenge for me was just parsing the input, which is pretty typical for me.
I probably went overboard spinning up a GenServer but it’s what I always think of when there’s some “moves” or “ops” that have to be tracked.

defmodule Day5 do
  defmodule Input do
    def sample_data() do
      """
          [D]    
      [N] [C]    
      [Z] [M] [P]
       1   2   3 

      move 1 from 2 to 1
      move 3 from 1 to 3
      move 2 from 2 to 1
      move 1 from 1 to 2
      """
    end

    def load() do
      ReqAOC.fetch!({2022, 05, System.fetch_env!("AOC2022Session")})
    end

    def parse(input) do
      [stacks, moves] = input |> String.split("\n\n", trim: true) |> IO.inspect()

      stacks =
        stacks
        |> String.split("\n", trim: true)
        |> Enum.drop(-1)
        |> Enum.flat_map(fn line ->
          line |> String.graphemes() |> Enum.drop(1) |> Enum.take_every(4) |> Enum.with_index(1)
        end)
        |> Enum.group_by(&elem(&1, 1))
        |> Enum.map(fn {column, vals} ->
          {column, vals |> Enum.map(&elem(&1, 0)) |> Enum.reject(&Kernel.==(&1, " "))}
        end)
        |> Map.new()

      moves =
        moves
        |> String.split("\n", trim: true)
        |> Enum.map(fn line ->
          line
          |> String.split(["move ", " from ", " to "], trim: true)
          |> Enum.map(&String.to_integer(&1))
        end)

      {stacks, moves} |> IO.inspect()
    end
  end

  defmodule Stacks do
    use GenServer

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

    def handle_cast({:move_9000, n, from, to}, stacks) do
      new_stacks =
        1..n
        |> Enum.reduce(stacks, fn _, new_stacks ->
          [crate | stack] = Map.get(new_stacks, from)
          dest = Map.get(new_stacks, to)
          Map.put(new_stacks, from, stack) |> Map.put(to, [crate | dest]) |> IO.inspect()
        end)

      {:noreply, new_stacks}
    end

    def handle_cast({:move_9001, n, from, to}, stacks) do
      {moving, staying} = Map.get(stacks, from) |> Enum.split(n)

      new_stacks =
        Map.put(stacks, from, staying)
        |> Map.update!(to, fn dest -> moving ++ dest end)

      {:noreply, new_stacks}
    end

    def handle_call(:crates_on_top, _from, stacks) do
      tops =
        stacks
        |> Enum.map(fn
          {_col, [hd | rest]} -> hd
          {_col, []} -> :empty
        end)
        |> Enum.reject(fn crate -> crate == :empty end)

      {:reply, tops, stacks}
    end
  end

  defmodule Part1 do
    def solve({stacks, moves}) do
      {:ok, pid} = GenServer.start_link(Stacks, stacks)

      moves
      |> Enum.each(fn [n, from, to] -> GenServer.cast(pid, {:move_9000, n, from, to}) end)

      GenServer.call(pid, :crates_on_top) |> IO.inspect()
      GenServer.stop(pid)
    end
  end

  defmodule Part2 do
    def solve({stacks, moves}) do
      {:ok, pid} = GenServer.start_link(Stacks, stacks)

      moves
      |> Enum.each(fn [n, from, to] -> GenServer.cast(pid, {:move_9001, n, from, to}) end)

      GenServer.call(pid, :crates_on_top) |> Enum.join("") |> IO.inspect()
      GenServer.stop(pid)
    end
  end
end

As always, I am here to advertise Access.

# moving crates (part I)
  Enum.reduce(0..count - 1, acc, fn _, acc ->
    {v, acc} = get_and_update_in(acc, [Access.at(from - 1)], fn [h|t] -> {h, t} end)
    update_in(acc, [Access.at(to - 1)], fn t -> [v|t] end)
  end)

# moving crates (part II)
  {v, acc} = get_and_update_in(acc, [Access.at(from - 1)], fn l -> Enum.split(l, count) end)
  update_in(acc, [Access.at(to - 1)], fn t -> v ++ t end)

Thanks. Learnt something new!

Access is the extremely powerful and most underrated Elixir feature.

Finite number of moves is a synonym of reduce/3 through

Sure. Wasn’t sure what part 2 was going to be though, so it felt most flexible to do it with a GenServer.

I think the use of a module and named functions greatly improves readability. But I wanted to be as close as possible to one-liners.

start = System.monotonic_time(:microsecond)

stacks = File.stream!("input.txt")
  |> Stream.take(8)
  |> Stream.map(fn line ->
    # pos = idx / 4 + 1 and idx = (pos - 1) * 4
    # Get the positions of the stacks going from 1 to 9. "[D]                     [N] [F]    " -> [1, 7, 8]
     Regex.scan(~r/\[\w\]/, line, return: :index) |> Enum.map(fn [{start, _end}] -> div(start,4)+1 end)
    # Get the letters on a line with their respective positions. [1, 7, 8] -> [{8, "F"}, {7, "N"}, {1, "D"}]
     |> Enum.reduce([], fn pos, acc -> crate = String.slice(line, (pos-1)*4+1, 1) ; [{pos, crate} | acc] end)
  end)
  # reverse the list to pile up the crates in the right order starting with the crates at the bottom
  |> Enum.reverse()
  # populate the map representing the stacks starting with an empty map
  |> Enum.reduce(%{}, fn lst, m ->
    Enum.reduce(lst, m, fn {pos, crate}, m -> update_in(m[pos], fn nil -> [crate] ; lst -> [crate | lst] end) end)
  end)
  # |> IO.inspect(label: "init stacks")

File.stream!("input.txt")
|> Stream.drop(10)
|> Stream.map(&String.trim_trailing/1)
|> Stream.map(fn line ->
   Regex.run(~r/^move (\d+) from (\d) to (\d)$/, line, capture: :all_but_first)
   |> Enum.map(&String.to_integer/1)
end)
|> Enum.reduce(stacks, fn [n,src,dst], stacks -> Enum.reduce(1..n, stacks, fn _i, stacks ->
    [crate | crates] = stacks[src]
    stacks
    |> put_in([src], crates) # remove the crate from the source stack
    |> update_in([dst], fn nil -> [crate] ; lst -> [crate | lst] end) # put the crate in the destination stack
  end)
end)
# |> IO.inspect(label: "final stacks")
# transform the map of stacks into a list of stacks in the right order
|> Enum.sort_by(fn {pos, _lst} -> pos end)
# keep only the top crate
|> Enum.map(fn {_pos, [crate | _]} -> crate end)
|> Enum.join("")
|> tap(fn crates -> IO.puts "Crates on top of each stack: #{crates}" end)

elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

Part 2 is very similar to part 1. The way of moving multiple crates is simplified since a reduce disappears.

start = System.monotonic_time(:microsecond)

stacks = File.stream!("input.txt")
  |> Stream.take(8)
  |> Stream.map(fn line ->
    # pos = idx / 4 + 1 and idx = (pos - 1) * 4
    # Get the positions of the stacks going from 1 to 9. "[D]                     [N] [F]    " -> [1, 7, 8]
     Regex.scan(~r/\[\w\]/, line, return: :index) |> Enum.map(fn [{start, _end}] -> div(start,4)+1 end)
    # Get the letters on a line with their respective positions. [1, 7, 8] -> [{8, "F"}, {7, "N"}, {1, "D"}]
     |> Enum.reduce([], fn pos, acc -> crate = String.slice(line, (pos-1)*4+1, 1) ; [{pos, crate} | acc] end)
  end)
  # reverse the list to pile up the crates in the right order starting with the crates at the bottom
  |> Enum.reverse()
  # populate the map representing the stacks starting with an empty map
  |> Enum.reduce(%{}, fn lst, m ->
    Enum.reduce(lst, m, fn {pos, crate}, m -> update_in(m[pos], fn nil -> [crate] ; lst -> [crate | lst] end) end)
  end)
  # |> IO.inspect(label: "init stacks")

File.stream!("input.txt")
|> Stream.drop(10)
|> Stream.map(&String.trim_trailing/1)
|> Stream.map(fn line ->
   Regex.run(~r/^move (\d+) from (\d) to (\d)$/, line, capture: :all_but_first)
   |> Enum.map(&String.to_integer/1)
end)
|> Enum.reduce(stacks, fn [n,src,dst], stacks ->
  crates = Enum.take(stacks[src], n)
  stacks
  |> update_in([src], fn lst -> Enum.drop(lst, n) end) # remove the crates from the source stack
  |> update_in([dst], fn nil -> crates ; lst -> crates ++ lst end) # put the crates in the destination stack
end)
# |> IO.inspect(label: "final stacks")
# transform the map of stacks into a list of stacks in the right order
|> Enum.sort_by(fn {pos, _lst} -> pos end)
# keep only the top crate
|> Enum.map(fn {_pos, [crate | _]} -> crate end)
|> Enum.join("")
|> tap(fn crates -> IO.puts "Crates on top of each stack: #{crates}" end)

elapsed = System.monotonic_time(:microsecond) - start
IO.puts "Job done in #{elapsed} µs"

I put each stack of crates in a map, indexed by the stacks index so I could access them without traversing the list of stacks all the time

Thanks for pointing me to the Access module, there are indeed some neat stuff in there that I didn’t know about.

I implemented my own Stack module that just wraps List with some (hopefully) more stack-ish names. I haven’t decided if this was overkill or not, but I thought it was okay in the end. My solution is just converting the move instructions to stack operations (peek, drop, and push). I didn’t see a cleaner way of doing a pop and not peek and drop, This one might be one I revisit with fresh eyes and consider a major refactor if I think of a cleaner way after reviewing solutions here tomorrow. advent-of-code/2022/elixir/advent_of_code_2022.livemd at main · bmitc/advent-of-code · GitHub

Also, I hand-coded the initial stacks because I didn’t want to waste time decoding such terrible input.

(Gotta scroll to see the bulk of the solution.)

defmodule Day5 do
  @moduledoc """
  Solutions for Day 5
  """

  alias Stack

  @typedoc """
  Represents a crate where the name of the crate is an integer index
  """
  @type crate() :: non_neg_integer()

  @typedoc """
  Represents a single stack of crates
  """
  @type stack() :: Stack.t(crate())

  @type stack_name() :: non_neg_integer()

  @typedoc """
  Represents an instruction that says which crate to move from what stack
  to what stack
  """
  @type move_instruction() :: %{
          crate: crate(),
          from: stack_name(),
          to: stack_name()
        }

  @spec initial_stacks() :: [Stack.t()]
  def initial_stacks() do
    [
      ["F", "T", "N", "Z", "M", "G", "H", "J"],
      ["J", "W", "V"],
      ["H", "T", "B", "J", "L", "V", "G"],
      ["L", "V", "D", "C", "N", "J", "P", "B"],
      ["G", "R", "P", "M", "S", "W", "F"],
      ["M", "V", "N", "B", "F", "C", "H", "G"],
      ["R", "M", "G", "H", "D"],
      ["D", "Z", "V", "M", "N", "H"],
      ["H", "F", "N", "G"]
    ]
    |> Enum.map(&Stack.new/1)
  end

  @doc """
  Parse an assignment pair string into a tuple of section assignment ranges

  ## Examples:
    iex> Day4.parse_assignment_pair("2-4,6-8")
    {2..4, 6..8}
  """
  @spec parse_move_instruction(String.t()) :: move_instruction()
  def parse_move_instruction(string) do
    ["move", number, "from", from, "to", to] = String.split(string, " ", trim: true)

    %{
      number_of_crates: String.to_integer(number),
      from: String.to_integer(from) - 1,
      to: String.to_integer(to) - 1
    }
  end

  @doc """
  List of all move instructions
  """
  @spec move_instructions() :: [move_instruction()]
  def move_instructions() do
    Utilities.read_data(5)
    |> Enum.map(&parse_move_instruction/1)
  end

  @doc """
  Handle a move instruction for the case where crates are moved one at a time
  """
  @spec handle_move_instruction([stack()], move_instruction()) :: [stack()]
  def handle_move_instruction(stacks, move_instruction) do
    # Pop (really peek and drop) and push crates
    1..move_instruction.number_of_crates
    |> Enum.reduce(stacks, fn _, stacks ->
      # Get the crate that will be moved by peeking it from the "from" stack
      crate_to_move =
        stacks
        |> Enum.at(move_instruction.from)
        |> Stack.peek()

      # Drop the crate from the "from" stack and push it to the "to" stack
      stacks
      |> List.update_at(move_instruction.from, &Stack.drop/1)
      |> List.update_at(move_instruction.to, &Stack.push(&1, crate_to_move))
    end)
  end


  @doc """
  Handle a move instruction for the case where multiple crates are moved at once
  """
  @spec handle_move_instruction_in_order([stack()], move_instruction()) :: [stack()]
  def handle_move_instruction_in_order(stacks, move_instruction) do
    # Pop (really peek and drop) and push crates
    crates_to_move =
      stacks
      |> Enum.at(move_instruction.from)
      |> Stack.peek(move_instruction.number_of_crates)

    stacks
    |> List.update_at(
      move_instruction.from,
      &Stack.drop(&1, move_instruction.number_of_crates)
    )
    |> List.update_at(move_instruction.to, &Stack.push_as_one(&1, crates_to_move))
  end

  def part_one() do
    move_instructions()
    |> Enum.reduce(initial_stacks(), fn move_instruction, stacks ->
      handle_move_instruction(stacks, move_instruction)
    end)
    # Peek the top of all the final stacks
    |> Enum.map(&Stack.peek/1)
    |> Enum.join()
  end

  def part_two() do
    move_instructions()
    |> Enum.reduce(initial_stacks(), fn move_instruction, stacks ->
      handle_move_instruction_in_order(stacks, move_instruction)
    end)
    # Peek the top of all the final stacks
    |> Enum.map(&Stack.peek/1)
    |> Enum.join()
  end
end