10
\$\begingroup\$

From this blog post:

Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.

I did this in with two tests and using a TDD style.

I am pretty unfamiliar with Java, so looking for overall feedback. And/or inputs this fails on...

import static org.junit.Assert.*;

import java.util.Arrays;
import junit.framework.TestCase;
import org.junit.Test;

public class ProblemFourTest extends TestCase{
    ProblemFour p;
    public void setUp(){
         p = new ProblemFour();
    }

    @Test
    public void testExample() {
        assertEquals("95021",p.largestNumberFromList(Arrays.asList(50,2,1,9)));

    }
    @Test
    public void test50556() {
        assertEquals("56550",p.largestNumberFromList(Arrays.asList(50,5,56)));

    }
    @Test
    public void testComplicatedExamples() {
        assertEquals("9999129220201",p.largestNumberFromList(Arrays.asList(99,2,20,20,29,91,1,9)));
    }

}

The associated code is:

import java.util.List;

public class ProblemFour {

    public String largestNumberFromList(List<Integer> input){

        return getStringFromList(sortIntegerList(input));
    };

    private String getStringFromList(List<Integer> input){
        String s = "";
        for (int i = 0; i < input.size(); i++){
            s += input.get(i);
        }

        return s;

    }
    private List<Integer> sortIntegerList(List<Integer> input){

        for (int i = 0; i < input.size(); i++){

            for (int j = i + 1; j < input.size(); j++) {

                int a = input.get(i);
                int b = input.get(j);

                if (b == getLargestLexiographcal(a,b)){
                    input.set(i, b);
                    input.set(j, a);
                }
            }

        };

        return input;

    }

    int getLargestLexiographcal(int a, int b){

        String first = "" + a;
        String second = "" + b;

        for (int i = 0; i < Math.max(first.length(), second.length()); i++){

            int firstVal = Integer.valueOf(first.charAt(Math.min(i,first.length() - 1)));
            int secondVal = Integer.valueOf(second.charAt(Math.min(i,second.length() - 1)));

            if (firstVal != secondVal ){
                if (firstVal > secondVal){
                    return Integer.valueOf(first);
                }
                else
                {
                    return Integer.valueOf(second);
                }   
            }
        }

        return 0;   

    }

}

I found that the refactor stage was quite easy to do having the test cases. I dropped a bunch of duplication from getLargestLexiographcal after my second test case. It was very, very painful to write working code and not refactor once I realized I was duplicating code. I had previous treated the equal length case as different than the unequal length. However, once the test passed refactoring was very simple and straightforward - a compelling reason for me to not refactor when trying to pass a test, and only afterwards. It lets you incremental refactor, rerun tests, repeat very quickly.

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

Style - good

The TDD is a great way to start. You can see the benefits already, especially in the fact that it was easy for me to copy your code and run it locally, and make sure it works (not that I doubted it, but it's nice to check).

There's a typo in a method name... I know that's a silly thing to point out, but it is the first thing I saw. My spelling (actually, my typing) is often criticised, and as a result I am sensitive to these things. The method getLargestLexiographcal is missing an i here: getLargestLexiographical.

Beyond that, though, the code is really neat, and well structured. Two nit-picks.... in your bracing style (yeah, yeah, I know, not the bracing....!) But, you should be consistent with the space before the opening brace. Sometimes you have a space before the brace, and sometimes, not. You should have a space. So, for example, the lines:

        if (firstVal != secondVal ){
            if (firstVal > secondVal){

should be:

        if (firstVal != secondVal) {
            if (firstVal > secondVal) {

The other nitpick is the newlines in the else block. Yeah, it's a real nitoick, but I prefer a single-line for the } else {, not 3 lines. Still, there is only one instance of this, so at least it is consistent ;-)

OK, enough about the trivials....

Minutia

String concatenation to get a String value of an Integer is overkill... things like:

 String first = "" + a;

Really, that should be:

 String first = a.toString();

The Integer.valueOf(...) in the following line should also probably be Character.getNumericValue(...):

Integer.valueOf(first.charAt(Math.min(i,first.length() - 1)))

should be:

Character.getNumericValue(first.charAt(Math.min(i,first.length() - 1)))

Sorting

Your sorting algorithm is simplistic, but effective. A bubble-sort, of sorts. The major drawback I see is the many comparisons, especially given that each comparison is performed from first-principles... calculating the lexographical value each time, instead of memoizing it.

All told, though, I really would have preferred to see a standard-library sort using a Comparator for the comparisons.... The comparator would look something like:

private static final Comparator<Integer> LEXIOGRAPHIC = new Comparator<Integer>() {

    @Override
    public int compare(Integer a, Integer b) {
        // same values compare the same.
        if (a.equals(b)) {
            return 0;
        }
        String first = a.toString();
        String second = b.toString();

        for (int i = 0; i < Math.max(first.length(), second.length()); i++){

            int firstVal = Character.getNumericValue(first.charAt(Math.min(i,first.length() - 1)));
            int secondVal = Character.getNumericValue(second.charAt(Math.min(i,second.length() - 1)));

            if (firstVal != secondVal ){
                if (firstVal > secondVal){
                    return -1;
                } else {
                    return 1;
                }   
            }
        }

        return 0;
    }

};

Then, with that comparator, you can just sort the list:

public String largestNumberFromList(List<Integer> input){

    input.sort(LEXIOGRAPHIC);

    return getStringFromList(input);
};

The sort used will be the native sort in Java, an efficient TimSort, I believe.

When possible, use the library functions available....

Alternative

I would recommend creating a number class, that implements Comparable, then, when you process the system, just create a new instance of that class for each input value. The constructor should create the lexographical value at that time, and the comparator will then be much simpler too. If you add the values to an always-sorted collection, like a TreeSet, then you can just do it all in one go.

Hmmm... in retrospect, I played around with it, and came up with the following class, and a 'simple' lambda expression to arrange it.... Note, the compareTo function is a 'clever' trick of appendign each value in opposite orders, and then comaring them. It makes the relative order easy to compute. It may not be the fastest, but it sure is simple to read....

private static final class LexiVal implements Comparable<LexiVal> {

    private final String value;

    public LexiVal(int value) {
        this.value = Integer.toString(value);
    }

    @Override
    public int compareTo(LexiVal o) {
        final String usthem = value + o.value;
        final String themus = o.value + value;
        return themus.compareTo(usthem);
    }

}

public String largestNumberFromList(List<Integer> input){
    return input.stream()
                .map(i -> new LexiVal(i))
                .sorted()
                .map(x -> x.value)
                .collect(Collectors.joining());
};

Aas a side note, that same logic used in the LexiVal could be used in the Comparator instead.....

private static final Comparator<Integer> LEXIOGRAPHIC = new Comparator<Integer>() {

    @Override
    public int compare(Integer a, Integer b) {
        String ab = a.toString() + b.toString();
        String ba = b.toString() + a.toString();
        return ba.compareTo(ab);
    }

};

then your algorithm becomes:

public String largestNumberFromList(List<Integer> input){
    input.sort(LEXIOGRAPHIC);    
    return getStringFromList(input);
};

Additionally, the getStringFromList(input) can be made in to a Jav8 stream, with:

return input.stream().map(i -> i.toString()).collect(Collectors.joining());
\$\endgroup\$
  • \$\begingroup\$ It's more idiomatic to use method references where possible - so map(i -> new LexiVal(i)) can be map(LexiVal::new) and map(i -> i.toString()) can be Object::toString. \$\endgroup\$ – Boris the Spider May 9 '15 at 7:56
  • \$\begingroup\$ Ahh, adding the strings together then comparing them is much more straightforward to compare and probably handles nearly all the edge cases better. Comparators are interesting, that seems like a nifty way to avoid having to write sort algorithms :) Funny on the typo, didn't even notice that - shows you I was copy/pasting it to use it... \$\endgroup\$ – enderland May 9 '15 at 11:20
  • \$\begingroup\$ To be clear, it took some fiddling and geeing an hawing before I figured out the ab/ba, you will see the time on the edit revisions.... It is certainly not obvious, but it does make the code much cleaner, and in fairness, your compare system was confusing, but I thought I understood it, but I never noticed the bugs.... and the fact that ab/ba solves them is not by design.... ;-) \$\endgroup\$ – rolfl May 9 '15 at 11:27
5
\$\begingroup\$

Your code fails for

@Test
public void test153() {
    assertEquals("15315", p.largestNumberFromList(Arrays.asList(153, 15)));
}

as you simply assume that 153 and 15 should be compared like "153" and "155". But repeating the last digit of the shorter string is wrong. Here, you must expect that the next digit will be 1 and treat 15 like "151". It looks like the outcome should depend on the biggest still available number, so I'm unsure if sorting and pairwise comparison can work.


I guess this problem occurs whenever one argument is a prefix of the other. Using something like

int firstVal = Character.getNumericValue(first.charAt(i % first.length()));

seems to solve it for the above case, but there may be other problems.

Comparator

My Comparator would accept strings instead of ints, as we're actually dealing with strings, the fact that they represent numbers is rather irrelevant.

private static final Comparator<String> LEXICOGRAPHIC = new Comparator<String>() {
    @Override public int compare(String a, String b) {
        int result = a.compareTo(b);
        // Handle equal strings, non-prefixes, and empty strings.
        // For equal strings, it's just a trivial optimization (drop it).
        // For non-prefixes, there's no need to look at the numerical value.
        // Empty strings shouldn't occur, but a sane Comparator must handle them (the below code would throw).
        if (result == 0 || !a.startsWith(b) && !b.startsWith(a) || a.isEmpty() || b.isEmpty()) {
            return result;
        }

        final int maxLength = Math.max(a.length(), b.length());
        for (int i = 0; i < maxLength; i++) {
            // A bigger character means bigger numerical value (unless we care about non-ASCII digits, which I don't).
            result = Character.compare(a.charAt(i % a.length()), b.charAt(i % b.length()));
            if (result != 0) {
                return result;
            }
        }

        return 0;
    }
};

Another Comparator idea

This answers the question "Is a and then b bigger than the other way round?" pretty directly. Assuming a comparator can be used, it must be right.

private static final Comparator<String> LEXICOGRAPHIC = new Comparator<String>() {
    @Override public int compare(String a, String b) {
        return (a+b).compareTo(b+a);
    }
};

Testing

It looks like writing a couple of tests manually is insufficient. I'd write a stupid method trying all permutations and compare the results for a few thousands pseudorandom inputs containing many strings which are prefixes of each other.

\$\endgroup\$
  • \$\begingroup\$ The trick in this case is writing a method that tests all the different input conditions, because to correctly evaluate them would require knowing their valid results. But if this was an interview problem or something of that sort where more criteria were specified I think it'd work better - with TDD you basically code the minimal working code for your given criteria, and in this case the coder (me) has to create those. \$\endgroup\$ – enderland May 9 '15 at 11:23
  • \$\begingroup\$ @enderland The problem with the trick, is that it's just an untested and untestable trick. You can never be sure that your trick does cover all the possibilities, but you can never be sure. That's why I consider pseudorandom testing important. The valid results can be obtained using a slow and stupid algorithm. \$\endgroup\$ – maaartinus May 9 '15 at 11:41
  • \$\begingroup\$ I guess the part I'm missing is actually validating the results - you need to have the "correct" answers somehow, and if you are testing your algorithm you can't use it to generate the results. \$\endgroup\$ – enderland May 9 '15 at 11:56
  • \$\begingroup\$ @enderland All you can do is to compare two things. Let's call the one produced by the code under test "actual" and the other "expected". The expected thing can be computed manually (as you did) or via a simple, stupid, slow, and foolproof code (as I'd do in the random test). Nothing is perfect, but when the results coincide, then the confidence grows. That's all we can get. \$\endgroup\$ – maaartinus May 9 '15 at 13:29
4
\$\begingroup\$

StringBuilder rather than String

        String s = "";

If you are building a String, you should use StringBuilder (or StringBuffer if you need thread safety). Concatenating strings creates a new object each time. The same StringBuilder can be used multiple times.

        StringBuilder s = new StringBuilder();

More about this in the next section of code.

Use the Java for each form

        for (int i = 0; i < input.size(); i++){
            s += input.get(i);
        }

        return s;

If you are iterating over an array or collection, you can use the for each variant:

        for ( int number : input ) {
            s.append(number);
        }

        return s.toString();

This saves having to index into the collection and maintains the loop limits for you. You should try to use it when you can, as it removes several areas of possible error.

Switching to StringBuilder caused more changes in this code as well.

Processing a string character by character

        String first = "" + a;
        String second = "" + b;

You don't actually want String values here. What you want are actually collections of digits.

        char [] aDigits = Integer.toString(a).toCharArray();
        char [] bDigits = Integer.toString(b).toCharArray();

Now you can dereference the individual digits easily. I also changed the name to make it clearer what the variables hold and what their relationships are with a and b.

Note that I don't say a.toString() because a is a primitive type, which doesn't have a toString method. You could also change the method declaration to take Integer variables instead of int.

        for (int i = 0; i < Math.max(first.length(), second.length()); i++){

There are two problems. One, you are repeatedly checking a value that will never change. Two, it's sometimes the wrong value.

        int i = 0;
        final int maxLength = Math.max(aDigits.length, bDigits.length);
        final int n = Math.min(maxLength, 2 * Math.min(aDigits.length, bDigits.length));
        for ( ; i < n; i++) {

Notice that I limit the length to twice that of the shorter number. The reason for this is that

@Test
public void test1515151() {
    assertEquals("1515151", p.largestNumberFromList(Arrays.asList(15151, 15)));
}

returns the wrong value without that.

I also move the i declaration outside of the loop. The reason for this is that I plan to use i again after the loop. I could put the n declaration in the loop declaration, but I think it's easier to have it outside if i is outside.

            int firstVal = Integer.valueOf(first.charAt(Math.min(i,first.length() - 1)));
            int secondVal = Integer.valueOf(second.charAt(Math.min(i,second.length() - 1)));

            if (firstVal != secondVal ){
                if (firstVal > secondVal){

OK, here's the subsequent logic. Which simplifies to

            final char aDigit = aDigits[i % aDigits.length];
            final char bDigit = bDigits[i % bDigits.length];

            if (aDigit != bDigit) {
                if (aDigit > bDigit) {

Part of that's the switch from a String to a char array, but the index is also simpler.

As @maaartinus noted, what you want to do is to compare the first digit after the end of the other number to the first digit of the other number.

                    return Integer.valueOf(first);
                }
                else
                {
                    return Integer.valueOf(second);
                }   
            }
        }

We don't need to convert the String values to integers. We already know the integer values.

                    return a;
                }
                else
                {
                    return b;
                }   
            }
        }

That's good, since I don't have a simple way to convert a char array to an integer.

        return 0;   

    }

Oops. We still have to handle the case where i < maxLength after the loop.

        if (i < maxLength && bDigits.length < maxLength) {
            return b;
        }

        return 0;   

    }

This handles your test cases plus the one I added above.

Still missing case

@Test
public void test1515715() {
    assertEquals("1515715", p.largestNumberFromList(Arrays.asList(15157, 15)));
}

This test breaks the latest version, although @rolfl's ab/ba trick handles it.

The primary point that I wanted to make was that if you want to traverse a String character by character, you don't have to keep the String. Converting to a char array makes the syntax simpler. If we weren't comparing two of them, we could have used the for each form on the array. We can't do that directly with the String.

\$\endgroup\$
  • \$\begingroup\$ Concatenating strings creates a new object each time <- did not realize this, though it makes a lot of sense. I removed the intermediate variables for .length() - I was assuming this was a simple lookup each time I called that. \$\endgroup\$ – enderland May 9 '15 at 11:30
3
\$\begingroup\$

Your code has already received a lot of feedback, I'll only comment on your testing style:

  • It's not recommended to mix JUnit3 (extends TestCase) and JUnit4 features (@Test annotation). Stick with JUnit4.
  • Since the class ProblemFour has no state (and shouldn't have state), there's no need to recreate a new instance in a setUp method, a private final field is enough
  • Test cases should have descriptive names. If the case test50556 fails, looking at just the name I cannot tell what that number is about, and it's impossible to tell that it should come from a list of 50, 5, 56. A name like test_50_5_56_to_56550 would make that easier to understand, and easier to understand when reading a test failure output.

The test class rewritten using the tips above becomes:

public class ProblemFourTest {

    private final ProblemFour p = new ProblemFour();

    @Test
    public void test_50_2_1_9_to_95021() {
        assertEquals("95021", p.largestNumberFromList(Arrays.asList(50, 2, 1, 9)));
    }

    @Test
    public void test_50_5_56_to_56550() {
        assertEquals("56550", p.largestNumberFromList(Arrays.asList(50, 5, 56)));
    }

    @Test
    public void test_99_2_20_20_29_91_1_9_to_9999129220201() {
        assertEquals("9999129220201", p.largestNumberFromList(Arrays.asList(99, 2, 20, 20, 29, 91, 1, 9)));
    }

}
\$\endgroup\$
  • \$\begingroup\$ Ahh, so that's why I had to prefix everything with testXXX for my names. I didn't realize TestCase was a Junit3 item, so no wonder the @Test wasn't working. \$\endgroup\$ – enderland May 9 '15 at 11:31

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.