Having Fun with PEDAC Approach, List and Functional Abstractions
Back in my early days of coding, I used to hack and slash during algorithmic exercises. I’d read through the problem, look at the given test cases and jump right into coding up the solution. In my mind, as long as I pass the given test cases, I have satisfied all the requirements and I’m done! However, based on my understanding, that is the most dangerous part of coding: not fully understanding the problem and identifying potential pitfalls/edge cases. I think its very natural for most beginners to think about tweaking the solution a little to meet the edge cases. However, this sometimes does not work in certain scenarios and you might find yourself having to change a considerable part of your algorithm to solve the problem. This situation is fine if you are just practicing at home but can be nerve-wracking in a technical interview with a potential employer.
Recently, I picked up a new problem-solving approach called the PEDAC process by Launch School. I won’t go too much into detail on this process since it has already been covered by another student (Edgar Mkaka Joel) so I’ll put the link right here:
In this blog post, I will provide a brief description about programming problem solving approach that I recently…medium.com
Here is the summary taken directly from Launch School :
- Understand the Problem
- Examples / Test cases
- Data Structure and Algorithms
Following this procedure gives me a solid game plan to stick with. Instead of stumbling around, hacking and slashing around like a crazed fruit ninja warrior, I have a more methodical and reliable approach to deconstruct a problem and solve it by parts. Here is an easier question which I tackled with the PEDAC process. Of course, the complexity of the problem determines how muct time you should spend on each step of the process.
Comparing Version Numbers
The requirements are pretty simple, given version numbers such as these: 1.0, 1.2.4, 3.5 etc, write a function that takes any 2 version numbers in this format and compare them. These are the conditions:
- if version 1 > version 2, return 1
- if version 1 < version 2, return -1
- if both versions are the same, return 0
- If either version number contains characters other than digits and the ‘ . ’ character, we should return null.
For the sake of brevity, I won’t go through each step in detail, but the problem is pretty straightforward and here’s the gist of it: Given two numbers separated by dots in String format, compare them and return the result. Return null if any of the inputs are invalid.
Writing the test cases: I like to write test cases sequentially. From normal cases to the weirder edge cases to the invalid cases. Given all the information above, here are the test cases I wrote:
I’m sure there are plenty more of edge cases I did not cover but for the purpose of this exercise, its sufficient. I did not come up with the 5th test case on my own. It was provided to me and it did cause me quite a bit of grief which I will explain later. Do spend some time working on this part. It helps give you a better understanding of the problem and you might be surprised at the amount of weird test cases you can come up with as you do more and more of these mental exercises.
Data structure: I think everyone will agree that an array is probably the best data structure to work with in this problem. It comes with a handy dandy set of list abstraction methods.
Algorithm: I personally think this is the most fun part. Its like coming up with an overall design plan of the problem and could make your life easier. Before I learnt PEDAC, I was not very disciplined in writing pseudo code or coming up with an algorithm to solve the problem. I just jumped straight into it and sort of hashed out the algorithm as I coded. Now, this would work in simpler problems but I think its very important to have a more disciplined approach especially when it comes to solving more complicated problems. You can surely get by without a structure in simpler problems but it becomes more difficult to hash out algorithms on the fly as you code. Not only are you dealing with how to solve the problem on a higher level, but you are also bogged with the syntax of the language. So, its best to separate out these two concerns and work with each one individually.
My first algorithm that I came up with was:
- Take string input and split with ‘ . ‘ delimiter into an array of String digits.
2. Map into array of digits.
3. Iterate through each number in the array and compare it with the other array that holds the number of the second version in the same index. So for example, 2 versions:
[1, 2, 2] versus [1, 2, 5]. Start by comparing 1 with 1. Since its same, we move on to the next pair. We then compare 2 with 2 and since its the same we move on. Then we compare 2 with 5 and since 5 is more than 2, the second version is thus bigger. However, things get a little dicey when the two versions are of unequal length.
- comparing 1.5 with 1.5.2
- comparing 1.0 with 1
In both cases, there’s an extra digit in one of the versions. My first approach was to tackle it with various if statements but it started becoming messy. It was along the lines of
- if version 1 had extra number at back, and if extra number is not 0 then its bigger but if the extra number is 0 then its equal but wait.. what it we are comparing 126.96.36.199 with 1?
There’s a solution to this issue which I did apply in my 2nd algorithm but I didn’t think about it at that moment. The point I’m trying to make is try not to get too committed with a single algorithm. Sometimes, our brain freezes when we are just trying stubbornly to solve the problem in a particular way. Its better to keep an open mind, take a step back, stay calm and come up with an alternative algorithm if needed. You might find your brain opening up to new ideas when its more relaxed. No code is written yet at this point and there’s no shame in taking a step back and thinking another way.
At this point, I knew I had a problem with the 3rd step of iterating through the elements of the array. Then it struck me, why don’t I just straight up compare the numbers instead of iterating through the numbers in both arrays and comparing them???
In essense, in the case of 2.0.1 with 2.0.5, I will combine them into 201 and 205 and straight up compare them. In cases where its 2.0 and 2.0.5, I will append an extra ‘0’ to make both inputs the same length and compare them! So, 2.0 will become 2.0.0 vs 2.0.5 and now we can compare them directly.
This is what I ended up coding with some functional abstractions:
The function splitIntoChars() takes a single string parameter (assume it will always be a String that is passed into the function) and splits in into an array of characters in String format. We then use the list abstraction method of interrogating every element to see if they are all valid. If they are all valid, return the array which is a ‘truthy’ value, else it will return false.
To check the validity of each element, I used a very simple regex. It basically only accepts numeric characters ‘0–9'. For a beginner friendly book to regex, I strongly suggest Launch School’s FREE regex book. Its all you need to be dangerous with Regex!
Launch School - Introduction to Regular Expressionslaunchschool.com
Referring to the final code, if either of the versions are invalid, the code returns null. If both are valid, we then adjust either of the 2 version to get them to the same length
To adjust, we take the difference of both arrays. If the difference is positive, we know the second array is shorter and we add the number of ‘0’s equivalent to the difference to the first array and vice versa.
This function employs a for loop that pushes in ‘0’ in String format to the array argument that is passed into the function. Arrays are mutable so this will mutate the array that is passed into this function.
This function is the main part of the solution. It takes the 2 arrays that are valid and have been adjusted and joins them into a string and parses the string into numbers. We then compare both numbers and return the appropriate values. Note that I decided to convert the String into numbers at this point instead of the beginning like my planned algorithm. The point I’m trying to make here is that its alright to tweak and adjust the algorithm as you code. Coding is meant to be fluid and fun, not rigid.
- PEDAC process provides a more structured approach to solve problems. It facilitates deconstruction of a problem, and forces you to write test cases first before coding to better understand the requirements.
- Make it a habit to flesh out an algorithm before jumping into coding. It encourages coding with intent, and avoids the pitfalls of hack and slashing
- Don’t be afraid to come up with alternative algorithms or even different data structures. Our brain sometimes tend to get stuck trying to figure out a solution in a particular manner. Its ok to take a step back and do some reassessment.
- Feel free to revise your algorithm while coding. Its not set in stone and you might find certain routes that might be easier during coding
- Have fun creating functional abstractions and coming up with good function names. It might sound silly, but I do get a kick out of making my code look as plain English as I possibly can! Makes coding more tolerable and makes me feel more like a human :-P
- The opinions and views here are based solely on the personal opinions of the author and has no 3rd party influence.
- A monetary credit may be applied to this article if Launch School publishes it under its collection of articles
- Join Launch School through this link:https://launchschool.com/join/039c4c52da and you and I bot hwill receive a one time $50 credit towards our tuition!