The Way of the Rubber Duck 2

Programmatic Problem Solving in Action

This is part two of a series on programmatic problem solving. If you haven’t read the first one on the steps for problem solving, you should read that first here. You can also view my github repo on this topic by clicking here. The repo has Jupyter Notebooks for teaching this topic as well a video of me teaching it in a live setting.

Before we get started we have a bit of housekeeping to do. First, we can’t demonstrate problem solving without a problem. So, let’s grab one:

If we list all the natural numbers below 10 that are  multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is  23. Find the sum of all the multiples of 3 or 5 below a given natural number.

We now have a problem but you might think it too simple, that’s ok. This is to make demonstration easier, the techniques for programmatic problem solving work just as well on complicated issues.

Next up, we need a reminder of the steps:

1. Believe you can solve the problem
2. Read the problem for understanding
3. Start with a simple solution and scale up
4. Translate the process of step 3 into pseudocode
5. Translate the pseudocode into code
6. Debug and Refactor
7. Break It
8. Feedback and Practice

Oh, and one last thing, you don’t need to write any code until step 5. Most of the problem solving, the hard part of programming, can be done without code. Problem solving in programming is much more about how you break down the problem than what the syntax is.

Step 1: Believe

This isn’t a terribly complicated step but it matters more than you may think. You need to trust that you have the tools to solve the problem, if you don’t you are likely to give up before you find a solution, especially for the harder problems.

Step 2: Read the Problem

There a couple parts to reading the problem correctly. First, simply explain the problem to yourself, a rubber duck, or someone else in your own words. For our problem we can write it as:

Find all multiples of 3 or 5 below a given positive integer. Find the sum of these numbers.

Now what is the expected input? What would we have to give to our code to kick the whole thing off? We want to give it as much detail as possible, not just that it’s a number.

`n`, a natural number, positive integer. Looking at all numbers BELOW `n`

Do the same with the output. What is the “answer”, the end product?

Positive integer (summing positive ints so no negative) representing the sum of multiples of 3 or 5. Minimum value is 0 (no multiples), max dependent on the size of `n`

Can I break this into smaller problems? If so, do so and solve those first.

Find the Multiples of 3 below a given number - (i % 3 == 0)
Find the Multiples of 5 below a given number - (i % 5 == 0)
Add all those numbers - simple addition

Continue asking questions to tease out information. The more you define upfront, the less likely you are to have issues or solve the wrong problem. Other questions you may ask — Are there any restrictions or considerations I should be aware of? or Have I seen a similar problem, how did I solve that one?

Step 3: Start Small and Scale

Start with the simplest possible situation, what should happen?

n = 1
Answer = 0

What is the next smallest step we can take?

n = 2
Answer = 0

Keep stepping through until the behavior changes.

n = 3
Answer = 0
n = 4
Answer = 3 #First number in our total is 3, which is a multiple of 3

We keep stepping until 4 since we defined above that we only check the numbers below n. Now keep stepping until you’ve seen all the cases that may arise.

n = 5
Answer = 3
n = 6
Answer = 3+5 = 8 # A multiple of 5
...
# What about multiples of 3 and 5? Do we add that number twice?
n = 16
Answer = 3+5+6+9+10+12+15 = 60 # 15, a multiple of 3 and 5

Congratulations, you’ve now solved the problem! Now to start the process of translating what you did in your head into code.

Step 4: Write out the process used in Step 3

This is going to be an iterative process of writing out what you did in your head in a very methodical way. Computers are dumb and only do what you tell them so be very explicit.

So what steps did we take above?

Start a running total at 0
Starting at 1, look at every integer below n
Check if it is a multiple of 3
Check if it is a multiple of 5
If it is a multiple of 3 or 5, add it to a running total
Once you have looked at all integers below n, total is your answer

Now simplify it, and add a bit of that programming structure:

Set a total to 0
Look at numbers in range 1 to n
  Is the current number a multiple of 3 or 5?
  If so, add current number to total
Total is the answer

One last pass with pseudocode, right at the boundary of needing a computer. If you aren’t familiar with pseudocode, it is effectively human readable code. That means syntax that makes it ok for our compiler is dropped in favor of conventions that are easier for a person to read.

total = 0
for i in range 1 to n
  if (i % 3 is 0) or (i % 5 is 0)
    total = total + i
Answer = total

We are officially at the end of what we can do without a computer. Notice how, if our logic is correct, we’ve already solved the problem. A lot of good programming is simply about being clever with the problem solving, so don’t stress over the syntax. Learning the syntax of a language comes with practice and exposure and is only good for that language. Problem solving skills are language independent and much more valuable.

Step 5: Pseudocode to Code

If you did Step 4 correctly, this should be fairly easy. Write workable code based on your pseudocode.

total = 0
for i in range(1, n):
  if i % 3 == 0 or i % 5 == 0:
    total = total + i
print(total)

Step 6: Debug and Refactor

Often times you may have a solution that works in your head but doesn’t work when translated. Make sure your code works!

n = 10 # Added a declaration for `n`, now it should run
total = 0
for i in range(1, n):
  if i % 3 == 0 or i % 5 == 0:
    total = total + i
print(total)

Or maybe it does work but it is code you would be embarrassed to show. This is where you fix that, and make your code DRY. Look for places you repeat or opportunities to make your code more universal, like putting it in a function.

# Make it reusable
def sum_of_multiples_3_5(n):
  total = 0

  for i in range(1, n):
    if ((i%3==0) | (i%5==0)):
      total+=i

  return total
sum_of_multiples_3_5(10)

Keep that cleanup going with a list comprehension and comments:

def sum_of_multiples_3_5(n):
  '''Return sum of all multiples of 3 or 5 below `n`'''
  return sum([i for i in range(1, n)
              if ((i%3==0) | (i%5==0))])
sum_of_multiples_3_5(10)

Many times you will be looking for a computationally effecient solution, in those cases it helps to solve it the slow way first, and then go back and find a faster solution. Sometimes all it takes is to rephrase the problem in a new way or solve the problem in reverse.

Look at a problem from all angles, some of the best solutions are non-linear

# Method with math instead of loops, refactored for efficiency
def sum_of_multi(target, multiple):
  #sum of all multiples up to and including target
  x = target // multiple
  return multiple*(x*(x+1))//2

def sum_of_multiples_3_5(target):
  #adjust target since the problem is non-inclusive
  target = target-1
  return (sum_of_multi(target, 3) +
          sum_of_multi(target, 5) -
          sum_of_multi(target, 15))
sum_of_multiples_3_5(3)

The solution directly above is hinted at if we restate our problem (Step 2) as:

Sum the multiples of 3 below n, repeat for multiples of 5, remove overlapping values and add summations together.

Step 7: Break It

Wait! What?! Why would I break it? Simple, people and computers are both dumb, someone is going to break it so it might as well be you. So, how do we break the code? We look for edge cases, corner cases, and even things no sane person should be doing.

# Some ways that might break our code
1. Non-natural numbers
2. Really big numbers
3. Really small numbers
4. Wrong Data type, string instead of number
5. No value for `n`
6. Extra parameter values

Once you brainstorm how to break it, assess what needs to be addressed. For instance, if this was a simple code challenge it may be the proctor’s decision what you issues you need to patch, but in real life that varies. Is this code being used just by you or are you on a team? Where is the input coming from? Where is the output going? These are just some of the considerations you’ll need to think about when deciding if your code is “good enough.”

Even if you don’t write extra code to fix these potential problems, it still helps to be aware of them so you know where to look if something does go wrong.

8. Feedback, and Practice

This is the step you should most take to heart if you want to become a good programmer. There is no secret sauce to becoming good at something, it boils down to getting feedback and practicing.

Ask for input and critique, how could this have been written better? Too shy or no one around, self-critique and ask the internet — google your problem and see how other people did it.

Practice is the other piece of the puzzle. Do code challenges on the regular. Choose problems that push you into unknown territory. Write code constantly. The more you do, the more you fail, the more you learn, the better you get.

The End — For now…

End of the article but I hope to continue with supporting articles such as breaking down and learning how someone else’s code works, and how to find answers online. If those materialize they will be linked here.