2023/Day05.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 5\n",
    "\n",
    "We arrive at the giant garde/farm. We need to process some very bizzare way of storing information."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part One \n",
    "\n",
    "From the Almanac, we need to essentially, via extensive mapping, map seeds to locations and choose the lowest location.\n",
    "\n",
    "```\n",
    "seeds: 79 14 55 13\n",
    "\n",
    "seed-to-soil map:\n",
    "50 98 2\n",
    "52 50 48\n",
    "\n",
    "soil-to-fertilizer map:\n",
    "0 15 37\n",
    "37 52 2\n",
    "39 0 15\n",
    "\n",
    "fertilizer-to-water map:\n",
    "49 53 8\n",
    "0 11 42\n",
    "42 0 7\n",
    "57 7 4\n",
    "\n",
    "water-to-light map:\n",
    "88 18 7\n",
    "18 25 70\n",
    "\n",
    "light-to-temperature map:\n",
    "45 77 23\n",
    "81 45 19\n",
    "68 64 13\n",
    "\n",
    "temperature-to-humidity map:\n",
    "0 69 1\n",
    "1 0 69\n",
    "\n",
    "humidity-to-location map:\n",
    "60 56 37\n",
    "56 93 4\n",
    "```\n",
    "\n",
    "* Seed 79, soil 81, fertilizer 81, water 81, light 74, temperature 78, humidity 78, location 82.\n",
    "* Seed 14, soil 14, fertilizer 53, water 49, light 42, temperature 42, humidity 43, location 43.\n",
    "* Seed 55, soil 57, fertilizer 57, water 53, light 46, temperature 82, humidity 82, location 86.\n",
    "* Seed 13, soil 13, fertilizer 52, water 41, light 34, temperature 34, humidity 35, location 35."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([79, 14, 55, 13],\n",
       " {0: {(98, 100): 50, (50, 98): 52},\n",
       "  1: {(15, 52): 0, (52, 54): 37, (0, 15): 39},\n",
       "  2: {(53, 61): 49, (11, 53): 0, (0, 7): 42, (7, 11): 57},\n",
       "  3: {(18, 25): 88, (25, 95): 18},\n",
       "  4: {(77, 100): 45, (45, 64): 81, (64, 77): 68},\n",
       "  5: {(69, 70): 0, (0, 69): 1},\n",
       "  6: {(56, 93): 60, (93, 97): 56}})"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "example_input = \"\"\"seeds: 79 14 55 13\n",
    "\n",
    "seed-to-soil map:\n",
    "50 98 2\n",
    "52 50 48\n",
    "\n",
    "soil-to-fertilizer map:\n",
    "0 15 37\n",
    "37 52 2\n",
    "39 0 15\n",
    "\n",
    "fertilizer-to-water map:\n",
    "49 53 8\n",
    "0 11 42\n",
    "42 0 7\n",
    "57 7 4\n",
    "\n",
    "water-to-light map:\n",
    "88 18 7\n",
    "18 25 70\n",
    "\n",
    "light-to-temperature map:\n",
    "45 77 23\n",
    "81 45 19\n",
    "68 64 13\n",
    "\n",
    "temperature-to-humidity map:\n",
    "0 69 1\n",
    "1 0 69\n",
    "\n",
    "humidity-to-location map:\n",
    "60 56 37\n",
    "56 93 4\n",
    "\"\"\"\n",
    "\n",
    "def process_input(input_string, example=False):\n",
    "    if example:\n",
    "        input_data = input_string.splitlines()\n",
    "    else:\n",
    "        with open(input_string) as f:\n",
    "            input_data = f.readlines()\n",
    "    mappings = {}\n",
    "    current_map = -1\n",
    "    for line in input_data:\n",
    "        line = line.strip()\n",
    "        if line == \"\":\n",
    "            continue\n",
    "        if line.startswith(\"seeds:\"):\n",
    "            seeds = [int(x) for x in line.split(\":\")[1].split()]\n",
    "        else:\n",
    "            if line.endswith(\"map:\"):\n",
    "                current_map += 1\n",
    "                mappings[current_map] = {}\n",
    "            else:\n",
    "                destination, source, n = (int(e) for e in line.split(\" \"))\n",
    "                mappings[current_map][(source, source+n)] = destination\n",
    "    return seeds, mappings\n",
    "\n",
    "process_input(example_input, example=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map_seeds_to_locations(seeds, mappings):\n",
    "    locations = []\n",
    "    for seed in seeds:\n",
    "        map_level = 0\n",
    "        s = seed\n",
    "        while map_level in mappings:\n",
    "            for (lower, upper), destination in mappings[map_level].items():\n",
    "                if lower <= s < upper:\n",
    "                    s = s- lower + destination\n",
    "                    break\n",
    "            map_level += 1\n",
    "        locations.append(s)\n",
    "    return locations\n",
    "\n",
    "def part_one(input_string, example=False):\n",
    "    return min(map_seeds_to_locations(*process_input(input_string, example=example)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(part_one(example_input, example=True) == 35)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "382895070"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part_one(\"./inputs/day05.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's the right answer! You are one gold star ⭐ closer to restoring snow operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 3, 4]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ss = [1, 5, 3, 2]\n",
    "[s+_ for s,r in zip(ss[::2], ss[1::2]) for _ in range(int(r))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(79, 93), (55, 68)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def process_input_mod(input_string, example=False):\n",
    "    if example:\n",
    "        input_data = input_string.splitlines()\n",
    "    else:\n",
    "        with open(input_string) as f:\n",
    "            input_data = f.readlines()\n",
    "    mappings = { }\n",
    "    current_map = -1\n",
    "    for line in input_data:\n",
    "        line = line.strip()\n",
    "        if line == \"\":\n",
    "            continue\n",
    "        if line.startswith(\"seeds:\"):\n",
    "            ss = [int(e) for e in line.split(\":\")[1].split()]\n",
    "            seeds = [(s, s+r) for s,r in zip(ss[::2], ss[1::2])]\n",
    "        else:\n",
    "            if line.endswith(\"map:\"):\n",
    "                current_map += 1\n",
    "                mappings[current_map] = {}\n",
    "            else:\n",
    "                destination, source, n = (int(e) for e in line.split(\" \"))\n",
    "                mappings[current_map][(source, source+n)] = destination\n",
    "        if current_map in mappings:\n",
    "            # arrange mappings in order of increasing source\n",
    "            mappings[current_map] = {k: v \n",
    "                                     for k, v \n",
    "                                     in sorted(mappings[current_map].items(), \n",
    "                                               key=lambda item: item[0][0])}\n",
    "    return seeds, mappings\n",
    "se, maps = process_input_mod(example_input, example=True)\n",
    "se"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_ranges(range1, range2, d):\n",
    "    # Unpacking the ranges\n",
    "    start1, end1 = range1\n",
    "    start2, end2 = range2\n",
    "\n",
    "    # Finding the overlap\n",
    "    overlap_start = max(start1, start2)\n",
    "    overlap_end = min(end1, end2)\n",
    "    overlap = (overlap_start, overlap_end) if overlap_start < overlap_end else None\n",
    "\n",
    "    # Adjusting the function to return only the non-overlapping parts within range1\n",
    "    if not overlap:\n",
    "        return (range1), (None, None)\n",
    "\n",
    "    # Finding non-overlapping parts in range1\n",
    "    non_overlap1 = (start1, overlap_start) if start1 < overlap_start else None\n",
    "    non_overlap2 = (overlap_end, end1) if overlap_end < end1 else None\n",
    "\n",
    "    # Formatting the output\n",
    "    non_overlaps = [region for region in [non_overlap1, non_overlap2] if region]\n",
    "    non_overlaps = [None] if len(non_overlaps) == 0 else non_overlaps\n",
    "    # adjust the d value\n",
    "    d = d + overlap_start - start2\n",
    "\n",
    "    return non_overlaps, (overlap, d) \n",
    "\n",
    "# Example usage\n",
    "range1 = (5, 10)\n",
    "range2 = (100, 150)\n",
    "d = 8\n",
    "a, (b, c) = check_ranges(range1, range2, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(79, 93), (55, 68)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "se"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: {(50, 98): 52, (98, 100): 50},\n",
       " 1: {(0, 15): 39, (15, 52): 0, (52, 54): 37},\n",
       " 2: {(0, 7): 42, (7, 11): 57, (11, 53): 0, (53, 61): 49},\n",
       " 3: {(18, 25): 88, (25, 95): 18},\n",
       " 4: {(45, 64): 81, (64, 77): 68, (77, 100): 45},\n",
       " 5: {(0, 69): 1, (69, 70): 0},\n",
       " 6: {(56, 93): 60, (93, 97): 56}}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(79, 93), (55, 68)]\n",
      "level: 0, range_destination: (50, 98), adj: 52, source_ranges: [(55, 68), (79, 93)]\n",
      "source: (55, 68), destination: (50, 98)\n",
      "source: (79, 93), destination: (50, 98)\n",
      "level: 0, range_destination: (98, 100), adj: 50, source_ranges: []\n",
      "level: 1, range_destination: (0, 15), adj: 39, source_ranges: [(112, 125), (160, 174)]\n",
      "source: (112, 125), destination: (0, 15)\n",
      "source: (160, 174), destination: (0, 15)\n",
      "level: 1, range_destination: (15, 52), adj: 0, source_ranges: [112, 125, 160, 174]\n",
      "source: 112, destination: (15, 52)\n"
     ]
    },
    {
     "ename": "TypeError",
     "evalue": "cannot unpack non-iterable int object",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[10], line 44\u001b[0m\n\u001b[1;32m     41\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m destination_mappings\n\u001b[1;32m     43\u001b[0m \u001b[38;5;28mprint\u001b[39m(se)\n\u001b[0;32m---> 44\u001b[0m \u001b[43mmap_seeds_to_locations_mod\u001b[49m\u001b[43m(\u001b[49m\u001b[43mse\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[43mmaps\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn[10], line 30\u001b[0m, in \u001b[0;36mmap_seeds_to_locations_mod\u001b[0;34m(seeds, mappings)\u001b[0m\n\u001b[1;32m     28\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m range_source \u001b[38;5;129;01min\u001b[39;00m source_ranges:\n\u001b[1;32m     29\u001b[0m     \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124mf\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124msource: \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mrange_source\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m, destination: \u001b[39m\u001b[38;5;132;01m{\u001b[39;00mrange_destination\u001b[38;5;132;01m}\u001b[39;00m\u001b[38;5;124m\"\u001b[39m)\n\u001b[0;32m---> 30\u001b[0m     non_overlaps, (overlap, d) \u001b[38;5;241m=\u001b[39m \u001b[43mcheck_ranges\u001b[49m\u001b[43m(\u001b[49m\u001b[43mrange_source\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\n\u001b[1;32m     31\u001b[0m \u001b[43m                                              \u001b[49m\u001b[43mrange_destination\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\n\u001b[1;32m     32\u001b[0m \u001b[43m                                              \u001b[49m\u001b[43madj\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     33\u001b[0m     \u001b[38;5;28;01mif\u001b[39;00m non_overlaps \u001b[38;5;241m!=\u001b[39m [\u001b[38;5;28;01mNone\u001b[39;00m]:\n\u001b[1;32m     34\u001b[0m         mod\u001b[38;5;241m.\u001b[39mextend(non_overlaps)\n",
      "Cell \u001b[0;32mIn[7], line 3\u001b[0m, in \u001b[0;36mcheck_ranges\u001b[0;34m(range1, range2, d)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mcheck_ranges\u001b[39m(range1, range2, d):\n\u001b[1;32m      2\u001b[0m     \u001b[38;5;66;03m# Unpacking the ranges\u001b[39;00m\n\u001b[0;32m----> 3\u001b[0m     start1, end1 \u001b[38;5;241m=\u001b[39m range1\n\u001b[1;32m      4\u001b[0m     start2, end2 \u001b[38;5;241m=\u001b[39m range2\n\u001b[1;32m      6\u001b[0m     \u001b[38;5;66;03m# Finding the overlap\u001b[39;00m\n",
      "\u001b[0;31mTypeError\u001b[0m: cannot unpack non-iterable int object"
     ]
    }
   ],
   "source": [
    "def adjust_ranges(ranges):\n",
    "    adjusted_ranges = []\n",
    "    for (lower, upper), destination in ranges.items():\n",
    "        adjusted_ranges.append((lower + destination, upper + destination))\n",
    "    \n",
    "    # sort the ranges\n",
    "    adjusted_ranges = sorted(adjusted_ranges, key=lambda item: item[0])\n",
    "    \n",
    "    # check for overlaps, if detected print error message\n",
    "    for i in range(len(adjusted_ranges)-1):\n",
    "        if adjusted_ranges[i][1] > adjusted_ranges[i+1][0]:\n",
    "            print(\"Overlapping ranges detected!\")\n",
    "            break\n",
    "    return adjusted_ranges\n",
    "\n",
    "def map_seeds_to_locations_mod(seeds, mappings):\n",
    "    destination_mappings = {}\n",
    "    for level in range(len(mappings)):\n",
    "        if level == 0:\n",
    "            # sort seeds\n",
    "            seeds = sorted(seeds, key=lambda item: item[0])\n",
    "            source_ranges = seeds\n",
    "        else:\n",
    "            source_ranges = adjust_ranges(destination_mappings)\n",
    "        for range_destination, adj in mappings[level].items():\n",
    "            mod = []\n",
    "            print(f\"level: {level}, range_destination: {range_destination}, adj: {adj}, source_ranges: {source_ranges}\")\n",
    "            for range_source in source_ranges:\n",
    "                print(f\"source: {range_source}, destination: {range_destination}\")\n",
    "                non_overlaps, (overlap, d) = check_ranges(range_source, \n",
    "                                                          range_destination, \n",
    "                                                          adj)\n",
    "                if non_overlaps != [None]:\n",
    "                    mod.extend(non_overlaps)\n",
    "                elif overlap:\n",
    "                    destination_mappings[overlap] = d\n",
    "                else:\n",
    "                    mod.append(range_source)\n",
    "            source_ranges = mod\n",
    "    \n",
    "    return destination_mappings\n",
    "\n",
    "print(se)\n",
    "map_seeds_to_locations_mod(se, maps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(55, 68), None]\n"
     ]
    }
   ],
   "source": [
    "print(se)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def part_two(input_string, example=False):\n",
    "    return min(map_seeds_to_locations(*process_input_mod(input_string, example=example)))\n",
    "\n",
    "assert(part_two(example_input, example=True) == 46)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "part_two(\"./inputs/day05.txt\")"
   ]
  }
 ],
 "metadata": {
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}