Advent of Code 2015 Day 14
Part 1
- An exercise of
modulo
- The correct answer...a few seconds early?!
- 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 first10
and resting the other127
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 from2503
to2501
, 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 increasingdistance
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
- Altogether, instead of all at once
- 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.
Top comments (0)