hauleth

hauleth

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 - https://github.com/hauleth/advent-of-code/blob/master/2021/solutions.livemd

3
Post #12
Aetherus

Aetherus OP

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:

0
Post #13
hauleth

hauleth

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.

0
Post #14
michallepicki

michallepicki

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

1
Post #15
ruslandoga

ruslandoga

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
Post #16
epilgrim

epilgrim

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
Post #17
Aetherus

Aetherus OP

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

2
Post #18
stefanluptak

stefanluptak

My Liveview solution here: https://github.com/stefanluptak/advent-of-code/blob/main/day_04.livemd

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
Post #19
egze

egze

Did it in Livebook today:

y2021/day_04.md

0
Post #20
kokolegorille

kokolegorille

Once the Bingo module was written…

defmodule Bingo do
  defdelegate new_board(list), as: :new, to: __MODULE__.Board
  defdelegate play(board, value), to: __MODULE__.Board
  defdelegate score(tuple), to: __MODULE__.Board
  defdelegate score(board, value), to: __MODULE__.Board

  defmodule Cell, do: defstruct [val: nil, marked: false]
  defmodule Board do
    @size 5
    alias Bingo.Cell
    defstruct [grid: %{}, win: false]

    def new(list) do
      {board, _} = Enum.reduce(list, {%__MODULE__{}, 0}, &reducer/2)
      board
    end

    def play(%__MODULE__{grid: grid} = board, value) do
      case Enum.find(grid, fn {_coord, cell} -> cell.val == value end) do
        {coord, cell} ->
          new_grid = Map.put(grid, coord, %{cell | marked: true})
          %{board | grid: new_grid, win: is_winning(new_grid, coord)}
        nil -> board
      end
    end

    def score({board, value}), do: score(board, value)
    def score(board, value) do
      board.grid
      |> Enum.filter(fn {{_row, _col}, %{marked: marked}} -> not marked end)
      |> Enum.map(fn {_coord, cell} -> cell.val end)
      |> Enum.sum()
      |> Kernel.*(value)
    end

    defp reducer(val, {board, current}) do
      grid = Map.put(board.grid, to_coord(current), %Cell{val: val})
      {%{board | grid: grid}, current + 1}
    end

    defp to_coord(index), do: {div(index, @size), rem(index, @size)}

    defp is_winning(grid, {row, col}) do
      Enum.all?(get_line(:row, grid, row), fn {_coord, cell} -> cell.marked end) ||
      Enum.all?(get_line(:col, grid, col), fn {_coord, cell} -> cell.marked end)
    end

    defp get_line(:row, grid, index),
      do: Enum.filter(grid, fn {{row, _col}, _cell} -> row == index end)
    defp get_line(:col, grid, index),
      do: Enum.filter(grid, fn {{_row, col}, _cell} -> col == index end)
  end
end

… the rest was simple

defmodule Day4 do
  def part1 do
    {moves, boards} = load_data()
    {boards, move} = moves
    |> Enum.reduce_while(boards, fn move, boards ->
      boards = Enum.map(boards, &Bingo.play(&1, move))
      if Enum.any?(boards, & &1.win),
        do: {:halt, {boards, move}},
        else: {:cont, boards}
    end)
    boards
    |> Enum.find(& &1.win)
    |> Bingo.score(move)
  end

  def part2 do
    {moves, boards} = load_data()
    moves
    |> Enum.reduce_while(boards, fn move, boards ->
      boards = Enum.map(boards, &Bingo.play(&1, move))
      case boards do
        [%{win: true} = board] -> {:halt, {board, move}}
        [board] -> {:cont, [board]}
        boards -> {:cont, Enum.filter(boards, & not(&1.win))}
      end
    end)
    |> Bingo.score()
  end

  def load_data do
    "input.txt"
    |> File.read!()
    |> String.split("\n", trim: true)
    |> sanitize()
  end

  defp sanitize([head | rows]) do
    moves = head
    |> String.split(",", trim: true)
    |> Enum.map(& String.to_integer(&1))

    boards = rows
    |> Enum.map(&String.split(&1, " ", trim: true))
    |> Enum.chunk_every(5)
    |> Enum.map(&sanitize_list/1)
    |> Enum.map(&Bingo.new_board(&1))

    {moves, boards}
  end

  defp sanitize_list(list),
    do: Enum.flat_map(list, fn l -> Enum.map(l, & String.to_integer(&1)) end)
end
1
Post #21