Dynamic Programming (Codility Q: NumberSolitaire)

Question

This is the question: codility.com/programmers/task/number_solitaire

and below link is my result (50% from Codility): https://codility.com/demo/results/training8AMJZH-RTA/

My code (at the first, I tried to solve this problem using Kadane's Algo):

class Solution {
    public int solution(int[] A) {
        int temp_max = Integer.MIN_VALUE;
        int max = 0;
        int k = 1;

        if(A.length == 2) return A[0] + A[A.length-1];

        for(int i = 1; i < A.length-1; i++) {
            if(temp_max < A[i]) temp_max = A[i];

            if(A[i] > 0) {
                max += A[i];
                temp_max = Integer.MIN_VALUE;
                k = 0;           

            } else if(k % 6 == 0) {
                max += temp_max;
                temp_max = Integer.MIN_VALUE;
                k = 0;
            }
            k++;
        }
        return A[0] + max + A[A.length-1];
    }

And below is the solution (100% from Codility result) that I found from web:

class Solution {
    public int solution(int[] A) {
        int[] store = new int[A.length];
        store[0] = A[0];
        for (int i = 1; i < A.length; i++) {
            store[i] = store[i-1];
            for (int minus = 2; minus <= 6; minus++) {
                if (i >= minus) {
                    store[i] = Math.max(store[i], store[i - minus]);
                } else {
                    break;
                }
            }
            store[i] += A[i];
        }
        return store[A.length - 1];
    }
}

I have no idea what is the problem with my code:(

I tried several test cases but, nothing different with the solution & my code

but, codility test result shows mine is not perfectly correct. (https://codility.com/demo/results/training8AMJZH-RTA/)

please anyone explain me the problem with my code~~

Armlet

Answer 1

Try this test case[-1, -2, -3, -4, -3, -8, -5, -2, -3, -4, -5, -6, -1]. you solution return -4 (A[0],A[1],A[length-1],Here is the mistake), but the correct answer is -6 (A[0],A[6],A[length-1]).

Here is a my solution,easy to understand:

public int solution(int[] A) {
    int lens = A.length;
    int dp[] = new int[6];
    for (int i = 0; i < 6; i++) {
        dp[i] = A[0];
    }
    for (int i = 1; i < lens; i++) {
        dp[i%6] = getMax6(dp) + A[i];
    }
    return dp[(lens-1)%6];
}

private int getMax6(int dp[]){
    int max = dp[0];
    for (int i = 1; i < dp.length; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}

Poulenc

not that easy to understand at the beginning, but really good solution. – Coterie

@Coterie (or OP) Could you explain why you add A[i] in this line: dp[i%6] = getMax6(dp) + A[i]; and also your return statement for the solution method – Wilber

@Wilber in this line dp[i%6] = getMax6(dp) + A[i]; you compute the maximum score you can get jumping to the current field(A[i]) from last 6 fields. Not sure what do you mean with return statement, could you reforge the question? – Coterie

(A[0],A[6],A[length-1]) is (-1 -5 -1) which should be -7 not 6. – Toler

Answer 2

Here is a solution similar to @0xAliHn but using less memory. You only need to remember the last 6 moves.

def NumberSolitaire(A):
    dp = [0] * 6
    dp[-1] = A[0]

    for i in range(1, len(A)):
        maxVal = -100001

        for k in range(1, 7):
            if i-k >= 0:
                maxVal = max(maxVal, dp[-k] + A[i])

        dp.append(maxVal)
        dp.pop(0)
    return dp[-1]

Rumormonger

I think this is the most time efficient and space efficient solution. Good job! – Chesnut

Awesome solution. However, Codility is giving to it 75%. I checked and for some reason they said that the minimum limit is -10000 but try to run it with -166680000... I changed limit to -166680001 and it scored 100%... thx! – Tact

As of end of 2023, this line in their guidance is indeed wrong "each element of array A is an integer within the range [−10,000..10,000]." - as @Tact says, changing the limit to their extreme_answers test case gets it to 100% – Risinger

Answer 3

Readable solution from Java:

public class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{1, -2, 0, 9, -1, -2}));
    }

    private int solution(int[] A) {
        int N = A.length;
        int[] dp = new int[N];
        dp[0] = A[0];

        for (int i = 1; i < N; i++) {
            double sm = Double.NEGATIVE_INFINITY;
            for (int j = 1; j <= 6; j++) {
                if (i - j < 0) {
                    break;
                }
                double s1 = dp[i - j] + A[i];
                sm = Double.max(s1, sm);
            }
            dp[i] = (int) sm;
        }

        return dp[N-1];
    }
}

Woodard

Answer 4

Here is the simple Python 3 solution:

import sys

def solution(A):        
    dp = [0] * len(A)
    dp[0] = A[0]

    for i in range(1, len(A)):
        maxVal = -sys.maxsize - 1

        for k in range(1, 7):
            if i-k >= 0:
                maxVal = max(maxVal, dp[i-k] + A[i])

        dp[i] = maxVal
    return dp[len(A)-1]

Esposito

I added a my Python solution too, which I think is slightly more Pythonic than yours. :) – Aube

Answer 5

Because you are not using dynamic programming, you are using greedy algorithm. Your code will fail when the max number in a range will not be the right choice.

function solution(A) {
  // This array contains a maximal value at any index.
  const maxTill = [A[0]];

  // It's a dynamic programming so we will choose maximal value at each
  // Index untill we reach last index (goal)
  for (let i = 1; i < A.length; i++) {
    // Step 1 . max value of each index will be atleast equal to or greater than
    // max value of last index.
    maxTill[i] = maxTill[i - 1];
    // For each index we are finding the max of last 6 array value
    // And storing it into Max value.
    for (let dice = 1; dice <= 6; dice++) {
      // If array index is itself less than backtrack index
      // break as you dont have 6 boxes in your left
      if (dice > i) {
        break;
      } else {
        // The most important line .
        // Basically checking the max of last 6 boxes using a loop.
        maxTill[i] = Math.max(
          maxTill[i - dice],
          maxTill[i]
        );
      }
    }
    // Until this point maxStill contains the maximal value
    // to reach to that index.
    // To end the game we need to touch that index as well, so
    // add the value of the index as well.
    maxTill[i] += A[i];
  }
  return maxTill[A.length - 1];
}

console.log(solution([-1, -2, -3, -4, -3, -8, -5, -2, -3, -4, -5, -6, -1]));

Hagiocracy

Answer 6

Based on the solutions posted, I made nice readable code. Not best performance.

int[] mark = new int[A.length];
    mark[0] = A[0];
    IntStream.range(1, A.length)
            .forEach(i -> {
                int max = Integer.MIN_VALUE;
                mark[i] = IntStream.rangeClosed(1, 6)
                        .filter(die -> i - die >= 0)
                        .map(r -> Math.max(mark[i - r] + A[i], max))
                        .max().orElse(max);
            });

    return mark[A.length - 1];

Thayne

Answer 7

This is my solution. I try to make the code easy to apprehend. It might not save space as much as it can.

    private static int solution(int A[])
{   
    // N //  N is an integer within the range [2..100,000];
    // A[] // each element of array A is an integer within the range [−10,000..10,000].
    int N = A.length;
    int[] bestResult = new int[N]; // record the current bestResult
    Arrays.fill(bestResult, Integer.MIN_VALUE); // fill in with the smallest integer value

    // initialize
    bestResult[0] = A[0];
    for (int i = 0;i < A.length;i++) {
        // calculate six possible results every round
        for (int j = i + 1; (j < A.length) && (i < A.length) && j < (i + 1) + 6; j++) {
            // compare
            int preMaxResult = bestResult[j]; // the max number so far
            int nowMaxResult = bestResult[i] + A[j]; // the max number at bestResult[i] + A[j]
            bestResult[j] = Math.max(preMaxResult, nowMaxResult);
        }
    }        
    return bestResult[bestResult.length-1];
}

Elinorelinore

Answer 8

100% c++ solution( results)

#include <climits>

int solution(vector<int>& A) {
    const int N = A.size();
    if (N == 2)
        return A[0] + A[1];

    vector<int> MaxSum(N, INT_MIN);
    MaxSum[0] = A[0];
    for (int i = 1; i < N; i++) {
        for (int dice = 1; dice <= 6; dice++) {
            if (dice > i)
                break;
            MaxSum[i] = max(MaxSum[i], A[i] + MaxSum[i - dice]);
        }
    }
    return MaxSum[N-1];
}

Lynnette

Very clean, I would optimize memory by keeping only the last 6 backward values! – Chesnut

Answer 9

100% python solution with the help of the answers above and https://sapy.medium.com/cracking-the-coding-interview-30eb419c4c57

def solution(A):
    # write your code in Python 3.6
    # initialize maxUntil [0]*n
    n = len(A)
    maxUntil = [0 for i in range(n)]
    maxUntil[0]=A[0]
    # fill in maxUntil, remember to chack limits
    for i in range(1, n): # for each 
        maxUntil[i] = maxUntil [i-1]
        # check the max 6 to the left:
        # for 1,..,6:
        for dice in range(1,7):
            if dice > i: # if dice bigger than loc - we are out of range
                break
            #else: check if bigger than cur elem, if so - update elem
            maxUntil[i] = max(maxUntil[i],maxUntil[i-dice])
        # add the current jump:
        maxUntil[i] +=A[i]
    # must reach the last sq:
    return maxUntil[n-1]
    

Thitherto

Answer 10

I would like to explain the algorithm I have come up with and then show you the implementation in C++.

1. Create a hash for the max sums. We only need to store the elements within reach, so the last 6 elements. This is because the dice can only go back so much.
2. Initialise the hash with the first element in the array for simplicity since the first element in this hash equals to the first element of the inputs.
3. Then go through the input elements from the second element.
4. For each iteration, find the maximum values from the last 6 indices. Add the current value to that to get the current max sum.
5. When we reach the end of the inputs, exit the loop.
6. Return the max sum of the last element calculated. For this, we need clipping with module due to the space optimisation

The runtime complexity of this dynamic programming solution is O(N) since we go through element in the inputs. If we consider the dice range K, then this would be O(N * K).

The space complexity is O(1) because we have a hash for the last six elements. It is O(K) if we does not consider the number of dice faces constant, but K.

int solution(vector<int> &A)                                                    
{                                                                               
  vector<int> max_sums(6, A[0]);                                                
  for (size_t i = 1; i < A.size(); ++i) max_sums[i % max_sums.size()] = *max_element(max_sums.cbegin(), max_sums.cend()) + A[i];
  return max_sums[(A.size() - 1) % max_sums.size()];                            
}

Perdition

Answer 11

Here's my answer which gives 100% for Kotlin

val pr = IntArray(A.size) { Int.MIN_VALUE }
pr[0] = A.first()
for ((index, value) in pr.withIndex()) {
  for (i in index + 1..min(index + 6, A.lastIndex)) {
      pr[i] = max(value + A[i], pr[i])
  }
}
return pr.last()

I used forwarded prediction, where I fill the next 6 items of the max value the current index can give.

Runofthemill

Answer 12

Here is my Python version of an answer that scored 100%:

from collections import deque

def solution(A):
    # Moving window of previous 6 squares from which you can come from.
    # Using a deck is efficient, and it provides the automatic popping when adding stuff.
    # We have to start on the first square as per the rules.
    moving_window = deque([A[0]], maxlen=6)

    # Compute the max score possible to reach each square based on the previous scores.
    # We move to a square and find the highest score in the reachable previous squares.
    for number in A[1:]:
        moving_window.append(number + max(moving_window))
    
    # Return the last score registered (at the last square, which marks the end of the game):
    return moving_window[-1]

I think the key is to understand the moving window principle used here. Coming from outside CS originally, dynamic programming doesn't mean much to me. I just see it as doing small steps. In this case, for each square, you try to see which is the previous square with the best score that you can come from.

Aube