Solving Coding Problems With PEDAC

Launch School
Jan 16, 2018 · 11 min read

This article outlines how to solve programming problems by using Launch School’s PEDAC process. There are many ways to solve coding problems, and PEDAC is but one. The purpose of this article isn’t to proclaim PEDAC as the best or only approach but provide it as one of the tools you can turn to when you begin working on a problem. You may not need PEDAC in every problem, but you’ll find a lot of advantages to employing some system when working on more sophisticated problems. The more complex the coding problem, the more you need a rigorous process like PEDAC. This approach is especially useful for beginners learning to code because many beginners have never been forced to employ a system of thinking before. It’s also a gateway concept for more formal algorithmic techniques to problem solving.

What is PEDAC?

Processing the problem consists of 4 steps that lead you from the initial problem statement to a solid understanding of what is required. The result is the Algorithm, which you will use to implement the solution.

Once you have understood the problem, chosen an appropriate data structure, and have an algorithm to approach the problem, all you need to do is convert the algorithm into the programming language of your choice. We call this final step coding with intent, and the final result is the implementation.

Why Use PEDAC?

Common pitfalls of hack and slash or coding without intent are:

  • Missed requirements
  • Unforeseen Edge Cases
  • Hard to understand code
  • Code that’s difficult to maintain

Example Problem

Suppose you have an arbitrary natural number (the target) and a set of one or more additional natural numbers (the factors). Write a program that computes the sum of all numbers from 1 up to the target number that are also multiples of one of the factors. For instance, if the target is 20, and the factors are 3 and 5, that gives us the list of multiples 3, 5, 6, 9, 10, 12, 15, 18. The sum of these multiples is 78.If no factors are given, use 3 and 5 as the default factors.

Understand the Problem

[Brain] Filling in the Gaps

Let’s first identify the inputs and outputs for our problem. Reading the problem statement, we can see that we have two inputs, and one output:

inputs:
target number
the set of factors
output:
sum of multiples

Unless you’re familiar with the problem domain, there’s also a subtle implicit concept that’s introduced in the problem: multiples.

To make the requirements/terms explicit, we must understand the terms as they apply to the problem domain. These aren’t limited to words you’re unfamiliar with, but also words that have multiple meanings. For instance, “balance” can mean different things depending on whether we use it in an accounting or a supply chain context.

Going back to the term “multiples,” assume that this is a “mathematical term” that means “a number that can be divided by another number without a remainder.” (Normally, you would not want to assume something if you’re unfamiliar with the problem domain but would seek clarification first. Here, we’re the problem giver, so we’re going to confirm that this assumed definition is correct.) Using the example in the second paragraph, we can confirm this:

target number: 
20
multiples of 3:
3, 6, 9, 12, 15, 18 (all have no remainder when divided by 3)
multiples of 5:
5, 10, 15 (all have no remainder when divided by 5)

Implicit Requirements

  1. The multiples to be summed must be unique. The number 15 is present as a multiple of 3 and 5, but we add it just once when computing the sum(3 + 5 + 6 + 9 + 10 + 12 + 15 + 18 = 78). Note that we learn this implicitly from the example: the uniqueness requirement is not stated explicitly.
  2. The target value is the limit, but it is not considered a multiple. In the example, the target, 20, is not included in the sum even though it’s a multiple of 5. As with the first rule, this requirement is implicit.
  3. All numbers are natural numbers: they are the set of integers greater than or equal to 0 or 1 (see this definition from mathworld.wolfram.com). Since adding 0 to any number doesn’t change it, it doesn’t matter which definition we use. For simplicity, we’ll assume that the natural numbers start with 1.

Now that we’ve processed the problem we can determine whether anything needs clarification.

Clarifying Questions

  1. How will the factors be provided to the program? As an array.
  2. What happens if only3 or 5 is provided as a factor? Should the program still default to both 3 and 5as factors? No. Default to 3 and 5 only if no factors are provided.

We now have a thorough understanding of the problem. To help round it off, though, let’s perform an optional processing step and come up with a mental model that describes it.

We can think of the mental model as our summary view of the “entire problem.” In other words, it is our perspective on what the problem requires. Be sure to note that we’re not yet interested in how to solve the problem (the algorithm).

Here’s a simple mental model for this problem:

Determine a list of all multiples of a set of factors up to a target value, then filter the list of multiples to the unique values. Finally, compute and return the sum of the unique multiples.

Here’s another mental model:

Incrementally build a list of numbers that are multiples of a set of one or more factors. Add a multiple to the list only if it is not yet on the list. Finally, compute and return the sum of the numbers on the list.

Note that we came up with two mental models in this example. We did this to highlight that there are multiple perspectives to generate a sound mental model; as a general rule, you don’t need to come up with more than one model as long as it fully and accurately captures the requirements.

Examples / Test Cases

Going back to the example problem, let’s come up with some examples. Our examples will be in the form of tests that show the expected outputs given certain inputs:

Note that we derived our examples from our rules. Those are typically an excellent place to find test cases.

In addition to test cases based on our rules, we should also provide test cases that handle any edge cases we can find. Edge cases are inputs at the “edges” of the problem description that may be mishandled if we aren’t careful. For instance, problems that involve iterating over numbers have edge cases at one or both ends of the range. If you’re not careful, you may get incorrect answers at these edges. Typical edge cases can involve working with negative numbers, the number zero, or extremely high values (if performance is a requirement). When working with collections, it’s normally a good idea to find test cases that deal with zero, one or multiple elements in the collection.

This example problem has one significant edge case: what happens at the last number before the target value is a multiple of one or more of the factors?

In each of our test cases above, the last number added to the sum is either 18 or 15. That leaves 19 (the last value checked) out of the sum, which is the right thing to do. Suppose, though, that 19should be included in the sum, which it should if19 is one of the factors. Since 19 is the last possible number to check (given a target of 20), it’s at the “edge” of the range of values that get summed. To be certain we include 19 in the sum, we need to provide a test case that handles it.

Data Structure

Using either of our mental models, we need to collect the values that are multiples of our factors, and then add them up. An array seems like a good fit for this collection of multiples. The only difference between our models lies in how and when we filter those numbers, but we’ll worry about that later.

One thing to take note of is that the data structure will influence your algorithm. For this reason, we typically pair the “Data Structure” and “Algorithm” steps together.

Algorithm

Our chief objective here is to determine a series of instructions that will transform the input to the desired output. The challenge is to get the right level of detail; we want something that we can readily convert to code without actually writing code.

The reason you don’t want it written at the programming language level is that you will lose flexibility during implementation. Programming languages often provide several ways to achieve a given result, but each of those approaches can affect other parts of the program. If you make an implementation choice too soon by making it part of your algorithm, then later discover you should have chosen something else, you may need to go back and modify both the code and the algorithm. If you don’t address the changes at both levels, you may encounter the pitfalls we discussed earlier.

That said, it is not uncommon to change an algorithm once coding starts; don’t feel constrained to stick with what you’ve initially written. In fact, two individuals working on the same problem will often come up with different algorithms, especially if each individual has formulated different mental models. To demonstrate this, here are the algorithms using both mental models from our example:

Before implementing your algorithm, you should test it manually with your test cases. You don’t need to check all of the test cases, just enough to be confident that the algorithm works.

Let’s try it using the first example from our first mental model:

After verifying that a few of our test cases gives the expected output, it’s time to put our algorithm to code.

Code

Don’t be alarmed if, after doing all the steps above, you still have to circle back to your algorithm. That can and will happen often. After all, you’re human, and you may have missed something. PEDAC, however, aims to minimize those mistakes, so you don’t miss major requirements and even if you are circling back to previous steps, it’s mostly for fine-tuning the approach.

Here’s a Ruby implementation of the algorithm we designed for the first mental model:

Here’s the JavaScript implementation using the algorithm we designed for the second mental model:

Either Ruby or JavaScript would work for both mental models. However, the first model is slightly better suited for Ruby since Ruby has a method for returning unique values in an Array; JavaScript does not.

Summary

FAQ

  1. When should I use PEDAC? Should I use it even if the problem is small? If you don’t have prior experience using a formal problem-solving process then, yes, use it for trivial problems too. Get your mind used to solving problems by following PEDAC. Once you get used to it, it will become part of your “muscle memory,” and you’ll be able to deploy it more naturally on more difficult problems, which is where you will really need it. If your first exposure to PEDAC is on the most difficult problems, then it’ll be hard to get good at using this process.
  2. Can I use PEDAC for developing applications and not just working on solving a coding problem? Yes, but you’ll have some pre-work to do before using it. To effectively use PEDAC, break down the application into smaller requirements. You’ll likely have to compare against previous coding problems you’ve solved if it’s appropriately small for PEDAC. PEDAC can be applied to any problem that has specific inputs and unambiguous outputs, so you’ll have to break down your application until you have specific and unambiguous requirements.

Launch School

Publications of the Launch School Community

Launch School

Written by

Launch School

Publications of the Launch School Community