The Software Engineering Process with an example

September 03, 2020

How to solve a software problem the "Software Engineer" way.

  1. Understand the problem
  2. Break it down into smaller problems
  3. Pseudo Code and run test cases in pseudo code
  4. Think about the output of the function and Code it
  5. Test Code
  6. Try to find a simpler, more elegant, or clever way to solve the problem

It takes practice to actually follow these steps. Specially when it seems most problems are solvable in your head.

But that could be a problem, you will encounter problems you cannot solve in your head (at least if you are challenging yourself), and having a process to solve them will prevent you from feeling inadequate and gain confidence.

Here is a relatively simple problem. It prompted me to write this article because when I started trying to solve it, I was taking too long. It's ok to take long as long as every time you take a step, you can quickly judge you are making progress. But this problem was taking too long because I was constantly getting stuck on the basics, I could not follow my code, I was getting lost, I frequently had to start from the beginning to try to make sense of what I was doing.

And this is the red flag. When you get lost despite making multiple attempts.

It's OK to be rusty at the fundamentals, but you can overcome that easily. Just look up a function reference, or review a formula derivation, etc. That's easy.

Getting lost means you are not following a series of simple steps. Then you end up with spaggetti code that you cannot even make sense of.

Here is the problem

Write a function that returns all the combinations by choosing k numbers from a series of numbers.

Understand the Problem

This is basically nCk if you ever took probability in school.

n=number of items C=choose k=number of items to choose

But in this case we are not just finding out how many combinations there are, we are listing the combinations.

Break it down

Easy cases:

Choosing 0 should return only one combination, an empty combination.

Given the series [1,2,3,4,5,6] choose 1,

I expect six combinations,

The cobinations are:

1,

2,

3,

4,

5,

6,

Given the series [1,2,3,4,5,6] choose 6,

I expect 1 combination,

The combination is: 1,2,3,4,5,6

Choosing more than there items available will return null to signify not possible.

Regular case:

How to build all the combinations for say [1,2,3,4,5,6] choose 3.

Well let's make the problem simpler by starting with [1,2,3,4,5,6] choose 2

I would start with the [1, and each of the other numbers], so:

[1,2] is one combination,

[1,3] is another,

[1,4]

... and so on.

So to solve [1,2,3,4,5,6] choose 2, I solved [1, choose 1 from the remaining].

Now back to choosing 3 from [1,2,3,4,5,6] but with what we just found out.

[1,2,3,4,5,6] choose 3 can be seen as, 1 [2,3,4,5,6] choose 2 which can be seen as, 1,2 [3,4,5,6] choose 1

1,2,3

1,2,4

1,2,5

1,2,6

OK, but those are not all the combinations, what about combinations that start with 2 but not including 1 since we already listed those?

2 [3,4,5,6] choose 2

2,3 [4,5,6] choose 1

2,3,4

2,3,5

2,3,6

Ah! it works, so next starting with 3 but not including 1, or 2.

3 [4,5,6] choose 2

3,4 [5,6] choose 1

3,4,5

3,4,6

Woot woot!

Now starting with 4 but not including 1, 2, or 3.

4, [5,6] choose 2

4,5,6

Stop because the next step would be 5,[6] choose 2, but cannot do that, meaning 5 cannot be combined with two more numbers because we only have the number 6 remaining.

Pseudo Code

OK so I solved one example by hand, now I need to pseudo code.

I'll need a function called combinations that takes an array $nums, which is the list of numbers, and a number $k which is the number of items to choose.

combinations(Array $nums, Int $k)

Output

What will the output of this function look like?

array[
  array[1,2],
  array[1,3],
  ...
]

So far then I have:

combinations(Array $nums, Int $k):Array

Since I see the same function being used again so solve a "sub problem," this hints me to use recursion.

combinations(Array $nums, Int $k):Array{

1. Handle cas $k=0. return [[]];
2. Handle case $k>count($nums). return null
3. Handle case $k=1 return [[1],[2],[3],[4],[5],[6]]
4. Handle case $k=count($nums), return [[1,2,3,4,5,6]]
5. Handle all other cases
   For each $nums as $num
       For each combinations( $nums without first element, $k-1)
           Save the combination $num, sub_combination
   Return all combinations
}

I'm writing a rushed pseudo code. Something that I just use as reference when writing the real code. This is not the kind of pseudo code I would write to explain it to someone so they can understand it and then go home and write their code.

Code


<?php
function combinations(Array $nums, Int $k):Array{
    $combinations=[];

    if($k==0){
        //Choosing none
        return [[]];
    }
    else if($k<1){
        //Choosing more than available
        return null;
    }
    else if($k==1){
        //Choosing one, just return each number as a combination
        foreach($nums as $n){
            $combinations[]=[$n];
        }
    }
    else if($k==count($nums)) {
        //Choosing all, just return one combination which is all numbers
        $combinations[]=$nums;
    }
    else{
        foreach($nums as $i=>$n){
            if($i==count($nums)-$k+1){
                break;
            }
            foreach( combinations( array_slice($nums, $i+1), $k-1) as $sub_combination){
                $combination=[];
                $combination[]=$n;
                $combinations[]=array_merge($combination, $sub_combination);
            }
        }
    }

    return $combinations;
}
?>

Tests

OK some of the testing happened while writing the code. A few var_dumps here and there to test the code at certain milestones.

For example:

$nums = [1,2,3,4,5,6];
var_dump( combinations($nums, 10) );
var_dump( combinations($nums, 1) );
var_dump( combinations($nums, 6) );

One thing I found myself doing is opening a Combinations calculator I found online and making sure the number of combinations returned by my function matched with the calculator.

So when it came to testing this function, I decided to employ PHPUnit so I can make assertions.

I coded a function called nCk(Array $nums, $k) that returns the number of combinations.

Since this is a small problem, using I did not use Test Driven Development (TDD) since I was writing the solution faster than I could write test.

But with more complex problems, TDD is the way to go.

BigO Time

Let $n = count($nums).

For $k=1, $k=$n, $k>$n, O(n,k)=Constant.

For 0<$k<count($nums), I have to call combinations()

  • $n-$k times.
  • $k-1 times for each items in $nums

O(n, k) = (n-k)(k-1)

Optimization

Thinking of a more clever way to do this.

At this point I'm not sure a better way is necessary.

Just to save more lines of code is not really motivating.

Improving O(n,k) is.

I'll have to come back to this problem.

Maybe explore a procedural solution without recursion.