Today’s problem came with a pretty complex explanation, but solving the first part was pretty simple. I created a MarbleGame class that dealt with the actual game mechanics. My solution was pretty straight forward by using a list to save the circle’s state and loop through each marble. It worked pretty good for finding the solution for the first part of the problem.
I then hit a wall when reusing this solution for the second part of the problem, as the numbers become a lot bigger. My first attempt took over 45 minutes and ended up overflowing. I then tried to switch to 64 bit integers and initializing my list with enough memory so it wouldn’t need to expand during the calculations, but that also took more than 45 minutes. At least it gave me the correct answer.
This is where I start expecting harder problems to start coming and make me think of optimizations and/or better solutions.
Although my solution was working with a C# List, I didn’t like the time it took to find the solution, so I went back and rewrote a part of it. I changed the list to use a doubly linked list (LinkedList in C#). That reduced the computation time from 45 minutes to less than 2 seconds.