2024/day_19/notebook.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "vscode": {
     "languageId": "raw"
    }
   },
   "source": [
    "---\n",
    "title: 'Day 19'\n",
    "author: \"Kasia Kedzierska\"\n",
    "date: December 19, 2024\n",
    "date-modified: last-modified\n",
    "format:\n",
    "  html:\n",
    "    theme: sketchy\n",
    "    css: misc/custom.css\n",
    "    code-fold: false\n",
    "    embed-resources: true\n",
    "    toc: true\n",
    "jupyter: python3\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the Day 19 of our little adventure we land in the hot springs on Gear Island! This time nothing is catastrophic, except for the fact we are short on cash to explore the onsen. To get the money we agree to figure out if the towels can be arranged into specified patterns! \n",
    "\n",
    "Read the full story on the official [Day 19 of Advent of Code 2024](https://adventofcode.com/2024/day/19) website.\n",
    "\n",
    "And the usual ChatGPT generated illustration (tho I must admit it is hard to get it to generate what I want, I might try ChatGPT 4 again, cause 4o seems to be less good at images and, unrelated, emails) to get us started:\n",
    "\n",
    "![](chatgpt_image.webp){width=75% fig-align=\"center\"}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "::: {.callout-note collapse=\"true\" title=\"Setting up\"}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from misc.helper import verify_answer\n",
    "\n",
    "example_input_file = \"../inputs/example_day_19.txt\"\n",
    "input_file = \"../inputs/day_19.txt\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ":::"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Combine patterns\n",
    "\n",
    "Our task here is from a given set of towels, count how many of the patterns can be assembled. \n",
    "\n",
    "Towels can have stipes that are white (w), blue (u), black (b), red (r), or green (g).\n",
    "\n",
    "Let's say we have towels with the following patterns: `wub`, `ggb`, `rrggbb`, `rr`, `b`. \n",
    "\n",
    "And we want to see if the following patterns can be assembled: `ggbrrb`, `wurggb`, `rrrrrr`, `rrggbbrr`, `brr` and `rgb`.\n",
    "\n",
    "- `ggbrrb` can be assembled from `ggb` and `rr` and `b`, \n",
    "- `wurggb` cannot be assembled,\n",
    "- `rrrrrr` can be assembled from `rr` and `rr` and `rr`,\n",
    "- `rrggbbrr` can be assembled from `rr` and `ggb` and `b` and `rr` or `rrggbb` and `rr`,\n",
    "- `brr` can be assembled from `b` and `rr`,\n",
    "- `rgb` cannot be assembled.\n",
    "\n",
    "The number of patterns that can be assembled from the given set of towels is `4`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(['wub', 'ggb', 'rrggbb', 'rr', 'b'],\n",
       " ['ggbrrb', 'wurggb', 'rrrrrr', 'rrggbbrr', 'brr', 'rgb'])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "example = \"\"\"\n",
    "wub, ggb, rrggbb, rr, b\n",
    "\n",
    "ggbrrb\n",
    "wurggb\n",
    "rrrrrr\n",
    "rrggbbrr\n",
    "brr\n",
    "rgb\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "def parse_input(input):\n",
    "    if Path(input).exists():\n",
    "        with open(input) as f:\n",
    "            input = f.read()\n",
    "    patterns = []\n",
    "    towels = []\n",
    "    for line in input.strip().split(\"\\n\"):\n",
    "        if \",\" in line:\n",
    "            towels = line.split(\", \")\n",
    "        elif line == \"\":\n",
    "            continue\n",
    "        else:\n",
    "            patterns.append(line)\n",
    "    return towels, patterns\n",
    "\n",
    "\n",
    "parse_input(example)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pattern_possible(towels, pattern):\n",
    "    if pattern == \"\":\n",
    "        return True\n",
    "    \n",
    "    possible_towels = [towel for towel in towels if pattern.startswith(towel)]\n",
    "    matching_patterns = [pattern[len(towel):] for towel in possible_towels]\n",
    "\n",
    "    if matching_patterns:\n",
    "        return any(is_pattern_possible(towels, pattern) for pattern in matching_patterns)\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def part_one(input):\n",
    "    towels, patterns = parse_input(input)\n",
    "    return sum(is_pattern_possible(towels, pattern) for pattern in patterns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✔️ That's right! The answer is 4.\n"
     ]
    }
   ],
   "source": [
    "verify_answer(part_one, example, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✔️ That's right! The answer is 6.\n"
     ]
    }
   ],
   "source": [
    "verify_answer(part_one, example_input_file, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 50.8 ms, sys: 2.03 ms, total: 52.9 ms\n",
      "Wall time: 58.8 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "296"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time part_one(input_file)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> That's the right answer! You are one gold star ⭐ closer to finding the Chief Historian."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: All the patterns!\n",
    "\n",
    "The staff is not in love with just one option to arrange the towels into patterns. They want to know all the possible patterns that can be assembled from the given set of towels.\n",
    "\n",
    "Since this time we need to count all the possible patterns, we need to be more careful about the "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_possible_patterns(towels, pattern, cache=None):\n",
    "    # create a cache to store the results of already calculated patterns\n",
    "    # this is created here instead of cache={} in the function signature\n",
    "    # to avoid mutable default arguments\n",
    "    if cache is None:\n",
    "        cache = {}\n",
    "\n",
    "    # if we have already calculated the result for this pattern, return it\n",
    "    if pattern in cache:\n",
    "        return cache[pattern]\n",
    "\n",
    "    # if the pattern is empty, we have found a valid pattern\n",
    "    if pattern == \"\":\n",
    "        return 1  \n",
    "\n",
    "    possible_towels = [towel for towel in towels if pattern.startswith(towel)]\n",
    "    matching_patterns = [pattern[len(towel) :] for towel in possible_towels]\n",
    "\n",
    "    if matching_patterns:\n",
    "        result = sum(\n",
    "            all_possible_patterns(towels, subpattern, cache)\n",
    "            for subpattern in matching_patterns\n",
    "        )\n",
    "    else:\n",
    "        result = 0\n",
    "\n",
    "    # cache the result to only test subpatterns once\n",
    "    cache[pattern] = result\n",
    "\n",
    "    return result\n",
    "\n",
    "\n",
    "def part_two(input):\n",
    "    towels, patterns = parse_input(input)\n",
    "    return sum(all_possible_patterns(towels, pattern) for pattern in patterns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✔️ That's right! The answer is 5.\n"
     ]
    }
   ],
   "source": [
    "verify_answer(part_two, example, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✔️ That's right! The answer is 16.\n"
     ]
    }
   ],
   "source": [
    "verify_answer(part_two, example_input_file, 16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 112 ms, sys: 3.69 ms, total: 116 ms\n",
      "Wall time: 123 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "619970556776002"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time part_two(input_file)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> That's the right answer! You are one gold star ⭐ closer to finding the Chief Historian."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "aoc2024",
   "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.13.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}