Oh thank goodness. Day 6 of Advent of Code came back to the simpler side of things. I was able to finish it by 12:30 and figured I would get to bed a bit earlier and get a good nights sleep…but then Minecraft Dungeons might have pushed that to 1AM thanks to TrueAchievement’s Twelve Days of Christmas Challenge. Oh well.
Part One – Boat Races
Sample Data:
Time: 7 15 30
Distance: 9 40 200What we need: To figure out how long we should hold the button to go the furthest
Time: 7 seconds
Hold for 1: Moves 1 for 6 seconds (6)
Hold for 2: Moves 2 for 5 seconds (10)
Hold for 3: Moves 3 for 4 seconds (12)
Hold for 4: Moves 4 for 3 seconds (12)
...I didn’t notice it right away. I started working through the logic, aiming to not run through every number thinking about memory issues again, and I thought “Well we know holding for 0 second or holding for all 7 won’t go anywhere, but 1 is too low, 6 would be as well. Can I start in the middle? Just go left and right so I’m only working with some of the numbers until the first one goes under? There has to be a formula to get numbers that would hit without running through all, but I’m not wasting time looking for that. Let’s just output everything.
As I’m typing this, I thought of a quicker way to do it. Below you will see me just going from lowest to middle, but I wonder if you started at the midpoint, or midpoint minus 0.5 if it’s an even amount of numbers, and worked down, you’ll eventually hit a number below the record. From here you can just break out and not calculate the rest.
In the case of 7/9, you’re only excluding one “hold” in the list that’s under the record, so not much time is saved, but in the 15/40, you’d be excluding three. In one of the non-sample races of mine, you’re skipping twenty-five. Definitely worth looking at more.
Breaking out the rows was pretty simple, taking the substr($rows[0], strpos($rows[0], ":") + 1) from a few other problems this year, exploding on the space, filtering the ones with only spaces, and using array_values to reset the keys, I had my array of $time_limits and $records;
Time to output to make sure it lines up:
foreach( $time_limit as $k => $time ) {
for ( $hold = 1; $hold < $time; $hold++ ) {
$total_distance = ( $time - $hold ) * $hold;
if ( $total_distance > $records[$k] ) {
$winning_times[$k] = $winning_times[$k] + 1;
}
}
}So as I output every step ($total_distance) to make sure I was lining up with sample data results, I noticed it looked like a bell curve.
Race 1: 6, 10, 12, 12, 10, 6
Race 2: 14, 26, 36, 44, 50, 54, 56, 56, 54, 50, …
It’s mirrored on each side! I can trim the result in half to save some calculations.
for ( $hold = 1; $hold < ($time / 2); $hold++ ) {
After that I output my results, I should get 4, 8, and 9
I get 4, 8, and 8
Well alright, race one and two are good, what’s wrong with race three?
Race 3: … 216, 221, 224, 225, 224, 221, 216 …
Oh! Races one and two were both odd times, so there was a [0]-1-2-3 on one side, and a 4-5-6-[7] on the other (ignoring 0 and 7 since those are 0 distance times). With 30, it went from 1-14, 15, 16-29.
That middle point is going to be the most efficient, so it’ll always be a win. I just need to add one to the result to give me the 9 I need.
// If the original number is even, add one
if ( $time % 2 === 0 ) {
$winning_times[$k] = $winning_times[$k] + 1;
}Looking back now, I could write this better to just multiply the results instead of adding them to an array, but array_product( $winning_times) gave me the 288 I needed for the sample, and the correct result for my problem. 7738th place at 00:23:35;
Part One Solution:
function part_one($rows) {
$time_limit = generate_records( $rows )[0];
$records = generate_records( $rows )[1];
$winning_times = [];
// Records are a bell curve
foreach( $time_limit as $k => $time ) {
$winning_times[$k] = 0;
for ( $hold = 1; $hold < ( $time / 2 ); $hold++ ) {
$total_distance = ( $time - $hold ) * $hold;
if ( $total_distance > $records[$k] ) {
$winning_times[$k] = $winning_times[$k] + 1;
}
}
$winning_times[$k] = $winning_times[$k] * 2;
if ( $time % 2 === 0 ) {
$winning_times[$k] = $winning_times[$k] + 1;
}
}
echo array_product( $winning_times );
}
function generate_records( $rows ) {
$times = array_values( array_filter( explode( ' ', substr($rows[0], strpos($rows[0], ":") + 1) ) ) );
$records = array_values( array_filter( explode( ' ', substr($rows[1], strpos($rows[1], ":") + 1) ) ) );
return [ $times, $records ];
}Part Two – One Race
This was exciting, part two was going to be exactly the same logic, it was just different race parameters.
Sample Data, same as above:
Time: 7 15 30
Distance: 9 40 200What we we’re looking for:
Time: 7 15 30 is really 71,530
Distance: 9 40 200 is really 940,200Instead of an array of values to loop through, I just needed to combine those into one number. generate_records( $rows )[0] became implode( '', generate_records( $rows )[0] );, mushing the numbers together without a space.
From here, it was the same function as before, just removing the foreach and using those single strings.
The sample data worked instantly, the real data on the other hand took about 3.2 seconds.
I was happy I got the answer, but could it be done quicker? Definitely. I had to figure out something better.
Either way, it was still a success, one that I got in less than three extra minutes thanks to how I wrote everything out from the start. Good enough for 6529th at 00:27:10.
Part Two Solution:
// generate_records( $rows ) - Same as Above
function part_two($rows) {
$time_limit = implode( '', generate_records( $rows )[0] );
$record = implode( '', generate_records( $rows )[1] );
$winning_times = 0;
// Records are a bell curve
for ( $hold = 1; $hold < round( $time_limit / 2 ); $hold++ ) {
$total_distance = ( $time_limit - $hold ) * $hold;
if ( $total_distance > $record ) {
$winning_times = $winning_times + 1;
}
}
$winning_times = $winning_times * 2;
if ( $time_limit % 2 === 0 ) {
$winning_times = $winning_times + 1;
}
echo $winning_times;
}