Codility - Number Solitaire

Solution to Codility lesson15-exercise1 Number Solitarie problem, link to Codility problem and complete solution at the end of the post.
Assume that:

\mathbf{A} = \{x \in \mathbb{Z}\ | -10,000 \leq x \leq 10,000 \land |A| = N \},\mathbf{A}\, is\, a\, multiset.
\{N \in \mathbb{N}\ |\ 2 \leq N \leq 100,000\}

Starting at index 0. The initial result is the value of the element at index 0. From index i we can move from 1 to 6 indexes, we'll call this difference k. Then we travel from the index i to the index i + k. But we cannot choose such that i + k > N - 1. Having a valid k we add the value of the element at i + k to the result, and i becomes i + k.

When we reach the index N + 1, we sum the value at N + 1 to the result, and this will be our final result.

Define a function solution with input A, such that solution returns the maximal result that can be achieved on the board represented by array A.

  • Expected worst-case time complexity is O(N);
  • Expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified. 


The number of possible combinations is,
f(N) = \left\{ \begin{array}{ll} 2^{N-2}& \mbox{if } N<8\\ 2^{N-2}-(2^{N-8})& \mbox{if } N\geq8\end{array} \right.
If you are interested only on the code you can skip this part.

Demonstration: First let's consider this, in a array A with size N, index i and k being the dice result, we have a tree of possibilities that could be described as follows. 
Starting from 0 we could go to indexes 1, 2, 3, 4, 5, 6, and them from 1, we could go to 2, 3, 4, 5, 6, 7, so basically from index i, we can go from i + 1, to i + 6, as long as i + 6 < N. So to calculate the total of possible combinations let's traverse the array from N - 1, to 0. 
Starting at N - 1, we have no possible combination, at N - 2, we have 1 combination with k = 1, from N - 3, we can get to N - 2, with k = 1, and N - 1 with k = 2, which gives 1 combination when we reach N - 1, and from N - 2 we know that we cant get only one combination, so this gives us 2 possibilities. The pattern follows on the table below. 

\begin{array}{|c|c|c|c|c|c|c|c|}\hline i & k=1 & k=2 & k=3 & k=4 & k=5 & k=6 & total
\\\hline N-1 & -- & -- & -- & -- & -- & -- & 0
\\\hline N-2 & 1 & -- & -- & -- & -- & -- & 1
\\\hline N-3 & 1 & 1 & -- & -- & -- & -- & 2
\\\hline N-4 & 2 & 1 & 1 & -- & -- & -- & 4
\\\hline N-5 & 4 & 2 & 1 & 1 & -- & -- & 8
\\\hline N-6 & 8 & 4 & 2 & 1 & 1 & -- & 16
\\\hline N-7 & 16 & 8 & 4 & 2 & 1 & 1 & 32\\\hline 

We can see that there is a pattern here, for an array of size N the total of combinations is 2^{N - 2}, but this pattern doesn't continue for too long, because we have a die with six sides when N >= 8 we start to lose some combinations, for example, when N = 8, N - 1 = 7, and we can't get from 0 to 7 with the values that can be assumed by k, so the total combinations for N = 8 would be 2^{N-2} - 1. For N = 9, we are not going to be able to reach from 0 indexes 7, 8, Losing two combinations, as you can see, this is going to be very similar to the pattern that we found before. For N\geq8 we have to a total combinations of 2^{N-2}-(2^{N-8}). This is not a strict proof.

The strategy to solve this using a Greedy Algorithm is:
First we have to realize that with a six side dice, from index we can only reach from i + 1 to i + 6, so we are going to declare an array of size 7, where we are going to keep our results, the index is going to store our current result and the rest will store the values of our next move relative to index i.
It's worth noticing that, if we have only two elements in A, the solution it's the sum of this elements. Because 0 is the start and 1 it's the last square.

At first we initialize our result array with the first move starting at index 0.

The second thing we have to realize is that by calculating the result at the next square i + k, we are adding to our possible path the value at index i, but this may not be a good idea, because the value at i, could decrease our result. So we have to compare the path going through index to achieve i + k  with the one that jumps the index to achieve i + k. And the path that do not go through  is the one currently stored at k + 1. Why is that? You might ask. Well, k + 1  holds the result of the last move, which is (i - 1) + (k + 1) = i + k and this is exactly the index that we are analyzing.

So by doing this we are removing all values that could decrease our final result, meaning that from 0 we are only adding the ones that increase our result, giving us the maximal result that can be achieved. At the end of each nested loop, you can see that we add to the result the value at k + 6 without doing a max operation, this is because this is the first time that we reach this square so there's nothing to compare it with.

One last thing that may seem obvious but helps to understand why this algorithm works, is that just as from i we can reach a maximum of six squares or less, to get to there is only six possible squares or less too. And this squares that come before i were already analyzed, so we don't have to analyze all the possible combinations.

For the time complexity at the first loop where we initialize the result array we have a constant time complexity, because the loop doesn't depends on the size of the input, so O(1) until here. For the second loop we have a linear time complexity on N, even though we have a nested loop inside this one, the nested loop just like the first has a constant time complexity, resulting in a total of O(N)  for the second loop. So O(N) + O(1) gives us a total time complexity of O(N).
For the space complexity, we did O(1), even though we could use a O(N) complexity, The reason for the O(1) complexity is pretty simple, the size of the result array is constant regardless the size of our input.

Complete Solution:

Time Complexity O(N)
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/