Euler - Largest Palindrome Product in Java

Question

Having been going over the documentation, learning more of the subtleties of Java. I am now going over some basic Project-Euler solution code I wrote a little while back. Hoping I can pick up some improvements that show more idiomatic functioning of the language.

Problem-4:

Find the largest palindromic number of the product of two 3-digit numbers.

Solution:

public class Euler_4
{
    static int largestPalindrome = 0;

    public static void findLargestPalindrome(int m1, int m2)
    {
        Integer threeDigitProduct = m1 * m2;
        if (threeDigitProduct < largestPalindrome) return;

        String productStr = threeDigitProduct.toString();

        int productStrLen = productStr.length();
        int j = productStrLen - 1;

        for (int i = 0; i < productStrLen; i++) {
            if (productStr.charAt(i) != productStr.charAt(j)) 
                return;
            j--;
        }

        largestPalindrome = threeDigitProduct;
    }

    public static void main(String[] args)
    {
        Integer threeDigitProduct;
        String productStr;

        for (int i = 100; i < 1000; i++) 
            for (int j = 100; j < 1000; j++) 
                findLargestPalindrome(i, j);

        System.out.println("Answer: " + largestPalindrome);
    }
}

Answer 1

Avoid keeping State in a static variable / Minimize the scope of variable

The advantage of not doing so might not be immediately obvious in this case because it's a sort of one-shot code (in a sense the problem is extremely narrow, there's only one largest palindromic product of tree digit numbers).

But if you'll try to extend making it into something reusable, it'll naturally become apparent that mutable state should not reside in a static field.

Instead, int largestPalindrome should be a local variable. Strive for minimizing the scope of variables.

Avoid side effects

Don't use side effects, when it's not necessary (in your implementation method findLargestPalindrome() operates through side effects).

Instead, prefer pure functions. Mathematical problems are well suited for being implemented as pure functions.

I.e. you can implement the problem of finding the largest palindromic product of 3-digit numbers as a method that returns an int (not void). That would already a step towards a better design, since it make the code easier to test (I'm talking about automated testing).

Single Responsibility Principle

Identification of responsibilities and their proper delineation makes code elements more readable and testable.

Take a look findLargestPalindrome() method, what it's responsible for?

• It computes a product of m1 and m2, then discard the new product if it is smaller than the current max palindromic product.
• Then it checks if the new product is a palindrome.

These actions look even more intertwined in the code because of the hack with the static variable. The second bullet point definitely warrants its own method.

Also, when method's responsibility is not clearly defined, it's difficult to come up with a proper name for it. Isn't the name findLargestPalindrome misleading?

{ } - Follow the Code convention

According to the Code conventions for Java language an opening curly brace should be placed on the same line with the declaration of class, interface, or method.

Open brace "{" appears at the end of the same line as the declaration statement

Also, it's not a good practice to omit curly braces around the body of loops and conditional statements. It might lead to nasty bugs when someone adds one more line of code in such places.

for (int i = 100; i < 1000; i++)
    for (int j = 100; j < 1000; j++)
        findLargestPalindrome(i, j);

Placing curly braces doesn't add much cognitive load, but makes the code less error-prone.

for (int i = 100; i < 1000; i++) {
    for (int j = 100; j < 1000; j++) {
        findLargestPalindrome(i, j);
    }
}

^{The only exception might be an if followed by an immediate throw, return, break, continue (this caveat is slightly opinionated, hence always when you're not sure about something that pertains to code style, ask your teammates / people you're collaborating with)}

Refactored version

The following design enables making changes (i.e. it would be easier to evolve the code if needed) and reuse logic.

public static int max3DigitPalindromicProduct() {
    int max = 0;
    
    for (int i = 101; i < 1000; i++) {
        for (int j = 101; j < 1000; j++) {
            int candidate = i * j;
            if (candidate > max && isPalindrome(candidate)) {
                max = candidate;
            }
        }
    }
    return max;
}

public static boolean isPalindrome(int candidate) {
    return isPalindrome(String.valueOf(candidate));
}

public static boolean isPalindrome(String candidate) {
    return new StringBuilder(candidate).reverse()
        .toString()
        .equals(candidate);
}

And here's an example of how this code can evolve to be a bit more versatile and expect a digit count (the number of digits in each factor) as a parameter:

^{Note that such change would not be feasible if we continue to keep state in a static variable, otherwise maxPalindromicProduct() might yield the result of previous call}

public static int maxPalindromicProduct(int digitNumber) {
    return switch (digitNumber) {
        case 1  -> maxPalindromicProductInRange(1, 10);
        case 2  -> maxPalindromicProductInRange(11, 100);
        case 3  -> maxPalindromicProductInRange(101, 1000);
        case 4  -> maxPalindromicProductInRange(1001, 10000);
        default -> throw new IllegalArgumentException();
    };
}

public static int maxPalindromicProductInRange(int from, int to) {
    int max = 0;
    
    for (int i = from; i < to; i++) {
        for (int j = from; j < to; j++) {
            int candidate = i * j;
            if (candidate > max && isPalindrome(candidate)) {
                max = candidate;
            }
        }
    }
    return max;
}

What about Performance?

^{inspired by comments}

One might be frowning upon the code demonstrated above, saying "it'll not perform well enough". If that's the case, then, dear reader, please pause for a moment and bear with me, because you completely missed the point of the answer.

The goal of these changes is to improve the design to enable further changes.

The father of TDD and Extreme programming Kent Beck in his book "Tidy first" expressed this idea in the following way:

Make the change easy, then make the easy change

Introducing changes into a code that is far from being clean is costly. Is some cases, it makes sense to improve the design, and then make an "easy change".

Design should evolve in small incremental steps. Here's the proper (least painful / time-consuming) sequence of actions leading to performant code:

• make it work, i.e. the code should pass all tests (no more no less), without spreading your focus on anything else;
• make it clean;
• optimize the performance.

It's akin to the metaphor of hats in TDD (you can wear only one hat at a time). We need to focus on achieving only one goal at a time, evolving the code in small incrementally.

The same holds true, when it comes to refactoring existing code the same principle applies as well. Tiding the code should happen separately from making performance optimizations. It's called a preparatory refactoring. Otherwise, an attempt to optimize a ball of mud is likely to produce a code which is still a mess and has a suboptimal performance (in the worst case you end up with the broken code and rolling back the changes losing time for no avail).

So, what performance tweaks we can introduce with the current design changes?

Eliminating the hack with the static variable and making the method for finding palindromic product a pure function by itself already gives a room for leveraging referential transparency. Since the result of its execution doesn't change, hence it can be computed only once and cached, reducing time complexity to constant. Functional languages like Haskell are leveraging this quite a bit (I'm leaving the research on how to achieve it in Java as homework).

Another performance improvement we can make is to quit employing strings while checking if a number is palindrome.

But first we need tests.

^{Note, that ideally tests should already be in place during the first phase of writing a solution that "simply works" and neither clean, no performant}

@ParameterizedTest
@ValueSource(ints = {-1, 0, 5})
@DisplayName("Should throw when the given number of factor digits is invalid")
void maxPalindromicProduct_ShouldThrow_WhenDigitNumberIsNotValid(
    int digitNumber) {
    
    assertThatIllegalArgumentException()
        .isThrownBy(
            () -> maxPalindromicProduct(digitNumber)
        );
}

@ParameterizedTest
@CsvSource({"1, 9", "2, 9009", "3, 906609", "4, 99000099"})
@DisplayName("""
        Should return a palindromic product
         corresponding to the given number
         of factor digit, when digit number
         is valid""")
void maxPalindromicProduct_ShouldReturnProduct_WhenDigitNumberIsValid(
    int digitNumber, int expectedProduct) {
    
    assertThat(
        maxPalindromicProduct(digitNumber)
    )
        .isEqualTo(expectedProduct);
}

^{Required test dependencies: JUnit, AssertJ}

Now we can reimplement isPalindrom(int) using modular arithmetic instead of messing with strings:

public static boolean isPalindrome(int candidate) {
    return candidate == reverse(candidate);
}

public static int reverse(int initial) {
    int reversed  = 0;
    int remainder = initial;
    while (remainder != 0) {
        reversed   = reversed * 10 + remainder % 10;
        remainder /= 10;
    }
    return reversed;
}

Method isPalindrome(String) becomes a dead code and goes away, we don't need it anymore.

The algorithm of going through combinations can be improved as well, but I'm not going to poke into this topic, there are already too many things to unpack here.

Answer 2

Unnecessary Boxing

Integer is a heavy weight Object in Java, with exactly the same range as the lightweight int. There is no need "box" the efficient int product of m1 * m2 in as an Object in Integer threeDigitProduct. Just use:

        int threeDigitProduct = m1 * m2;

Since using "boxed" values is generally slower than the primitives, removing the boxing should result in a slight speed improvement.

Unused variable

Integer threeDigitProduct; in main is unused and should be deleted.

Halving you Work

In your multiplication table ...

  X |   100    101    102    103 ...
----+-------------------------------
100 | 10000  10100  10200  10300 ...
101 | 10100  10201  10302  10403 ...
102 | 10200  10302  10404  10506 ...
103 | 10300  10403  10506  10609 ...
 :  |   :      :      :      :

... it should be obvious that your table is symmetric about the diagonal, because of the commutative property of multiplication (\$a * b = b * a\$). You don't need to check for products of \$a * b\$ when \$a \gt b\$, if you've already examined the products for \$a \le b\$.

  X |   100    101    102    103 ...
----+-------------------------------
100 | 10000
101 | 10100  10201
102 | 10200  10302  10404
103 | 10300  10403  10506  10609
 :  |   :      :      :      :   ...

That removes about half of the values you need to do, cutting the runtime in about half!

The code:

        for (int i = 100; i < 1000; i++) 
            for (int j = 100; j < 1000; j++) 

could become

        for (int i = 100; i < 1000; i++) 
            for (int j = 100; j <= i; j++) 

Halving your work (reprise)

        for (int i = 0; i < productStrLen; i++) {
            if (productStr.charAt(i) != productStr.charAt(j)) 
                return;
            j--;
        }

Again, you are doing twice as much work as necessary here. For 6-digit palindromes like 123321, you're checking ...

         productStr.charAt(0) != productStr.charAt(5)
         productStr.charAt(1) != productStr.charAt(4)
         productStr.charAt(2) != productStr.charAt(3)
         productStr.charAt(3) != productStr.charAt(2)
         productStr.charAt(4) != productStr.charAt(1)
         productStr.charAt(5) != productStr.charAt(0)

The first tests is effectively the same test as the last one; the second test is the same as the second last; the third test is the same as the third last.

Stop checking when you get to the middle (i & j switches from i < j to i >= j), and cut the number of tests in half.

        for (int i = 0; i < j; i++) {
            if (productStr.charAt(i) != productStr.charAt(j)) 
                return;
            j--;
        }

Reversing the search

You start at 100*100 and search upwards until you reach 999*999. The product which produces the largest palindrome is likely near the end of your search space. If you started at 999*999 and worked down towards 100*100, you'd likely encounter the largest palindrome earlier. Can you determine a point where it is futile to continue searching?

Consider 202 * 202 == 40804. That's a palindrome. Would any product of numbers i < 202 and j < 202 ever be larger than 40804?

More generally, if you find a j <= i where i * j is a palindrome, at what point is additional searching futile?

Left to student.

Answer 3

One additional remark:

Method and variable naming

Try to name a method in such a way that this name tells you what the method achieves. That's an art and something that typically improves with experience. This is to some extent related to the Single Responsibility Priciple, in that a method or class that can easily be given a good name, often also follows that principle.

E.g. from its name, I read findLargestPalindrome(int m1, int m2) to be a method that finds the largest palindrome of two numbers m1 and m2, and that leaves me confused. From the name, I expect this method to produce a result, but it does not return a result, you declared it as void. And the role of the two arguments m1 and m2 is unclear.

This method does not do what its name suggests:

• it does not find a palindrome, it checks one (indirectly given) candidate.

As an aid to good naming (and software structuring) and a good habit anyway, write Javadoc comments for your methods. A description for your current findLargestPalindrome(int m1, int m2) method might be something like:

Check whether the product of the two given numbers is a palindrome greater than the currently largest one, and if so, save it as the currently largest one.

So, based on that analysis, a name better describing your method would be checkProductForBeingAPalindromeGreaterThanCurrentLargestAndStore(), and you'd surely agree that this is undesirable. This naming now shows that the structure can be improved (and Alexander's answer shows an example of a better structure).

Code Structure

Your code structure is similar to what I might have written 40 years ago, when beginning my delevoper career. It works, but I'd do it very differently today (and for good reasons).

As exercise for code structure, begin a new task by dividing it into sub-tasks. Do this on paper, not yet in code. For each sub-task, imagine a clerk who will do just this task. What is the wording that you give him for the task, what are the inputs given to him, what is the output you expect, and what does he have to write down as notes that persist from task to task? Each sub-task can become a method, with the inputs translated to method arguments, the output as method return value, and the notes as fields in a class. And the wording for the task gives the method name.

Only then start to write code that follows this structure.

Maybe your first attempts will fail, in the sense that, while coding, you detect that some information is missing when implementing some method. You can then either modify the task descriptions, if you feel that does not contradict the initial concept, or throw away the code, and restart from scratch.

This will improve with experience.