2023/Day04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 4\n",
    "\n",
    "We arrived at the island in the sky!\n",
    "\n",
    "This is the best I could get ChatGPT/DALL·E to draw. \n",
    "\n",
    "<img src=\"./ChatGPT_illustrations/day04.png\" width=\"400\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part One\n",
    "\n",
    "To get a boat and visit the gardener that might know where the source of snow is, we need to help the Elf know how many scratch games they won. The cards information is presented as follows: `Card <number>: <winning numbers> | <Elf's numbers>`. The first match makes the card worth one point and each match after the first doubles the point value of that card.\n",
    "\n",
    "\n",
    "```\n",
    "Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53\n",
    "Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19\n",
    "Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1\n",
    "Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83\n",
    "Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36\n",
    "Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11\n",
    "```\n",
    "\n",
    "* For Card 1 the overlap is `48, 83, 17, and 86` which means it is worth `8` points.  \n",
    "* Card 2: `32 and 61` ==> `2` points;\n",
    "* Card 3: `1 and 21` ==> `2` points;\n",
    "* Card 4: `84` ==> `1` point.\n",
    "* Card 5 and 6 have no overlap. \n",
    "\n",
    "In total the scratchcards are worth `13` points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "example_input = \"\"\"Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53\n",
    "Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19\n",
    "Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1\n",
    "Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83\n",
    "Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36\n",
    "Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11\"\"\"\n",
    "\n",
    "def count_overlaps(input, example=False):\n",
    "    \"\"\"\n",
    "    Counts the number of overlaps between winning numbers and card numbers.\n",
    "\n",
    "    Parameters:\n",
    "    - input (str): The input file path or the input data string.\n",
    "    - example (bool): Flag indicating whether the input is an example or a file path.\n",
    "\n",
    "    Returns:\n",
    "    - list: A list of integers representing the number of overlaps for each line in the input.\n",
    "\n",
    "    Example:\n",
    "    >>> count_overlaps(\"Card 1: 1 2 3 4 5 | 3 4 5 7 8 9 10\", example=True)\n",
    "    [3]\n",
    "    \"\"\"\n",
    "    if example: \n",
    "        input_data = input.split(\"\\n\")\n",
    "    else:\n",
    "        with open(input) as f:\n",
    "            input_data = f.readlines()\n",
    "    \n",
    "    overlaps = []\n",
    "    for line in input_data:\n",
    "        _, numbers = line.split(\":\")\n",
    "        numbers_split = numbers.split(\"|\")\n",
    "        winning_numbers = set(int(n) for n in numbers_split[0].split())\n",
    "        card_numbers = [int(n) for n in numbers_split[1].split()]\n",
    "        overlap = [n for n in winning_numbers if n in card_numbers]\n",
    "        overlaps.append(len(overlap))\n",
    "\n",
    "    return overlaps\n",
    "\n",
    "def calculate_score(overlaps):\n",
    "    return sum(2**(i-1) for i in overlaps if i > 0)\n",
    "    \n",
    "\n",
    "def part_one(input, example=False):\n",
    "    return calculate_score(count_overlaps(input, example))\n",
    "\n",
    "assert(part_one(example_input, example=True) == 13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_case = \"\"\"Card 1: 1 2 3 4 | 1 2 3 4 5 6 7 8\n",
    "Card 2: | 1 2 8\"\"\"\n",
    "\n",
    "assert(part_one(test_case, example=True) == 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_case = \"\"\"Card 1: 1 2 3 4 | 1 2 3 4 5 6 7 8\n",
    "Card 2: 1 | 1 1 1\"\"\"\n",
    "\n",
    "assert(part_one(test_case, example=True) == 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22488"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part_one(\"./inputs/day04.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer! You are one gold star ⭐ closer to restoring snow operations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part \n",
    "\n",
    "Well, it gets more complicated. Now the number of overlaps between the winning numbers and the card numbers signify how many copies of the cards below a given card one gets.\n",
    "\n",
    "With the same example:\n",
    "\n",
    "```\n",
    "Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53\n",
    "Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19\n",
    "Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1\n",
    "Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83\n",
    "Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36\n",
    "Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11\n",
    "```\n",
    "\n",
    "| Card | Overlap | N Overlap | N Copies |\n",
    "| :--: | :-----: | :-------: | :------: |\n",
    "| 1 | 48, 83, 86, 17 | 4 | 1 [1] |\n",
    "| 2 | 32, 61 | 2 | 2 [1 + 1(C1)] |\n",
    "| 3 | 1, 21 | 2 | 4 [1 + 1(C1) + 2(C2)] |\n",
    "| 4 | 84 | 1 | 8 [1 + 1(C1) + 2(C2) + 4(C3)] |\n",
    "| 5 | - | 0 | 14 [1 + 1(C1) + 4(C3) + 8(C4)] |\n",
    "| 6 | - | 0 | 1 [1] | \n",
    "\n",
    "In total: 30 cards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_cards(overlaps):\n",
    "    \"\"\"\n",
    "    Counts the number of cards based on the given overlaps.\n",
    "\n",
    "    Parameters:\n",
    "    - overlaps (list): A list of integers representing the number of overlaps for each card.\n",
    "\n",
    "    Returns:\n",
    "    - int: The total number of cards.\n",
    "\n",
    "    Example:\n",
    "    >>> overlaps = [1, 2, 0, 0]\n",
    "    >>> count_cards(overlaps)\n",
    "    9\n",
    "    \"\"\"\n",
    "    cards = [1] * len(overlaps)\n",
    "    for i, o in enumerate(overlaps):\n",
    "        if o > 0:\n",
    "            for j in range(i+1, min(i+o+1, len(cards))):\n",
    "                cards[j] += cards[i]\n",
    "    return sum(cards)\n",
    "\n",
    "def part_two(input, example=False):\n",
    "    return count_cards(count_overlaps(input, example))\n",
    "\n",
    "assert(part_two(example_input, example=True) == 30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7013204"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part_two(\"./inputs/day04.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer! You are one gold star ⭐ closer to restoring snow operations."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}