Reindeer Olympics

Advent of Code 2015 Day 14

Part 1

1. An exercise of modulo
2. The correct answer...a few seconds early?!
3. The correct answer...right on time!

An exercise of modulo

Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.

How it seems the math works:

• In any given span of 10 + 127 seconds, Comet is flying the first 10 and resting the other 127

Thus, an algorithm could be:

Set distance to 0
For i from 0 up to but not including the specified duration
  If the remainder after dividing i by the sum of seconds flying and resting is equal to 0
    For j from 0 up to but not including the seconds spent flying
      Increment distance by the km/s

My algorithm in JavaScript:

// Inside input.reduce()
let distance = 0
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      distance += kmps
    }
  }
}

That algorithm sits inside a reduce() that accumulates a maximum number based on the distance traveled by each reindeer.

• It generates the correct answer for the example input
• But the wrong answer for my puzzle input

The correct answer...a few seconds early?!

Interestingly enough:

• When I move target up from 2503 to 2501, I generate the correct answer!

Why is that?

...

The correct answer...right on time!

Oh, I think I see why:

• My inner-most for loop is increasing distance the same amount of times each time
• But when right near the target second, it should only increase distance enough seconds until reaching the target second...and no more

My updated algorithm in JavaScript:

let distance = 0
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      if (second + i < target) {
        distance += kmps
      }
    }
  }
}

As hoped, that generates the correct answer at the right target second!

Part 2

1. Altogether, instead of all at once
2. A series of loops

Altogether, instead of all at once

• My algorithm in Part 1 completes each reindeer's route individually
• Now, I'll have to somehow complete each reindeer's route together, one second at a time
• I think I can repurpose my algorithm to generate each reindeer's list of seconds spent flying
• And use a separate loop to tally each reindeer's points and distance travelled

A series of loops

The first loop generates each reindeer's list of seconds spent flying, coupled with its km/s and initial distance traveled, 0:

// Inside input.map()
let seconds_awake = []
for (let second = 0; second < target; i++) {
  if (second % (flying + resting) == 0) {
    for (let i = 0; i < flying; i++) {
      if (second + i < target) {
        seconds_awake.push(i + j)
      }
    }
  }
}
return { 
  kmps: kmps, 
  secs: seconds_awake, 
  distance: 0 
}

Next, I need an array to track each reindeer's score:

let points = new Array(input.length).fill(0)

Lastly, the race and point-collecting algorithm:

For second from 0 to the target, again
  For each reindeer
    If second is a number in the list of seconds spend flying
      Increment distance by kmps
    Else, increment by 0
  Create a list of only the reindeer's distances travelled
  Calculate the furthest distance travelled
  For each point
    If the distance in the same position as point matches the furthest distance travelled
      Increment point by 1
    Else, increment by 0
Return the largest value in points

My algorithm in JavaScript:

for (let second = 0; second < 2503; second++) {
  reindeer = reindeer.map(r => {
    r.distance += r.secs.includes(second) ? r.kmps : 0
    return r
  })
  let distances = reindeer.map(r => r.distance)
  let leader = Math.max(...distances)
  points = points.map((point, i) => {
    return point += distances[i] == leader ? 1 : 0
  })
}
return Math.max(...points)

• At first I mistakenly thought points were added to the distance, and the largest distance was still the expected answer
• So, my first answer submitted was way too high
• But after reading, Part 2 only cared about the score resulting from the points awarded each second

My updated algorithm shown above generated the correct answer!

I did it!!

• I solved both parts!
• By understanding how to leverage modulo to determine each second a reindeer spent awake and flying!
• And fixing my first algorithm to not over-increment distance travelled!
• And fixing my second algorithm to not combine points with distance travelled!

It's incredible to come across puzzles that feel novel this far into my journey!

Sure, I used familiar algorithmic and mathematical tools to solve it, but the puzzle itself felt unlike any others I've encountered thus far.

Hopefully the second half of the year will offer a few more twists on some themes that I've become all too familiar with.