Advent of Code 2021 - Day 4

Learning Questions & Discussions Coding Challenges
22

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 Like
23

Hi all; great to see all the different approaches. I’ve been doing AOC for some years now, but this year in elixir. I’ve been using elixir for some small projects over the last months, but AOC is a fun way to spend some more time learning the language and finding all kinds of nifty stuff in the standard libraries.

My day 4 in two different versions:

1 Like
24

I used MapSets all the way…

defmodule Day4 do
  def board_to_sets(str_board) do
    str_board = Enum.map(str_board, &String.split/1)
    hor_lines = 
      for line <- str_board do
        for num <- line do
          String.to_integer(num)
        end
      end
    vert_lines = Enum.zip(hor_lines) |> Enum.map(&Tuple.to_list/1)
    diag1 = for i <- 0..4, do: Enum.at(Enum.at(hor_lines, i), i)
    diag2 = for i <- 0..4, do: Enum.at(Enum.at(hor_lines, i), 4-i)
    hor_lines ++ vert_lines ++ [diag1, diag2]
    |> Enum.map(&MapSet.new/1)
  end

  def bingo?(input, board) do
    Enum.any?(board, fn line -> MapSet.size(MapSet.intersection(input, line)) == 5 end)
  end

  def get_first_bingo_board(input, boards), do: get_first_bingo_board(input, boards, [])

  def get_first_bingo_board([h | tail], boards, current_numbers) do
    current_numbers = [h | current_numbers]
    set_current_numbers = MapSet.new(current_numbers)
    found_boards = for board <- boards, bingo?(set_current_numbers, board), do: board
    case found_boards do
      [] -> get_first_bingo_board(tail, boards, current_numbers)
      [board | _] -> [board, current_numbers]
    end
  end

  # For the last board, we will start with the reverse input list, and find
  # the length of the input which has 99 bingos - i.e. 1 less that total boards
  def get_last_bingo_board([_h | tail] = current_numbers, boards) do
    set_current_numbers = MapSet.new(current_numbers)
    found_boards = for board <- boards, bingo?(set_current_numbers, board), do: board
    case length(found_boards) do
      100 -> get_last_bingo_board(tail, boards)
      99 -> [MapSet.difference(MapSet.new(boards), MapSet.new(found_boards)), length(current_numbers)]
    end
  end
end
25

First part was easy with a naive solution. Second part I kept getting the wrong answer, possibly because my method for checking winners was off somehow. Reading through here helped, especially @princemaple’s solution. Using the cell value as the key with coords as the value in the map was the critical piece for me from that solution.

26

Hi all, Similar to @zevv I too am doing it in elixir for the first time and I’m also trying to force my brain into writing the code in a manner that is as functional as possible (which not exactly easy for someone who’s been doing all manner of imperative languages for years)

I do think that day four did turn out quite elegant, but would love to hear additional feedback.

1 Like
27

Day 4 solution

I opted to just create a BingoBoard struct that kept track of the state of the board, the score, and used single element tuple to mark a number.

Criteria for each part was implemented using Enum.reduce_while.

28

My solution now cleaned up a bit:

I still think it could be better organized but I’m tired of it. This year seems tougher the last couple days than I remember the early going last year. Maybe I’m just rusty.

29

Here’s my try.

A few things I tried:

  • The board is represented as a map, with {x, y} => number
  • When a number is taken, the {pos, number} will be removed from the map
  • Checking diagonally at {0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4} to see if any column or row has been fully taken
30

I tried something a little different - instead of keeping track of the position of called numbers, I only keep track of the number of times a number has been called in a specific row/column. When a row or column then has 5, I know that board had a bingo.

I calculated the number of moves to win a bingo for each board, which made part two really easy. I just needed to use the Enum.min/2 or Enum.max/2 functions to determine the board that was the winner/loser.

Code below, run in LiveBook:
(edit: I was reading other methods that people used and I realize that there is a Enum.reduce_while function. That would have been helpful! Will use in the future)

defmodule Part1 do

  def get_board_statistics(board, numbers) do
    numbers
    |> Enum.reduce({[0,0,0,0,0], [0,0,0,0,0], 0, "", false}, fn number, acc = {row_counts, col_counts, count_til_bingo, winning_number, stop} ->
      unless stop do
        case get_index_row_col(board, number) do
          {row_index, col_index} ->
            row_counts = List.update_at(row_counts, row_index, & &1 + 1)
            col_counts = List.update_at(col_counts, col_index, & &1 + 1)
            {row_counts, col_counts, count_til_bingo + 1, number, 5 in row_counts or 5 in col_counts}
          nil ->
            {row_counts, col_counts, count_til_bingo + 1, winning_number, stop}
        end
      else
        acc
      end
    end)
  end

  defp get_index_row_col(board, number) do
    row_index = 
      board
      |> Enum.find_index(&(number in &1))

    unless is_nil(row_index) do
      col_index = 
        board
        |> Enum.at(row_index)
        |> Enum.find_index(&(number == &1))
  
      {row_index, col_index}
    end
  end
end

inputs =
  "advent/inputs/day04.txt"
  |> Path.relative()
  |> File.read!()
  |> String.split("\n")
  |> Enum.drop(-1)

[numbers | rest] = inputs
numbers = numbers |> String.trim() |> String.split(",")

boards = 
  rest
  |> Enum.drop(1)
  |> Enum.chunk_every(5, 6)
  |> Enum.map(fn board ->
    Enum.map(board, fn row ->
      row
      |> String.trim() 
      |> String.split(" ") 
      |> Enum.reject(&(&1 == ""))
    end)
  end)

{count_to_win, winning_number, winning_board} =
  Enum.map(boards, fn board ->
    {_, _, count_til_bingo, winning_number, _} = Part1.get_board_statistics(board, numbers)
    {count_til_bingo, winning_number, board}
  end)
  |> Enum.min(fn {num1, _, _}, {num2, _, _} -> num1 < num2 end)

numbers_called = Enum.take(numbers, count_to_win)

score = 
  winning_board
  |> List.flatten()
  |> Enum.reject(& &1 in numbers_called)
  |> Enum.map(&String.to_integer/1)
  |> Enum.sum
  |> Kernel.*(String.to_integer(winning_number))

# part 2
{count_to_lose, losing_number, losing_board} =
  Enum.map(boards, fn board ->
    {_, _, count_til_bingo, losing_number, _} = Part1.get_board_statistics(board, numbers)
    {count_til_bingo, losing_number, board}
  end)
  |> Enum.max(fn {num1, _, _}, {num2, _, _} -> num1 > num2 end)
  |> IO.inspect

numbers_called = Enum.take(numbers, count_to_lose)

score = 
  losing_board
  |> List.flatten()
  |> Enum.reject(& &1 in numbers_called)
  |> Enum.map(&String.to_integer/1)
  |> Enum.sum
  |> Kernel.*(String.to_integer(losing_number))
1 Like
31

VOD of day 4 is here: Twitch

I solved Advent of Code in the first half of the video and in the second half we used Elixir’s inspect protocol to print the board using Christmas colors. Then we also did sigils. :smiley:

Code is here: aoc/day-04.livemd at main · josevalim/aoc · GitHub

2 Likes
32

part 1:

part 2

33

Sorry I posted the solution for the wrong day :frowning:

34

Jose Valim’s Day 4 stream summary: Is Functional Programming Better For This Bingo Problem? (Advent of Code Day 4: Giant Squid) - YouTube