I hope to explore Mathematica by using it for Advent of Code puzzles this year, so spoiler alert for anyone interested in solving https://adventofcode.com/2018/day/1 for themselves.

Part 2 of yesterday’s problem requires you to repeatedly iterate through a list of positive and negative integers, compute the running sum, and terminate when the sum repeats. Here is my code with reference data:

`data = {7, 7, -2, -7, -4}; day1total = 0; day1frequencies = {}; i = 1; While[Not[MemberQ[day1frequencies, day1total]], day1frequencies = Append[day1frequencies, day1total]; day1total += data[[i]]; i = Mod[i, Length[data]] + 1] day1frequencies day1total `

This algorithm produces the correct answer (14). When I run this algorithm against the real input ($ |\texttt{data}|=1029$ ) this algorithm computed the answer in 141207 iterations, which means $ 0\le|\texttt{day1frequencies}|<141207$ throughout the computation.

This algorithm took several minutes to complete. I wonder if `{}`

creates a basic array with $ O(n)$ searches with `MemberQ`

, but I do not know how to prove this. I notice that printing `day1frequencies`

preserves insertion order.

I experimented with `day1frequencies = Association[{}]`

, hoping searches would occur in $ O(\log{n})$ or $ O(1)$ , but it didn’t seem any faster.

Why is this algorithm so slow?