Project Euler 17: counting letters needed to write numbers

Question

The statement of the problem is :

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

This problem seemed simple at first, but got me really involved. So my implementation is pretty straightforward and really dirty.

public class Euler_17{

public static String[] digits = {"Error", "one", "two", "three", "four", "five", "six",
                        "seven", "eight", "nine"};

public static String[] tensArray = {"Error", "twenty", "thirty", "forty", "fifty", 
                     "sixty", "seventy", "eighty", "ninety"};

public static String[] elevenToNineteen = {"Error", "eleven", "twelve", "thirteen", "fourteen",
                                    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};

public static String giveMeString(int num){
    // Using StringBuilder to make up the number
    StringBuilder theNumber = new StringBuilder();
    // String value of the number so that I can
    // extract specific numbers from it
    String number = String.valueOf(num);
    // Deals with three digit numbers
    if(number.length()==3){
        int units = Integer.parseInt(String.valueOf(number.charAt(2)));
        int tens = Integer.parseInt(String.valueOf(number.charAt(1)));
        int hundreds = Integer.parseInt(String.valueOf(number.charAt(0)));
        if(tens == 0){
            if(units == 0){
                theNumber.append(digits[hundreds]);
                theNumber.append("Hundred");
                return theNumber.toString();
            }
            xHunderedAnd(theNumber, hundreds);
            theNumber.append(digits[units]);
        }else{
            theNumber.append(digits[hundreds]);
            theNumber.append("HundredAnd");
            StringBuilder _ifNumberLessThanNineteen = new StringBuilder();
            _ifNumberLessThanNineteen.append(tens);
            _ifNumberLessThanNineteen.append(units);
            int ifNumberLessThanNineteen = Integer.parseInt(_ifNumberLessThanNineteen.toString());
            if(ifNumberLessThanNineteen<=19){
                lessThanNineteen(theNumber, ifNumberLessThanNineteen);
            }else{
                theNumber.append(tensArray[tens-1]);
                if(units!=0)
                    theNumber.append(digits[units]);
            }
        }
    // Deal with 2 digit numbers
    }else if(number.length()==2){
        int units = Integer.parseInt(String.valueOf(number.charAt(1)));
        int tens = Integer.parseInt(String.valueOf(number.charAt(0)));
        StringBuilder _ifNumberLessThanNineteen = new StringBuilder();
        _ifNumberLessThanNineteen.append(tens);
        _ifNumberLessThanNineteen.append(units);
        int ifNumberLessThanNineteen = Integer.parseInt(_ifNumberLessThanNineteen.toString());
        if(ifNumberLessThanNineteen<=19){
            lessThanNineteen(theNumber, ifNumberLessThanNineteen);
        }else{
            theNumber.append(tensArray[tens-1]);
            if(units!=0)
                theNumber.append(digits[units]);
        }
    // This one will only go for 1,000
    }else if (number.length() == 4){
        theNumber.append("oneThousand");
    // This one is for single digit number
    }else{
        theNumber.append(digits[num]);
    }
    return theNumber.toString();
}

// Appends to StringBuilder the numbers in the form of
// {1-9} Hundered and {1-9} {1-9}
public static void xHunderedAnd(StringBuilder theNumber, int num){
    theNumber.append(digits[num]);
    theNumber.append("HundredAnd");
}

// Special case for the numbers less than nineteen
public static void lessThanNineteen(StringBuilder theNumber, int numberLessThanNineteen){
    if(numberLessThanNineteen==10){
        theNumber.append("Ten");
        return;
    }
    theNumber.append(elevenToNineteen[numberLessThanNineteen-10]);
}

public static void main(String[] args) {
    int totalChars = 0;
    for(int i=1; i<=1000; i++){
        String number = giveMeString(i);
        System.out.println(number);
        totalChars += number.length();
    }
    System.out.println("The total length is : " + totalChars);
}
}

Answer 1

You don't quite seem to have realized this, but...

"One hundred and ..." means that what you can do is, for a 3 digit number - count the hundreds, as "One hundred" and "Two hundred", and then append what's left if the number passed in is not a multiple of hundred.

That way you deal with 2 digit numbers in only 1 place. As for how you'd go about it - just call giveMeString again, but with the remainder - so giveMeString(150) does "OneHundred" + "and" + giveMeString(50).

There's other tricks you could use, though. You know how long "OneTwoThree...NinetyNine" is. You also know it continues with "OneHundredOneHundredAndOneOneHundredAndTwo" or, basically, length of (1-99) + 99x ("OneHundredAnd") + 1 x ("OneHundred") gives you 1-199. From there on, it becomes simple addition and multiplication.

If you keep your old implementation, you can use that to verify that the maths based approach works.

Answer 2

Simple optimisation

At the moment, all your code relies on String : you retrieve Strings, you concatenate them and ultimately, you check the length.

An easier solution would be to keep your arrays :

public static String[] digits = {"Error", "one", "two", "three", "four", "five", "six",
                        "seven", "eight", "nine"};

public static String[] tensArray = {"Error", "twenty", "thirty", "forty", "fifty", 
                     "sixty", "seventy", "eighty", "ninety"};

public static String[] elevenToNineteen = {"Error", "eleven", "twelve", "thirteen", "fourteen",
                                    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};

but also to use them to get the corresponding lengths once (and only once). For instance, instead of converting 15 (number) to "fifteen" (string) then 7 (number), you can directly map 15 (number) to 7 (number). String concatenations become simple number additions ; adding " and " corresponds to adding andLength.

Reorganising the logic

Trying to handle cases with 3 digits then 2 then 4 then 1 is complicated ... and likely to fail.

It is probably easier to split your number into different parts than can be easily converted to numbers.

I modified your code to do so and got :

public class Euler_17{

    public static String[] digits = {"Error", "one", "two", "three", "four", "five", "six",
        "seven", "eight", "nine"};
    public static String[] tensArray = {"Error", "Error2", "twenty", "thirty", "forty", "fifty", 
        "sixty", "seventy", "eighty", "ninety"};
    public static String[] elevenToNineteen = {"Error", "eleven", "twelve", "thirteen", "fourteen",
        "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
    public static String and = "And";
    public static String ten = "Ten";
    public static String hundred = "Hundred";
    public static String thousand = "Thousand";

    public static String giveMeString(int num){
        // Using StringBuilder to make up the number
        StringBuilder theNumber = new StringBuilder();
        int units = num % 10;
        num /= 10;
        int tens = num % 10;
        num /= 10;
        int hundreds = num % 10;
        num /= 10;
        int thousands = num % 10;

        if (thousands > 0)
        {
            theNumber.append(digits[thousands]);
            theNumber.append(thousand);
        }

        if (hundreds > 0)
        {
            theNumber.append(digits[hundreds]);
            theNumber.append(hundred);

            if (tens > 0 || units > 0)
                theNumber.append(and);
        }

        if (tens > 0){
            int ifNumberLessThanNineteen = 10 * tens + units;
            if(ifNumberLessThanNineteen<=19){
                if(ifNumberLessThanNineteen==10)
                    theNumber.append(ten);
                else
                {
                    theNumber.append(elevenToNineteen[ifNumberLessThanNineteen-10]);
                    units = 0;
                }
            }else{
                theNumber.append(tensArray[tens]);
            }
        }

        if (units > 0) {
            theNumber.append(digits[units]);
        }
        return theNumber.toString();
    }

    public static void main(String[] args) {
        System.out.println("BEGIN");
        int totalChars = 0;
        for(int i=1; i<=1000; i++){
            System.out.println(i);
            String number = giveMeString(i);
            System.out.println(number);
            totalChars += number.length();
            //System.out.println(i + "," + totalChars);
        }
        System.out.println("The total length is : " + totalChars);
    }
}

Once this is done, I suggest rewriting digits, tens and elevenToNineteen in a single container even if it seems a bit dodgy.

You could then write something like :

public static String[] from0to19 = {"Error", "one", "two", "three", "four", "five", "six",
    "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen",
    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
....
    if (tens > 1)
        theNumber.append(tensArray[tens]);
    else
        units += 10 * tens; // hack to move tens in units
    if (units > 0) {
        theNumber.append(from0to19[units]);
    }

From this point it is very easy to take into account my first comment. (I can't be bothered to use code to do things properly so I've copy-pasted like crazy). You'll notice than the function compute the length of the string without calling length() even once. I've kept the original code so that you can see that the translation if pretty obvious.

public class Euler_17{

    public static int error = -2000; // arbitrary
    public static int from0to19_[] = {error, "one".length(), "two".length(), "three".length(), "four".length(), "five".length(), "six".length(),
        "seven".length(), "eight".length(), "nine".length(), "ten".length(), "eleven".length(), "twelve".length(), "thirteen".length(), "fourteen".length(),
        "fifteen".length(), "sixteen".length(), "seventeen".length(), "eighteen".length(), "nineteen".length()};
    public static int tensArray_[] = {error, error, "twenty".length(), "thirty".length(), "forty".length(), "fifty".length(),
        "sixty".length(), "seventy".length(), "eighty".length(), "ninety".length()};
    public static int and_ = "And".length();
    public static int hundred_ = "Hundred".length();
    public static int thousand_ = "Thousand".length();

    public static int giveMeInt(int num)
    {
        int total = 0;
        int units = num % 10;
        num /= 10;
        int tens = num % 10;
        num /= 10;
        int hundreds = num % 10;
        num /= 10;
        int thousands = num % 10;

        if (thousands > 0)
        {
            total+=from0to19_[thousands];
            total+=thousand_;
        }

        if (hundreds > 0)
        {
            total+=from0to19_[hundreds];
            total+=hundred_;

            if (tens > 0 || units > 0)
                total+=and_;
        }

        if (tens > 1)
            total+=tensArray_[tens];
        else
            units += 10 * tens; // hack to move tens in units

        if (units > 0) {
            total+=from0to19_[units];
        }
        return total;
    }

    public static String[] from0to19 = {"Error", "one", "two", "three", "four", "five", "six",
        "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen", "fourteen",
        "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
    public static String[] tensArray = {"Error", "Error2", "twenty", "thirty", "forty", "fifty",
        "sixty", "seventy", "eighty", "ninety"};
    public static String and = "And";
    public static String hundred = "Hundred";
    public static String thousand = "Thousand";


    public static String giveMeString(int num){
        // Using StringBuilder to make up the number
        StringBuilder sb = new StringBuilder();
        int units = num % 10;
        num /= 10;
        int tens = num % 10;
        num /= 10;
        int hundreds = num % 10;
        num /= 10;
        int thousands = num % 10;

        if (thousands > 0)
        {
            sb.append(from0to19[thousands]);
            sb.append(thousand);
        }

        if (hundreds > 0)
        {
            sb.append(from0to19[hundreds]);
            sb.append(hundred);

            if (tens > 0 || units > 0)
                sb.append(and);
        }

        if (tens > 1)
            sb.append(tensArray[tens]);
        else
            units += 10 * tens; // hack to move tens in units

        if (units > 0) {
            sb.append(from0to19[units]);
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        System.out.println("BEGIN");
        int totalChars = 0;
        for(int i=1; i<=1000; i++){
            System.out.println(i);
            String number = giveMeString(i);
            System.out.println(number);
            assert (number.length() == giveMeInt(i));
            totalChars += number.length();
        }
        System.out.println("The total length is : " + totalChars);
    }
}

Real optimisation

As explained by Pimgd's answer, once you have a proper solution, it could be a nice idea to group number with similar prefixes in order to compute the length of the prefixes once and to multiply it by the number of times it occurs.

Answer 3

If you don't want to calculate the total number of letters for different upper bounds then you can calculate the:

• sum for the numbers 1 .. 9
• sum for the numbers 10 .. 19
• sum for the tens in 20 .. 90
• use those pre-calculated values to calculate the sum for the numbers 1 .. 99
• use all of the above to calculate the sum for the numbers 1 .. 999
• then just add the number of letters in "OneThousand".

Like this:

public class ProjectEuler017_SumLettersInNumbers {
    public static void main( String[] args ){
        int sum = 0;
        for ( final String word : new String[]{ "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" } )
            sum += word.length();
        final int letters1To9 = sum;

        sum = 0;
        for ( final String word : new String[]{ "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" } )
            sum += word.length();
        final int letters10To19 = sum;

        sum = 0;
        for ( final String word : new String[]{ "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" } )
            sum += word.length();
        final int lettersTens = sum;

        final int letters1To99 = 9 * letters1To9 + letters10To19 + 10*lettersTens;

        System.out.println(
            10*letters1To99
            + 100*letters1To9
            + 900 * "Hundred".length()
            + 891 * "And".length()
            + "One".length()
            + "Thousand".length()
        );
    }
}

Answer 4

At the risk of complicating this coding project by reorienting toward the real world, and recognizing that I can't find a definitive source for the grammar rule, I would note that I never use "and" in writing numerals in American English.

e.g. One hundred twenty-three thousand, three hundred fifty-seven (123,357) instead of one hundred and twenty-three thousand, three hundred and fifty-seven.

This does impact the number of letters required.

I did a little more checking about the grammar rule and have determined that a cultural variation exists, according to the GrammarGirl's website: http://www.quickanddirtytips.com/education/grammar/it-two-thousand-and-ten-or-two-thousand-ten The variation is between British vs American English.

I don't have the privileges to make this merely a comment, delete for non-answer if you wish.