Let’s imagine a beginner programmer, who have learned a programming language basics, can write programs and can read someone else’s programs. Now, for any somewhat non-trivial problem, they have trouble coming up with a solution. And if they read one of the possible solutions, they will understand it and conclude: “I understand how this program works, but I don’t know how to get there.”. If that sounds like you, my dear reader, or someone you would like to coach or teach, then come and learn Iterative Divide & Conquer problem-solving technique.
English Numbers Kata
Given an integer number in the range of -999 999 999
to 999 999 999
, write a program, that will output that number in English words.
Example:
Given number 37545
, the program outputs thirty-seven thousands five hundred forty-five
.
I can solve that!
If you are confident, that you are able to solve that problem, my congratulations, you have problem-solving skill at a necessary level!
If you still feel, that you can solve this Kata easily, although there are more complex problems that give you troubles, then, probably, your problem-solving strategy is not scalable. The technique described in this article is scalable.
Let’s dive in
NOTE: this article uses pseudo-code, that doesn’t belong to any programming language, so it makes sense for you, my reader, to implement this step-by-step in the programming language you know.
OK. Let’s imagine, that you don’t know how to solve the whole English Numbers Kata and you don’t even know where to start.
Now, let’s try to solve much simpler problem:
Given an integer number in the range of 0
to 9
, write a program that will output that number in English words.
Can you solve that? I am pretty sure you can. And easily at that.
Let’s write down some of our possible inputs and corresponding outputs:
1 2 3 4 |
|
If we run that program, we will get an error, that english_number
function is not defined yet. Let’s define it:
1 2 3 |
|
Now if we run our program, we will get four empty lines on the screen as expected. Easiest implementation of english_number
function would probably look like that:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
If we run our program, then we will get our expected output:
1 2 3 4 |
|
If you already know arrays and access array by index, english_number
can be simplified greatly:
1 2 3 4 5 6 |
|
After making this change, let’s run the program, we should see the same output:
1 2 3 4 |
|
OK. Seems like we have solved our current problem at hand. What about the initial problem? How do we get there?
Increase size of the problem slightly
Or as you would say in real-world programming: Add a new requirement.
Our initial problem has only two axes, where we can add requirements to our current solution to move it towards final solution:
- increase the supported range
- allow negative integers
Let’s go with latter, it seems easier. First we write down our possible inputs and outputs:
1 2 3 4 5 |
|
Now, implement english_integer
as a simple call to english_number
(that will make half of our inputs produce correct output):
1 2 3 |
|
Depending on what your programming language this can:
- output partly incorrect data (for negative values)
- fail at run time
- fail at compile time
We can fix that by handling the case of negative numbers:
1 2 3 4 5 |
|
That might be confusing at first. Especially, part, where we call english_integer
from the body of the same function. Let’s draw a diagram on how that function works:
If we were to unwind this diagram into possible paths, we would end up with two possible cases:
- When
number < 0
:english_integer(number)
if (number < 0)
- YESenglish_integer(-number)
if (number < 0)
- NOenglish_number(number)
- prepend result of last call with
minus
- and return it
- When
number >= 0
:english_integer(number)
if (number < 0)
- NOenglish_number(number)
- return result of last call
Running this program results in expected output:
1 2 3 4 5 |
|
Implementation of english_integer(number)
function can be simplified by eliminating else
clause and treating number < 0
as an edge case and using “guard clause” to handle it:
1 2 3 4 5 |
|
If we run our program, the output should be the same as before.
Add more requirements!
Now, that we are done with handling a negative case, we have only one requirement axis left: range of integers. Currently, we support integers from -9
to 9
. Now let’s extend support for integers from 10
to 19
. This problem should be as trivial as the problem for the range of 0...9
.
Our inputs with corresponding outputs:
1 2 3 4 5 |
|
And the implementation to make the output of the program correct (very similar to english_number
function):
1 2 3 4 5 6 7 8 9 |
|
Now we want to glue our current solution with english_teen_number
to add support for range 10..19
. This sounds like another if .. else
case handling:
- when
number < 10
, useenglish_number
- when
number >= 10
, useenglish_teen_number
Let’s change our input/output pairs for english_integer
function:
1 2 3 4 5 6 7 8 |
|
That should fail in some way (compile error, runtime error or incorrect output). Now it is time to implement missing functionality for last 3 examples in our english_integer
function. Replace the last call to english_number
with:
1 2 3 4 5 |
|
If we run the program, we should see correct output:
1 2 3 4 5 6 7 8 |
|
What about negative numbers in the range of -19...-10
? Let’s add input/output examples and see what happens if we run the program:
1 2 3 |
|
And the output if we run the program:
1 2 3 |
|
Yes, it works already thanks to the guard statement that we have at the top of english_integer
function. And the whole function body:
1 2 3 4 5 6 7 8 9 |
|
Going further!
Next smallest requirement seems to be an addition of the range 20...99
. Let’s write down our example inputs and outputs:
1 2 3 4 5 |
|
So how do we solve this problem? Can we follow the same pattern as before, for ranges 0...9
and 10...19
?
We certainly do. We create a constant INTEGERS_IN_TENS = [...]
, where [...]
will contain 79 (mostly two-word) strings. It seems like an excess effort to me. So can we do better?
Yes! We can apply the same problem-solving technique here. What is the smallest problem, that we can solve here easily and independently from other problems?
What about solving the problem only for numbers 20
, 30
, 40
, …, 90
? Sounds simple enough! Let’s write our example input/outputs:
1 2 3 4 |
|
This is no longer different from ranges 0...9
and 10...19
. The only detail is that we need to find a way to convert range 20...90
to 0...7
to be able to access the array by that index. This can be done in 2 steps:
- obtain the first digit of the number:
number / 10
, which results in the range2...9
, - and shift resulting digit by
-2
:number / 10 - 2
, which results in the range0...7
,
exactly, what we expect. Now, we can implement english_ten
similarly to english_number
and english_teen_number
:
1 2 3 4 5 6 |
|
Now it is time to return to the original requirement: support range 20...99
. Looking at our example input/outputs for a function english_integer_in_tens
, we can conclude, that we have 2 different cases:
- When second digit is 0 (
number % 10 == 0
):- we output only
twenty
,thirty
, …,ninety
, depending on the first digit of thenumber
; - by the way, this is exactly, what
english_ten
function is doing. Great!
- we output only
- When the second digit is not 0:
- we output
twenty
,thirty
, …,ninety
, depending on the first digit of thenumber
; - and we output a hyphen character:
-
; - and we output
one
,two
, …,nine
, depending on the second digit; - by the way, latter is exactly, what
english_number
function is doing. Great!
- we output
So, let’s implement that in english_integer_in_tens
:
1 2 3 4 5 6 7 8 9 |
|
Running the program will produce the expected output:
1 2 3 4 5 |
|
Now we should glue the solution for range 20...99
with our main solution, that currently supports only -19...19
. As always, start with example input/outputs:
1 2 3 |
|
This results in incorrect output or failure. How can we merge two solutions together now? Let’s remember our current main solution’s different cases:
- Guard
number < 0
, that prepends “minus ” and makes number non-negative. - When
number < 10
, useenglish_number
. - Otherwise, use
english_teen_number
.
Seems, like first two cases should not be touched and we are interested in the last one. We should split it in two:
- Otherwise:
- When
number < 20
, useenglish_teen_number
. - Otherwise, use
english_integer_in_tens
.
- When
I believe, we are done and can implement merged version:
1 2 3 4 5 6 7 8 9 10 11 |
|
Running the program confirms that our new solution now supports integers in the range -99...99
.
Final solution
I’m leaving the final solution as an exercise for you, my dear reader. There is nothing more to this technique. Careful application of this technique and careful choice of smallest baby-steps as new requirements to your current solution will get you there - to the final solution, that supports the range of -999 999 999...999 999 999
.
If you have any troubles, don’t hesitate to share your questions, ideas and code with me. I will try my best to help you, my dear reader. I am reachable via Twitter by handle @tdd_fellow.
Challenge
Extend solution to support floating-point numbers to a precision level of 6 digits after the dot.
Thank you for reading!
Final note: did you notice, how tedious it is to check, that output of all these print
-s is correct, each time you run the program? This can and should be automated! Stay tuned, I am going to publish an article on how to easily automate these checks really soon!
Next issue is out: Automating Manual Checks or How to Save Time and Get Rapid Feedback!