Notebooks/day-07.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 180,
   "id": "01592625-6bc9-4ead-9af8-2eda676a5f09",
   "metadata": {},
   "outputs": [],
   "source": [
    "data = open(\"../inputs/day-07\").read().splitlines()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "id": "1cf7f832-179c-43f3-af6c-c0253ab4c884",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node():\n",
    "    def __init__(self, name: str, up, size=None):\n",
    "        self.name = name\n",
    "        self.up = up\n",
    "        self.size = size\n",
    "        self.children = []\n",
    "    \n",
    "    def sub(self, name, size=None):\n",
    "        self.children.append(Node(name=name, size=size, up=self))\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return f\"name:{self.name}, size: {self.size}, dir: {[l.name for l in self.children]}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "id": "d8deaffb-a842-4224-b91a-815e0c4b67b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "top = Node(\"/\", None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "9089b6f6-8284-45e2-a6d5-4d4254493c24",
   "metadata": {},
   "outputs": [],
   "source": [
    "visiting = top"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "d343cee0-7761-4218-bb05-274b5812d691",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cd_into(path):\n",
    "    global visiting\n",
    "    if path == '..':\n",
    "        visiting = visiting.up\n",
    "        return\n",
    "    for s in visiting.children:\n",
    "        if s.name == path:\n",
    "            visiting = s\n",
    "            return\n",
    "    raise Exception(f\"Unknown children {path}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "id": "608c6303-414f-42d4-a263-4e42b7db6254",
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_folder(instructions):\n",
    "    global visiting\n",
    "    if instructions == []:\n",
    "        return\n",
    "    if \"$\" not in instructions[0]:\n",
    "        info, name = instructions[0].split(' ')\n",
    "        sub = Node(name, up=visiting, size=None if 'dir' in info else int(info))\n",
    "        visiting.children.append(sub)\n",
    "        parse_folder(instructions[1:])\n",
    "    else:\n",
    "        process(instructions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "id": "1cf42dd0-2ae5-4bd0-b493-03412c70ee51",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process(instructions):\n",
    "    global visiting\n",
    "    if len(instructions) == 0:\n",
    "        return\n",
    "    if instructions[0] == \"$ ls\":\n",
    "        parse_folder(instructions[1:])\n",
    "    elif instructions[0].startswith(\"$ cd\"):\n",
    "        cd_into(instructions[0].removeprefix(\"$ cd \"))\n",
    "        process(instructions[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "id": "61a99f39-cbc2-47d4-be24-0a089de395c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sum_nodes(node: Node):\n",
    "    if node.children != []:\n",
    "        size = 0\n",
    "        for s in node.children:\n",
    "            size += sum_nodes(s)\n",
    "        node.size = size\n",
    "    return node.size"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "ab9b6af7-fc4e-4d9e-8f6b-e92f0b99b6da",
   "metadata": {},
   "outputs": [],
   "source": [
    "process(data[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "a69d2ff5-da3c-4575-8f58-9420b9f6334d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "46975962"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum_nodes(top)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "158b79db-af39-495b-ac81-d6778caebe10",
   "metadata": {},
   "outputs": [],
   "source": [
    "total = 0\n",
    "def print_nice(node, threshold):\n",
    "    global total\n",
    "    if node.size < threshold and node.children != []:\n",
    "        total += node.size\n",
    "    for s in node.children:\n",
    "        print_nice(s, threshold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "cf8ef4f7-ce32-4210-bff6-99162438e02d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1334506"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_nice(top, 100_000)\n",
    "total"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af2f75ad-9765-4894-8b68-600e7405c210",
   "metadata": {},
   "source": [
    "----\n",
    "## Finding the right dir to delete"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "id": "e2c00051-233a-4f30-8b56-7d572277dbf7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6975962"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "space_needed = 30000000 - (70000000 - 46975962)\n",
    "space_needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "777299d4-0c7b-4872-a323-e44cad5e7968",
   "metadata": {},
   "outputs": [],
   "source": [
    "options = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "0850a1dc-6da2-4bcf-ba42-2175e554fb31",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_match(node):\n",
    "    global options\n",
    "    if node.children == [] or node.size < space_needed:\n",
    "        return False\n",
    "    \n",
    "    if all([False if find_match(l) else True for l in node.children]):\n",
    "        options.append(node.size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "id": "1ef602de-b09c-4947-8e82-ebc7c2aaceb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "find_match(top)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "dc924b5d-5547-4b6e-941a-4f8335b82fd4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7421137"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min(options)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f97a41f8-f554-47ef-9c5a-987f6ef71594",
   "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.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}