Two Problem Solving Approaches

Ralf Westphal

Solving a problem can be hard at times. What I’ve found helpful then is to distinguish between two different approaches to tackle the problem. Without distinguishing them I’m prone to use an unsuitable approach and make things harder than they actually are.

Here’s a sample problem:

Write a bash/console program to convert roman numbers entered by the user into decimal numbers. The user can enter one or more roman numbers separated by commas. After a conversion is done the user is prompted for more numbers. The user can exit the program by entering an empty string.

To implement a solution might take you from 20 minutes up to 1 or two hours. So I’d say this is not a trivial problem. It’s worth a systematic approach.

How can you attack this problem? How to make it easier for you? Considerable logic has to be written to create the required behaviour. You won’t be able to just write it down from the top of your head. At least most developers I know won’t be able to pull off such a feat.

Problem decomposition I: Partition

The first approach I usually take is to partition the problem. A problem partition is a problem within the original problem in the form of a puzzle piece or a processing step. Partial problems are complementary.

A definition that works well for me is:

If you decompose a problem into n partial problems the user will not be satisfied before all n partial problems have been solved.

With regard to the sample problems I’d identify the following very quickly as partial problems:

  • P1. Ask the user for the next batch of roman numbers.
  • P2. Parse the string of roman numbers into individual numbers.
  • P3. Convert each individual roman number into a decimal number.
  • P4. Convert all roman numbers into decimal numbers
  • P5. Display all decimal numbers.

Implementing just a solution for even partial problem no. S3 - which seems to be at the domain heart of the overall problem - would not make the customer very happy. Provided he could check the correctness of your implementation he/she would be able to provide feedback and maybe even pay you some money. But the partial solution would be useless to him/her. No way to put it into the hand of users.

The same is true for implementing a solution to partial problem no. 1. Great, the user can enter some text - but nothing would be done with it. Again, feedback could be given, but the partial solution would be of no use.

Partial problems are by definition smaller, easier to solve then the whole problem. Hence looking for them is very helpful.

You can even repeat the decomposition into partial problems. Partial problems mostly form a hierarchy. For example partial problem no. 3 could be decomposed into:

  • P3. Convert each individual roman number into a decimal number.
    • P3.1. Map the roman digits in a roman number to their decimal values, e.g. „XVI“ -> [10, 5, 1].
    • P3.2 Add those values up to produce a result, e.g. [10, 5, 1] -> 16.
    • P3.3 If needed apply the subtraction rule to the values before they get added, e.g. [10, 1, 5] -> [10, -1, 5].

You see: partial problems can get very small, which means easy to implement. Once you found the above partial problems for the parent problem no. 3 roman to decimal conversion should be a piece of cake.

Problem decomposition II: Simplify

The other approach to breaking up a large problem into smaller ones is to identify simplifications. Simple problems are sub-problems. They are, so to speak, embedded in the large problem.

If you decompose a problem into n sub-problems the user might be satisfied with less than n solved sub-problems.

Sub-problems are real increments. You can serve sub-problem solutions to the customer until he/she says stop. And each solution will increase his/her satisfaction. Even with the first sub-problem he/she might start putting it at the fingertips of users to make their life easier. That’s markedly different from partial problems!

Here’s a list of sub-problems I’d identify in the example problem:

  • S1. Convert one roman number only once.
  • S2. Convert several roman numbers only once.
  • S3. Convert several roman numbers multiple times.
  • S4. Convert roman numbers with just one roman digit (e.g. „I“, „V“).
  • S5. Convert roman numbers with multiple roman digits with just decreasing/equal value (e.g. „III“, „XVI“).
  • S6. Convert roman numbers with multiple roman digits even if a smaller value precedes a larger (e.g. „IV“, „MCMLXXXIV“).

Even if just a single roman number with a single digit could be converted that would provide some value to some users.

You see how sub-problem no. S4 is not only smaller than no. S6, but also a part of it. No. S6 is based on no. S4 to be solved. Sub-problems form a hierarchy of nested problems with upper ones building on lower ones:

  • S3(S2(S1))
  • S6(S5(S4))

In this case please also note how both hierarchies are orthogonal. They span a problem space where you could, for example, pick to solve (S1,S4) or (S3,S1) etc.

Mixing problem decomposition approaches

If you detect multiple dimensions in your sub-problems that’s a symptom of mixed decomposition approaches. The two hierarchies of subproblems belong to the partial problems (P1,P2,P4,P5) and P3 respectively. Deciding to go for (S1,S4) would lead to a solution which also attacks ((P1,P5), P3). No need to implement a solution to P2 or P4 since there are just single roman numbers to process.

My experience is that both decomposition approaches are needed all the time in software development. In fact, I guess, you’re already applying them intuitively. Doing it more consciously will make difficult things easier for you, though, I hope.

What I have found useful is to start with 1) partitioning a problem and then 2) simplifying the partitions. And then: 3) rinse and repeat. I constantly mix the approaches. If I don’t make progress one way I try the other.

And here’s an insight I gained since I’ve started to distinguish these approaches: TDD seems to be geared towards solving problems by simplification. Look at the TDD examples out there and check how they progress incrementally by solving sub-problems. TDD works its way up the sub-problem hierarchy.

This has an implication, I think: TDD works best with problems you are able to decompose into sub-problems in the first place. Code katas like „From Roman“ or „FizzBuzz“ or „Bowling Kata“ are examples of that.

But how do you know what kind of problem you are facing? What to do when in doubt? For me it’s simple: As I said, I always (at least mostly) start by looking for partial problems. The risk of blocking myself by underestimating the difficulty of decomposing into sub-problems is too big.

And this shows in my code. Both approaches differ in how I implement the solutions to the decompositions:

  • Solutions to sub-problems manifest themselves as logic.
  • Solutions to partial-problems manifest themselves as functions and modules.

I’m happy to report that this also leads to cleaner code right from the start. Ever since I started to look closer how to solve a problem best and use different implementation approaches, the need for refactoring dropped dramatically.

Image source: pixaby