Candie distribution algorithm

Question

I am studying algorithms and I solved this problem under Dynamic Programming section:

Alice is a kindergarten teacher. She wants to give some candies to the children in her class. All the children sit in a line ( their positions are fixed), and each of them has a rating score according to his or her performance in the class. Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to save money, so she needs to minimize the total number of candies given to the children.

Input Format

The first line of the input is an integer N, the number of children in Alice's class. Each of the following N lines contains an integer that indicates the rating of each child.

Code:

import java.io.*;
import java.util.*;

public class Candie{

 static int candieCalculator(int[] numbers) {
    int len = numbers.length;
    int result=0;

    if (len==1) {
        return 1;
    }

    for (int i=0; i<len; i++) {
        result++;
        if (i==0) {
            if (numbers[i] > numbers[i+1]) {
                result++;
            }
        }
        else if (i==len-1) {
            if (numbers[i] > numbers[i-1]) {
                result++;
            }
        }
        else {

            if (numbers[i] > numbers[i+1]) {
                result++;
            }

            if (numbers[i] > numbers[i-1]) {
                result++;
            }
        }
    }

    return result;
 }

 public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] numbers = new int[n];

    for(int i=0; i < n; i++) {
        numbers[i] = in.nextInt();
    }
    System.out.println(candieCalculator(numbers));

 }
}

Sample input:

3 1 2 2

Sample output:

4

What do you think? Also this solution is considered as DP? It doesn't look DP to me.

Answer 1

Imports

import java.io.*;
import java.util.*;

It's more common to import just what you need. E.g.

import java.io.Scanner;

Then a reader can easily see what your dependencies are. Many IDEs will manage dependencies for you.

Naming

public class Candie{

The more common spelling is

public class Candy {

When I first read this problem I was wondering why the children needed candles.

The space between Candy { won't matter to the compiler but makes it easier for humans to read.

 static int candieCalculator(int[] numbers) {

As a general rule, objects and classes get noun names (e.g. Candy) while methods get verb names. Consider

 static int calculate(int[] ratings) {

We already knew that this involved Candy, so we don't have to say that again in the method name (although you could). An even better name in this case might be apportion, as that better reflects what we are doing with the candy. We are apportioning them between students. We do have to calculate that apportionment, but apportion seems a more specific (less generic) name. And if we name it apportion, we can still name another method calculate.

Similarly, numbers is a pretty generic name. In this case, we know that the numbers represent a "rating score" for each student, so let's base the name on that. E.g. ratings, scores, or ratingScores.

Don't Repeat Yourself

        if (i==0) {
            if (numbers[i] > numbers[i+1]) {
                result++;
            }
        }
        else if (i==len-1) {
            if (numbers[i] > numbers[i-1]) {
                result++;
            }
        }
        else {

            if (numbers[i] > numbers[i+1]) {
                result++;
            }

            if (numbers[i] > numbers[i-1]) {
                result++;
            }
        }

This is longer than it needs to be. You currently check for each edge condition and then apply a general condition if they aren't true. Instead, consider the real problem: if i == 0, you don't want to subtract from it as the index would be out of bounds. So you can just say

        if (i + 1 < ratings.length) {
            if (ratings[i] > ratings[i+1]) {
                result++;
            }
        }

        if (i > 0) {
            if (ratings[i] > ratings[i-1]) {
                result++;
            }
        }

In the typical case, you'll do the same number of comparisons as previously. The only time you do more is if i is equal to 0. But you can make that back by getting rid of

    if (len==1) {
        return 1;
    }

As the new code will handle that case. This will do two extra comparisons in that case, but that shouldn't matter as that case is pretty fast regardless.

Correctness

I don't believe that this returns the desired result for all inputs. Consider

7 1 2 3 4 5 6 7

This has an easy solution of \$1+2+3+4+5+6+7 = 28\$ but your code will instead return 13. But that's not enough candy! We can easily see that the first child must have a piece. So the higher rated second child needs two pieces, etc.

Dynamic Programming

I would agree that this is not dynamic programming. As a general rule, dynamic programming is a system to reduce recursive calculations. This doesn't recurse at all.

You should think about how to express the problem in terms of subsets of the problem. For example, if you know the apportionments for all the children less than i and greater than i, then what is the apportionment for i?

If you figure that out, you will have fixed the bug.

Hint: what do you do if the apportionment for i is 0? Obviously that's an incorrect answer to the problem. So what should you do in that case?

Answer 2

Correctness

Unfortunately your algorithm fails for as simple inputs as [1, 2, 3] and [1, 3, 2].

Consider this alternative algorithm:

1. Create an auxiliary array for counting the candies, same size as the input array. Let's call this array candies.

2. Set candies[0] = 1

3. Going from index 1 to the end of the input array, if ratings[i] > ratings[i - 1], then set candies[i] = candies[i - 1] + 1, otherwise to 1.

4. Going from index candies.length - 2, if ratings[i] > ratings[i + 1], then set candies[i] to candies[i + 1] + 1 if that's bigger than candies[i] as was already set in the pass from left to right.

Here's an online judge where you can verify the correctness of your implementation: https://leetcode.com/problems/candy/

Method decomposition

It's good to decompose the implementation to multiple smaller methods, to stand for each logical step. It leads to modular design that's more reusable and easier to test.

Dynamic programming

Dynamic programming is about breaking down a complex problem to simpler subproblems, and avoid solving the same subproblem repeatedly. The algorithm I outlined above uses dynamic programming in various ways:

• When going from left to right, we answer the question: what is the minimum number of candies I must give to the i-th child, considering the ratings of this child and the previous. If we had to answer this question for a random i in the middle, we would have to calculate the candies for i-1. Then in turn, to know the candies for i-1, we would have to calculate for i-2, and so on, all the way until the start. But we don't have to calculate the values randomly. We arranged the calculation in a certain way to avoid repeated calculations, by going consistently from left to right, so that at each step we can benefit from the value calculated at the previous step.

• Then when going from right to left, we use the same logic, and more, we also use the calculation results of going from left to right. If we had not already built an array with those values, we would have to recalculate at each step.

Not using dynamic programming would be extremely poor performance. I invite you to read more about dynamic programming on Wikipedia.

Suggested implementation

Putting the above suggestions together:

public int calculateCandies(int[] ratings) {
    if (ratings.length < 1) {
        return 0;
    }
    if (ratings.length == 1) {
        return 1;
    }

    int[] candies = calculateCandiesFromLeft(ratings);
    calculateCandiesFromRight(ratings, candies);
    return IntStream.of(candies).sum();
}

private static int[] calculateCandiesFromLeft(int[] ratings) {
    int[] candies = new int[ratings.length];
    candies[0] = 1;

    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        } else {
            candies[i] = 1;
        }
    }
    return candies;
}

private static void calculateCandiesFromRight(int[] ratings, int[] candies) {
    for (int i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }
}