# Codility ‘NumberSolitaire’ Solution

##### Short Problem Definition:

In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.

NumberSolitaire

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

Prototypical Dynamic Programming. Remember all sub-solutions and use them to compute the next step. I prefixed the array by 6 min_values to use the same computation for the whole algorithm (besides the first). Do not forget to set the minimal_value small enough to handle a purely negative input array.

##### Solution:
```NR_POSSIBLE_ROLLS = 6
MIN_VALUE = -10000000001

def solution(A):
sub_solutions = [MIN_VALUE] * (len(A)+NR_POSSIBLE_ROLLS)
sub_solutions[NR_POSSIBLE_ROLLS] = A[0]

# iterate over all steps
for idx in xrange(NR_POSSIBLE_ROLLS+1, len(A)+NR_POSSIBLE_ROLLS):
max_previous = MIN_VALUE
for previous_idx in xrange(NR_POSSIBLE_ROLLS):
max_previous = max(max_previous, sub_solutions[idx-previous_idx-1])
# the value for each iteration is the value at the A array plus the best value from which this index can be reached
sub_solutions[idx] = A[idx-NR_POSSIBLE_ROLLS] + max_previous

return sub_solutions[len(A)+NR_POSSIBLE_ROLLS-1]
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• Dusan Orlovic

Just to add my ruby 100% solution

def solution(a)
n = a.length – 1
state = [a.shift]
a.each_with_index do |e, i|
if i < 5
state << state[-(i+1)..-1].max + e
else
state << state[-6..-1].max + e
state.shift
end
end
state[-1]
end

• Jorge O

This one took me a while to wrap my head around but finally I came up with what I think is a pretty Python solution:

> def solution(A):
> N = len(A) # Original size of A

# Suffix small values after the array for convenience
A = A + [ -10001 ] * (6-1)

# print A

# Store best score per stage

S = [0] * (N+(6-1))

# Goal:

n = N-1 # position

# S[n] = 0 # cumulative score

# Last stage (only 1 path from here to goal: +1):

n = n-1

S[n] = A[n+1] # + S[n] which is 0

# ^ The goal’s value is always part of the score.

# Backwards memoized loop starting at previous stage (2nd to last)

for n in reversed(xrange(0, n)):

# print S

# print n, A[n+1]

# print [A[n+i]+S[n+i] for i in xrange(1,7)]

S[n] = max( [A[n+i]+S[n+i] for i in xrange(1,7)] )

# ending at first case, where n = 0

# Initial state:

s = A[0]+S[0]

return s
“`