Teaser Image

qnoid

Markos Charatzas - London, UK




public final class Wording
    {
        private final Map<Integer, String> wordings;
        
        public Wording(Map<Integer, String> wordings)
        {
            this.wordings = wordings;
        }
        
        public String of(int number){
        return this.of(number, 10);
        }

        private String of(int number, int mod) 
        {
            if(number == 0)
                return "";
            
            int value = number % mod;

            /*
             * if there is no value for a digit skip to the next mod.
             * e.g.  
             * missing units
             *  120 % 10 = 0
             *  
             * missing tens
             *  100 % 100 = 0 //missing tens
             */
            if(value == 0) {
            return this.of(number, mod * 10);
            }
            
            StringBuilder sb = new StringBuilder();

            String wording = this.wordings.get(value);
            
            sb.append( wording );
            
            int remaining = number - value;

            String stringOf = this.of(remaining, mod * 10);
        
            sb.insert(0, stringOf);
            
        return sb.toString();
        }
    }


    public class WordingTest 
    {
        public static final Map<Integer, String> wordings = 
            new HashMap<Integer, String>()
            {
                {
                    this.put(7, "seven");                   
                    this.put(20, "twenty");
                    this.put(100, "onehundred");
                }
            };

        private void assertOf(String name, int number) 
        {   
            Wording wording = new Wording(wordings);
            
            Assert.assertEquals(name, wording.of(number));
        }

        @Test
        public void stringOfSeven() throws Exception 
        {
            assertOf("seven", 7);
        }

        @Test
        public void stringOfTwentySeven() throws Exception 
        {
            assertOf("twentyseven", 27);
        }

        @Test
        public void stringOfOneHundred() throws Exception 
        {
            assertOf("onehundred", 100);
        }
        
        @Test
        public void stringOfOneHundredTwenty() throws Exception 
        {
            assertOf("onehundredtwenty", 120);
        }
        
        @Test
        public void stringOfOneHundredSeven() throws Exception 
        {
            assertOf("onehundredseven", 107);
        }
        
        @Test
        public void stringOfOneHundredTwentySeven() throws Exception 
        {
            assertOf("onehundredtwentyseven", 127);
        }
    }

Just recently came across this case needing to convert a number to its wording. For example, given the number 27 produce "twentyseven".

One way to tackle this is to dissect the number to its digits one by one, starting by the lower ones.

(0)         2       7
(hundreds)  tens    units

Using a lookup table on units, tens, hundreds will allow us to get the wording for a single number.

    Map<Integer, String> units = new HashMap<Integer, String>();
    units.put(7, "seven");

    Map<Integer, String> tens = new HashMap<Integer, String>();
    tens.put(20, "twenty");

The real question then becomes, what algorithm will give us the number of the right magnitude? In other words, how can we get the units, the tens and the hundreds of a number?

For that we will take advantage of the mod operator with a touch of recursion to traverse the whole number.

First a reminder on the mod. Whenever you mod a number, the value you get back is anywhere within the range of the modulo, starting from 0.

e.g.

27 % 10     =   7   (units)
20 % 100    =   20  (tens)
0  % 1000   =   0   (hundreds)

With that in mind, starting from 10 as the modulo we get the value of the units, thus its wording.

Every time subtracting the current value from the number to be left with the next scale.

27 - 7 = 20

and modding again with the next modulo

mod * 10

until we get a 0 as the number, which is the stop condition.

What about numbers that are missing digits like 100 which will give a 0 as soon as we mod them? Well, there are a couple of ways to go about it.

  • Add a lookup value of an empty string to 0. This although works, breaks the semantics of the lookup.

  • Check for a null and use an empty string instead. In this case you will have the overhead of allocating the StringBuilder and that of the append.

  • Skip to the next mod.

There is however a serious limitation to the above. How do you go on about numbers between 11 ("eleven" and not "tenone") through 19? What about the number 0?

Developers challenge: Implement the above in your preferred language while also coming up with an answer to the above limitation. The first one to write a solution and a test that proves it, gets a postcard from Edinburgh.

How would you improve the algorithm to produce better wordings? Do you have another algorithm to share for figuring out the wording of a number?

As always, you can find the source code of the post over at github.

Kudos to @nelstrom, the person behind Vimcasts.org. Drew recently visitted Egypt and was pleased to find out that numbers are read left to right as opposed to arabic script and figuring out their wording.