Advent of Code 2023 Day 5

Part 1

Huh?

I read the entire exposition and example explanation once.

And I'm a bit confused.

Then I saw my puzzle input.

The numbers are massive: in the billions!

So, I likely won't be working with filled number ranges, only boundaries.

Still, I gotta read this again.

A second playback

My understanding:

• Each journey is from seed to location: because each seed needs to be planted
• Each map step performs a numeric conversion from one category to another: source to destination
• Seemingly backwards, the first number is the lowest destination number, and the second is the lowest source number
• Lastly is the range of values from the lowest of each number

Inspecting the first mapping:

50 98 2
52 50 48

In words:

soil range start    seed range start    range length
soil range start    seed range start    range length

Another way to think of it:

50 <= 98 (+1)
52 <= 50 (+47)

Ok, this is making more sense.

The important edge case

Any source numbers that aren't mapped correspond to the same destination number.

That should be a fun condition to account for in my algorithm...eventually.

The abridged sample list makes more sense now

It is rendered in the opposite order of the input:

seed  | soil

instead of

soil <= seed

So, if I render it in the order of the input:

soil <= seed
50 98
51 99

52 50
53 51
54 52

0  0
1  1
2  2
...
49 49

I now understand the four confirmative seed number to soil number mappings.

Following Seed 79 through its mapping journey

I see how Seed 79 maps to Soil 81: 52 50 48.

Since no soil-to-fertilizer mapping ranges include 81, I see how Soil 81 maps too Fertilizer 81.

Same for Water, so Fertilizer 81 maps to Water 81.

Water's source range for Light includes 81, so Water 81 maps to Light 74.

Light's source range for Temperature includes 74, so Light maps to Temperature 78.

Temperature has no source number mapping to Humidity, so Temperature 78 maps to Humidity 78.

Finally, Humidity's source range for Location includes 78, so Humidity 78 maps to Location 82.

Was that the right answer?
Yup! Nice.

I think I finally get all this!

Now, how the heck am I gonna programmatically find the lowest Location number?

Piece-by-piece and trial-and-error. That's how!

Writing my program a little at a time

The input contains groups of text separated by double line breaks:

input.split('\n\n')

That will give me eight groups: the first is the seeds; the other seven are the mappings:

[ 'seeds...', 'mapping 1...', 'mapping 2...', ... ]

I need a list of the seed numbers - and I actually want to remove the seed number list from the processed input:

[....input.shift().matchAll(/\d+/g)].map(el => +el[0])

Then, I intend to do the following:

For each seed, accumulate a number that will become the lowest location number
  Check each mapping group for a source number and range
  Carry forward any mapped number to the next group
  At the end, compare the resulting number to the accumulated number, and swap only if the new number is lower

Sounds simple, but it will require a lot of code to extract numbers, determine ranges, iterate through each group, compare numbers and update numbers.

Converting each mapping group into lists of numbers:

const mappings = input.map(group => {
  group = group.split('\n')
  group.shift()
  return group.map(line => {
    return [...line.matchAll(/\d+/g)].map(el => +el[0])
  })
})

The shift() removes the first line of each group describing the mapping. I don't need that, since I can process each list in order.

Work in progress: Determining which - if any - mappings matches the current number:

const part1 = seeds.reduce((lowest, seed) => {
  mappings.reduce((num, group) => {
    let flags = group.map(set => num >= set[1] && num <= (set[1] + (set[2] - 1))).indexOf(true)
    if (flags === -1) {
      return num
    } else {
      // To-do: perform conversion using appropriate mapping range
    }
  }, seed)
  // To-do: compare this number with accumulated number
  return lowest
}, Infinity)

Work in progress: determining the location numbers:

const part1 = seeds.reduce((lowest, seed) => {
  const location = mappings.reduce((num, group) => {
    let match = group.map(set => num >= set[1] && num <= (set[1] + (set[2] - 1))).indexOf(true)
    if (match === -1) {
      return num
    } else {
      if (group[match][1] > group[match][0]) {
        return num - (group[match][1] - group[match][0])
      } else {
        return num + (group[match][0] - group[match][1])
      }
    }
  }, seed)
  console.log(location)
  return lowest
}, Infinity)

Running this on the example input shows me all four correct location numbers!

I'm seemingly on the right track!

With the last return statement updated, my algorithm generates the correct answer on the puzzle input!

const part1 = seeds.reduce((lowest, seed) => {
  const location = mappings.reduce((num, group) => {
    let match = group.map(set => num >= set[1] && num <= (set[1] + (set[2] - 1))).indexOf(true)
    if (match === -1) {
      return num
    } else {
      if (group[match][1] > group[match][0]) {
        return num - (group[match][1] - group[match][0])
      } else {
        return num + (group[match][0] - group[match][1])
      }
    }
  }, seed)
  return location >= lowest ? lowest : location
}, Infinity)

Will it generate an answer - let alone the correct one - on my puzzle input???

...

YES!!!

Wow!!!

I did it!!!

Part 2

This feels a lot harder...

...even though it seems like there must be some hidden fact about the numbers in a range that can prevent having to check each of them.

Since, of course, there are trillions of them.

How can I attempt to reveal this truth, if there is one?

I'm not gonna crack this code any time soon

I tried the brute-force approach on a single range of seeds.

My program ran for a minute without spitting out a result before I stopped it.

Clearly that isn't a feasible solution.

Sadly, I don't see any way to short-circuit this problem other than checking every seed...which would take an eternity and is clearly not the intended solve path.

So, I admit defeat and throw in the towel.

Part 1 was a blast to solve.

Part 2 requires more advanced computer science skills than I have.

Onward to Day 6!

cover photo is of The Bad Seed, a popular children's book hero