aoc9_part2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code Day 9 Part 2: Enhanced Disk Fragmenter\n",
    "First, read the input file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-09T09:01:21.482118Z",
     "iopub.status.busy": "2024-12-09T09:01:21.481493Z",
     "iopub.status.idle": "2024-12-09T09:01:21.485661Z",
     "shell.execute_reply": "2024-12-09T09:01:21.485203Z"
    }
   },
   "outputs": [],
   "source": [
    "with open('aoc9.txt', 'r') as f:\n",
    "    disk_map = f.read().strip()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a function to parse the disk map into files with their sizes and positions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-09T09:01:21.487838Z",
     "iopub.status.busy": "2024-12-09T09:01:21.487427Z",
     "iopub.status.idle": "2024-12-09T09:01:21.491280Z",
     "shell.execute_reply": "2024-12-09T09:01:21.490800Z"
    }
   },
   "outputs": [],
   "source": [
    "def parse_disk_map(disk_map):\n",
    "    files = []\n",
    "    current_pos = 0\n",
    "    file_id = 0\n",
    "    \n",
    "    for i, length in enumerate(disk_map):\n",
    "        length = int(length)\n",
    "        if i % 2 == 0:  # File block\n",
    "            files.append({'id': file_id, 'size': length, 'pos': current_pos})\n",
    "            file_id += 1\n",
    "        current_pos += length\n",
    "    return files"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to find available free spaces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-09T09:01:21.493608Z",
     "iopub.status.busy": "2024-12-09T09:01:21.493199Z",
     "iopub.status.idle": "2024-12-09T09:01:21.496947Z",
     "shell.execute_reply": "2024-12-09T09:01:21.496433Z"
    }
   },
   "outputs": [],
   "source": [
    "def find_free_spaces(disk_map):\n",
    "    spaces = []\n",
    "    current_pos = 0\n",
    "    \n",
    "    for i, length in enumerate(disk_map):\n",
    "        length = int(length)\n",
    "        if i % 2 == 1:  # Free space\n",
    "            spaces.append({'pos': current_pos, 'size': length})\n",
    "        current_pos += length\n",
    "    return spaces"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function to compact files by moving whole files"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-09T09:01:21.499200Z",
     "iopub.status.busy": "2024-12-09T09:01:21.498815Z",
     "iopub.status.idle": "2024-12-09T09:01:21.506620Z",
     "shell.execute_reply": "2024-12-09T09:01:21.506065Z"
    }
   },
   "outputs": [],
   "source": [
    "def compact_whole_files(disk_map):\n",
    "    files = parse_disk_map(disk_map)\n",
    "    blocks = ['.' for _ in range(sum(int(x) for x in disk_map))]\n",
    "    \n",
    "    # Place files in initial positions\n",
    "    for file in files:\n",
    "        pos = file['pos']\n",
    "        for i in range(file['size']):\n",
    "            blocks[pos + i] = file['id']\n",
    "    \n",
    "    # Move files from right to left\n",
    "    for file_id in range(len(files) - 1, -1, -1):\n",
    "        file_size = next(f['size'] for f in files if f['id'] == file_id)\n",
    "        file_start = next(i for i, x in enumerate(blocks) if x == file_id)\n",
    "        \n",
    "        # Find leftmost suitable space\n",
    "        pos = 0\n",
    "        while pos < file_start:\n",
    "            if all(b == '.' for b in blocks[pos:pos + file_size]):\n",
    "                # Move file\n",
    "                for i in range(file_size):\n",
    "                    blocks[pos + i] = file_id\n",
    "                    blocks[file_start + i] = '.'\n",
    "                break\n",
    "            pos += 1\n",
    "    \n",
    "    return blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate and save the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-12-09T09:01:21.509001Z",
     "iopub.status.busy": "2024-12-09T09:01:21.508591Z",
     "iopub.status.idle": "2024-12-09T09:06:41.104551Z",
     "shell.execute_reply": "2024-12-09T09:06:41.103751Z"
    }
   },
   "outputs": [],
   "source": [
    "def calculate_checksum(blocks):\n",
    "    checksum = 0\n",
    "    for pos, block in enumerate(blocks):\n",
    "        if block != '.':\n",
    "            checksum += pos * block\n",
    "    return checksum\n",
    "\n",
    "compacted_blocks = compact_whole_files(disk_map)\n",
    "checksum = calculate_checksum(compacted_blocks)\n",
    "\n",
    "with open('result_part2.txt', 'w') as f:\n",
    "    f.write(f'Filesystem checksum (part 2): {checksum}')"
   ]
  }
 ],
 "metadata": {
  "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.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}