Learning to Solve Programming Problems Efficiently with PEDAC
Lately, I have been pairing programming with fellow software engineering students at Launch School as we prepare to take an interview assessment on our problem-solving process (for fellow LS students, I’m referring to the RB119 Interview Assessment). Launch School teaches a method they call PEDAC for working through a problem logically and building an algorithm before writing the code. (You may read about it here, and watch an introduction here.)
The PEDAC process is immensely helpful. However, many students new to solving problems with PEDAC end up with an overly complicated solution. This article seeks to demonstrate why this happens and how to use PEDAC more effectively. If you are short on time, skip down to the ‘Strategy Questions for Optimizing PEDAC’ section.
The Problem
Consider the following problem which I modified from a problem shared with me by a fellow student, and which I believe is originally from CodeWars:
Write a method that takes a pair of integers as arguments, x and y. Remove y digits of x without reordering the digits of x such that you get the smallest possible value z, and return z.
Examples:
shrink(1358210, 1) => 135210
shrink(1358210, 2) => 13210
shrink(1358210, 3) => 1210
shrink(1358210, 4) => 110
shrink(135089, 1) => 13089
shrink(135089, 2) => 1089
shrink(135089, 3) => 89
shrink(135089, 4) => 8
Here is one way to solve this problem using PEDAC, but as you will see, it is not optimized:
EXAMPLE OF PROCESS WITHOUT OPTIMIZATION
PROBLEM
We rewrite the problem in our own words:
Our method will take two integers, and remove the second integer number of digits from the first integer such that the resulting integer has the smallest possible value.
We consider the assumptions and rules gleaned from the problem and provided test cases:
- all inputs are positive integers,
- none start with a 0, and
- there will always be at least 1 more digit in the first integer than the value of the second integer.
Next, we walk through the provided examples trying to understand how our method should solve the problem:
shrink(1358210, 1) => 135210
We notice that the largest digit was removed. We look at the next three and confirm that the largest digit is removed each time:
shrink(1358210, 2) => 13210
shrink(1358210, 3) => 1210
shrink(1358210, 4) => 110
However, the next set does not follow the same rule:
shrink(135089, 1) => 13089
The 5
is removed, not the 9
! Why is that? We then think about the numbers as a series of digits whose individual value is somehow related to the values of the digits immediately preceding and following. There are only three possible relations: greater than, equal to, or less than. We look at the rest of the test cases:
shrink(135089, 2) => 1089
shrink(135089, 3) => 89
shrink(135089, 4) => 8
We discover that the number removed is always the leftmost digit preceding a digit smaller than itself. We describe it thus: ‘Find the first dip, and remove the number to the left of the dip.’
Satisfied that we have gleaned what we can from the test cases, we move on to the next step, coming up with the appropriate data structures.
DATA
Our input is a pair of integers.
Our output is an integer.
We don’t need any other data structures for this problem, so we move on to our algorithm.
ALGORITHM
At a high level, we need to:
- find the index of the dip
- remove the preceding digit
- if there is no dip, remove the last digit (it will be the largest value)
- repeat as many times as is specified by the second input integer
- convert array to integer and return
With more detail:
Find the index of the dip:
- convert the first input integer to a string and save it as a variable
str_integers
- convert the string into an array of characters and save it as a variable
arr_integers
- iterate over each character with its index (starting at the second entry if two or more entries) and see if it is smaller than the previous digit.
Remove the preceding digit:
- delete the previous digit using its index
If there is no dip:
- remove the last digit
Repeat as many times as is specified by the second input integer:
- create an outer loop to hold each iteration
- set counter to the second input integer before the outer loop
- deduct 1 from the counter at the end of each iteration
- break if counter = 0
Convert array to integer and return:
- join array elements as one string
- convert string to integer
- return integer
Satisfied that our algorithm is complete, we move on to code the solution:
CODE
We write the code following our algorithm, but the process is not smooth. We have to go back and add a couple of things to our algorithm above, like what to do if there is no dip, then we test the code, get a couple of errors, fix the code, and eventually end up with the following functional method which passes all the tests:
def shrink(int, num_remove)
str_int = int.to_s
arr_int = str_int.chars
counter = num_remove
loop do
arr_int.each_with_index do |num, idx|
next if idx == 0
if num < arr_int[idx-1]
arr_int.delete_at(idx-1)
break
elsif idx == arr_int.count - 1
arr_int.delete_at(idx)
break
end
end
counter -= 1
break if counter < 1
end
arr_int.join.to_i
end
#test cases
p shrink(1358210, 1) == 135210 # => true
p shrink(1358210, 2) == 13210 # => true
p shrink(1358210, 3) == 1210 # => true
p shrink(1358210, 4) == 110 # => true
p shrink(135089, 1) == 13089 # => true
p shrink(135089, 2) == 1089 # => true
p shrink(135089, 3) == 89 # => true
p shrink(135089, 4) == 8 # => true
The process worked, but this was not an optimal process. Because our program first looked for the ‘dip’, we identified the index of the element following the element we needed to delete. This resulted in needing to add code to account for the first and last digits and it made deleting the correct element more complicated since we were not deleting the currently selected element.
EXAMPLE OPTIMIZED — A BETTER ALGORITHM
Here is the same problem solved again. But this time the process is more direct. As you read it, see if you can pick up on the subtle differences in the choices made this time, and how they help us find a better solution faster.
At a high level, we need to:
- find the first digit which is followed by a smaller digit or that is the last digit
- delete the digit
- repeat as many times as is specified by the second input integer
- return the integer
With more detail:
Find the first digit which is followed by nil or a smaller digit:
- convert the first input integer to an array of characters and save as a variable
arr_integers
- iterate over each character with its index and see if the following digit is smaller or if this is the last digit.
Delete the digit:
- delete the digit
Repeat as many times as is specified by the second input integer:
- create a loop to run second integer times and place find and delete logic in the loop
Return the integer:
- convert
arr_integers
to integer
CODE
def shrink(int, num_remove)
arr_int = int.to_s.chars
num_remove.times do
arr_int.each_with_index do |num, idx|
if idx == arr_int.count - 1 || num > arr_int[idx+1]
arr_int.delete_at(idx)
break
end
end
end
arr_int.join.to_i
end
This code passed all the test cases, but it was easier to write, less complicated to debug, and took less time to write than the previous code. Did you catch any of the differences in the process? It followed a more direct route from input to output. So, how can we learn to write our algorithms and code more succinctly? I believe asking strategic questions throughout the PEDAC process can help us make choices that will result in tighter code.
Strategy Questions for Optimizing PEDAC
When we first learn to use a method for breaking down a problem and finding a solution, we tend to come up with the first solution that takes shape from our process. We may be so eager to get to a solution that we bypass opportunities to develop an optimized solution. When we make decisions about our solution while we are still breaking down the problem, we often make decisions that lead to complicated solutions. Instead, we must trust the process and take one step at a time. But we can do even better than that! By learning to ask strategy questions with each step of the process, we can make better decisions ultimately saving us time and trouble.
The best strategy generally takes the most direct and clearest approach from input to output. After all, the shorter and clearer the path, the less that can go wrong. Here are some strategy questions to ask at each part of the PEDAC process:
Problem Stage:
- What needs to happen to the input to get to the output?
- What edge cases need to be considered when choosing the best strategy?
Example Stage:
- Is there a path from input to output that takes care of the most complex examples?
- Can we write an algorithm that solves the edge cases without additional logic?
Algorithm Stage:
- What forms do the input and output take?
- What is the shortest path from input to output?
- What is the least information the computer needs to convert from input to output?
- What is the simplest data structure for holding the data necessary for converting the input to the output?
- Am I selecting or iterating over the object directly in the path between the input and the output?
Code:
- Can I combine some steps from the algorithm into a single line or method (e.g. chaining methods)?
- Are there common methods available in this language that can simplify the implementation of our algorithm (e.g. using `map` instead of `loop`)?
- Are we needlessly creating information or collections (if so, go back and simplify our algorithm)?
CONCLUSION
Hopefully thinking through these strategy questions has been helpful. Let me know in the comments below if you have additional strategy questions to add or suggestions for making this process even more efficient.