I did the part 1 using array and splicing and it took ~30 seconds to finish (and it was getting exponentially slower as the number of marbles increased).
So for the part 2 I tried to find the correct data structure, but not having CS background I spent a lot of time just googling around not finding anything suitable. Finally I looked at reddit for a hint and learned about Doubly Circular Linked List. After that implementation was quick and easy :)
<?php$players=463;$marbles=71787;functionplay($players,$marbles){$circle=[];$player=0;$scores=[];$currentMarble=0;for($marble=0;$marble<=$marbles;$marble++){if(!$marble){$circle[0]['prev']=0;$circle[0]['next']=0;}elseif($marble%23){$newPrev=$circle[$currentMarble]['next'];$newNext=$circle[$newPrev]['next'];$circle[$newPrev]['next']=$marble;$circle[$newNext]['prev']=$marble;$circle[$marble]=['prev'=>$newPrev,'next'=>$newNext];$currentMarble=$marble;}else{$currScore=!empty($scores[$player])?$scores[$player]:0;$taken=$currentMarble;for($i=0;$i<7;$i++){$taken=$circle[$taken]['prev'];}$currentMarble=$circle[$taken]['next'];$leftMarble=$circle[$taken]['prev'];$circle[$currentMarble]['prev']=$leftMarble;$circle[$leftMarble]['next']=$currentMarble;$scores[$player]=$currScore+$marble+$taken;$i++;}$player=++$player%$players;}returnmax($scores);}echo"Answer to Part 1: ".play($players,$marbles)."\n";echo"Answer to Part 2: ".play($players,$marbles*100)."\n";?>
Ryan is an engineer in the Sacramento Area with a focus in Python, Ruby, and Rust. Bash/Python Exercism mentor. Coding, physics, calculus, music, woodworking. Looking for work!
I did the part 1 using array and splicing and it took ~30 seconds to finish (and it was getting exponentially slower as the number of marbles increased).
So for the part 2 I tried to find the correct data structure, but not having CS background I spent a lot of time just googling around not finding anything suitable. Finally I looked at reddit for a hint and learned about Doubly Circular Linked List. After that implementation was quick and easy :)
Nice find!