Advent of Code 2023 - Day 4

Hello all, hopefully I post this before someone else does and I don’t dupe.

IMO Day 4 was much easier than Day 3 (yay, I can sleep before work!)

My set-up:

defmodule Card do
  defp to_list_numbers(str) do
    str 
    |> String.split(" ")
    |> Enum.filter(fn s -> String.length(s) !== 0 end)
    |> Enum.map(fn u ->
      {i, _} = Integer.parse(u)
      i
    end)
  end
  def parse("Card " <> rest) do
    [_, numbers] = rest |> String.split(":")
    [winning, player] = numbers |> String.split("|")
    [winning |> String.trim() |> to_list_numbers(), player |> String.trim() |> to_list_numbers()]
  end
end

cards = for card <- input |> String.split("\n"),
[winning_numbers, our_numbers] = Card.parse(card) do
  [winning_numbers, our_numbers]
end

Then part 1 was really simple (10 minutes from start for me to get here):


for [winning_numbers, our_numbers] <- cards
do
  case count_winning_cards.(our_numbers, winning_numbers) do
    n when n > 0 -> 2**(n-1)
    0 -> 0
  end
end |> Enum.sum()

Part 2 slightly less so (40 minutes from start to get here):


cards 
  |> Enum.with_index()
  |> Enum.reduce(
    List.duplicate(1, cards |> Enum.count()),
    fn {[winning, player], idx}, copies ->
      self_copies = Enum.at(copies, idx)
      won = count_winning_cards.(player, winning)
      slice = if won > 0, do: (idx+1)..(idx+won), else: ..
      copies |> Enum.with_index() |> Enum.map(
        fn {count, idx} ->
          if idx in slice, do: count + self_copies, else: count
        end
      )
    end
  ) |> Enum.sum()

The biggest time sink for me was remembering that 1..1 is a non-empty range in Elixir, so I needed to write the slice to be:

      slice = if won > 0, do: (idx+1)..(idx+won), else: ..
3 Likes

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

Here’s my code:

3 Likes

good point, probably just muscle memory from the previous days

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

7 Likes

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

2 Likes

Part Two really took me a minute, here.

Input

Processing

A simple map of id to map of mapsets of winners and picks helped me out, meaning that determining the number of winning picks was a MapSet.intersection/2 away. This is strictly more efficient than --/2, but probably doesn’t make a difference at these sizes.

Types
@type id :: non_neg_integer()

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

@type input :: {id(), card()}
Example Input
%{
  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])
  }
}

Source code available here.

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

Solution

Scoring a card is counting the number of winning picks, and then doing some :math.pow. I’m getting better at breaking calculations in part one apart such that some functions prove useful later in part two.

Source code available here.

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

Solution

This took a while. The insights that got me over the finish line was that

  • the very final cards must always have no/few winners, since there is nothing to copy after them
  • earlier cards are always defined by the value of later ones

This means if you start at the end of the cards, you can walk backwards through the card list determining each one’s value without recursive operations or actually generating copies of anything.

First I count how many wins each card has, then I generate a map of id => [id] to reference what each card creates a copy of.

Then I generate a map of how many copies each id must create, starting from the last_id. list_id must always have Map.get(copies, last_id) == [], so its count is 1; Map.get(copies, last_id -1) must be either [] or [last_id], and can reliably look up the number of copies since last_id must have already been computed, etcera.

Source code available here.

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 :sweat_smile:

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.

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).

3 Likes
import AOC

aoc 2023, 4 do
  def p1(input) do
    input
    |> winning_cards()
    |> Enum.unzip()
    |> elem(1)
    |> Enum.map(fn 0 -> 0; n -> 2 ** (n-1) end)
    |> Enum.sum()
  end

  def winning_cards(input) do
    process = fn card -> card |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1) |> MapSet.new end
    input
    |> String.split("\n", trim: true)
    |> Enum.map(
      fn line ->
        ["Card " <> n, cards] = String.split(line, ": ")
        card_strs = String.split(cards, "|")
        [winning, holding] = card_strs |> Enum.map(process)
        {String.to_integer(String.trim(n)), MapSet.intersection(winning, holding) |> Enum.count()}
      end
    )
  end

  def p2(input) do
    input
    |> winning_cards()
    |> Enum.map(fn {i, n} -> {i, {1, n}} end)
    |> process()
    |> Enum.unzip()
    |> elem(1)
    |> Enum.unzip()
    |> elem(0)
    |> Enum.sum()
  end

  def process([]), do: []
  def process([{i, {0, n}} = x | xs]), do: [x | process(xs)]
  def process([{i, {count, multiplier}} = x | xs]) do
    {before, after_} = Enum.split(xs, multiplier)
    [x | process(Enum.map(before, fn {i, {c, n}} -> {i, {c + count, n}} end) ++ after_)]
  end
end
1 Like

Here it is. It’s fun how we are mostly doing the same thing but nobody writes it the same.

defmodule AdventOfCode.Y23.Day4 do
  alias AoC.Input, warn: false

  def read_file(file, _part) do
    Input.stream!(file, trim: true)
  end

  def parse_input(input, _part) do
    input
    |> Enum.map(fn "Card " <> rest ->
      rest = String.trim_leading(rest)
      {card_id, ": " <> rest} = Integer.parse(rest)
      [winnings, playings] = String.split(rest, " | ")
      winnings = list_of_ints(winnings)
      playings = list_of_ints(playings)
      {card_id, winnings, playings}
    end)
  end

  defp list_of_ints(str) do
    str |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
  end

  def part_one(problem) do
    problem
    |> Enum.map(fn {_, winnings, playings} ->
      wins = MapSet.new(winnings)
      plays = MapSet.new(playings)
      pow = MapSet.size(MapSet.intersection(wins, plays))
      trunc(:math.pow(2, pow - 1))
    end)
    |> Enum.sum()
  end

  def part_two(problem) do
    problem
    |> Enum.map_reduce(%{}, fn {card_id, winnings, playings}, acc ->
      n_cards = 1 + Map.get(acc, card_id, 0)
      wins = MapSet.new(winnings)
      plays = MapSet.new(playings)

      acc =
        case MapSet.size(MapSet.intersection(wins, plays)) do
          0 ->
            acc

          n_wins ->
            adds = (card_id + 1)..(card_id + n_wins)

            Enum.reduce(adds, acc, fn next_card_id, acc ->
              Map.update(acc, next_card_id, n_cards, &(&1 + n_cards))
            end)
        end

      {n_cards, acc}
    end)
    |> elem(0)
    |> Enum.sum()
  end
end

@Aetherus I just read your post and indeed there is no need to parse as integers. But with my code it is actually faster when I pay the cost to do it. Probably because it speeds up the matching in Map.get

2 Likes

My solution :

defmodule Scratchcards do
  import NimbleParsec

  defparsec(
    :parse_line,
  
    ignore(string("Card") |> repeat(ignore(string(" "))))
    |> integer(min: 1, max: 3)
    |> ignore(string(":"))
    |> ignore(repeat(ignore(string(" "))))
    |> tag(repeat(integer(min: 1, max: 2) |> repeat(ignore(string(" ")))), "numbers")
    |> ignore(string("|"))
    |> repeat(ignore(string(" ")))
    |> tag(repeat(integer(min: 1, max: 2) |> repeat(ignore(string(" ")))), "winning")
  )
  defp points(0), do: 0

  defp points(x), do: 2 ** (x - 1)


  defp calculate_score(line) do
    {:ok, [_, {"numbers", numbers}, {"winning", winning}], _, _, _, _} = parse_line(line) 
    MapSet.intersection(MapSet.new(numbers), MapSet.new(winning))
    |> MapSet.to_list()
    |> length()
  end

  def part1(input) do
    input
    |> String.split("\n")
    |> Enum.map(fn line ->
      line
      |> calculate_score()
      |> points()
    end)
    |> Enum.sum()
  end

  defp count(input, pos, total) do
    
    score = Enum.at(input, pos)
    if score > 0 do
      Enum.reduce((pos + 1)..(pos + score), total, fn(i, total) -> 
        count(input, i, total + 1)
      end)
    else
      total
    end
  end

  def part2(input) do
    scores = input
    |> String.split("\n")
    |> Enum.map(fn line ->
      calculate_score(line)
    end)
    
    scores
    |> Enum.with_index()
    |> Enum.reduce(0, fn({_v, i}, total) ->
       total + count(scores, i, 1)
    end)
  end
end

Scratchcards.part2(input)
2 Likes

Parsing

cards =
  puzzle_input
  |> String.split("\n", trim: true)
  |> Enum.map(fn "Card" <> rest ->
    {id, ": " <> rest} = rest |> String.trim() |> Integer.parse()

    [wins, inputs] =
      rest
      |> String.split(" | ")
      |> Enum.map(fn part ->
        part
        |> String.split()
        |> Enum.map(&String.to_integer/1)
      end)

    {id, wins, inputs}
  end)

Part 1

cards
|> Enum.map(fn {_, wins, inputs} ->
  matches = length(wins) - length(wins -- inputs)

  if matches > 0, do: 2**(matches - 1), else: 0
end)
|> dbg()
|> Enum.sum()

Part 2

cards
|> Enum.reduce(%{}, fn {id, wins, inputs}, acc ->
  matches = length(wins) - length(wins -- inputs)
  {current, acc} = Map.get_and_update(acc, id, fn v ->
    v = (v || 0) + 1
    {v, v}
  end)

  Enum.reduce(1..matches//1, acc, &Map.update(&2, id + &1, current, fn a -> a + current end))
end)
|> Map.values()
|> Enum.sum()
2 Likes

Learned Map.get_and_update.

3 Likes

My beginner’s solution, Day 4.
I had a lot of fun implementing a function using [tail | head] syntax. Is it idiomatic?

defmodule Day04 do

  def part2(input) do
   input
    |> String.split("\n")
    |> Enum.map(&parse_to_map_of_your_and_winning_numbers/1)
    |> Enum.map(&amount_of_winning_numbers/1)  
    |> Enum.reverse
    # [0, 0, 1, 2, 2, 4]
    |> total_scratchcards
  end
  
  def part1(input) do
    input
    |> String.split("\n")
    |> Enum.map(&parse_to_map_of_your_and_winning_numbers/1)
    |> Enum.map(&amount_of_winning_numbers/1)
    |> Enum.map(&calculate_worth/1)
    |> Enum.sum
  end 

  def parse_to_map_of_your_and_winning_numbers(line) do
    # "Card 1: 41 48 83 86 17 | 83 86 6 31 17 9 48 53"
    line
    |> String.split(": ")
    |> List.last
    |> String.split(" | ")
    |> Enum.map(fn x -> x
                |> String.split
                |> Enum.map(&String.to_integer/1)
                end)
    |> then(fn [w, y] -> %{your: y, winning: w} end)
    # %{ winning: [41, 48, 83, 86, 17], 
    #       your: [83, 86, 6, 31, 17, 9, 48, 53] }    
  end

  def amount_of_winning_numbers(card) do
    # %{ winning: [41, 48, 83, 86, 17], 
    #       your: [83, 86, 6, 31, 17, 9, 48, 53] }    
    for your_number <- card.your do
      Enum.member?(card.winning, your_number)
    end
    |> Enum.count(&(&1))
  end

  def calculate_worth(0), do: 0
  def calculate_worth(n), do: :math.pow(2, n-1) |> round

  def total_scratchcards(how_many_wins_list, scratchcards_amount_list \\ [])
  def total_scratchcards([], amount_list), do: Enum.sum(amount_list)
  def total_scratchcards([head | tail], amount_list) do
    amount = amount_list
      |> Enum.take(head)
      |> Enum.sum
      |> Kernel.+(1)
    
    total_scratchcards(tail, [amount] ++  amount_list)
  end

end

I was proud of my recursive copy function, until I saw @bjorng’s :flushed:

edit: tidied up enough to share. Both parts under a ms.

  def part1(input) do
    input
    |> Enum.map(fn 0 -> 0; num_winners -> 2 ** (num_winners - 1) end)
    |> Enum.sum()
  end

  def part2(input) do
    input
    |> Enum.map(fn num_winners -> {_num_copies = 1, num_winners} end)
    |> copy()
    |> Enum.sum()
  end

  def copy([]), do: []

  def copy([{num_copies, num_winners} | rest]) do
    {to_copy, left_alone} = Enum.split(rest, num_winners)

    copied =
      Enum.map(to_copy, fn {child_num_copies, num_winners} ->
        {num_copies + child_num_copies, num_winners}
      end)

    [num_copies | copy(copied ++ left_alone)]
  end
2 Likes

Solved part 2 with a single for reduce:

2 Likes

For me it was the easier this year. quite fun to solve.

1 Like