Julius Seporaitis
on hobbies and work

Bottom Up Problem Solving - Part I

Among the variety of strategies for solving various problems that apply to software engineering are top-down and bottom-up approaches. The top-down approach emphasizes planning and complete understanding of the system, and coding begins only after a sufficient level of detail has been reached in the design of the system. Bottom-up emphasizes coding and early testing but runs the risk that parts of the system may be coded without having a clear idea of how they connect. Top-down is the what and bottom-up is the how.

Both are indispensable tools in a system or product-building toolbelt, both transcend software engineering and go into adjacent areas. There are probably countless books and blog posts written about both already. So what is this post about? I want to use a simple example to show the difference between knowing what to do and how to do it. The first one is usually straightforward to express in words - “a system for …” or “a module to do …”. The second is what makes the first happen, and people just starting in programming, using a new library, or working on a new project may find it very intimidating.

Why do I want to show that difference? Because someone just starting may feel inadequate, looking at some simple exercise, understanding pretty clearly what outcome they want, but feeling frozen without any idea how to get there. The important message I want you to internalize, if you ever find yourself in this situation, is that there is absolutely nothing shameful or noob about starting with a “Hello, World!” application. Every software engineer I know goes through this process. Experience and practice only help with making short-cuts and broader leaps in the process I am about to show you. Sometimes these short-cuts may indeed backfire on the most experienced engineer as the times, tools, and technologies change. But that’s another topic.

Right now, let’s start by concerning ourselves with an exercise that should put us through our paces through this bottom-up process. As it happens, Harvard summer school CS50 course has a problem called Mario - it requires us to implement the following program using more or less only for loops in the C programming language:

Implement a program that prints out a double half-pyramid of a specified height, per the below.

$ ./mario
Height: 4
   #  #
  ##  ##
 ###  ###
####  ####

The first thing to note is that it should be obvious what result is expected. How to do it is a different matter. To put you at ease, I genuinely am not confident that I could write the solution without going through this process in some form first.

Simplify Top-Down

One of my teachers at university was notorious for collecting quirky and challenging maths problems and sharing them with students. He eventually published a little book with a collection of these problems and one thing in the introduction left an impression in my memory. He wrote: if you are genuinely stuck and don’t know how to move towards a solution, do not bang your head against a wall, but look at the problem statement again and see if you can relax some conditions and solve a more straightforward problem. Usually, an insight into how to solve the big one comes more naturally after the simple one is solved. It is not a new idea, but I think it’s worth re-iterating, and it applies brilliantly here.

How does it apply in this case? If the final solution is the “top”, we will try to simplify the original statement multiple times, and in the following section, we will “walk” bottom-up to write the full solution. Let’s begin simplifying.

  1. Implement a program that prints out two squares of a specified height, per the below.

    $ ./mario
    Height: 4
        ####  ####
        ####  ####
        ####  ####
        ####  ####
    

    This simplification identifies that at each line, a certain number of spaces and # symbols are printed in alternating sequence: spaces, #, spaces, #. However, there is no requirement for the pyramid.

  2. Implement a program that prints out one rectangle of a specified height.

    $ ./mario
    Height: 4
    ########
    ########
    ########
    ########
    

    This simplification takes away the spaces and alternation.

  3. Implement a program that prints a line of a specified length.

    $ ./mario
    Height: 4
    ####
    

    This simplification removes the requirement of printing multiple lines.

  4. Implement a program that prints out the specified length.

    $ ./mario
    Height: 4
    4
    

    This change replaces a sequence of symbols with just output.

  5. Implement a program that takes input.

    $ ./mario
    Height: 4
    

    This simplification removes the printing of the input value.

  6. Implement a program that prints “Hello, World!”

    $ ./mario
    Hello, World!
    

    This simplification removes the value input and is the standard starting point of any language.

Implement Bottom-Up

  1. Starting at the “bottom”, the first step is to write a “Hello, World!” application:

    #include <stdio.h>
    
    int main(void) {
      printf("Hello, World!\n");
      return 0;
    }
    

    Assuming the above code is in mario.c file, compile with gcc mario.c -o mario and run ./mario. All subsequent examples will be changes to mario.c, so I will not repeat the compilation instructions.

  2. Implement a program that takes input.

    #include <stdio.h>
    
    int get_int(const char* text) {
      int num = -1;
      do {
        printf("%s", text);
        scanf("%d", &num);
      } while (num < 0 || num > 24);
      return num;
    }
    
    int main(void) {
      int height = get_int("Height: ");
      return 0;
    }
    

    The get_int function does not change from now onwards, so I will omit it from example code and leave // ... comment where the function would be instead.

  3. Implement a program that prints the specified length.

    #include <stdio.h>
    
    // ...
    
    int main(void) {
      int height = get_int("Height: ");
      printf("%d\n", height);
      return 0;
    }
    
  4. Implement a program that prints a line of specified length.

    #include <stdio.h>
    
    // ...
    
    int main(void) {
      int height = get_int("Height: ");
      for (int ii = 0; ii < height; ii++) {
        printf("#");
      }
      printf("\n");
      return 0;
    }
    

    Looking at this loop and knowing the next step is to print a rectangle should already hint that a loop inside a loop is needed.

  5. Implement a program that prints out one rectangle of specified height.

    #include <stdio.h>
    
    // ...
    
    int main(void) {
      int height = get_int("Height: ");
      for (int line = 0; line < height; line++) {
        for (int ii = 0; ii < height; ii++) {  // (1)
          printf("#");
        }
        for (int ii = 0; ii < height; ii++) {  // (2)
          printf("#");
        }
        printf("\n");
      }
      return 0;
    }
    

    There are two inner loops (1 & 2), even though the output is a rectangle, we know that the final result will have to have two halfs, so two loops here will make that easier.

  6. Implement a program that prints out two squares of a specified height, per the below.

    #include <stdio.h>
    
    // ...
    
    int main(void) {
      int height = get_int("Height: ");
      for (int line = 0; line < height; line++) {
        for (int ii = 0; ii < height; ii++) {
          printf(" ");  // (1)
        }
        for (int ii = 0; ii < height; ii++) {
          printf("#");
        }
    
        printf("  ");  // (2)
    
        for (int ii = 0; ii < height; ii++) {
          printf("#");
        }
        printf("\n");
      }
      return 0;
    }
    

    Rectangle is split into two squares by putting two space characters between two loops on each line (2). In addition, this adds spaces before the first square (1). This will help make the pyramid steps in the final step below.

  7. Implement a program that prints out a double half-pyramid of a specified height.

    #include <stdio.h>
    
    // ...
    
    int main(void) {
      int height = get_int("Height: ");
      for (int line = 0; line < height; line++) {
        for (int ii = height - line; ii > 0; ii--) {  // (1)
          printf(" ");
        }
        for (int ii = 0; ii <= line; ii++) {  // (2)
          printf("#");
        }
    
        printf("  ");
    
        for (int ii = 0; ii <= line; ii++) { // (2)
          printf("#");
        }
        printf("\n");
      }
      return 0;
    }
    

    The thing to note here is that the step (#) symbols increase with each line (2). The opposite is true about the space characters in the first sub-loop (1) - their number decreases with each line, relative to the height. Hence, ii = height - line.

By this time - the problem was simplified gradually and solution engineered from the ground up and, hopefully, the difference at each step is easy to follow and understand. For a more convenient medium of trying this code - I have put all of the above code steps in this repository.

If you liked this example and would like to practice something more challenging you might find the post about kilo - an uncomplicated text editor in 1000 lines of code - by Antirez1 enjoyable. It has been turned into a series of short tutorials that anyone who prefers text and code examples can follow, build a text editor, and, most importantly, understand how each step combines into the final application.

It may not seem like much, but this type of problem-solving has a great practical significance in a real software engineering environment, but I will expand on that subject in a follow-up post.


[Footnotes]

  1. Antirez is the author of a wildly popular in-memory key-value storage engine Redis↩︎