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.

Link

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.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • 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
    “`