JavaScript Weekly: Using a Structured Problem-Solving Approach
Understanding a Problem Before Writing a Single Line of Code
A common misconception about coders is that their job is to write code. OK, maybe that’s not totally wrong, but it fails to capture the essence of what a coder does, which is solve problems. Every day coders are confronted by myriad problems that need to be solved, whether it is sorting a set of data, transforming messy input into something organized, or figuring out when and how to return some value to a user. We spend all day solving problems, which is why problem solving is a skill worth practicing. And for that reason, we’re taking a break this week from JavaScript in particular and focusing instead on language agnostic problem solving practices.
Plan, Plan, Plan
When confronted with a problem, most coders’ first instinct is to immediately start writing code. We are problem solvers after all, so one can be forgiven for wanting to dive in. But, if you want to solve a problem accurately and completely, then your first task is to resist this urge. Diving into code without a plan is a trap, escape from which will almost certainly prove painful. Thankfully, this is a trap that can be easily avoided. Taking the time to understand the problem and structure an effective approach may seem like a time sink, but not only will it lead you to a better solution, it will also save you time in the long run.
When planning an approach to a problem, you have several tasks. First, you need to understand the problem. This step is absolutely critical because if you don’t understand the parameters of the problem then you can’t possibly expect to develop an effective solution. One of the worst things that can happen to you is to get to the end of a “solution” only to realize that it doesn’t address the actual problem.
Once you understand the problem, your next task is to look for potential pitfalls. Many (in fact, most) problems that you work on will have edge cases — unexpected inputs that may lead to unusual outputs. If you identify these edge cases ahead of time then you can plan for them in your solution. This is significantly preferable to encountering them later when the stakes are a lot higher.
After you feel like you have a complete grasp of the problem, your last major task is to develop an approach. During this stage you can start working through potential solutions, prepare your algorithm, and write out pseudo-code to describe it. By the time you finish doing this you will already have completed the lion’s share of the problem. Writing the actual code should be the easiest part of the whole process.
Step-by-Step
As with most things in coding, perhaps the best way to illustrate the problem solving process is with a real example. Let’s look at a typical coding challenge and see if we can come up with a potential solution. Consider the following problem:
Write a program that takes a string as input and returns a count of how many words in the string can be rearranged to form palindromes. You may assume that input strings are at least 1 character in length and contain only alphabetic characters. You may ignore case for the purpose of assessing possible palindromes.ex. Processing the string “aaa bca Abab” should return the integer 2 because “aaa” is already a palindrome and “Abab” can be rearranged to “Abba”, which is also a palindrome (case insensitive). Thus, two of the three words in the string can be made into palindromes.
Understand
Our first task is to understand what this problem is really asking. From reading the problem we can ascertain three key elements: the expected input; the expected output; and, any relevant rules for processing. In order to go about this in a structured fashion, let’s write out our understanding of each of these elements:
Input:
- A string consisting of alphabetic characters only
- Minimum length of 1
- Upper and lowercaseOutput:
- An integer representing the number of words in the string that may be rearranged to form palindromes.Rules:
- A palindrome is formed when a string is the same reading forwards or backwards.
- For the purpose of this problem, case may be ignored when assessing possible palindromes.
Our goal here has been to extract relevant information from the problem and document it in a place that we can easily reference. You will note that our documentation of the problem is drawing both from the actual written problem and from the examples we are given. You might also find yourself drawing on implicit knowledge (such as the definition for a string that is a palindrome.) However, be careful in such instances not to make too many assumptions. For example, if you are in a job interview setting, then now is the time to ask questions and get clarification on the problem parameters.
Pitfalls
Now that we have a good idea of the problem parameters, it’s time to consider potential pitfalls. Considering possible input is particularly important because depending on the problem types of input could cover a wide range of possibilities. Unexpected inputs can wreak havoc in your code if you don’t plan for them, so taking the time to expect the unexpected will pay dividends. In this case we don’t have too many edge cases, but let’s document some possible inputs anyway.
Edge / Test Cases:
- String is only one character in length.
- String contains no words that can be rearranged into palindromes.
- String contains words that are already palindromes.
- String contains words that must be rearranged to make palindromes.
- String contains both upper and lower case characters.And while we are at it, let’s write some tests for each possible input so that when we start the actual coding process we are ready to examine outputs.
console.log(palindromeCounter(“a”)); // 1 (“a”)
console.log(palindromeCounter(“ab”)); // 0
console.log(palindromeCounter(“Abc Def G”)); // 1 (“g”)
console.log(palindromeCounter(“abbAc C ddEf”)); // 2 (“abcba”, “c”)
console.log(palindromeCounter(“lmn opq rst”)); // 0
console.log(palindromeCounter(“AAA bAbbB”)); // 2 (“aaa”, “bbabb”)Approach
It feels like we’ve got a strong sense now for the problem, for possible inputs, and for what we expect as outputs. Now that we know what we are working with we are ready to start developing an approach. A problem like this has many different ways to go about it, and you should choose the approach that makes the most sense to you. The important thing is to know what you are going to code before you actually write any code. Here is one possible approach to our palindrome counter problem:
Approach:
- Transform the input string to be all lower case
- Split the string into an array of words
- Set a counter to 0
- Iterate over the word array
- Test if word can be rearranged into a palindrome
- (See sub-task approach)
- If true, increment counter by 1
- Return counterSub-task approach:
- Test if word is already a palindrome (word === reverse)
- If true, return true
- Split word into array of chars
- Set an empty object, charCounts
- Iterate over chars array
- If charCounts[c], increment charCounts[c]
- Else, set charCounts[c] to 1
- Set an odd value counter to 0
- Iterate over charCounts values
- If value is odd, increment odd value counter
- If odd counter > 1, return false
- Return true
Things are looking good. But do we really understand what this approach will produce? If you’re not sure, then it may be worth taking the time to manually run through your pseudo-code and consider how it will handle some given input. Try “running” the code in your head and work through the variables you expect to be in existence at any given point in the algorithm and their values. Do they match what you expect? Is the final output what you planned?
The pseudo-code you have just completed is going to serve as your guide for solving the problem in real code. For this reason, you should use appropriate technical language, which will provide you with useful hints during the actual coding process. For example, if you need to iterate over an array of integers and double each value along the way, you might write pseudo-code that says “map over each value (n) in the integer array, returning 2 * n at each step” rather than “go through the array and multiply each value by 2.”
Coding
Finally, the fun part! After carefully going through our problem, understanding its parameters, developing test cases, and planning an approach, we are finally ready to start the actual coding. But don’t get ahead of yourself — we have a lot of steps here, each one of which is expected to produce a certain output.
As you are writing your code, look for ways to break it down into distinct, testable pieces. For example, in this problem we are going to write a function called palindromeCounter, but there is a lot going on inside its implementation. In order to abstract certain pieces of the problem away, we might write several additional functions to be used by palindromeCounter. Perhaps one that checks if a string is a valid palindrome, another to rearrange the characters in a string into a possible palindrome, and another to count character occurrences in a given string. There are many options, and how you choose to implement a solution is up to you, but take the time to run mini tests throughout the coding process to ensure that each piece is giving you the output you expect. The more you run your code, the better you will understand what it is doing. In this case, we might end up with an implementation like the following:
And voila! There we have it — a working solution to our problem that mirrors the pseudo-code we wrote earlier. In this case we haven’t worried too much about algorithmic complexity, but we have something that works and now we can go back and refactor as needed.
A structured problem-solving approach of this nature can, at times, seem a bit like overkill. This is especially true when problems seem straight-forward or we already have a potential solution in mind. However, getting into the habit of using a structured approach will help you in the long run. Coding is an artful practice, but it also requires discipline. As the complexity of the problems you are solving increases, the chance for error does as well. Using a measured approach will set you up for success in the long run, and hopefully save you from a lot of unnecessary pain.
