# Improving performance of algorithm to compute Code puzzles

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?

Edit: here is the input data.

day1 = {-7, +16, +5, +11, +18, -14, +11, +14, -2, +13, -12, +10, +1, +16, +17, +5, -8, +17, +15, -17, +7, -1, -3, -8, -12, -1, -14, -19, +2, -19, +5, +10, +1, -9, -18, -3, +8, +3, +1, +5, +7, -2, -21, -2, +11, +10, +19, +8, -15, +19, -3, +7, -1, -13, +5, +17, -18, +7, +9, +1, -6, +13, -3, +12, +17, +1, +10, +9, -17, -15, +14, +13, +15, +12, +2, -19, +11, -3, +10, +17, -6, +11, -2, +13, +17, +16, +4, -16, +14, -10, -2, -13, -11, -1, -5, -5, +15, +12, -1, -2, +6, +8, +2, +8, -17, -11, -17, -12, -4, -3, -1, -1, +13, +11, +10, -3, -9, +19, +19, +4, +15, +19, -14, -6, -8, -9, -9, +21, -1, +2, +15, -1, +3, +3, +14, +3, +3, -9, +4, +19, +6, -7, -15, +4, +3, +7, -5, +20, +13, -6, +19, +8, +15, +6, +9, +17, -7, -11, +7, -19, +16, +6, -8, -7, +18, +9, +16, +8, -5, -8, +10, +11, +3, -7, -18, -3, -9, +17, -18, -16, -18, -18, +16, -1, -1, -5, -16, -2, -3, +2, +5, +10, -13, -6, -15, +14, -12, -1, +17, -2, +12, +12, +19, +12, -15, +20, -6, +15, +11, +15, +14, -16, -2, -17, -2, -9, -30, -12, -14, +16, +12, +2, +15, +18, +24, +11, +18, -7, +6, +5, +15, -4, +10, +8, +4, -11, -14, -6, -19, +16, -2, -11, -15, -10, +19, -1, +5, +14, -8, -18, -13, +16, +10, +9, +13, +5, +1, +1, -13, -20, -23, -3, -20, +14, -15, +12, -28, +22, -23, -14, -16, +2, -6, -17, -18, -13, +4, +5, +9, +14, +1, +16, +8, +1, -23, -5, -3, -1, +3, -13, -11, -2, +16, +6, -23, +13, -4, -1, -20, -3, -6, +12, -11, -6, +8, +2, -19, +8, -20, +1, +17, +10, +14, +1, -37, +19, -20, -21, -2, -11, -7, +4, +7, +21, +19, -8, -14, +17, -8, +9, +11, +18, -16, +33, +5, +3, +43, +17, +39, +20, +3, +15, +17, +19, +19, -15, +5, -7, +15, +13, -15, -19, +12, +8, +13, +11, -20, -9, +10, -3, -4, -8, -17, +10, +14, -3, -18, -10, +8, +13, +19, -27, -36, +19, +19, -32, +10, -12, -3, +28, -11, -35, -7, -19, -13, -22, -21, +11, +13, +12, +26, +131, +7, +9, -10, +8, -19, +26, +10, +1, +21, +11, +10, +17, -16, +8, -4, +7, +8, -1, +19, -11, +4, -17, +18, -17, +1, -17, -11, +14, +8, -12, +5, +22, -1, -3, +13, -1, -11, -15, -1, -21, -14, +20, -2, -15, -18, +21, -11, +12, +6, -12, +20, -22, -32, -31, +9, +25, +14, +14, +86, -9, +13, +5, +10, -20, -3, -6, -2, +7, +15, +1, -24, -12, +19, -21, +80, -32, -5, +22, -18, +56, -30, +21, -111, -107, +424, +535, +64723, -2, +7, -14, +5, +11, -8, +17, +1, -8, -17, +3, +8, +16, -4, +6, +13, -6, +1, +4, -3, -3, +13, -18, +13, +2, +18, -3, -14, +10, +12, -9, +12, +11, +6, -8, -7, +2, +18, -12, -9, +15, +3, -4, +3, -15, -19, +21, -9, +2, -5, -14, +15, -18, +6, +8, -17, -4, -6, +5, +19, -7, -18, -13, -19, -10, -19, -19, -2, -7, -5, +8, -1, -1, -9, +5, -7, -15, -2, +8, +17, +6, +9, -14, -10, -9, +14, -12, -3, -9, +13, +8, -4, +9, +14, -5, +19, +3, +8, +4, +13, -9, -6, -14, +18, +9, -4, -2, +1, -13, -16, +22, -2, -16, -2, +1, +12, -5, +3, -8, +21, -9, -19, +3, -2, +7, -10, +22, -23, +14, +23, +6, -1, +5, -9, +12, +7, +6, +8, +6, -1, -3, -14, +7, -26, +15, -36, +10, +25, +10, -3, +6, +30, +18, -16, +3, +20, +1, +21, +3, +8, +3, +18, +5, -18, -18, +15, -12, -6, +9, +16, +3, +5, -18, +14, +9, +9, +18, -7, -10, +14, -5, +13, +9, -4, -14, +2, -12, +4, +5, +4, +5, +4, +15, +9, -17, +2, -10, +6, -2, +17, +10, +15, +9, -14, +16, +2, -10, -6, -15, -8, -6, -1, +5, -3, +14, +15, -5, -2, +17, +11, +16, +7, +18, +4, +16, +16, -5, +18, +10, +16, +4, -11, +4, +4, +18, -13, -12, +17, +13, -19, +16, +17, +9, -18, +3, +8, -10, -13, -5, -5, -20, -11, +10, -5, -3, -11, -8, +11, -10, +12, -14, +15, -10, -21, +8, -14, -12, -8, -5, +15, -16, -2, -4, -6, -12, -6, +10, +15, -16, -7, +6, -11, -10, -12, -12, +8, -15, +18, -9, -14, -1, -9, -3, -19, -9, -13, +15, +8, +14, -26, -9, -5, -17, +10, -6, +10, +16, -18, -5, +20, +22, +22, -15, -10, -21, +19, -10, +6, -19, -19, -8, -10, +13, -8, -17, +4, +15, -13, +9, -10, -35, +17, -4, +43, +15, -28, +3, +21, +17, +32, +9, +37, -8, +6, +5, +2, +21, -18, -12, -16, +5, +6, +27, -7, -1, -1, +11, +18, +3, +10, -18, -3, -16, +20, +18, +7, -19, +14, +16, -12, -16, -11, +14, -9, -14, +10, -8, +11, +25, +1, +18, +17, -18, -11, +13, +12, -7, +1, +18, -1, +11, -13, -7, +16, -19, +17, -20, -6, -16, +5, +2, +1, -21, +9, +28, +26, +8, +4, +2, +7, +15, +5, +2, +15, -9, +19, +5, -13, +2, -3, -2, -18, -6, -15, -16, -11, +24, +16, +17, -3, +6, -5, +4, +30, +4, -19, +17, -10, -18, -17, -15, -11, -22, -12, -6, -10, -20, +15, +49, +21, -7, -6, +12, -19, -39, -7, -7, +50, +29, +6, +36, -18, +11, +14, +8, +15, -40, +231, +56, -7, -4, -42, -7, -16, -15, +159, +471, -309, +65050, -5, -18, -17, +7, -11, +3, -18, +5, -8, -11, -14, +13, +3, -14, +16, +19, +8, -9, -10, +9, +14, +16, +1, +17, +17, +14, -4, -19, +13, +18, +11, +17, -14, +17, +14, -3, +19, -7, +12, +3, +2, -16, -14, +2, -5, -18, +6, -17, -5, +3, +17, +8, -14, -13, +17, +12, -11, -17, -15, -17, -10, -12, -1, -13, -5, -2, -2, -11, -6, -2, -131610}

• do not use Append to accumulate data. See tips-for-writing-fast-mathematica-code and alternatives-to-append-appendto-for-generating-a-list-in-an-interactive Dec 2, 2018 at 4:41
• Using itertools.cycle, Python can solve this problem in about 0.02 second. Waiting for someone making Wolfram competitive too. Dec 2, 2018 at 8:25
• Can you place real data to check the code? Dec 2, 2018 at 11:20
• @Nasser thank you for these! Dec 2, 2018 at 13:18
• Another good thing to keep in mind is that Mathematica sometimes seems slow whenever you ask it to print large output into the notebook. For example, when you evaluate Range[10^6], it will take close to a second before it dumps a summary of the data onto your screen. Most of this time is spend printing the output, though. The actual process of generating the list in the kernel is much faster: when you evaluate RepeatedTiming[Range[10^6];], you'll see that it only takes mere milliseconds to generate the list. Dec 2, 2018 at 13:54

You can improve modestly by using down values instead of Association.

Clear[sums];
Timing[
i = 0;
day1total = 0;
len = Length[day1];
While[
sums[day1total += day1[[Mod[++i, len, 1]]]] =!= 1,
sums[day1total] = 1
];
{i, day1total}]

(* Out[94]= {1.65625, {141207, 66105}} *)


This gives a factor of 2 on my somewhat slow laptop machine.

One can do better by recognizing that the repeated value must be in the list of accumulated sums. Since the sum of absolute values is modest in value, we can avoid down values and Association and instead use a list of machine integers to tell when a particular value has been hit twice. This is still not blindingly fast, but it can be put through Compile and that gives a nice boost.

I have not mentally proven this, but I believe the size of the list used below is adequate, provided a repeat exists. [Later note: it is adequate, subject to the stated proviso. Also the prior version had some excess I had forgotten to remove. This one now compiles to C (my home laptop didn't have C installed) and also is a faster machine.]

findRepeatC = Compile[{{data, _Integer, 1}}, Module[
{i = 0, len = Length[data], min = Total[Abs[data]] + 1, vals,
vtot = 0},
vals = ConstantArray[0, 2*min];
While[vtot += data[[Mod[++i, len, 1]]];
vals[[vtot + min]] == 0, vals[[vtot + min]]++];
{i, vtot}], CompilationTarget -> "C"];


Test:

In[55]:= RepeatedTiming[findRepeatC[day1]]

(* Out[55]= {0.0110, {141207, 66105}} *)


[About 4x faster than on my home laptop and not compiling to C.]

Nasser's comment pointed me in the right direction. The bottleneck is apparently in the Append[] function. By switching to an Association we can write to the data structure without copying it.

data = day1;
day1total = 0;
day1frequencies = Association[];
i = 1;
While[Not[KeyMemberQ[day1frequencies, day1total]],
day1frequencies[day1total] = 1;
day1total += data[[i]];
i = Mod[i, Length[data]] + 1]
day1frequencies
day1total


Profiling the updated algorithm with Timing[] shows that it completes in less than one second.

Another possible solution (not as fast as Daniel's compile):

n = 0;
nn = 1;

While[
DuplicateFreeQ[
Prepend[Accumulate[Flatten[ConstantArray[day1, n]]], 0]
]
, n++];
acc = Prepend[Accumulate[Flatten[ConstantArray[day1, n - 1]]], 0];
While[DuplicateFreeQ[acc],
AppendTo[acc, acc[[-1]] + day1[[nn]]];
nn++];
acc[[-1]]