Red-Nosed Reports

Advent of Code 2024 Day 2

Part 1

To just solve, or to solve optimally? That is the question

To just solve:

• Compare the list in original order to two copies, each sorted, but in reverse orders. If one is a match, then success for criteria one
• Iterate through every item in the list, except the first. Track the difference of each item and previous item. If any differences are 0 or greater than 3, then this test fails.

Performance-wise, that means:
For criteria 1:

• Two list copies
• Sorting each copy
• Comparing original list twice For criteria 2:
• Check every number in each list

To solve optimally:

• For criteria 2, I'll leverage a while loop to check subsequent numbers for valid differences. That way, as soon as a disqualifying difference occurs, the rest of the numbers won't get processed
• For criteria 1, I'll track the differences, then do one check for whether all are less than or greater than zero

I think this will work. Only one way to find out.

Writing an optimized algorithm

Here's my code for identifying criteria 2 (difference of 1, 2, or 3):

let differFlag = true;
let i = 1;
while (differFlag && i < list.length) {
  let amount = Math.abs(list[i] - list[i - 1]);
  if (![1, 2, 3].includes(amount)) {
    differFlag = false;
  }
  i++;
}

• I only 'walk' the list until an invalid difference is caught, if any
• As soon as one is caught, the while loop exits
• After the while loop, I can check differFlag for the results

Here's my code for identifying criteria 1 (all differences increase or decrease):

let differFlag = true;
let i = 1;
let differences = [];
while (differFlag && i < list.length) {
  let amount = list[i] - list[i - 1];
  differences.push(amount);
  if (![1, 2, 3].includes(Math.abs(amount))) {
    differFlag = false;
  }
  i++;
}

• I create a list of each difference
• I moved the absolute value calculation to the conditional because I actually want to capture the sign of the difference
• After the while loop, I can check differences to see whether every value is positive or negative

Here's the final condition that captures a safe report:

if (
     differFlag &&
    (differences.every((el) => el > 0) || 
     differences.every((el) => el < 0))
    ) {
      safeCount++;
    }

Altogether, my algorithm generates the correct answer for the example input.

Will it do the same for my puzzle input??

Yessssirrrreeee!!

Sweet!

Part 2

Welllll...shoot.

This certainly complicates things a bit.

I'd like to avoid an algorithm that checks every possible permutation of a report. That would require generating millions of reports.

The first bit of good news is:

• All safe reports can still be counted as safe

For my puzzle input, that's about 200 that don't require me to check permutations.

Still, 800/1000 is still a lot of lists to fully explore permutations.

I honestly don't see a way to avoid running my algorithm on each permutation of unsafe reports.

Bummer.

Time to add a loop to iterate through each number in unsafe reports - the number to remove and then check the mutated list for a passing grade.

Adding a permutation-checking loop

I ended up duplicating my while loop with the added lines to duplicate and remove one number from each subsequent test report.

It's a lot more code.

But, it works! I generate the correct answer for the puzzle input!

Question is:

• Will it run...and generate the correct answer for my puzzle input?

Let's run it and see...

Hmmm, it runs, but I get an answer that it only slightly greater than my Part 1 answer. That seems wrong.

Doesn't hurt to submit it, right????

It is correct!

Holy smokes!

That's incredible!

And really fun to solve!

Four gold stars going into Day 3.

Bring on more wonderful puzzles!

The above is the detailed content of Red-Nosed Reports. For more information, please follow other related articles on the PHP Chinese website!