Day 09 - Disk Fragmenter.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "id": "4902fe81-7b45-486d-b79d-b3e976b29afd",
   "metadata": {},
   "source": [
    "Day 9 I learned the difference between isnumeric() and isdigit(). I couldn't do part 2, but was introduced to the CS concept of memoization/caching already computed results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "d5fc503e-0fb4-4104-ac0d-a0b438e185db",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open(\"day_09_input_1.txt\") as fname:\n",
    "    diskmap = fname.read().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1815de92-8b1c-47fb-b0e9-1fa2da9ce514",
   "metadata": {},
   "outputs": [],
   "source": [
    "def explode_diskmap(dm):\n",
    "    hdd = []\n",
    "    for i in range(len(dm)):\n",
    "        if i%2 == 0:\n",
    "            for j in range(int(dm[i])):\n",
    "                hdd.append(str(i//2))\n",
    "        else:\n",
    "            for j in range(int(dm[i])):\n",
    "                hdd.append(\".\")\n",
    "    return hdd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e520bdb6-22e2-4741-87c9-8e7cc8adb705",
   "metadata": {},
   "outputs": [],
   "source": [
    "harddrive = explode_diskmap(diskmap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a64ad5ca-3e2c-4203-a8bc-410212c7cd15",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rightmost_number_index(hdd):\n",
    "    for i in range(len(hdd)-1,0,-1):\n",
    "        if hdd[i].isnumeric():\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "855594ba-3bce-44a7-a2d2-e2425b97c66d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leftmost_dot_index(hdd):\n",
    "    for i in range(len(hdd)):\n",
    "        if hdd[i] == \".\":\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8cd77f52-b7c1-4d0a-add1-c4565ae838da",
   "metadata": {},
   "outputs": [],
   "source": [
    "while True:\n",
    "    leftmost_gap_location = leftmost_dot_index(harddrive)\n",
    "    rightmost_file_location = rightmost_number_index(harddrive)\n",
    "    \n",
    "    if leftmost_gap_location > rightmost_file_location:  # we've gone too far\n",
    "        print(''.join(harddrive))\n",
    "        break\n",
    "\n",
    "    # move file into gap\n",
    "    harddrive[leftmost_gap_location] = harddrive[rightmost_file_location]\n",
    "    harddrive[rightmost_file_location] = \".\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "14718d8f-1190-4b47-adbb-d0fb66a99109",
   "metadata": {},
   "outputs": [],
   "source": [
    "def checksum(hdd):\n",
    "    checksum = 0\n",
    "    for i in range(leftmost_dot_index(harddrive)):\n",
    "        checksum += int(hdd[i]) * i\n",
    "    return checksum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "091c2e99-3c62-4f0d-8454-ba562942b390",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6378826667552\n"
     ]
    }
   ],
   "source": [
    "print(checksum(harddrive))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5548d52d-7619-49f9-b304-c56129b10caa",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "72abac52-806d-48c9-8c0c-ee2924763d8d",
   "metadata": {},
   "source": [
    "## Other people's code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "2187ab3c-d2d0-4ec2-8997-28b54d892e8b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6413328569890\n"
     ]
    }
   ],
   "source": [
    "class Mem():\n",
    "    def __init__(b, pos, len): b.pos = pos; b.len = len\n",
    "    def val(b): return (2*b.pos + b.len-1) * b.len // 2\n",
    "\n",
    "\n",
    "pos, mem = 0, []\n",
    "for len in map(int, diskmap):\n",
    "    mem += [Mem(pos, len)]\n",
    "    pos += len\n",
    "\n",
    "for used in mem[::-2]:\n",
    "    for free in mem[1::2]:\n",
    "        if (free.pos <= used.pos\n",
    "        and free.len >= used.len):\n",
    "            used.pos  = free.pos\n",
    "            free.pos += used.len\n",
    "            free.len -= used.len\n",
    "\n",
    "print(sum(id*m.val() for id, m in enumerate(mem[::2])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ba8d407-f406-41dc-bec2-b4d502f70a97",
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}