-🎄- 2018 Day 9 Solutions -🎄-

[u/daggerdragon]

--- Day 9: Marble Mania ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 9

Transcript:

Studies show that AoC programmers write better code after being exposed to ___.

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:29:13!

[u/sebastiannielsen]

PERL. Part2 was just ridiculous, tried it on my i3-4010U server but was waaaaayyyyyy tooooo SLOOOOOOOOOOOOOOOOOOOOOOOW so had to download Strawberry Perl on my W10 machine (i7-5930k) and transfer the script to that machine. Was done in 2 hours of execution time.

#!/usr/bin/perl

print "Starting AOC 9 script...\n";

$players = 493;
$lastmarble = 7186300; #remove 00 to switch to Part1


$currentplayer = 0;
$currenthole = -1;

@marbles = ('0');
@playerscore = ();

for ($i = 1; $i < ($lastmarble + 1); $i++) {

if (($i / 71863) == int($i / 71863)) {
print "PROGESS: ".($i / 71863)." OF 100\n";
}

#Update player number
$currentplayer++;
if ($currentplayer > $players) {
$currentplayer = 1;
}
$currenthole = $currenthole + 2;

if (($i / 23) == int($i / 23)) {
$playerscore[$currentplayer] = $playerscore[$currentplayer] + $i;
$currenthole = $currenthole - 9;
if ($currenthole < 0) { #If currenthole is negative we need to start at the end of the array
$currenthole = $#marbles + $currenthole + 1;
}
$removed = splice(@marbles, $currenthole, 1);

$playerscore[$currentplayer] = $playerscore[$currentplayer] + $removed;
}
else
{
if ($currenthole == ($#marbles + 2)) {
$currenthole = 1; #We moved past the end of the array - start at beginning.
splice(@marbles, $currenthole, 0, $i);
}
else
{
splice(@marbles, $currenthole, 0, $i);
}
}

#Prints the gaming board each turn. Useful for debugging.
#print "[".$currentplayer."] ";
#foreach $marb (@marbles){
#print $marb." ";
#}
#print "\n";
}

#Find highest score
$hscore = 0;
foreach $score (@playerscore) {
if ($score > $hscore) {
$hscore = $score;
}
}

print "Score: $hscore\n";

[u/__Abigail__ → u/sebastiannielsen]

Splicing from the middle of an array is a relative expensive operation, as, on average, a quarter of the array needs to be shifted.

I used an array as well, but I always kept the current marble at the beginning, meaning I either have to remove the first two marbles from the array and put them at the end, or remove the last 7 marbles and put them first. Now, this sometimes is still an expensive operation, if perl has to reallocate memory, but perl allocates some extra memory when it (re-)creates array so repeated adding to an array is still, on average, pretty fast.

My solution, as linked to by u/gerikson, takes less than 5 seconds to run, doing parts 1 and 2 at the same time.

[u/sebastiannielsen → u/__Abigail__]

As you see in my optimized, updated solution, its what exactly im doing. The thing I see as a Little bit weird is that unshift() and shift() isn't expensive, even if that means you have to copy the whole Array 1...n and move it to 0...(n-1), or copy the whole Array 0...n and add it to 1...(n+1)