Mapping Seeds to Locations

Day 5 presented us with a unique puzzle: determining the optimal planting locations based on a series of mappings in the Island Island Almanac. The challenge required us to navigate through multiple layers of conversions from seeds to locations.

Our Solution

We developed two TypeScript functions, partOne and partTwo, to decode the complex mappings detailed in the almanac. Both functions also utilized a shared utils.ts file that contained helper functions.

utils.ts: Helper Functions

function parseMap(input: string): number[][] {
  return input
    .trim()
    .split(":\n")[1]
    .split("\n")
    .map(row => row.split(" ").map(Number));
}

export function getMaps(inputArray: string[]): number[][][] {
  return inputArray.map(parseMap);
}

Our utility function getMaps played a crucial role in parsing and converting the almanac’s data into usable formats, significantly reducing code duplication and enhancing readability.

Part One: Finding the Lowest Location

import { getMaps } from "./utils";

function findMapping(map: number[][], source: number): number {
  const correspondence = map.find(row => {
    const [, sourceStart, range] = row;
    return source >= sourceStart && source < sourceStart + range;
  });

  if (!correspondence) return source;

  const [destStart, sourceStart] = correspondence;
  const difference = destStart - sourceStart;
  return source + difference;
}

function lowestLocation(inputArray: string[], seeds: number[]): number {
  const [
    soilMap,
    fertilizerMap,
    waterMap,
    lightMap,
    temperatureMap,
    humidityMap,
    locationMap,
  ] = getMaps(inputArray.slice(1));

  let lowestLocation: number = Infinity;

  for (const seed of seeds) {
    const soil = findMapping(soilMap, seed);
    const fertilizer = findMapping(fertilizerMap, soil);
    const water = findMapping(waterMap, fertilizer);
    const light = findMapping(lightMap, water);
    const temperature = findMapping(temperatureMap, light);
    const humidity = findMapping(humidityMap, temperature);
    const location = findMapping(locationMap, humidity);

    lowestLocation = Math.min(lowestLocation, location);
  }

  return lowestLocation;
}

export default function partOne(inputArray: string[]): number {
  const [seedString] = inputArray;

  const seeds = seedString.split(": ")[1].split(" ").map(Number);

  return lowestLocation(inputArray, seeds);
}

In partOne, we used a series of mapping functions to translate each seed number through various categories until we found its corresponding location number. Our goal was to find the lowest location number for the initial seeds.

Part Two: Expanding Seed Ranges

import { getMaps } from "./utils";

function findMapping(map: number[][], source: number): number {
  const correspondence = map.find(row => {
    const [destStart, , range] = row;
    return source >= destStart && source < destStart + range;
  });

  if (!correspondence) return source;

  const [destStart, sourceStart] = correspondence;
  const difference = sourceStart - destStart;
  return source + difference;
}

function validSeed(seed: number, pairs: number[][]): boolean {
  return pairs.some(([start, end]) => seed >= start && seed < start + end);
}

function lowestLocation(inputArray: string[], pairs: number[][]): number {
  const [
    soilMap,
    fertilizerMap,
    waterMap,
    lightMap,
    temperatureMap,
    humidityMap,
    locationMap,
  ] = getMaps(inputArray.slice(1));

  let lowestLocation = Infinity;
  let location = 0;

  while (lowestLocation === Infinity) {
    const humidity = findMapping(locationMap, location);
    const temperature = findMapping(humidityMap, humidity);
    const light = findMapping(temperatureMap, temperature);
    const water = findMapping(lightMap, light);
    const fertilizer = findMapping(waterMap, water);
    const soil = findMapping(fertilizerMap, fertilizer);
    const seed = findMapping(soilMap, soil);

    if (validSeed(seed, pairs)) lowestLocation = location;
    else location++;
  }

  return lowestLocation;
}

export default function partTwo(inputArray: string[]): number {
  const [seedRangeArray] = inputArray;

  const pairs = seedRangeArray
    .split(": ")[1]
    .split(" ")
    .map(Number)
    .map<number[]>((seedStart, index, original) => {
      if (index % 2 !== 0) return [];
      return [seedStart, original[index + 1]];
    })
    .filter(pair => pair.length > 0);

  return lowestLocation(inputArray, pairs);
}

Part Two of Day 5’s challenge proved to be an exercise in both patience and ingenuity. Initially, my strategy involved testing every single seed within the specified ranges. I tried tracking all possible seeds in an array, but this quickly led to an overflow error as it consumed too much memory.

Overcoming Computational Challenges

In an attempt to brute force my way through the problem, I computed all seed values and iterated through them. This approach, while theoretically sound, was impractical in terms of efficiency. In fact, I left it running overnight, hoping for a solution by morning. However, in a twist of fate, my computer entered sleep mode, halting the process and leaving me without a solution.

A Shift in Strategy

Realizing the need for a different tactic, I shifted my focus from seeds to location numbers. I started with a location number of zero and incrementally increased it, checking each time to see if it corresponded to a valid seed from the initial ranges. This method proved to be far more efficient, taking only about three and a half minutes to find the solution! (A lot faster than overnight!)

Continuous Learning and Improvement

This journey highlighted the importance of flexibility in problem-solving. While my final solution was significantly faster than my initial attempts, I know there is still room for improvement. I plan to further research and explore more efficient algorithms and techniques to optimize the solution. Day 5 was not just about finding the right answer; it was about evolving our approach and learning from each attempt.

Stay tuned as we continue to delve into more complex challenges and refine our coding strategies in the Advent of Code!