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

Assume that:

**Definitions:**

** Problem:**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

*k*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.**** **

### Analysis:

The number of possible combinations is,

If you are interested only on the code you can skip this part.

Demonstration:First let's consider this, in a arrayAwith sizeN, indexiandk being the dice result, we have a tree of possibilities that could be described as follows. Starting from0we could go to indexes1, 2, 3, 4, 5, 6,and them from1, we could go to2, 3, 4, 5, 6, 7, so basically from indexi, we can go fromi + 1, toi + 6, as long asi + 6 < N.So to calculate the total of possible combinations let's traverse the array fromN - 1, to 0. Starting at N - 1, we have no possible combination, at N - 2,we have1combination withk = 1, from N - 3,we can get toN - 2,withk = 1,andN - 1withk = 2,which gives1combination when we reachN - 1,and fromN - 2we know that we cant get only one combination, so this gives us2 possibilities. The pattern follows on the table below.We can see that there is a pattern here, for an array of size N the total of combinations is

, but this pattern doesn't continue for too long, because we have a die with six sides when

N >= 8we start to lose some combinations, for example, whenN = 8,N - 1 = 7, and we can't get from0 to 7with the values that can be assumed byk,so the total combinations forN = 8 would beFor.

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. Forwe have to a total combinations of

.

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 *i *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 *0 *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.

8 9 10 |
# If we have only two elements the result should be the sum of this elements if N < 2: |

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

12 13 14 15 16 17 18 19 |
result = [0] * 7 result[0] = A[0] # First iteration, sets the first values for the result array for dice in xrange(7): # The first movement so A[0] plus the next house ranging from 1 to 6, # notice that, if we have less than 6 houses on our board we have to ignore the results if dice < N: |

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 *i *to achieve *i + k * with the one that jumps the index *i * to achieve *i + k.* And the path that do not go through *i * 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.

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# Greedy loop for k in xrange(1, N): # First set the maximum result that got us at index k result[0] = result[1] # Calcs the next five (from 1 to 5) possible results departing from index k for dice in xrange(1, 6): if k + dice < N: # Keeps the greater result, to reach the house k + dice, # going trough house k may decrease the result, so we ignore it if that's it the case result[dice] = max(result[dice + 1], result[0] + A[k + dice]) else: # We've made all the possible calculations break # It's the first time we reached this house, so no need to do max() here if k + 6 < N: |

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.

35 36 37 |
# It's the first time we reached this house, so no need to do max() here if k + 6 < N: |

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 *i *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:**

1234567891011121314151617181920212223242526272829303132333435363738394041
# Name: NumbertSolitaire# Link: https://codility.com/demo/take-sample-test/number_solitaire/ def solution(A): N = len(A) # If we have only two elements the result should be the sum of this elements if N < 2: return A[0] + A[1] result = [0] * 7 result[0] = A[0] # First iteration, sets the first values for the result array for dice in xrange(7): # The first movement so A[0] plus the next house ranging from 1 to 6, # notice that, if we have less than 6 houses on our board we have to ignore the results if dice < N: result[dice] = A[0] + A[dice] # Greedy loop for k in xrange(1, N): # First set the maximum result that got us at index k result[0] = result[1] # Calcs the next five (from 1 to 5) possible results departing from index k for dice in xrange(1, 6): if k + dice < N: # Keeps the greater result, to reach the house k + dice, # going trough house k may decrease the result, so we ignore it if that's it the case result[dice] = max(result[dice + 1], result[0] + A[k + dice]) else: # We've made all the possible calculations break # It's the first time we reached this house, so no need to do max() here if k + 6 < N: result[6] = result[0] + A[k + 6] return result[0]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
# Name: NumbertSolitaire # Link: https://codility.com/demo/take-sample-test/number_solitaire/ def solution(A): N = len(A) # If we have only two elements the result should be the sum of this elements if N < 2: return A[0] + A[1] result = [0] * 7 result[0] = A[0] # First iteration, sets the first values for the result array for dice in xrange(7): # The first movement so A[0] plus the next house ranging from 1 to 6, # notice that, if we have less than 6 houses on our board we have to ignore the results if dice < N: result[dice] = A[0] + A[dice] # Greedy loop for k in xrange(1, N): # First set the maximum result that got us at index k result[0] = result[1] # Calcs the next five (from 1 to 5) possible results departing from index k for dice in xrange(1, 6): if k + dice < N: # Keeps the greater result, to reach the house k + dice, # going trough house k may decrease the result, so we ignore it if that's it the case result[dice] = max(result[dice + 1], result[0] + A[k + dice]) else: # We've made all the possible calculations break # It's the first time we reached this house, so no need to do max() here if k + 6 < N: result[6] = result[0] + A[k + 6] return result[0] |

*Time Complexity O(N)*

*Space Complexity O(1)*