CODEWITHSUNDEEP
javaalgorithm
Mike1st
Mike1st

Reputation: 9

What is wrong with my Havel-Hakimi Algorithm code?

I am trying to practice my coding skill and I found a coding practice on Dailyprogrammer Reddit that uses Havel-Hakimi Algorithm (https://www.reddit.com/r/dailyprogrammer/comments/bqy1cf/20190520_challenge_378_easy_the_havelhakimi/), but it keeps returning the wrong boolean.

I tried to check my process in every loop to make sure all the methods are doing the right jobs and the output is what I expected, yet it keeps returning the wrong boolean.

public static void main(String[] args) {
    int[] answer = {16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16};
    System.out.println(hh(answer));
    ArrayList<Integer> temp = new ArrayList<Integer>();
    System.out.println(temp.size());
}

//This is the actual Havel-Hakimi Algorithm Method
public static boolean hh(int[] answer) {
    ArrayList<Integer> temp = new ArrayList<Integer>();
    int n;
    for(int i = 0; i < answer.length; i++) {
        temp.add(answer[i]);
    }
    for(int j = 0; j < temp.size(); j++) {
        if(temp.get(j) == 0)
            temp.remove(j);
    }

    if(temp.size() == 0) {
        return true;
    }
    Collections.sort(temp);
    for(int t = 0; t < temp.size(); t++) {
    }
    n = temp.get(0);
    temp.remove(0);
    if(n > temp.size()) {
        return false;
    }
    for(int k = 0; k < n; k++) {
        temp.set(k, temp.get(k) - 1);
    }
    int[] newAnswer = new int[temp.size()];;
    for(int l = 0; l < temp.size(); l++) {
        newAnswer[l] = temp.get(l);
    }
    return hh(newAnswer);

}

Using the array provided in main method, "hh" method should return true but it returns false.

Upvotes: 0

Views: 172

Answers (1)

Ammar
Ammar

Reputation: 820

The problem is with Collections.sort(temp), it sorts the input collection in ascending order, while you want it to be sorted in descending order. You can use Collections.sort(temp, Collections.reverseOrder())

That was the logical problem in your code.

I should point out that some statements are unnecessary in your code (such as the for loop just after Collections.sort(temp), it does nothing), other statements can be enhanced (such as the first two for loops, instead of copying the whole array, then filter it, why not just copy the needed elements?), you can also avoid using recursion by using a while(true) loop.

Here's a code that will help you solve your problem:

public static void main(String[] args) {
    int[] answer = {16, 9, 9, 15, 9, 7, 9, 11, 17, 11, 4, 9, 12, 14, 14, 12, 17, 0, 3, 16};
    System.out.println(hh(answer));
}

//This is the actual Havel-Hakimi Algorithm Method
public static boolean hh(int[] answer) {
    while(true) {
        // Filter zero's from answer array 
        ArrayList<Integer> temp = new ArrayList(Arrays
                // get a Stream<Integer> from int[]
                .stream(answer)
                // filter zero's (this returns an IntStream)
                .filter(a -> a != 0)
                // reconvert it to Stream<Integer>
                .boxed()
                // Collect the stream as a List<Integer>
                .collect(Collectors.toList()));

        // Check the filtered array if it became empty after filtering
        if (temp.isEmpty()) {
            return true;
        }

        // Sort the filtered array in descending order
        Collections.sort(temp, Collections.reverseOrder());

        // Remove the first element (note that remove method returns the removed element)
        int n = temp.remove(0);

        // Check if the first removed element is larger than the new size of the array
        if (n > temp.size()) {
            return false;
        }

        // Reconstruct the input array for the next iteration
        answer = IntStream.range(0, temp.size())
                .map(i -> i < n ? temp.get(i) - 1 : temp.get(i))
                .toArray();
    }
}

If you're not familiar with Streams you can simply use for loops instead.

Upvotes: 2

Related Questions