TDD for Euler Problem #4

I am in the process of learning Java and going through the Euler problems. For Problem 4 I decided to also implement a TDD approach with JUnit.

My questions are:

1. Is there a better TDD approach to this problem?
• I wrote out all these test cases initially. Some obviously pass and some fail initially because I'm checking a boolean. This makes it impossible to write a failing test in this fashion, should I have written only a failing scenario (say test100), then added in more as my method worked?
2. Being new to Java, are there obvious code organization things I am missing?
3. Any naming tips would be appreciated as well as I am terrible at this generally!

I have three source files:

main.java

public class main {

public static void main(String[] args) {

PalindromeChecker p = new PalindromeChecker();
int largest=0;
int product;

for (int i = 999; i>100; i--){

for (int j = 999; j>100; j--){
product = i*j;
if (p.isPalindrome(product) && product > largest) {
largest = product;
}
}
}
System.out.println(largest);
}
}


PalindromeChecker.java

public class PalindromeChecker {

public boolean isPalindrome(int input){

String str = new Integer(input).toString();
int len = str.length();

for(int i = 0; i < Math.ceil(len/2.0); i++){

if (str.charAt(i) != str.charAt(len-i-1)) {
return false;
}
}

return true;

}
}


PalindromeCheckerTest.java

import static org.junit.Assert.*;
import org.junit.Test;

public class PalindromeCheckerTest {

@Test
public void test10() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse("10 failed",checker.isPalindrome(10));
}
@Test
public void test112() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse("112 failed",checker.isPalindrome(112));
}
@Test
public void test900() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse("900 failed",checker.isPalindrome(900));
}

@Test
public void test1000() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse("1000 failed",checker.isPalindrome(1000));
}

@Test
public void test909() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(909));
}

@Test
public void test1001() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(1001));
}

@Test
public void test11() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(11));
}

@Test
public void test111() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(111));
}

}

• If you are really writing your tests first, then it's easy to write a failing test, even if it's a boolean. This is because the code won't even compile, because the code under test doesn't exist yet. – RubberDuck Feb 28 '15 at 19:02

First of all, your PalindromeChecker does not contain any state, it is a simple input --> output operation not depending on outer factors. This makes it an ideal candidate for being a static method.

Your naming is okay overall, but I would use the name Palindromes for your class.

String str = new Integer(input).toString();


It is better to use String.valueOf here. There's no need to create an Integer object.

for (int j = 999; j>100; j--){


Technically, you're off by one here. You're missing the case when j == 100, which is also a three-digit number (the same goes for i btw).

Correct would be (also with improved spacing)

for (int j = 999; j >= 100; j--) {


So, here's how I would make your class:

public class Palindromes {

public static boolean isPalindrome(int input) {
String str = String.valueOf(input);
int len = str.length();

for(int i = 0; i < Math.ceil(len/2.0); i++) {
if (str.charAt(i) != str.charAt(len - i - 1)) {
return false;
}
}
return true;
}

}


All your test cases contains pretty much the same code, but with different parameters.

With the change to a static method, the test cases will look more like:

assertFalse("10 failed", Palindromes.isPalindrome(10));


This is ideal for a Parameterized test, which will make it significantly easier to add more tests.

@RunWith(Parameterized.class)
public class PalindromeTest {
@Parameters
public static Collection<Object[]> data() {
return Arrays.asList(new Object[][] {
{ 10, false },
{ 100, false },
{ 909, true },
...
});
}

private final int input;

private final boolean expectedPalindrome;

public PalindromeTest(int input, boolean expectedPalindrome) {
this.input = input;
this.expectedPalindrome = expectedPalindrome;
}

@Test
public void test() {
assertEquals("Failed for " + input,
expectedPalindrome, Palindromes.isPalindrome(input));
}
}

• Yey for parameterised tests! – Boris the Spider Mar 1 '15 at 19:22

Using TDD

It's a great idea to use TDD to drive your development, keep it up!

1. Is there a better TDD approach to this problem?

This is an odd question. TDD is a way to develop a program. It's a process, and its result is a finished program that is working and passing all the tests. What I'm trying to say is that you can comment on somebody's TDD technique while he's still working, once his work is finished, the process is over, the job is done.

You could comment on the class and method organization that emerged in the process. When you have a complex problem, TDD will drive your development to a solution that passes your assertions. In the beginning you might not even know what the final structure will be, it will just emerge naturally, as you write more and more tests, as you realize all the features you would like your program to have.

In this program, the structure that "emerged" is very simple: it's just one method. It's good that way, but there's nothing I could comment on in terms of TDD.

Unit testing

All test cases create a new PalindromeChecker instance. That's fine, but tedious to type every time. When you find yourself repeating too much, I suggest to add some private helper methods in your test class. Especially in the program at hand, since the class has no state, the method calls will have no side effects, so there's no need to create a new instance for every test case.

In fact, when I know that multiple tests will test the same method, I always create a private helper for it. That way, if later I want to replace the class being tested with something else, I can easily make the change in one place. Like this:

private boolean isPalindrome(int num) {
PalindromeChecker checker = new PalindromeChecker();
return checker.isPalindrome(num);
}

@Test
public void test10() {
assertFalse("10 failed", isPalindrome(10));
}

@Test
public void test112() {
assertFalse("112 failed", isPalindrome(112));
}


Now the helper method encapsulates the underlying method that's being tested. I can easily change the underlying call in one place instead of in every single test case.

It's nice to add a message parameter in unit tests in general, but in this case they are quite redundant. Since your test methods are nicely named, for example test112, when you see in your IDE that this test case failed, the method name is already clear enough, no need to spell out "112 failed". So I'd just drop the message parameter (I'm quite lazy).

Main implementation

You don't need to iterate until Math.ceil(len / 2.). This will result in an unnecessary check for numbers with odd length, as in the end the middle digit will be compared against itself, which is pointless. The loop condition can be simplified to this:

    for (int i = 0; i < len / 2; i++) {


Also, converting to string to check if a number is palindromic doesn't really feel right. Perhaps a solution using math would be more elegant.

• Even better, make the checker static. – Cole Johnson Feb 28 '15 at 19:12

TDD

A TDD strategy starts with the tests, and I don't see much evidence that the tests came first, in your code (not saying that it didn't come first, but that the evidence is absent).

A good TDD strategy will identify the anticipated issues early, and I don't see these cases:

@Test
public void testMAX() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse(checker.isPalindrome(Integer.MAX_VALUE));
}

@Test
public void testMIN() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse(checker.isPalindrome(Integer.MIN_VALUE));
}

@Test
public void testNeg1() {
PalindromeChecker checker = new PalindromeChecker();
assertFalse(checker.isPalindrome(-1));
}

@Test
public void testZero() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(0));
}

@Test
public void testOne() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(1));
}

@Test
public void testLarge() {
PalindromeChecker checker = new PalindromeChecker();
assertTrue(checker.isPalindrome(2147447412));
}


There, there are some tests, that should all pass..., now you go, and code it to work to fit the tests.

Review

Other reviews have covered a bunch of things already.

I will only say that there are about 1000 palindrome numbers that are possible.... the largest 3-digit product would be 999 * 999 giving 998001, and the smallest is 100 * 100 giving 10000, I would consider an algorithm which counts down from 999 making the mirrored palindrome sequence 999999 998899 997799, etc, and then finding the first one that has two 3-digit factor pairs....

• but to find the first one that is the multiple of two 3-digit numbers is not an easy task. You're essentially replacing a multiplication with a division to check if it is evenly divisible by a number from 100 to 999, and if the remainder of that is a three-digit number. I wonder what the speed difference would be (if only there was a microbench framework where that could be tested....) – Simon Forsberg Feb 28 '15 at 18:12
• If you practice TDD you should start with writing a single test for a specific, simple case; make it pass; make it better - repeat until done. (A.k.a. the red-green-refactor cycle.) TDD is not writing a bunch of tests and making them all pass in one go. You could call this latter approach test-first, but there is no actual test-driven design going on. – Eric Mar 1 '15 at 21:13

Is there a better TDD approach to the problem?

Difficult to answer as I can only see your end result, not your process. My general impression: you TDD'd the palyndrome checker, but not the general problem of finding the largest number that satisfies the problem's restriction.

One approach that works with this sort of algorithmic problems is to (a) generalize the problem and then (b) start with the simplest instance of the generalized problem. In this case, the generalized problem would be

Find the largest palindrome that is the product of N-digits numbers.

So you could start TDD by finding the largest palindrome that is the product of 1-digit numbers. This approach has the advantage that it's reasonably easy to compute the expected solution by hand, so you know what is the expected result :) (which would be 3*3=9)

The key in TDD is to be able to do very small steps, so that you have a fast TDD cycle (minutes, not tens of minutes). If the above problem is still too big to solve in less then ten minutes, you could generalize further:

Find the largest number satisfying predicate P that is the product of N-digits numbers.

So you can start with P="being even" and N=1 and then complicate step by step.

Tips for Java coding

I think the palyndrome checker only needs to check up to n/2, no need for Math.ceil here.

Naming tips

Peter Coad once said that class names should not end in ...er :) (see http://www.carlopescio.com/2011/04/your-coding-conventions-are-hurting-you.html) One idea would be to do define a Number class that has a isPalindrome method. Another is to use Function<Integer, Boolean>.

For test-driving this method, I would tend to start simple and work my way deeper. Yes, the fact that it's a boolean result makes it likely that you'll sometimes find yourself writing passing tests, but that's just how it goes sometimes.

So what's the simplest case? Probably null or the empty string. Is either one of those a palindrome? Make the relevant assertion. Now make it pass (easy: just return true). Now a single-character string - OK, no change needed. Now a two-character string containing two different characters: it begins to get interesting, because now the method under test needs some actual logic. Maybe

if (s == null || s.length < 2) return true;
return false;


Which isn't final or correct - but it's on the right path. That first line will work for all palindromes; we just need to enrich it a bit. Add a two-character string where both characters are the same - another failing test. So now add the logic which tests that the first and last characters match:

if (s == null || s.length < 2) return true;
return s.charAt(0) == s.charAt(s.length - 1);


From here, you can see your way forward to the solution; just make a couple of longer cases pass and you're good to go.

This is the more incremental TDD approach, where you can really witness the tests driving your design.