Solving Coding Problems With PEDAC
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?
PEDAC stands for “[Understand the] Problem, Examples / Test Cases, Data Structure, Algorithm, and Code.” PEDAC has two primary objectives: process the problem (PEDA) and code with intent (C).
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?
For problems of a certain sophistication, PEDAC saves time. It may seem counter-intuitive that a laborious process like PEDAC can save time, but that’s exactly what it does when the problem is complicated. That’s not to say that going straight to coding is always slower; in fact, it is sometimes faster for simple problems. However, the more complex the problem, the more likely that going straight to coding will lead to what we call “hack and slash” coding, a derogatory term used to describe code written without intent or context. Hack and slash coding often fails to meet the requirements and handle the edge cases, and produces programs that are hard to understand, maintain, and scale. A disciplined approach, such as PEDAC, helps you identify and avoid the pitfalls you may encounter when you don’t code with intent.
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
Let’s work through PEDAC using an example.
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
It’s tempting to jump into a REPL and type out some code real quick. Resist this temptation. The first critical step of PEDAC is to digest the problem to gain a holistic and well-rounded understanding of what the entire problem is asking. Don’t rush. Read the problem statement carefully; don’t miss any details. In most problem statements, there are no wasted words, so don’t read it like you would a magazine article. Every word and every detail matters. Your brain tends to fill in the gaps if you skip any details, but it may not do so correctly, as demonstrated by the following:
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:
the set of factors
sum of multiples
Unless you’re familiar with the problem domain, there’s also a subtle implicit concept that’s introduced in the problem:
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:
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)
This problem statement also conveys a few rules that we must keep in mind:
- The multiples to be summed must be unique. The number
15is present as a multiple of
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.
- 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.
- All numbers are natural numbers: they are the set of integers greater than or equal to
1(see this definition from mathworld.wolfram.com). Since adding
0to 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
Now that we’ve processed the problem we can determine whether anything needs clarification.
- What are the possible values for the target number? Are negative numbers allowed? Any natural number greater than
0. There will always be a target value.
- How will the factors be provided to the program? As an array.
- What happens if only
5is provided as a factor? Should the program still default to both
5as factors? No. Default to
5only 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
That was a lot, but it was only the first step — the “P” in PEDAC. We’re now ready to move on to the “E”, which stands for “Examples or Test Cases”. In this step, our objective is to come up with examples that validate our understanding of the problem and confirm that we are working in the right direction. The confirmation will typically come from a person or documentation of a process: we can ask the person to confirm the output given the input, or we can follow the process to check the output given the input.
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
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 if
19 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.
We’re now ready to move on to the third step in the PEDAC approach, the “D”. With our test cases ready, the next thing to do is to determine what data structures we will work with to convert the input to the output. The chief considerations here are our intended programming language and our mental model.
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.
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.
This is the last step in PEDAC — the “C”, which stands for “code with intent”. This stage is all about implementing the solution in your language of choice. The major benefit of investing time in the previous steps (the PEDA) is that it reduces the implementation to a simple translation of the algorithm into programming language syntax.
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:
We hope that this demonstration of the PEDAC process has made a case for using it. Though it was on the verbose side of things to give each step ample coverage, this type of verbosity isn’t always needed for every problem. You also don’t need to follow the PEDA sequence strictly. The key ideas are to process the problem so that you come up with an algorithm and then code with intent. It may seem like a lot of work at first, but once you get used to employing it, you’ll be surprised at how fast and effective PEDAC is in assisting your problem solving ability.
- What problems can I solve using PEDAC? PEDAC isn’t well suited for many abstract operations like “designing a UI.” It works well with procedural coding problems since it leads you to a series of steps/instructions that you can follow to produce a deterministic result.
- 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.
- 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.