day04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ac2e96ad",
   "metadata": {},
   "source": [
    "# Day 04: Giant Squid\n",
    "\n",
    "You're already almost 1.5km (almost a mile) below the surface of the ocean, already so deep that you can't see any sunlight. What you can see, however, is a giant squid that has attached itself to the outside of your submarine.\n",
    "\n",
    "Maybe it wants to play bingo?\n",
    "\n",
    "Bingo is played on a set of boards each consisting of a 5x5 grid of numbers. Numbers are chosen at random, and the chosen number is marked on all boards on which it appears. (Numbers may not appear on all boards.) If all numbers in any row or any column of a board are marked, that board wins. (Diagonals don't count.)\n",
    "\n",
    "The submarine has a bingo subsystem to help passengers (currently, you and the giant squid) pass the time. It automatically generates a random order in which to draw numbers and a random set of boards (your puzzle input). For example:\n",
    "\n",
    "```text\n",
    "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\n",
    "\n",
    "22 13 17 11  0\n",
    " 8  2 23  4 24\n",
    "21  9 14 16  7\n",
    " 6 10  3 18  5\n",
    " 1 12 20 15 19\n",
    "\n",
    " 3 15  0  2 22\n",
    " 9 18 13 17  5\n",
    "19  8  7 25 23\n",
    "20 11 10 24  4\n",
    "14 21 16 12  6\n",
    "\n",
    "14 21 17 24  4\n",
    "10 16 15  9 19\n",
    "18  8 23 26 20\n",
    "22 11 13  6  5\n",
    " 2  0 12  3  7\n",
    " ```\n",
    "\n",
    "After the first five numbers are drawn (7, 4, 9, 5, and 11), there are no winners, but the boards are marked as follows (shown here adjacent to each other to save space):\n",
    "\n",
    "```text\n",
    "22 13 17 11  0         3 15  0  2 22        14 21 17 24  4\n",
    " 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19\n",
    "21  9 14 16  7        19  8  7 25 23        18  8 23 26 20\n",
    " 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5\n",
    " 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7\n",
    "```\n",
    "\n",
    "After the next six numbers are drawn (17, 23, 2, 0, 14, and 21), there are still no winners:\n",
    "\n",
    "```text\n",
    "22 13 17 11  0         3 15  0  2 22        14 21 17 24  4\n",
    " 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19\n",
    "21  9 14 16  7        19  8  7 25 23        18  8 23 26 20\n",
    " 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5\n",
    " 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7\n",
    "```\n",
    "\n",
    "Finally, 24 is drawn:\n",
    "\n",
    "```text\n",
    "22 13 17 11  0         3 15  0  2 22        14 21 17 24  4\n",
    " 8  2 23  4 24         9 18 13 17  5        10 16 15  9 19\n",
    "21  9 14 16  7        19  8  7 25 23        18  8 23 26 20\n",
    " 6 10  3 18  5        20 11 10 24  4        22 11 13  6  5\n",
    " 1 12 20 15 19        14 21 16 12  6         2  0 12  3  7\n",
    "```\n",
    "\n",
    "At this point, the third board wins because it has at least one complete row or column of marked numbers (in this case, the entire top row is marked: 14 21 17 24 4).\n",
    "\n",
    "The score of the winning board can now be calculated. Start by finding the sum of all unmarked numbers on that board; in this case, the sum is 188. Then, multiply that sum by the number that was just called when the board won, 24, to get the final score, 188 * 24 = 4512.\n",
    "\n",
    "To guarantee victory against the giant squid, figure out which board will win first. **What will your final score be if you choose that board?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "367db664",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Python imports\n",
    "from pathlib import Path\n",
    "from typing import Iterable, List, Tuple\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "# Paths to data\n",
    "testpath = Path(\"day04_test.txt\")\n",
    "datapath = Path(\"day04_data.txt\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8c074769",
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_input(fpath: Path) -> Tuple[List[int], List[np.array]]:\n",
    "    \"\"\"Return a tuple of bingo calls and boards\n",
    "    \n",
    "    :param fpath:  Path to data file\n",
    "    \"\"\"\n",
    "\n",
    "    boards = []\n",
    "    \n",
    "    with fpath.open(\"r\") as ifh:\n",
    "        lines = ifh.readlines()\n",
    "        \n",
    "        # Bingo calls\n",
    "        calls = [int(_) for _ in lines[0].split(\",\")]\n",
    "        \n",
    "        # Boards\n",
    "        board = []\n",
    "        for line in [_.strip().split() for _ in lines[1:]]:\n",
    "            if len(line) == 0:\n",
    "                if len(board):\n",
    "                    boards.append(np.array(board))\n",
    "                board = []\n",
    "            else:\n",
    "                board.append([int(_) for _ in line])\n",
    "            \n",
    "        return calls, boards"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e635b954",
   "metadata": {},
   "source": [
    "It seems easiest to implement the mechanism described in the puzzle text, using `numpy` arrays for boards, so we can use the array methods to make our lives easier. Specifically, we can test the board (and retain its shape) against a list of called numbers with `np.isin()` to generate a mask of marked/unmarked numbers. Then we can operate on the mask to test for winning boards.\n",
    "\n",
    "Once we have a winning board, we can use the mask to exclude marked values, and calculate the sum of unmarked values quickly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fbf1158b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_rows(mask: np.array) -> bool:\n",
    "    \"\"\"Return True if any row is all True\n",
    "    \n",
    "    :param mask:  numpy array mask\n",
    "    \"\"\"\n",
    "    for row in mask:\n",
    "        if row.all():\n",
    "            return True\n",
    "        \n",
    "    return False\n",
    "\n",
    "def check_cols(mask: np.array) -> bool:\n",
    "    \"\"\"Return True if any column is all True\n",
    "    \n",
    "    :param mask:  numpy array mask\n",
    "    \"\"\"\n",
    "    for row in mask.T:\n",
    "        if row.all():\n",
    "            return True\n",
    "        \n",
    "    return False\n",
    "\n",
    "\n",
    "def score_board(board: np.array, mask: np.array) -> int:\n",
    "    \"\"\"Return the sum of the unmarked values in the board\n",
    "    \n",
    "    \n",
    "    :param board:  bingo board\n",
    "    :param mask:  mask of marked (True) numbers in bingo board\n",
    "    \"\"\"\n",
    "    # Take inverse of mask so that False now indicates marked\n",
    "    # values, for taking the sum of unmarked values\n",
    "    return sum(board[~mask])\n",
    "\n",
    "def win_bingo(calls: List[int], boards: List[np.array]) -> int:\n",
    "    \"\"\"Return the score of the winning board\n",
    "    \n",
    "    :param calls:  list of bingo calls\n",
    "    :param boards:  list of bingo boards\n",
    "    \"\"\"\n",
    "    # Iterate over bingo calls\n",
    "    for idx in range(len(calls)):\n",
    "        called = calls[:idx+1]  # numbers called, so far\n",
    "\n",
    "        # Check boards for a winner\n",
    "        for board in boards:\n",
    "            \n",
    "            # mask values as True if number called\n",
    "            mask = np.isin(board, called)\n",
    "            \n",
    "            # If a row or column is complete, we have a winner\n",
    "            if check_rows(mask) or check_cols(mask):\n",
    "                print(f\"winner!\\n{board}\")\n",
    "                \n",
    "                return called[-1] * score_board(board, mask)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08eef0ee",
   "metadata": {},
   "source": [
    "With the test data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d3dc6b90",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "winner!\n",
      "[[14 21 17 24  4]\n",
      " [10 16 15  9 19]\n",
      " [18  8 23 26 20]\n",
      " [22 11 13  6  5]\n",
      " [ 2  0 12  3  7]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4512"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calls, boards = load_input(testpath)\n",
    "win_bingo(calls, boards)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41da32e9",
   "metadata": {},
   "source": [
    "And solving the puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "903f1f94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "winner!\n",
      "[[80 16 10 79 55]\n",
      " [93 60  4  0 29]\n",
      " [ 7 97  3  9 86]\n",
      " [43 67 78 64 35]\n",
      " [44 83 40 33 12]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "51776"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calls, boards = load_input(datapath)\n",
    "win_bingo(calls, boards)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51bb55d8",
   "metadata": {},
   "source": [
    "## Puzzle 2\n",
    "\n",
    "On the other hand, it might be wise to try a different strategy: let the giant squid win.\n",
    "\n",
    "You aren't sure how many bingo boards a giant squid could play at once, so rather than waste time counting its arms, the safe thing to do is to figure out which board will win last and choose that one. That way, no matter which boards it picks, it will win for sure.\n",
    "\n",
    "In the above example, the second board is the last to win, which happens after 13 is eventually called and its middle column is completely marked. If you were to keep playing until this point, the second board would have a sum of unmarked numbers equal to 148 for a final score of 148 * 13 = 1924.\n",
    "\n",
    "Figure out which board will win last. **Once it wins, what would its final score be?**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16eef501",
   "metadata": {},
   "source": [
    "To implement this tweak in the strategy, we update the list of boards when checking after every called number. We only keep boards where there is not a winning row or column, until we reach the last board. For the last board, we check as before, when we wanted to find a winning board."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1b4e071d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def lose_bingo(calls: List[int], boards: List[np.array]) -> int:\n",
    "    \"\"\"Return score of losing board\n",
    "    \n",
    "    :param calls:  list of bingo calls\n",
    "    :param boards:  list of bingo boards\n",
    "    \"\"\"\n",
    "    # Iterate over bingo calls\n",
    "    for idx in range(len(calls)):\n",
    "        called = calls[:idx+1]\n",
    "\n",
    "        # Check boards for winners. Obtain a list of boards that have not\n",
    "        # won yet (newboards), until we reach the last board\n",
    "        newboards = []\n",
    "        \n",
    "        # Iterate over the current set of boards\n",
    "        for board in boards:\n",
    "            \n",
    "            # mask values True if number called\n",
    "            mask = np.isin(board, called)\n",
    "            \n",
    "            # if the board is not a winner, append it to newboards\n",
    "            if not(check_rows(mask) or check_cols(mask)):\n",
    "                newboards.append(board)\n",
    "            elif len(boards) == 1:  # but if it is, and it's the last one...\n",
    "                print(f\"loser!\\n{board}\")\n",
    "                \n",
    "                return called[-1] * score_board(board, mask)\n",
    "            \n",
    "        # Continue only with list of boards that have not won, yet\n",
    "        boards = newboards[:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25adb9cf",
   "metadata": {},
   "source": [
    "For the test data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "79b6963e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loser!\n",
      "[[ 3 15  0  2 22]\n",
      " [ 9 18 13 17  5]\n",
      " [19  8  7 25 23]\n",
      " [20 11 10 24  4]\n",
      " [14 21 16 12  6]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1924"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calls, boards = load_input(testpath)\n",
    "lose_bingo(calls, boards)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e36ed00",
   "metadata": {},
   "source": [
    "And for the puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e9cd5557",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loser!\n",
      "[[ 6  3 41  5 44]\n",
      " [91 21 32 49 81]\n",
      " [29 85 47 20 14]\n",
      " [99 31 43 22 69]\n",
      " [90  4 45  8 16]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "16830"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calls, boards = load_input(datapath)\n",
    "lose_bingo(calls, boards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2402cabb",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}