# Iterative Divide & Conquer or How to Solve Problems

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:

If we run that program, we will get an error, that `english_number` function is not defined yet. Let’s define it:

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:

If we run our program, then we will get our expected output:

If you already know arrays and access array by index, `english_number` can be simplified greatly:

After making this change, let’s run the program, we should see the same output:

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:

Now, implement `english_integer` as a simple call to `english_number` (that will make half of our inputs produce correct output):

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:

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:

1. When `number < 0`:
• `english_integer(number)`
• `if (number < 0)` - YES
• `english_integer(-number)`
• `if (number < 0)` - NO
• `english_number(number)`
• prepend result of last call with `minus`
• and return it
2. When `number >= 0`:
• `english_integer(number)`
• `if (number < 0)` - NO
• `english_number(number)`
• return result of last call

Running this program results in expected output:

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:

If we run our program, the output should be the same as before.

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:

And the implementation to make the output of the program correct (very similar to `english_number` function):

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`, use `english_number`
• when `number >= 10`, use `english_teen_number`

Let’s change our input/output pairs for `english_integer` function:

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:

If we run the program, we should see correct output:

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:

And the output if we run the program:

Yes, it works already thanks to the guard statement that we have at the top of `english_integer` function. And the whole function body:

### Going further!

Next smallest requirement seems to be an addition of the range `20...99`. Let’s write down our example inputs and outputs:

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:

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:

1. obtain the first digit of the number: `number / 10`, which results in the range `2...9`,
2. and shift resulting digit by `-2`: `number / 10 - 2`, which results in the range `0...7`,

exactly, what we expect. Now, we can implement `english_ten` similarly to `english_number` and `english_teen_number`:

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 the `number`;
• by the way, this is exactly, what `english_ten` function is doing. Great!
• When the second digit is not 0:
• we output `twenty`, `thirty`, …, `ninety`, depending on the first digit of the `number`;
• 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!

So, let’s implement that in `english_integer_in_tens`:

Running the program will produce the expected output:

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:

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`, use `english_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`, use `english_teen_number`.
• Otherwise, use `english_integer_in_tens`.

I believe, we are done and can implement merged version:

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 @waterlink000.

## Challenge

Extend solution to support floating-point numbers to a precision level of 6 digits after the dot.

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!