8
\$\begingroup\$

Follow up to Duplicate like a weapon, arrays like heaven.

@rolfl suggested in chat that I try to complete this challenge again in a Java 8 friendly way. I took the opportunity to also employ the algorithm suggested in this brilliant answer.

I'm not familiar with Java 8 features, but am definitely interested in using it more and finding the best ways to implement it.

import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.util.Arrays;

public class ArrayAbsurdityJava8 {
    public static void main(String[] args) throws IOException {
        Files.lines(new File(args[0]).toPath())
                .filter(s -> !s.isEmpty())
                .forEach(ArrayAbsurdityJava8::printDuplicate);
    }

    private static void printDuplicate(String line) {
        int length = Integer.parseInt(line.split(";")[0]);
        int total = Arrays.stream(line.split(";")[1].split(","))
                .mapToInt(Integer::parseInt)
                .sum();

        System.out.println(total - (length - 1) * (length - 2) / 2);
    }
}

This ended up shorter than I expected. Is this best? I was thinking of doing it my way as well, but the boolean comparison requires a for loop (am I wrong?).

\$\endgroup\$
6
\$\begingroup\$

I like the way you have solved this, and cannot think of any serious criticisms. The most significant thing I can think of is the double-duty method printDuplicate. I would prefer that method to be just findDuplicate and then print the value outside the function. That makes the function more reusable.

Other trivials are:

new File(args[0]).toPath()

should be:

Paths.get(args[0])

Finally, I would expect the 'expected' value to be a simpler algorithm. The code:

(length - 1) * (length - 2) / 2

is just messy, and hard to understand.

The reasons it is like that are because of two factors:

  1. You expect the sum to be based on the number of values less 1 for the duplicate.
  2. the forumla is designed for a 1-based start point, not a 0-based one.

As a result, the input value: 5;3,2,1,0,1 should have the expected-value calculated from 4 values, not 5, and indexed from 0, not 1. I would recode the formula to be:

(values - 1) * (values) / 2

where values is:

Integer.parseInt(....) - 1;

Incorporating @mjolka's good suggestions and simplifying the functions, you can end up with improved code:

public static void main(String[] args) throws IOException {
    Files.lines(Paths.get(args[0]))
            .filter(s -> !s.isEmpty())
            .mapToInt(s -> findDuplicate(s))
            .forEach(System.out::println);
}

private static int findDuplicate(String line) {
    String[] parts = line.split(";");

    // expect is based on 1-fewer values than are supplied (no duplicate)
    int expect = Integer.parseInt(parts[0]) - 1;

    int total = Arrays.stream(parts[1].split(","))
            .mapToInt(Integer::parseInt)
            .sum();

    return total - ((expect - 1) * (expect)) / 2;
}

As a side note, the total can be computed easily in a parallel stream, instead of a stream. This would, in theory, improve performance for large arrays of data in systems with multiple cores:

    int total = Arrays.parallelStream(parts[1].split(","))
            .mapToInt(Integer::parseInt)
            .sum();
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

line.split(";") is being called twice, so you can assign it to a variable to remove one of the calls.

Since we know there's only one ; per line, we can use indexOf to find it, and substring to extract the relevant parts of the string. This may be a little bit faster than calling split(";").

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

With Java 8 Streams you can also using arrays or collections to get an algorithm that runs with constant memory, no matter how long your lines are. The complexity would be O(1) memory and O(n) time, where n is the line length - if you have m lines, you'll have O(n*m). The time complexity if your algorithm is the same, but it reads the full line into memory, so takes O(n) memory.

public class FindDuplicates8 {
    public static void main(String[] args) throws Exception {
        Scanner input = new Scanner(new File(args[0]));
        input.useDelimiter("[;,]|\r?\n");
        while (input.hasNext()) {
            int n = input.nextInt();
            long sum = Stream.generate(() -> input.nextInt())
                    .limit(n)
                    .mapToLong(x -> x.longValue())
                    .sum();
            System.out.println(sum - (n - 2) * (n - 1) / 2);
        }
    }
}

Please note that I'm heavily relying on the format of the input being correct - I don't distinguish between ';' and ',' and ignore line breaks. That's probably not be what you want in a real program - I just want to demonstrate the algorithmic possibilities.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.