{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code - Day 7: Handy Haversacks\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part One\n",
    "\n",
    "You land at the regional airport in time for your next flight. In fact, it looks\n",
    "like you'll even have time to grab some food: all flights are currently delayed\n",
    "due to issues in luggage processing.\n",
    "\n",
    "Due to recent aviation regulations, many rules (your puzzle input) are being\n",
    "enforced about bags and their contents; bags must be color-coded and must\n",
    "contain specific quantities of other color-coded bags. Apparently, nobody\n",
    "responsible for these regulations considered how long they would take to\n",
    "enforce!\n",
    "\n",
    "For example, consider the following rules:\n",
    "\n",
    "- light red bags contain 1 bright white bag, 2 muted yellow bags.\n",
    "- dark orange bags contain 3 bright white bags, 4 muted yellow bags.\n",
    "- bright white bags contain 1 shiny gold bag.\n",
    "- muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.\n",
    "- shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.\n",
    "- dark olive bags contain 3 faded blue bags, 4 dotted black bags.\n",
    "- vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.\n",
    "- faded blue bags contain no other bags.\n",
    "- dotted black bags contain no other bags.\n",
    "\n",
    "These rules specify the required contents for 9 bag types. In this example,\n",
    "every faded blue bag is empty, every vibrant plum bag contains 11 bags (5 faded\n",
    "blue and 6 dotted black), and so on.\n",
    "\n",
    "You have a **shiny gold** bag. If you wanted to carry it in at least one other\n",
    "bag, how many different bag colors would be valid for the outermost bag? (In\n",
    "other words: how many colors can, eventually, contain at least one shiny gold\n",
    "bag?)\n",
    "\n",
    "In the above rules, the following options would be available to you:\n",
    "\n",
    "- A bright white bag, which can hold your shiny gold bag directly.\n",
    "- A muted yellow bag, which can hold your shiny gold bag directly, plus some\n",
    "  other bags.\n",
    "- A dark orange bag, which can hold bright white and muted yellow bags, either\n",
    "  of which could then hold your shiny gold bag.\n",
    "- A light red bag, which can hold bright white and muted yellow bags, either of\n",
    "  which could then hold your shiny gold bag.\n",
    "\n",
    "So, in this example, the number of bag colors that can eventually contain at\n",
    "least one shiny gold bag is 4.\n",
    "\n",
    "**How many bag colors can eventually contain at least one shiny gold bag?** (The\n",
    "list of rules is quite long; make sure you get all of it.)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load and Clean Input data\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ":::{note} The input data can be found\n",
    "[here](https://adventofcode.com/2020/day/7). :::\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "594\n",
      "['light salmon bags contain 5 dotted olive bags, 4 wavy lavender bags.', 'dark purple bags contain 5 striped maroon bags, 1 wavy maroon bag.']\n"
     ]
    }
   ],
   "source": [
    "with open('../../data/advent-of-code/2020/day-7-input') as fid:\n",
    "    data = fid.readlines()\n",
    "    data = [x.strip() for x in data]\n",
    "\n",
    "print(len(data))\n",
    "print(data[0:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_rule(rule):\n",
    "    \"\"\"Parse rule and create a clean data structure for holding information about each rule.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    rule: str\n",
    "        A string corresponding to a given rule for a particular color bag\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    dict\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def clean_func(item, split_on=' '):\n",
    "        return item.strip().split(split_on)\n",
    "\n",
    "    if 'contains' in rule:\n",
    "        split_on = 'contains'\n",
    "    else:\n",
    "        split_on = 'contain'\n",
    "\n",
    "    x = clean_func(rule, split_on)\n",
    "\n",
    "    key = ' '.join(clean_func(x[0])[:-1])\n",
    "    items = clean_func(x[-1], ',')\n",
    "    clean_items = {}\n",
    "    for item in items:\n",
    "        clean_item = clean_func(item)\n",
    "        if clean_item[0] == 'no':\n",
    "            pass\n",
    "        else:\n",
    "            count = int(clean_item[0])\n",
    "            name = ' '.join(clean_item[1:3])\n",
    "\n",
    "            clean_items[name] = count\n",
    "\n",
    "    return (key, clean_items)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "light salmon bags contain 5 dotted olive bags, 4 wavy lavender bags.\n",
      "('light salmon', {'dotted olive': 5, 'wavy lavender': 4})\n"
     ]
    }
   ],
   "source": [
    "print(data[0])\n",
    "print(parse_rule(data[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vibrant magenta bags contain 2 dark lime bags.\n",
      "('vibrant magenta', {'dark lime': 2})\n"
     ]
    }
   ],
   "source": [
    "print(data[-1])\n",
    "print(parse_rule(data[-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "clean_data = dict([parse_rule(rule) for rule in data])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'light red': {'bright white': 1, 'muted yellow': 2},\n",
       " 'dark orange': {'bright white': 3, 'muted yellow': 4},\n",
       " 'bright white': {'shiny gold': 1},\n",
       " 'muted yellow': {'shiny gold': 2, 'faded blue': 9},\n",
       " 'shiny gold': {'dark olive': 1, 'vibrant plum': 2},\n",
       " 'dark olive': {'faded blue': 3, 'dotted black': 4},\n",
       " 'vibrant plum': {'faded blue': 5, 'dotted black': 6},\n",
       " 'faded blue': {},\n",
       " 'dotted black': {}}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_data = \"\"\"\n",
    "light red bags contain 1 bright white bag, 2 muted yellow bags.\n",
    "dark orange bags contain 3 bright white bags, 4 muted yellow bags.\n",
    "bright white bags contain 1 shiny gold bag.\n",
    "muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.\n",
    "shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.\n",
    "dark olive bags contain 3 faded blue bags, 4 dotted black bags.\n",
    "vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.\n",
    "faded blue bags contain no other bags.\n",
    "dotted black bags contain no other bags.\n",
    "\"\"\".strip().split('\\n')\n",
    "\n",
    "clean_test_data = dict([parse_rule(rule) for rule in test_data])\n",
    "clean_test_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def contains(data, color):\n",
    "    def _helper(color):\n",
    "        if color == 'shiny gold':\n",
    "            return True\n",
    "\n",
    "        if not data.get(color):\n",
    "            return False\n",
    "\n",
    "        contents = data[color]\n",
    "        for color in contents:\n",
    "            if _helper(color):\n",
    "                return True\n",
    "\n",
    "    total = 0\n",
    "    for key in data:\n",
    "        if key != color and _helper(key):\n",
    "            total += 1\n",
    "\n",
    "    return total\n",
    "\n",
    "\n",
    "contains(clean_test_data, 'shiny gold')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "261 bag colors contain at least one shiny gold bag\n"
     ]
    }
   ],
   "source": [
    "contains_shiny_gold = contains(clean_data, 'shiny gold')\n",
    "print(f'{contains_shiny_gold} bag colors contain at least one shiny gold bag')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part Two\n",
    "\n",
    "It's getting pretty expensive to fly these days - not because of ticket prices,\n",
    "but because of the ridiculous number of bags you need to buy!\n",
    "\n",
    "Consider again your shiny gold bag and the rules from the above example:\n",
    "\n",
    "```\n",
    "faded blue bags contain 0 other bags.\n",
    "dotted black bags contain 0 other bags.\n",
    "vibrant plum bags contain 11 other bags: 5 faded blue bags and 6 dotted black bags.\n",
    "dark olive bags contain 7 other bags: 3 faded blue bags and 4 dotted black bags.\n",
    "```\n",
    "\n",
    "So, a single shiny gold bag must contain 1 dark olive bag (and the 7 bags within\n",
    "it) plus 2 vibrant plum bags (and the 11 bags within each of those): 1 + 1*7 +\n",
    "2 + 2*11 = 32 bags!\n",
    "\n",
    "Of course, the actual rules have a small chance of going several levels deeper\n",
    "than this example; be sure to count all of the bags, even if the nesting becomes\n",
    "topologically impractical!\n",
    "\n",
    "Here's another example:\n",
    "\n",
    "- shiny gold bags contain 2 dark red bags.\n",
    "- dark red bags contain 2 dark orange bags.\n",
    "- dark orange bags contain 2 dark yellow bags.\n",
    "- dark yellow bags contain 2 dark green bags.\n",
    "- dark green bags contain 2 dark blue bags.\n",
    "- dark blue bags contain 2 dark violet bags.\n",
    "- dark violet bags contain no other bags.\n",
    "\n",
    "In this example, a single shiny gold bag must contain 126 other bags.\n",
    "\n",
    "**How many individual bags are required inside your single shiny gold bag?**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "In part 2, we have to check our bags again. This time, we want to find out, how\n",
    "many bags a **shiny gold bag** contains. We have to count the bags inside a\n",
    "shiny gold bag and then count the bags inside those bags and then count the bags\n",
    "inside those and then...\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_bag_count(bags, color):\n",
    "    total = 0\n",
    "    contents = bags[color]\n",
    "    for key, value in contents.items():\n",
    "        total += value\n",
    "        p = get_bag_count(bags, key)\n",
    "        if p is not None:\n",
    "            total += p * value\n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try this function on a few sample tests:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_bag_count(clean_test_data, 'shiny gold')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "126"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_bag_count(\n",
    "    {\n",
    "        'shiny gold': {'dark red': 2},\n",
    "        'dark red': {'dark orange': 2},\n",
    "        'dark orange': {'dark yellow': 2},\n",
    "        'dark yellow': {'dark green': 2},\n",
    "        'dark green': {'dark blue': 2},\n",
    "        'dark blue': {'dark violet': 2},\n",
    "        'dark violet': {},\n",
    "    },\n",
    "    'shiny gold',\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3765 individual bags are required inside a single shiny gold bag\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    f'{get_bag_count(clean_data, \"shiny gold\")} individual bags are required inside a single shiny gold bag'\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "author": "Anderson Banihirwe",
  "date": "2020-12-07",
  "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.8.8"
  },
  "tags": "python,adventofcode",
  "title": "Advent of Code - Day 7: Handy Haversacks",
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {},
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}