Print Queue

Advent of Code 2024 Day 5

Part 1

There will be order!

This is gonna be a doozy.

I like the added caveat that rules for pages not included in an update should not be considered.

I have a vague idea of how to approach this puzzle.

But I'll need to work out my strategy here to get clarity and make sure I'm ready to write actual code.

Stumbling into a strategy, I hope

It's funny. I feel like I know how to solve this in an over-check-y kind of way.

Here's what I'm thinking.

Convert the first of two lists into a catalogue of page numbers to any/all pages it must precede:

From this:

47|53
97|13
97|61
...

To this:

{
  47: [53],
  97: [13, 61],
  ...
}

But how might I use it?

Wait. Pivot!!

Looking at the first example pages update:

75,47,61,53,29

And reviewing the in-depth proof for its correct order...

...makes me think about the overly tedious approach:

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

Downsides, performance-wise:

• This requires walking the whole set of page order rules for each list
• Seems like a factorial in the task of checking all possible pairs of numbers

Not too sure about that approach.

Back to my object of keys and lists of 'before's.

What if I made the object more comprehensive:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

• The first nested list catalogues the numbers that must come before it
• The second nested list catalogues the numbers that must come after it

In theory (and pseudocode):

For each number in the list
  Create an ordered list of the previous numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  Create an ordered list of the subsequent numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  If both flags are true
    Number is in the correct order

An example walkthrough:

75

Before: []
After: [47,61,53,29]

Catalog:
{
  75: [ [29, 47, 53, 61, 13], [97] ]
}

Before: Empty - success

After: [True, True, True, True]

All True? Yes - success

Correct Order

I definitely think it's time to write an algorithm that at least builds my catalogue object.

Building the cataloging algorithm

Separating the rules from the update list:

let [rules, updates] = input.split('\n\n')

Parsing the input into a list of 2-item lists where each item is a number:

rules = rules.split('\n').map(el => el.split('|').map(Number))

Reducing that list into an object full of keys and list values:

rules = rules.reduce((obj, item) => {
  if (!(item[0] in obj)) {
    obj[item[0]] = []
  }
  obj[item[0]].push(item[1])
  return obj
}, {})

Does this work as expected?

Yes, it output this object:

{
  '29': [ 13 ],
  '47': [ 53, 13, 61, 29 ],
  '53': [ 29, 13 ],
  '61': [ 13, 53, 29 ],
  '75': [ 29, 53, 47, 61, 13 ],
  '97': [ 13, 61, 47, 29, 53, 75 ]
}

Notice I'm back to only recording numbers that must come after any given number.

That's because I don't think I have to check both sides.

I may be wrong.

But I'm going to proceed under this assumption.

Checking all numbers after each number

I'll work on the first example update, which should show as correct.

First, I need to parse the input into lists of numbers:

updates = updates.split("\n").map((el) => el.split(",").map(Number));

Then, extract the first list for testing:

let test = updates[0];

Now for the real work.

First attempt:

47|53
97|13
97|61
...

It seemed to be working until I tried it on the fifth example list item:

{
  47: [53],
  97: [13, 61],
  ...
}

My algorithm checks for each number to exist as a key in the catalog, and checks all numbers in its associated list for a match.

But 13 isn't in the catalog. My algorithm wrongly assumes a correct verdict.

And when it gets to 29, since there are no more numbers, it assumes correct, too.

So, I need to adjust my strategy.

Second attempt:

75,47,61,53,29

This generates the correct answer for every example list!

It correctly checks each number in the sub-list of numbers that appear after each number for the inclusion of the number being checked (the number that is immediately preceding the sub-list).

Thus, in the case of:

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

When it encounters 13, it looks up 29 and sees 13, which means they are in the wrong order.

Plugging this into a reduce and adding up middle numbers

It wasn't as tough as I thought:

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

It generates the correct answer for the example input!

How will it do with my puzzle input???

It generated the correct answer again!!!

Woohoo!!!

I feel like I overthought that for a while. Then the answer became clear when I saw what wasn't working.

Fun stuff!

What new challenges will Part 2 bring...?

Part 2

An exercise in sorting

I probably should have seen this coming.

Thankfully, I think my algorithm has set me up well for this.

I'm going to have to sort each list.

Sorting works by comparing two values and doing one of two things based on one of three outcomes:

• If a -1 is returned from the sorting function, the first value comes before the second
• If a 1 is returned, the second value should come before the first
• If a 0 is returned, no values are moved since they are equal

My algorithm generates lists of boolean values.

When all boolean values are true, the number that generated them correctly comes before all of them.

However, if any boolean values are false, one of those numbers should come before the current number.

But if I were to compare two numbers, and both of their lists had a false value, how would I know which should come first?

I really only have a way to address cases where one list is all true and the other is not, or both are all true.

Hmmmm.

I think I need to perform my test on two numbers at a time instead of on a list of numbers.

Exactly like in how sorting works: a vs b

Adjusting my algorithm for 1 v. 1 combat instead of 1 v. many

After some head-scratching, ternary-checking, and second-guessing, I arrived at a working algorithm:

47|53
97|13
97|61
...

Running it on each of the incorrect-order example updates produces a correctly-ordered list!

I'm excited to run it on all the lists in both inputs and hopefully finish today with two well-earned gold stars!

Overlooking a huge...minor detail

I ran my algorithm on the example input and got a larger number than shown.

I had no idea why. Printing out each correctly-sorted list proved its elements are in the right order.

Then I re-read the instructions:

only the incorrectly-ordered updates

That makes sense! I was adding up every list's middle value!

Fixing for this requires a little slice()ing to duplicate the list, then comparing stringified versions:

{
  47: [53],
  97: [13, 61],
  ...
}

Viola! I get the correct answer for the example input.

Fingers crossed I get it for my puzzle input!

Indeed!!!

SWEEEEET!!

Two gold stars. All mine!

What another fun puzzle.

Took a few days to think through and derive some strategies.

But I eventually found my way through the fog.

Onward to Day 6!

The above is the detailed content of Print Queue. For more information, please follow other related articles on the PHP Chinese website!