NumberSolitaire

This page discusses different solutions to the problem NumberSolitaire presented by Codility in the lesson 17 “ Dynamic Programming”.

One simple solution is to distinguish between the length of A being less or more than 6.

def solution(A):
    N = len(A)
    dp = [A[0]] + [0]*(N-1)
    for i in xrange(1,min(N,6)):
        dp[i] = max(dp[:i]) +A[i]
    for j in xrange(6,N):
        dp[j] = max(dp[j-6:j]) +A[j]
    return dp[-1]

The solution above might have the best performance for large inputs of the three solutions on this page. However, the two for-loops could be joined together into one making the solution look neater:

def solution(A):
    N = len(A)
    dp = [A[0]] + [0]*(N-1)
    for j in xrange(1,N):
        dp[j] = max(dp[max(0,j-6):j]) +A[j]
    return dp[-1]

Moreover, if we assume that the input array can be modified, then there is no need to create a new list:

def solution(A):
    for j in xrange(1,len(A)):
        A[j] += max(A[max(0,j-6):j])
    return A[-1]

In any case, all three solutions on this page have the same worst-case time complexity of O(N) and score 100% under Codility’s test.

Leave a Reply

Your email address will not be published.