Day 15. Rambunctious Recitation

Problem statement

https://adventofcode.com/2020/day/15 (mirror)

---

My solution

The most important statement in problem description from day 15 is:

So, after the starting numbers, each turn results in that player speaking aloud either 0 (if the last number is new) or an age (if the last number is a repeat).

If we then create a method that implements this requirement literally:

int RecitedNumberAge(int numberToLook, int currentIndex, int[] arrayToSearch)
{
    int memoryContent = arrayToSearch[numberToLook];
    arrayToSearch[numberToLook] = currentIndex;

    return memoryContent != -1 ? currentIndex - memoryContent : 0;
}

and simply loop it the required number of times (2020 for Part A, 30000000 for Part B), we will get the result. Array arrayToSearch is used as a map, which at index i holds the last turn during which number i was recited; we also initialize it to -1, to explicitly know if a number was never recited before – internally, the turn numbers are zero-indexed (which in hindsight was probably not the smartest choice 😑).

Therefore, the expression currentIndex - memoryContent means exactly the age of a number (of course, if the number was recited previously).

Note that after the initial sequence the age of any number is limited by the number of previous turns, so at most we need to initialize the size arrayToSearch to the number of turns we are expected to simulate! (The obvious exception would be if a number from the initial sequence was greater than the number of turns; for actual inputs this never happens though).

---

The last thing worth mentioning is the condition for stopping the for loop:

for (int i = initialNumbers.Length - 1; i <= iterations - 2; i++)
{
    currentNumberRecited = RecitedNumberAge(currentNumberRecited, i, lastRecitation);
}

We need to consider two things:

1. Turn numbers are zero-indexed internally.
2. Method RecitedNumberAge(currentNumberRecited, i, lastRecitation) returns the number that is uttered in turn i+1.

Each of those facts “decreases” the value of i at which we need to stop by 1, hence iterations - 2.