src/day_5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0cd13cd8",
   "metadata": {},
   "source": [
    "> # Day 5: If You Give A Seed A Fertilizer\n",
    "\n",
    ">You take the boat and find the gardener right where you were told he would be: managing a giant \"garden\" that looks more to you like a farm.\n",
    ">\n",
    ">\"A water source? Island Island is the water source!\" You point out that Snow Island isn't receiving any water.\n",
    ">\n",
    ">\"Oh, we had to stop the water because we ran out of sand to filter it with! Can't make snow with dirty water. Don't worry, I'm sure we'll get more sand soon; we only turned off the water a few days... weeks... oh no.\" His face sinks into a look of horrified realization.\n",
    ">\n",
    ">\"I've been so busy making sure everyone here has food that I completely forgot to check why we stopped getting more sand! There's a ferry leaving soon that is headed over in that direction - it's much faster than your boat. Could you please go check it out?\"\n",
    ">\n",
    ">You barely have time to agree to this request when he brings up another. \"While you wait for the ferry, maybe you can help us with our food production problem. The latest Island Island Almanac just arrived and we're having trouble making sense of it.\"\n",
    ">\n",
    ">The almanac (your puzzle input) lists all of the seeds that need to be planted. It also lists what type of soil to use with each kind of seed, what type of fertilizer to use with each kind of soil, what type of water to use with each kind of fertilizer, and so on. Every type of seed, soil, fertilizer and so on is identified with a number, but numbers are reused by each category - that is, soil 123 and fertilizer 123 aren't necessarily related to each other.\n",
    ">\n",
    ">For example:\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",
    ">The almanac starts by listing which seeds need to be planted: seeds 79, 14, 55, and 13.\n",
    ">\n",
    ">The rest of the almanac contains a list of maps which describe how to convert numbers from a source category into numbers in a destination category. That is, the section that starts with seed-to-soil map: describes how to convert a seed number (the source) to a soil number (the destination). This lets the gardener and his team know which soil to use with which seeds, which water to use with which fertilizer, and so on.\n",
    ">\n",
    ">Rather than list every source number and its corresponding destination number one by one, the maps describe entire ranges of numbers that can be converted. Each line within a map contains three numbers: the destination range start, the source range start, and the range length.\n",
    ">\n",
    ">Consider again the example seed-to-soil map:\n",
    ">```\n",
    "50 98 2\n",
    "52 50 48\n",
    ">```\n",
    ">The first line has a destination range start of 50, a source range start of 98, and a range length of 2. This line means that the source range starts at 98 and contains two values: 98 and 99. The destination range is the same length, but it starts at 50, so its two values are 50 and 51. With this information, you know that seed number 98 corresponds to soil number 50 and that seed number 99 corresponds to soil number 51.\n",
    ">\n",
    ">The second line means that the source range starts at 50 and contains 48 values: 50, 51, ..., 96, 97. This corresponds to a destination range starting at 52 and also containing 48 values: 52, 53, ..., 98, 99. So, seed number 53 corresponds to soil number 55.\n",
    ">\n",
    ">Any source numbers that aren't mapped correspond to the same destination number. So, seed number 10 corresponds to soil number 10.\n",
    ">\n",
    ">So, the entire list of seed numbers and their corresponding soil numbers looks like this:\n",
    ">\n",
    ">```\n",
    "seed  soil\n",
    "0     0\n",
    "1     1\n",
    "...   ...\n",
    "48    48\n",
    "49    49\n",
    "50    52\n",
    "51    53\n",
    "...   ...\n",
    "96    98\n",
    "97    99\n",
    "98    50\n",
    "99    51\n",
    ">```\n",
    ">\n",
    ">With this map, you can look up the soil number required for each initial seed number:\n",
    ">\n",
    ">- Seed number 79 corresponds to soil number 81.\n",
    ">- Seed number 14 corresponds to soil number 14.\n",
    ">- Seed number 55 corresponds to soil number 57.\n",
    ">- Seed number 13 corresponds to soil number 13.\n",
    ">\n",
    ">The gardener and his team want to get started as soon as possible, so they'd like to know the closest location that needs a seed. Using these maps, find the lowest location number that corresponds to any of the initial seeds. To do this, you'll need to convert each seed number through other categories until you can find its corresponding location number. In this example, the corresponding types are:\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.\n",
    ">\n",
    ">So, the lowest location number in this example is 35.\n",
    ">\n",
    ">What is the lowest location number that corresponds to any of the initial seed numbers>>?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "faea4fb8",
   "metadata": {},
   "source": [
    "## Read input\n",
    "\n",
    "Today's input was multisectioned and different sections needed different handling so I decided to do everything right here instead of using my `read_input` functionality.\n",
    "\n",
    "First I split all the sections by empty lines. Then, I read in the seeds which are all the numbers on the first section.\n",
    "\n",
    "Then for each other section, I parse the destination start, source start and range length attributes for each line and store them into lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c4aa8da3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "from collections import namedtuple\n",
    "\n",
    "Range = namedtuple('Range', ['dest_start', 'source_start', 'range'])\n",
    "\n",
    "prod = '../inputs/day_5.txt'\n",
    "test = '../inputs/day_5_example.txt'\n",
    "\n",
    "with open(prod) as raw_input:\n",
    "    data_sections = raw_input.read().split('\\n\\n')\n",
    "    \n",
    "seeds = [int(seed) for seed in re.findall(r'\\d+', data_sections[0].split(': ')[1])]\n",
    "\n",
    "def process_ranges(section):\n",
    "    lines = section.split('\\n')[1:]\n",
    "    ranges = []\n",
    "    for line in lines:\n",
    "        numbers = [int(value) for value in re.findall(r'\\d+', line)]\n",
    "        ranges.append(Range(*numbers))\n",
    "    return ranges\n",
    "        \n",
    "seed_to_soil = process_ranges(data_sections[1])\n",
    "soil_to_fertilizer = process_ranges(data_sections[2])\n",
    "fertilizer_to_water = process_ranges(data_sections[3])\n",
    "water_to_light = process_ranges(data_sections[4])\n",
    "light_to_temperature = process_ranges(data_sections[5])\n",
    "temperature_to_humidity = process_ranges(data_sections[6])\n",
    "humidity_to_location = process_ranges(data_sections[7])\n",
    "\n",
    "ranges = [\n",
    "    seed_to_soil,\n",
    "    soil_to_fertilizer,\n",
    "    fertilizer_to_water,\n",
    "    water_to_light,\n",
    "    light_to_temperature,\n",
    "    temperature_to_humidity,\n",
    "    humidity_to_location\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34d37b9e",
   "metadata": {},
   "source": [
    "To calculate the location for each seed, I loop through the ranges, find the next correct value for each range and finally keep track of them all to calculate the smallest end result at the end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "b642450b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def map_to_value(source, r):\n",
    "    if source >= r.source_start and source <= r.source_start + r.range:\n",
    "        n = source - r.source_start\n",
    "        return r.dest_start + n\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "def calculate_location(seed, ranges):\n",
    "    source = seed\n",
    "    for _range in ranges:\n",
    "        for individual_range in _range:\n",
    "            potential = map_to_value(source, individual_range)\n",
    "            if potential != -1:\n",
    "                source = potential\n",
    "                break\n",
    "            else:\n",
    "                continue\n",
    "    return source"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "05cd43e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution: 88151870\n"
     ]
    }
   ],
   "source": [
    "smallest = None\n",
    "for seed in seeds:\n",
    "    location = calculate_location(seed, ranges)\n",
    "    if not smallest or location < smallest:\n",
    "        smallest = location\n",
    "        \n",
    "print(f'Solution: {smallest}')\n",
    "assert smallest == 88151870"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51e3d407",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "\n",
    ">Everyone will starve if you only plant such a small number of seeds. Re-reading the almanac, it looks like the seeds: line actually describes ranges of seed numbers.\n",
    ">\n",
    ">The values on the initial seeds: line come in pairs. Within each pair, the first value is the start of the range and the second value is the length of the range. So, in the first line of the example above:\n",
    ">```\n",
    "seeds: 79 14 55 13\n",
    ">```\n",
    ">This line describes two ranges of seed numbers to be planted in the garden. The first range starts with seed number 79 and contains 14 values: 79, 80, ..., 91, 92. The second range starts with seed number 55 and contains 13 values: 55, 56, ..., 66, 67.\n",
    ">\n",
    ">Now, rather than considering four seed numbers, you need to consider a total of 27 seed numbers.\n",
    ">\n",
    ">In the above example, the lowest location number can be obtained from seed number 82, which corresponds to soil 84, fertilizer 84, water 84, light 77, temperature 45, humidity 46, and location 46. So, the lowest location number is 46.\n",
    ">\n",
    ">Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "020ef7cc",
   "metadata": {},
   "source": [
    "Oof, this one was tough. I spent an entire Wednesday evening trying to figure this out. I got tipped by a friend to start from the locations and find a matching seed.\n",
    "\n",
    "I wrote a `map_to_prev` function that is the inverse of the previous `map_to_value` and finds the corresponding value in the earlier section of input."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "07f4e3e4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def map_to_prev(dest, r):\n",
    "    low = r.dest_start\n",
    "    high = r.dest_start + r.range - 1\n",
    "    # Any source numbers that aren't mapped\n",
    "    # correspond to the same destination number.\n",
    "    if dest < low or dest > high:\n",
    "        return -1\n",
    "    else:\n",
    "        return dest - r.dest_start + r.source_start"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b36d7d3",
   "metadata": {},
   "source": [
    "Then I did a similar thing with `find_seed` which is the inverse of `find_location`. I give it starting location and ranges in reverse order and find a match for each step. If one is not found, keep the value as it is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "982c6999",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_seed(location, ranges):\n",
    "    src = location\n",
    "    for _range in ranges:\n",
    "        for individual_range in _range:\n",
    "            potential = map_to_prev(src, individual_range)\n",
    "            if potential != -1:\n",
    "                src = potential\n",
    "                break\n",
    "    return src"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a682d27c",
   "metadata": {},
   "source": [
    "I needed a way to check if any given number exists as a seed. Since expanding all those ranges would take too much space and looping them processor cycles, I only deal with the lower end and the length.\n",
    "\n",
    "To check if a seed is in any given seed range, I check if it's within its range."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "1a8826e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_all_seed_ranges(data_sections):\n",
    "    seed_range_input = [int(seed) for seed in re.findall(r'\\d+', data_sections[0].split(': ')[1])]\n",
    "    return zip(seed_range_input[::2], seed_range_input[1::2])\n",
    "\n",
    "def is_valid_seed(seed, seed_ranges):\n",
    "    for seed_range in seed_ranges:\n",
    "        if seed_range[0] < seed < seed_range[0] + seed_range[1]:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "853f1a26",
   "metadata": {},
   "source": [
    "To get the locations, I find the highest value in any given range and create a range from 1 to that value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f0ca6878",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "location_ranges = ranges[-1]\n",
    "\n",
    "# max() would work here without the lambda\n",
    "# because the first value in the Range happens\n",
    "# to be what we want.\n",
    "#\n",
    "# I wanted to make it explicit though\n",
    "highest_location_range = max(location_ranges, key=lambda range: range.dest_start)\n",
    "max_location = highest_location_range.dest_start + highest_location_range.range\n",
    "all_locations = range(1, max_location)\n",
    "\n",
    "seed_ranges = list(get_all_seed_ranges(data_sections))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9c3d4ee",
   "metadata": {},
   "source": [
    "To find the smallest location that maps to a seed, I start from 1 and loop until I find a matching seed and then stop.\n",
    "\n",
    "This takes roughly 40 seconds to run so there's probably a neater way to solve it in way less time. But it doesn't crash my computer and doesn't take more a minute to run so I'm okay with this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "140acf8c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found seed=2243422640 at location=2008785\n",
      "Solution: 2008785\n"
     ]
    }
   ],
   "source": [
    "part_2 = None\n",
    "\n",
    "for location in all_locations:\n",
    "    # `ranges[-1::-1]` skips the locations range and reverses list\n",
    "    seed = find_seed(location, ranges[-1::-1])\n",
    "    if is_valid_seed(seed, seed_ranges):\n",
    "        print(f'Found {seed=} at {location=}')\n",
    "        part_2 = location\n",
    "        break\n",
    "print(f'Solution: {part_2}')\n",
    "assert part_2 == 2008785"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bb777cb",
   "metadata": {},
   "source": [
    "## Two stars!\n",
    "\n",
    "Finally, managed to wrap this up before I got too much behind. We're now at 8/50 stars."
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}