Principles To Code By: How To Solve Problems With Code
What I love most about programming is the problem solving. I don’t believe anyone is born with problem solving skills. It’s a muscle that is built and sustained by repeated exercise. Like any exercise, there’s a set of guidelines to help you be more effective at developing your problem solving muscles. I will introduce 5 of the most important software design principles that have guided my problem solving process and show you how to apply these principles to solve a real problem.
This article was also published on Medium under DailyJS.
1. Keep It Simple (KISS)
If there’s anything you should takeaway from this article, it’s the “keep it simple” principle. This principle is often known as KISS, which stands for “Keep it simple, stupid”.
Just because the problem we have to solve is complex, it doesn’t mean our solution has to be complex.
The rest of the principles guide our problem solving strategy to achieve simplicity in our solution. Generally speaking, we develop simple solutions to complicated problems by breaking the complex problem down to simpler sub-problems that we can easily solve.
I’m a fan of learning from examples so let’s look at an example of what keeping it simple looks like.
Suppose you were asked to write a function with the following signature to check for balanced parentheses in a string. For example, '('
returns false, ')('
returns false, '()'
returns true, and 'foo'
returns true.
function hasBalancedParen(str) {
return false;
}
So how do we approach this problem?
Step 1 is to apply the KISS principle, develop an outline for an algorithm that can be articulated in simple English:
Given a string,
s
, which consists of characters
- Start from the leftmost character and look at each character in the string
- Keep track of occurrences of
(
.- Keep track of occurrences of
)
to “cancel out” a previous occurrence of(
.- Ignore characters that are not
(
or)
.- If there’s a
)
for which there’s no(
, return false.- Once we finish looking at the last character, if there’s no leftover
(
or)
, return true.
The computational complexity is O(N) where N is the length of the string. In the worst case, we have to look at all of the characters in the string to be able to say that the string has balanced parentheses.
2. Separation of Concerns (SoC)
So we have developed our algorithm in simple English, which is essentially pseudocode! There are three logical domains for our algorithm:
- Continue or Stop?: Logic for whether to continue looking at the characters or stop and return true or false.
- Parentheses Tally: Logic for tallying up occurrences of
(
and)
as we go through the characters. - What to Look At Next? Logic for determining what to look at next.
Let’s map the 6 steps of the pseudocode above to one of these three logical domains:
Continue or Stop? | Parentheses Tally | What to Look At Next? |
---|---|---|
If there’s a ) for which there’s no ( , return false |
Keep track of occurrences of ( |
Start from the leftmost character and look at each character in the string |
Once we finish looking at the last character, if there’s no leftover ( or ) , return true |
Keep track of occurrences of ) to “cancel out” a previous occurrence of ( . |
|
Ignore characters that are not ( or ) |
What we just did was we partitioned the algorithm into three logical domains each dealing with a particular concern. Each domain specific concern can be tackled independently by a software component. The three software components are each designed to accomplish a specific mission and need not be concerned with what other components are doing. This demonstrates the principle of Separation of Concerns or SoC.
SoC is the key to developing a complicated application or software system with many moving parts. For example, web applications separate concerns between presentation (how the webpage looks), business logic (content of the webpage), and content delivery (accessing the resource via a JSON API, querying the database, etc).
Poorly executed SoC
I’ve seen poorly designed software in which the software is divided into separate domains but concerns are not separated. Consider the following example:
Write a function foo that doubles then increments every number in an array of numbers.
// Poorly executed separation of concerns
// Helper Functions
function double(arrIn) {
let arrOut = []
for (let i = 0; i < arrIn.length; i++) {
arrOut[i] = arrIn[i] * 2
}
return arrOut
}
function increment(arrIn) {
let arrOut = []
for (let i = 0; i < arrIn.length; i++) {
arrOut[i] = arrIn[i] + 1
}
return arrOut
}
// foo
function foo(arrIn) {
return increment(double(arrIn))
}
Why is this a poor execution of SoC?
Well, double
and increment
are both concerned with looping through an array to modify each elements. Notice how the double
and increment
functions look almost identical with the exception of how they modify the array element. This is called boilerplate.
Whenever you have boilerplate in your code, you know you can do better in separating concerns. This plays into the next principle:
3. Don’t Repeat Yourself (DRY)
The Don’t Repeat Yourself (DRY) principle and SoC go hand-in-hand. The DRY principle is aimed at reducing repetition and boilerplate in the software by forming abstractions. I can write a whole separate article on abstractions but here are the key points for how to apply abstraction to write code that doesn’t repeat itself:
- Create functions for common software patterns. We call them higher order functions.
- Replace the boilerplate in your code with higher order functions.
Some examples of higher order functions include:
map
- modifying each element in the array based on a give rulefilter
- getting a subset of the array that passes a given criterionreduce
- combining everything in the array based on a given rule
Let’s apply the DRY principle and rewrite foo
to abstract away the boilerplate using the map
higher order function:
// Well executed separation of concerns and DRY code
const double = elem => elem * 2
const increment = elem => elem + 1
function foo(arrIn) {
return arrIn.map(elem => increment(double(elem)))
}
I’m taking a shortcut by using the ES6 arrow functions, which lets you create elegant one-liners. JavaScript provides higher order functions like map
function for Array. Array.map
takes one argument: a function. In this example, this function is elem => increment(double(elem))
, which takes an argument elem
and returns elem * 2 + 1
. Since this function doesn’t have a name, it’s called an anonymous function.
Ok that was a long detour. Can we get back to the hasBalancedParen problem?
Yes! We are close to arriving at the final solution but there’s one more principle we need:
4. Divide and Conquer
When you hear “Divide and Conquer” in the context of algorithm design, think recursion. The term recursion has roots in mathematics and commonly entails applying a rule repeatedly to update itself to create an infinite sequence for which the next things in the sequence depends on the previous things in the sequence. For example, fractals, the fibonacci series, and Pascal’s triangle are all recursive mathematical constructs.
For the Divide and Conquer algorithms, we are interested in the repeated application of a rule but instead of constructing a sequence, we want to deconstruct the problem space and eventually return a final solution. In pseudo code, a recursive function for divide and conquer algorithm has the basic structure:
function recursiveFun(input, output) {
if we hit a base case, updated output as necessary and return the final output
otherwise, simplify the input. update the output then
return recursiveFun(simplerInput, updatedOutput)
}
The emphasis is simplifying input until the problem becomes trivial to solve and we can return an output immediately in the beginning of the function. This is called the base case. What if we forget to add a base case to the recursive function? The function will keep calling itself forever until you run out of memory and get a stack overflow error.
Note, we don’t have to use a recursive function to implement a Divide and Conquer algorithm. We can use a loop and a mutable data structure. I’m not a fan of mutable data structures option although it is more efficient sometimes.
Let’s look at a simple example for a Divide and Conquer algorithm implemented with a recursive function and a mutable data structure:
Write a function sum that takes an array of numbers and returns the sum of all the numbers
Option 1: Recursive Function
function sum(arr) {
function add(arr, sum) {
// Base Case
if (arr.length === 0) return sum
// Recursive Step
return add(arr.slice(1), sum + arr[0])
}
return add(arr, 0) // <-- Initial Values
}
Option 2: Mutable Data Structure
function sum(arr) {
// Initial Values
let result = 0
let elems = arr // <-- mutable data structure
while(elems.length > 0) { // <-- Base Case
result += elems.pop() // <-- Recursive step
}
return result
}
In both Options 1 and 2, every time we repeat the procedure of adding the next element to the current sum, we are creating a simpler array and an updated sum that’s a little closer to the final solution. The stopping point is when we run out of things in the array to add to the current sum, in which case we just return the current sum which is the final solution.
Fans of functional programming and one-liners will implement sum as follows using the higher order function reduce
, which JavaScript gives you out-of-the-box for the Array prototype:
const sum = (arr) => arr.reduce((res, elem) => res + elem, 0)
With Divide and Conquer, we have the last important problem solving principle to solve the hasBalancedParen problem:
// Parentheses Tally
const newOpenCnt = (c, openCnt) => {
if(c === '(') return openCnt + 1
if(c === ')') return openCnt - 1
return openCnt
}
function isBalanced(str, openCnt) {
// Continue or Stop?
if (typeof str !== 'string') return false
if (openCnt < 0) return false
if (str.length === 0) return openCnt === 0
// What to Look At Next?
const fst = str[0]
const rst = str.slice(1)
return isBalanced(rst, newOpenCnt(fst, openCnt))
}
function hasBalancedParen(str) {
return isBalanced(str, 0)
}
5. Always Test Your Code
The final problem solving principle is to always test your code to make sure there’s no mistake in the implementation and your code behaves correctly for all edge cases. Below I created a unit test that incorporated most of the previous design principles:
KISS
Create a unit test function called test
that performs unit testing on a function fun
using a set of test cases. We want to be able to run a test for any function like so:
test(fun, testCases)
For each test case, test
should print to console “passed” if successful or “failed” with more details if unsuccessful.
SoC - Keep the data (the input and expected value) in a data structure called testCases
separate from the business logic of unit testing:
let testCases = [
{test: '(', shouldBe: false},
{test: '())', shouldBe: false},
{test: null, shouldBe: false},
{test: undefined, shouldBe: false},
{test: 22, shouldBe: false},
{test: ')(', shouldBe: false},
{test: '', shouldBe: true},
{test: '()', shouldBe: true},
{test: '()()', shouldBe: true},
{test: '(())', shouldBe: true},
{test: 'hi', shouldBe: true},
{test: '(hi)', shouldBe: true},
{test: '(((())(())',shouldBe: false}
]
DRY
Abstract away the part of code that loops through all the testCases by using a higher order function map
:
const test = (fun testCases) => {
testCases.map(t => {
const shouldBe = t.shouldBe;
const is = fun(t.test);
const res = (shouldBe === is) ? 'passed' : 'failed';
const moreInfo = (res === 'failed') ? `testing ${t.test}. Should be ${shouldBe} but got ${is}` : ''
console.log(`${res} ${moreInfo}`);
})
}
Run the test:
let fun = (str) => hasBalancedParen(str)
test(fun, testCases)
Conclusion
Problem solving is the application of knowledge and tools to achieve a desired outcome so the better your knowledge and tools are, the better your problem solving will be. Without a framework for problem solving, the process of problem solving could be inefficient and iterative, requiring rounds of experimentation and refactoring. Use the these five principles to power your problem solving process to write more efficient and beautiful code!