TDD svino Problem #4 - largest value from concatenated integers?

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 input){

        return getStringFromList(sortIntegerList(input));
    };

    private String getStringFromList(List input){
        String s = "";
        for (int i = 0; i  sortIntegerList(List input){

        for (int i = 0; i  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 un

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 LEXIOGRAPHIC = new Comparator() {

    @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  secondVal){
                    return -1;
                } else {
                    return 1;
                }   
            }
        }

        return 0;
    }

};

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

public String largestNumberFromList(List 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 {

    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 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 LEXIOGRAPHIC = new Comparator() {

    @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 input){
    input.sort(LEXIOGRAPHIC);    
    return getStringFromList(input);
};

Additionally, the `ge

StackExchange Code Review Q#90206, answer score: 6