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.)

Writing Good Code (Photo by Danny Meneses)

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:

1. all inputs are positive integers,
2. none start with a 0, and
3. 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:

1. find the index of the dip
2. remove the preceding digit
3. if there is no dip, remove the last digit (it will be the largest value)
4. repeat as many times as is specified by the second input integer
5. convert array to integer and return

With more detail:

Find the index of the dip:

1. convert the first input integer to a string and save it as a variable str_integers
2. convert the string into an array of characters and save it as a variable arr_integers
3. 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:

1. delete the previous digit using its index

If there is no dip:

1. remove the last digit

Repeat as many times as is specified by the second input integer:

1. create an outer loop to hold each iteration
2. set counter to the second input integer before the outer loop
3. deduct 1 from the counter at the end of each iteration
4. break if counter = 0

Convert array to integer and return:

1. join array elements as one string
2. convert string to integer
3. 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:

1. find the first digit which is followed by a smaller digit or that is the last digit
2. delete the digit
3. repeat as many times as is specified by the second input integer
4. return the integer

With more detail:

Find the first digit which is followed by nil or a smaller digit:

1. convert the first input integer to an array of characters and save as a variable arr_integers
2. 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:

1. delete the digit

Repeat as many times as is specified by the second input integer:

1. create a loop to run second integer times and place find and delete logic in the loop

Return the integer:

1. convert arr_integersto 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:

1. What needs to happen to the input to get to the output?
2. What edge cases need to be considered when choosing the best strategy?

Example Stage:

1. Is there a path from input to output that takes care of the most complex examples?
2. Can we write an algorithm that solves the edge cases without additional logic?

Algorithm Stage:

1. What forms do the input and output take?
2. What is the shortest path from input to output?
3. What is the least information the computer needs to convert from input to output?
4. What is the simplest data structure for holding the data necessary for converting the input to the output?
5. Am I selecting or iterating over the object directly in the path between the input and the output?

Code:

1. Can I combine some steps from the algorithm into a single line or method (e.g. chaining methods)?
2. Are there common methods available in this language that can simplify the implementation of our algorithm (e.g. using `map` instead of `loop`)?
3. 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.