Advent of Code 2021 - Day 4

This topic is about the Advent of Code 2021 - Day 4.

Thanks to @bjorng , we now have a new Private Leaderboard.

The entry code is:
370884-a6a71927

2 Likes

It is already getting a bit trickier. Here is my solution:

1 Like

Today I tried LiveBook on the new Elixir 1.13.0, and accidentally deleted my part 1 code, so I just post my part 2:

[moves | boards] =
  File.read!("input.txt")
  |> String.split("\n\n", trim: true)

# [integer]
moves =
  moves
  |> String.split(~r/\D/, trim: true)
  |> Enum.map(&String.to_integer/1)

# %{val => {row, col}}
boards =
  boards
  |> Enum.map(&String.split/1)
  |> Enum.map(&Enum.chunk_every(&1, 5))
  |> Enum.map(fn board ->
    for {row, i} <- Enum.with_index(board), {num, j} <- Enum.with_index(row), into: %{} do
      {String.to_integer(num), {i, j}}
    end
  end)

{_, {move, last_winning_board}} = 
  for move <- moves, reduce: {boards, nil} do
    {boards, last_win} ->
      boards = Enum.map(boards, fn board ->
        Map.delete(board, move)
      end)
      {wins, boards} = Enum.split_with(boards, fn board ->
        Enum.any?(0..4, fn i ->
          Enum.all?(board, &not match?({_, {^i, _}}, &1))
        end) or
        Enum.any?(0..4, fn j ->
          Enum.all?(board, &not match?({_, {_, ^j}}, &1))
        end)
      end)

      case wins do
        [] -> {boards, last_win}
        _ -> {boards, {move, List.last(wins)}}
      end
  end

last_winning_board
|> Map.keys()
|> Enum.sum()
|> Kernel.*(move)
|> IO.inspect()

It feels a little bit tricky implementing a modification-based algorithm in an immutable way.

2 Likes

Sorry for posting twice. There was a network issue when I tried to edit my answer, and I don’t know how to delete one.

1 Like

It’s starting to get difficult already, at least from the perspective of Elixir. It’s difficult to come up with a solution fast that is mutation and early return friendly on a matrix like data.

3 Likes

I usually use %{{x, y} => val} to represent a matrix, but for today’s challenge, I recognized that I need to look up {x, y} by values, so I swapped the keys and the values.

3 Likes

Here I am thinking the opposite direction, I am thinking %{value => {row, col}} where row = div(idx, 5) and col = rem(idx, 5). That way I can just remove the value into a bucket of rowlist, collist as I move forward. But it’s feeling slightly weird and verbose.

Update: Seems like you’re doing the same thing. Sorry, brain’s not keeping up with eyes lol.

Ah, finally got the first one right, also, I got to use the new Map.map :smiley:

UPDATE: Did both parts, Part 2 was quicker to implement, but I don’t have a good feeling about this code for some reason.

defmodule AdventOfCode.Y2021.Day04 do
  @moduledoc """
  --- Day 4: Giant Squid ---
  Problem Link: https://adventofcode.com/2021/day/4
  """
  use AdventOfCode.Helpers.InputReader, year: 2021, day: 4

  def run_1, do: input!() |> parse() |> play_1()
  def run_2, do: input!() |> parse() |> play_2()

  def parse(data) do
    [order_data | board_data] = String.split(data, "\n\n", trim: true)
    {get_orders(order_data), get_boards(board_data)}
  end

  defp get_orders(data), do: data |> String.split(",") |> Enum.map(&String.to_integer/1)

  defp get_boards(data), do: data |> Enum.with_index() |> Enum.map(&get_board/1)

  defp get_board({data, idx}) do
    data
    |> String.split("\n")
    |> Enum.flat_map(fn line ->
      line
      |> String.split(" ", trim: true)
      |> Enum.map(&String.to_integer/1)
    end)
    |> Enum.with_index()
    |> Enum.into(%{})
    |> Map.map(fn {_, idx} -> {div(idx, 5), rem(idx, 5)} end)
    |> then(&board_state(&1, idx))
  end

  defp board_state(board, idx), do: {idx, board, [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]}

  def play_1({orders, board_states}) do
    orders
    |> Enum.reduce_while(board_states, fn order, acc ->
      acc = Enum.map(acc, &mark_board(&1, order))

      case get_winner(acc) do
        nil -> {:cont, acc}
        board -> {:halt, {score(board), order}}
      end
    end)
    |> Tuple.product()
  end

  def score(board), do: board |> Map.keys() |> Enum.sum()

  defp mark_board({idx, board, rows, cols} = state, order) do
    case Map.pop(board, order) do
      {{row, col}, board} ->
        {idx, board, List.update_at(rows, row, &(&1 + 1)), List.update_at(cols, col, &(&1 + 1))}

      {nil, _} ->
        state
    end
  end

  defp get_winner(board_states) do
    Enum.reduce_while(board_states, nil, fn {_, board, rows, cols}, _ ->
      5 in rows or (5 in cols && {:halt, board}) || {:cont, nil}
    end)
  end

  def play_2({orders, board_states}) do
    orders
    |> Enum.reduce({board_states, []}, fn order, {acc, winners} ->
      acc = Enum.map(acc, &mark_board(&1, order))

      {acc,
       [Enum.map(get_winners(acc), fn {idx, board} -> {idx, score(board), order} end) | winners]}
    end)
    |> elem(1)
    |> Enum.reverse()
    |> Enum.drop_while(&Enum.empty?/1)
    |> Enum.flat_map(&Function.identity/1)
    |> last_winner(Enum.count(board_states), MapSet.new())
    |> Tuple.product()
  end

  defp last_winner([{idx, score, order} | rest], size, map_set) do
    set = MapSet.put(map_set, idx)
    (Enum.count(set) == size && {score, order}) || last_winner(rest, size, set)
  end

  defp get_winners(board_states) do
    Enum.reduce(board_states, [], fn {idx, board, rows, cols}, acc ->
      ((5 in rows or 5 in cols) && [{idx, board} | acc]) || acc
    end)
  end
end
2 Likes

My solution: y2021/day_04.ex

I’m already ashamed by posting this horrible Part 1.
At this point, I’ll have to switch to normal function definitions because it’s becoming a spaghetti mess with anons and it’s just Day 4.

Don’t ask how I did Part 2, I have to clean both solutions up first.
It’s a challenge trying to do this in an immutable way.

# Day 4

## Input

<!-- livebook:{"livebook_object":"cell_input","name":"input","type":"text","value":"7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1  22 13 17 11  0  8  2 23  4 24 21  9 14 16  7  6 10  3 18  5  1 12 20 15 19   3 15  0  2 22  9 18 13 17  5 19  8  7 25 23 20 11 10 24  4 14 21 16 12  6  14 21 17 24  4 10 16 15  9 19 18  8 23 26 20 22 11 13  6  5  2  0 12  3  7"} -->

```elixir
# Livebook Input (atleast the default one) doesn't support multiline
[winning_nums | boards] = IO.gets(:input) |> String.split(~r{\s}, trim: true)

winning_nums =
  winning_nums
  |> String.split(",")
  |> Enum.map(&String.to_integer/1)

boards =
  boards
  |> Enum.map(&String.to_integer/1)
  |> Enum.chunk_every(5)
  |> Enum.chunk_every(5)
```

## Part 1

```elixir
calculate_card = fn bingo_card, last_number ->
  List.flatten(bingo_card)
  |> Enum.reject(&(&1 == -1))
  |> Enum.sum()
  |> Kernel.*(last_number)
  |> IO.inspect()

  # exit after first find
  Kernel.exit(:ok)
end

# mark all matching numbers inside boards
mark_boards = fn boards, n ->
  List.flatten(boards)
  |> Enum.map(&if(&1 == n, do: -1, else: &1))
  # convert back to 5x5 boards
  |> Enum.chunk_every(5)
  |> Enum.chunk_every(5)
end

check_boards = fn boards, last_n ->
  Enum.each(boards, fn b ->
    for i <- 0..4 do
      # horizontal || vertical
      if Enum.sum(Enum.at(b, i)) == -5 || Enum.sum(Enum.map(b, &Enum.at(&1, i))) == -5 do
        calculate_card.(b, last_n)
      end
    end
  end)

  boards
end

Enum.reduce(winning_nums, boards, fn n, b -> mark_boards.(b, n) |> check_boards.(n) end)
```

## Part 2

```elixir
# So ugly I had to hide it
```

1 Like

Again, LiveBook:


Day 4

Input

This time it is a little bit more convoluted, as there are 2 parts of the input.
Fortunately we can easily disect the parts via pattern matching.

Technically the conversion to the numbers is not needed, but it does no harm
and provides additional layer of safety against some whitespace characters left there
and here.

The Day4.win/2 function is manually unrolled, as it is easier to write than some
random jumping in the list.

[numbers | bingos] =
  File.read!("day4.txt")
  |> String.split("\n\n", trim: true)

numbers =
  numbers
  |> String.trim()
  |> String.split(",")
  |> Enum.map(&String.to_integer/1)

bingos =
  bingos
  |> Enum.map(fn bingo ->
    bingo
    |> String.split(~r/\s+/, trim: true)
    |> Enum.map(&String.to_integer/1)
  end)

defmodule Day4 do
  def win(
        [
          a1, a2, a3, a4, a5,
          b1, b2, b3, b4, b5,
          c1, c2, c3, c4, c5,
          d1, d2, d3, d4, d5,
          e1, e2, e3, e4, e5
        ],
        nums
      ) do
    # Rows
    all_in([a1, a2, a3, a4, a5], nums) or
    all_in([b1, b3, b3, b4, b5], nums) or
    all_in([c1, c2, c3, c4, c5], nums) or
    all_in([d1, d2, d3, d4, d5], nums) or
    all_in([e1, e2, e3, e4, e5], nums) or
    # Columns
    all_in([a1, b1, c1, d1, e1], nums) or
    all_in([a2, b2, c2, d2, e2], nums) or
    all_in([a3, b3, c3, d3, e3], nums) or
    all_in([a4, b4, c4, d4, e4], nums) or
    all_in([a5, b5, c5, d5, e5], nums) or
    # Diagonals
    all_in([a1, b2, c3, d4, e5], nums) or
    all_in([a5, b4, c3, d2, e1], nums)
  end

  def not_matched(bingo, nums) do
    Enum.reject(bingo, &(&1 in nums))
  end

  defp all_in(list, nums) do
    Enum.all?(list, &(&1 in nums))
  end
end

Task 1

We simply traverse the numbers list aggregating the numbers (order doesn’t really matter,
here we aggregate them in reverse order to speedup the code). When we have enough numbers
that any of the bingos is winning one, then we halt the reduction and return computed
result.

numbers
|> Enum.reduce_while([], fn elem, acc ->
  matches = [elem | acc]

  case Enum.find(bingos, &Day4.win(&1, matches)) do
    nil -> {:cont, matches}
    bingo -> {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
  end
end)

Task 2

numbers
|> Enum.reduce_while({bingos, []}, fn elem, {bingos, acc} ->
  matches = [elem | acc]

  case bingos do
    [bingo] ->
      if Day4.win(bingo, matches) do
        {:halt, Enum.sum(Day4.not_matched(bingo, matches)) * elem}
      else
        {:cont, {bingos, matches}}
      end

    _ ->
      {:cont, {Enum.reject(bingos, &Day4.win(&1, matches)), matches}}
  end
end)

Whole project can be watched there - advent-of-code/solutions.livemd at master · hauleth/advent-of-code · GitHub

3 Likes

I’m surprised that you can work out the answers taking diagonals into account.

If all numbers in any row or any column of a board are marked, that board wins . (Diagonals don’t count.)

By the way, I also checked diagonals until I failed in Part 2. :sweat_smile:

Ah, missed that. This probably is why I needed to spend a little more on Task 2, but in general it doesn’t change the result.

You got lucky! Every user’s input is different and many people got stuck there :slight_smile:

1 Like

I represented the boards as binaries,

<<
 22, 13, 17, 11, 0,
  8,  2, 23,  4, 24,
 21,  9, 14, 16,  7,
  6, 10,  3, 18,  5,
  1, 12, 20, 15, 19
>>

where marked number becomes <<-1::signed>>

defp mark_board(board, number) do
  String.replace(board, <<number>>, <<-1>>, global: false)
end

and used binary pattern matching to identify winners:

marked_row = quote(do: <<-1::40-signed>>)

column_patterns = [
  quote(do: <<-1::signed, _, _, _, _>>),
  quote(do: <<_, -1::signed, _, _, _>>),
  quote(do: <<_, _, -1::signed, _, _>>),
  quote(do: <<_, _, _, -1::signed, _>>),
  quote(do: <<_, _, _, _, -1::signed>>)
]

winning_patterns =
  List.flatten([
    # rows
    quote(do: <<unquote(marked_row), _::bytes>>),
    quote(do: <<_::5-bytes, unquote(marked_row), _::bytes>>),
    quote(do: <<_::10-bytes, unquote(marked_row), _::bytes>>),
    quote(do: <<_::15-bytes, unquote(marked_row), _::bytes>>),
    quote(do: <<_::20-bytes, unquote(marked_row)>>),
    # columns
    for pattern <- column_patterns do
      quote(do: <<unquote_splicing(List.duplicate(pattern, 5))>>)
    end
  ])

for pattern <- winning_patterns do
  defp winner?(unquote(pattern)), do: true
end

defp winner?(<<_::25-bytes>>), do: false

To calculate the sum I used

def unmarked_sum(board)
  Enum.sum(for <<cell::signed <- board>>, cell > 0, do: cell)
end

Full

3 Likes

My solution
I created a struct that contained a reverse index {value -> {row, col}}, the sum of the fields, and the amount of unfinished columns and rows

defmodule Board do
  defstruct [:index, :row_count, :column_count, :sum, :winner]
  def new(matrix)
  # Returns the updated board, marking it as a winner if one of it's columns or rows is completed
  def draw(board, number)

with that in place, the solution is

    {draws, boards} = Support.input()

    {winner, draw} =
      Enum.reduce_while(
        draws,
        boards,
        fn draw, boards ->
          boards = Enum.map(boards, &Board.draw(&1, draw))
          winner = Enum.find(boards, & &1.winner)

          if winner do
            {:halt, {winner, draw}}
          else
            {:cont, boards}
          end
        end
      )

    IO.inspect(winner.sum * draw, label: "Part 1")

    {_, winner, draw} =
      Enum.reduce(
        draws,
        {boards, nil, nil},
        fn draw, {boards, last_winner, last_draw} ->
          boards = Enum.map(boards, &Board.draw(&1, draw))
          {winners, boards_left} = Enum.split_with(boards, & &1.winner)
          winner = List.last(winners)

          if winner do
            {boards_left, winner, draw}
          else
            {boards_left, last_winner, last_draw}
          end
        end
      )

    IO.inspect(winner.sum * draw, label: "Part 2")
  end
1 Like

Wow, that was a whole lot of fun reading your solutions! I learned new ways of metaprogramming from your code. :heart:

2 Likes

My Liveview solution here: advent-of-code/day_04.livemd at main · stefanluptak/advent-of-code · GitHub

Surprisingly, this day puzzle was a lot more pleasant for me compared to the Day 03 (esp part 2). That frustrated me a lot. :smiley:

1 Like

Did it in Livebook today:

y2021/day_04.md