10
\$\begingroup\$

I've never did a real Project Euler in my life, so I figured it was about to do one.

And what better Project Euler to start with than Problem 42?

Project description from Project Euler:

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt, a 16K text file containing nearly two-thousand common English words, how many are triangle words?

I realized quite quickly that to determine if a number is triangular, you can solve a quadratic equation.

The part that I'm the least proud of is how the words are read from the URL. Reading the whole line into memory (the whole text file is essentially one whole line) feels unnecessary, just to then split it into words, cut off the quotation marks, and read it.

Even though I could keep the quotation marks and add a filter in wordValue, it feels like it makes more sense to change the string before passing it there.

I considered using StreamTokenizer to read the words, but that class felt old and ugly and not Java 8-ish at all.

The project euler assignment only asks to print the count of triangular numbers, I figured that it doesn't hurt to also write them and their word values - this can be easily disabled by removing the .peek(System.out::println) lines.

public class ProjEuler42 {

    public static int wordValue(String str) {
        return str.toUpperCase().chars().map(ch -> ch - 'A' + 1).sum();
    }

    public static boolean isTriangular(int number) {
        // The Nth triangular number, T(n), is n*(n+1)/2,
        // by doing T(n) - number = 0 we get a quadratic equation.
        // If the solution to this equation is an integer, it is a triangular number
        double n = Math.round(-0.5 + Math.sqrt(0.25 + 2 * number));
        return 0.5 * n * (n + 1) == number;
    }

    public static void main(String[] args) throws IOException {
        URL url = new URL("https://projecteuler.net/project/resources/p042_words.txt");
        InputStream in = url.openStream();
        try (BufferedReader reader = new BufferedReader(
          new InputStreamReader(in, StandardCharsets.UTF_8))) {
            long count = reader.lines()
                    .flatMap(line -> Arrays.stream(line.split(",")))
                    .map(str -> str.substring(1, str.length() - 1))
                    .filter(str -> isTriangular(wordValue(str)))
                    .peek(System.out::println)
                    .mapToInt(ProjEuler42::wordValue)
                    .peek(System.out::println)
                    .count();
            System.out.println("There are a total of " + count + " triangular words");
        }
    }
}

From a Project Euler perspective, and from a Java 8 perspective, is there anything to improve?

\$\endgroup\$
  • 2
    \$\begingroup\$ I did not know Java code could be that pleasant to read, thanks for sharing! \$\endgroup\$ – Josay Mar 10 '15 at 14:33
  • 1
    \$\begingroup\$ @Josay Java 8 is awesome :) \$\endgroup\$ – Simon Forsberg Mar 10 '15 at 14:33
8
\$\begingroup\$

Processing chunk-by-chunk vs line-by-line

Obviously, if the input file was of 1TB size, containing a single line full of words, your computer probably wouldn't have enough memory to run this program. It could be rewritten to process the input chunk by chunk rather than line by line, and it will work with input of arbitrary size. It won't be nearly as pretty and definitely not a pleasant reading.

That being said...

  • The problem description clearly states the input is a 16K text file
  • If somebody asked you to process a 1TB file with a single line I think you could safely tell them to go to ... Tell them to change their specs.

So, I'd say don't sweat it. Using Java 8 streams for the effect of elegant code that even non-Java programmers find pleasant to read, at the expense of reading the entire line 16K into memory, is a good trade-off.

Another way to cut off the double quotes, without .substring

Instead of this:

.flatMap(line -> Arrays.stream(line.split(",")))
.map(str -> str.substring(1, str.length() - 1))

You could split on sequences of non-word characters, and skip the first value (an empty string):

.flatMap(line -> Arrays.stream(line.split("\\W+")))
.skip(1)

Slightly more natural arithmetic expression

In isTriangular, instead of multiplying by 0.5, I find dividing by 2 more natural. That way it also nicely corresponds to the formula you included there in the comment:

    return n * (n + 1) / 2 == number;

Going beyond the specs a bit

The wordValue method converts input to uppercase, but the referenced file already contains only uppercase words. So the step is unnecessary for Euler, but sure it's more generally useful this way (except for the hard-coded path to the input file).

Comment out bits not for review

For clarity for reviewers, I would comment out these lines, which are clearly meant for yourself only (and for playing around):

        .peek(System.out::println)
        .mapToInt(ProjEuler42::wordValue)
        .peek(System.out::println)
\$\endgroup\$
  • \$\begingroup\$ is a dash considered a non-word character for this application? probably way out in left field but I am curious how that plays out? \$\endgroup\$ – Malachi Mar 10 '15 at 16:37
  • 2
    \$\begingroup\$ You have a point, @Malachi, that should be a non-word. Luckily, there's no dash in the input, and the change I suggested produces the same output as the original. If there was dash in the input, the regex could be adjusted accordingly. \$\endgroup\$ – janos Mar 10 '15 at 16:51

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.