Advent of Code 2023 - Day 4

You don’t have to convert those numeric strings to integers.

Here’s my code:

https://github.com/Aetherus/advent-of-code/blob/master/2023/day-04.livemd

good point, probably just muscle memory from the previous days

I also found today’s puzzle much easier than yesterday’s.

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

Wow, today I learned --, that’s a really clean way to get the winning numbers!

Part Two really took me a minute, here.

Input

@type id :: non_neg_integer()

@type card :: %{winners :: MapSet.t(), picks :: MapSet.t()}

@type input :: {id(), card()}

%{
  1 => %{
    picks: MapSet.new([6, 9, 17, 31, 48, 53, 83, 86]),
    winners: MapSet.new([17, 41, 48, 83, 86])
  },
  2 => %{
    picks: MapSet.new([17, 19, 24, 30, 32, 61, 68, 82]),
    winners: MapSet.new([13, 16, 20, 32, 61])
  },
  3 => %{
    picks: MapSet.new([1, 14, 16, 21, 63, 69, 72, 82]),
    winners: MapSet.new([1, 21, 44, 53, 59])
  },
  4 => %{
    picks: MapSet.new([5, 51, 54, 58, 59, 76, 83, 84]),
    winners: MapSet.new([41, 69, 73, 84, 92])
  },
  5 => %{
    picks: MapSet.new([12, 22, 30, 36, 70, 82, 88, 93]),
    winners: MapSet.new([26, 28, 32, 83, 87])
  },
  6 => %{
    picks: MapSet.new([10, 11, 23, 35, 36, 67, 74, 77]),
    winners: MapSet.new([13, 18, 31, 56, 72])
  }
}

defmodule AoC.Day.Four.Input do
  def parse(input_file \\ System.fetch_env!("INPUT_FILE")) do
    input_file
    |> File.read!()
    |> String.split("\n")
    |> Enum.reject(&(&1 == ""))
    |> Enum.map(&parse_card/1)
    |> Map.new()
  end

  def parse_card("Card" <> card) do
    card = String.trim(card)
    {id, rest} = Integer.parse(card)
    <<": ">> <> numbers = rest

    [winners, picks] =
      String.split(numbers, "|", parts: 2)
      |> Enum.map(&String.trim/1)
      |> Enum.map(&parse_numbers/1)

    {id, %{winners: winners, picks: picks}}
  end

  def parse_numbers(numbers) do
    numbers
    |> String.split(~r{\s+})
    |> Enum.map(&String.to_integer/1)
    |> MapSet.new()
  end
end

Part One

defmodule AoC.Day.Four.Part.One do
  def solve(cards) do
    cards
    |> Enum.map(fn {_id, card} ->
      card
      |> number_of_wins()
      |> score_card()
    end)
    |> Enum.sum()
  end

  def winning_numbers(card) do
    MapSet.intersection(card.winners, card.picks)
  end

  def number_of_wins(card) do
    card
    |> winning_numbers()
    |> MapSet.size()
  end

  def score_card(number_of_wins)

  def score_card(0), do: 0

  def score_card(number_of_wins) when number_of_wins > 0 do
    round(:math.pow(2, number_of_wins - 1))
  end
end

Part Two

defmodule AoC.Day.Four.Part.Two do
  import AoC.Day.Four.Part.One

  def solve(cards) do
    wins =
      Map.new(cards, fn {id, card} ->
        {id, number_of_wins(card)}
      end)

    copies =
      Map.new(wins, fn {id, wins} ->
        {id, Range.new(id + 1, id + wins, 1) |> Range.to_list()}
      end)

    counts =
      copies
      |> Enum.into([])
      |> Enum.sort_by(fn {id, _copies} -> id end)
      |> Enum.reverse()
      |> Enum.reduce(%{}, fn
        {id, []}, counts ->
          Map.put(counts, id, 1)

        {id, copies}, counts ->
          count =
            copies
            |> Enum.map(&Map.get(counts, &1))
            |> Enum.sum()

          Map.put(counts, id, count + 1)
      end)

    counts |> Map.values() |> Enum.sum()
  end
end

Once again parsing the input was the biggest challenge. Once I had that both parts went quickly. I kept thinking the card IDs would be necessary in Part 2 but when they weren’t I didn’t bother cleaning them out of the code.

Full code here.

defmodule Parser do
    alias AocToolbox.Input

    def parse_raw_cards(text) do
      text
      |> Input.lines()
      |> Enum.map(&parse_card/1)
    end

    defp parse_card(<<"Card ", rest::binary>>), do: parse_card(rest)
    defp parse_card(<<" ", rest::binary>>), do: parse_card(rest)

    defp parse_card(<<d, rest::binary>>) when d > 47 and d < 58 do
      {card_id, card} = parse_num(d - 48, rest)

      {card_id, parse_card_nums(card, MapSet.new(), MapSet.new(), :winners)}
    end

    defp parse_num(acc, <<d, rest::binary>>) when d > 47 and d < 58 do
      parse_num(acc * 10 + (d - 48), rest)
    end

    defp parse_num(acc, bin), do: {acc, bin}

    defp parse_card_nums("", winners, matches, set), do: {winners, matches}

    defp parse_card_nums(<<d, rest::binary>>, winners, matches, set) when d > 47 and d < 58 do
      {next_num, card} = parse_num(d - 48, rest)

      if set == :winners do
        parse_card_nums(card, MapSet.put(winners, next_num), matches, set)
      else
        parse_card_nums(card, winners, MapSet.put(matches, next_num), set)
      end
    end

    defp parse_card_nums(<<"|", rest::binary>>, winners, matches, _set),
      do: parse_card_nums(rest, winners, matches, :matches)

    defp parse_card_nums(<<_s, rest::binary>>, winners, matches, set),
      do: parse_card_nums(rest, winners, matches, set)
  end

I’m sure there’s something really clever to be done with bit shifting for part 1 but I didn’t bother trying.

I must be tired. I can’t seem to figure out how reversing the list helps you here. The thing that made it click for me was that for each copy operation you make as many copies as the number of current cards you have.

My solution skips creating any copies—instead I generate a map of what card ids would get copied. Then I start with the base case of “the last card cannot generate any copies as there is nothing left to copy, it must have the value of 1” and work backwards, translating each list of “these cards would get copied” to their innate value.

The value of later cards must be computed by the time we get to any given earlier card going backwards. The resulting counts map is kind of odd—for the example set,

%{
  1 => 15,
  2 => 7,
  3 => 4,
  4 => 2,
  5 => 1,
  6 => 1
}

Later cards like the final 6 is only worth one point, but then the value of earlier cards factor in the repetition of their reference to later ones.

I’m tired as well though, so I can’t tell if it’s clever or not.

I just woke up so the main obstacle for me was figuring out what it wanted me to do for part 2

I couldn’t think about an efficient “math-y” way to do it for part 2, so I just pre-save the intersections in a map and check them all the time. I thought it was going to be super slow, but it finishes in ~140ms, which is good enough for me.

https://github.com/mexicat/aoc-2023/blob/main/lib/aoc/day_04.ex

I heard that when running a -- b, the Erlang runtime will first convert b to a red-black tree if b is long enough (maybe when length(b) > 32). If that’s the case, then a -- a -- b can be as performant as MapSet.intersection(set1, set2).