Problem solving process

In this post, I want to show you a solving problems process called The "PEDAC" Problem Solving Process.

One of the principles in that process is spending some time with the problem before we start writing a code.

The main steps of "PEDAC" process are:
1) Understand the Problem
2) Examples / Test Cases
3) Data Structure and Algorithms
4) Code

Let's try this steps in practice. I'll go through that process with three examples.

1) Rotating Matrices

Problem: Write a function that takes an arbitrary matrix as array and rotates it 90 degrees clockwise

First step - understand the problem:

The first step of our process is to understand the problem. The first thing that we want to do here is defining what is an input and an output.

Input: Array of arrays
Output: Rotated array of arrays

But what it actually means?

Let's take some matrix:

3 4 1
9 7 5
6 2 8

When we take a matrix outline like that and rotate it 90 degrees we will have

6 9 3
2 7 4
8 5 1

When we write our matrix as an array we will have:
[[3, 4, 1],[9, 7, 5],[6, 2, 8]] => [[6, 9, 3],[2, 7, 4],[8, 5, 1]]
With that example I can write some rules:

Rules/ Requirements:

• Matrix is an array of nested arrays, that nested arrays are rows of matrix
• Input matrix first row becomes output matrix last column
• Nested arrays have same lengths
• Column of matrix is built by elements from nested arrays with the same index
• Output matrix has number of columns equal to input matrix number of rows
• Output matrix has number of rows equal to length of matrix array
• Elements from last nested arrays becomes first elements of each nested output array

Second step - examples and test cases:

 rotate90( [[3, 4, 1],[9, 7, 5],[6, 2, 8]])  // => [[6, 9, 3],[2, 7, 4],[8, 5, 1]]
 rotate90([[3, 7, 4, 2], [5, 1, 0, 8]]);  // =>  [[5, 3], [1, 7], [0, 4], [8, 2]]

Test cases help us clarify an understanding problem. We should to ask question about some edge cases. Here for example our second case isn't a square matrix.

Third step - Data Structure and Algorithms

In this problem, our data structure is defined in the problem description. It will be an array of arrays.

So it's time to write some algorithm.

Algorithm:

• Create a result array with length equal to length of nested array length
• Fill result arrays with empty arrays
• For input array length-1 to 0 take nested arrays
  • take elements of the current array and push its elements to every nested array of the result matrix
  • take the first number and push it to result first nested array
  • take the second array and push it to result second nested array

My algorithm to that problem isn't split into small details steps.
Algorithm step should be as detailed as you need to solve the problem.
If you don't know how to solve some of that steps, try simply that step and split it to simpler steps

Fourth step - Code

function rotate90(matrix) {
  var result = [];


 for (var row = 0; row < matrix[0].length; row++) {
    result.push([]);
  }

  for (var i = matrix.length-1; i >= 0; i--) {
    for (var j = 0; j < matrix[i].length; j++) {
      result[j].push(matrix[i][j]);
    }
  }

  return result;
}

var matrix1 = [
  [3, 4, 1],
  [9, 7, 5],
  [6, 2, 8]
]

var matrix2 = [
  [3, 7, 4, 2],
  [5, 1, 0, 8]
]

var newMatrix1 = rotate90(matrix1);
var newMatrix2 = rotate90(matrix2);
var newMatrix3 = rotate90(rotate90(rotate90(rotate90(matrix2))));

console.log(newMatrix1); // [[6, 9, 3], [2, 7, 4], [8, 5, 1]]
console.log(newMatrix2); // [[5, 3], [1, 7], [0, 4], [8, 2]]
console.log(newMatrix3); // matrix2

For the first point in my algorithm, I create an empty array then I push some empty arrays to that result array with for loop. Amount of nested empty arrays is equal to nested array length. That created a frame to the result matrix.

Next step was second for loop followed by another nested loop which takes a nested array from an input matrix and pushes that elements to each of result nested arrays.

The last step returned a result array.

2) 1000 Ligths

Problem: You have a bank of switches before you, numbered from 1 to n. Each switch is connected to exactly one light that is initially off. You walk down the row of switches and toggle every one of them. You go back to the beginning, and on this second pass, you toggle switches 2, 4, 6, and so on. On the third pass, you go back again to the beginning and toggle switches 3, 6, 9, and so on. You repeat this process and keep going until you have been through n repetitions.

Write a program that takes one argument, a total number of switches, and returns an array of lights that are on after n repetitions.

First Step - Understand problem

Input: An integer
Output: Array of numbers of lights that are on;

Rules:

• All lights are off on start
• There are n times repetition where n is number of lights
• In round one we switch all lights
• In second run we switch lights that are power of 2 from first up to last lights
• In the third run, we switch lights that are next powers of 3
• In n round, we switch lights that are next powers of n

Second Step - Example / Test Cases

console.log(lightsOn(5)); // [1,4];
console.log(lightsOn(100)); // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100];

Third step: Data Structure / Algorithm

To solve that problem we use arrays

From last rule, we know that we always turn light that is equal to the power of that round. Our output array will consist next powers of natural numbers up to our input number.

Base on this my algorithm for that problem looks like this:

• Create an array with length of quantity of natural numbers powers up to input number
• Fill that array with random number
• Map that array
  • take each index of the element
  • increment that index by one
  • Return power of the index
• Return an array

Fourth step: Code

At first, I create an array of lights that will be on.
I get the square root of input number and round it down. That return me a number of elements of my array. Then I fill it with random number.

var lights = Array(Math.floor(Math.sqrt(number))).fill(0);

Next step was mapping my array. In each iteration, I first increment index number. That let me get natural numbers and get the power of that number.

return lights.map(function(element, index) {
    index += 1;
    return Math.pow(index, 2)    
  });

I return the result of that mapping and get the result of our problem.

function lightsOn(number) {
  var lights = Array(Math.floor(Math.sqrt(number))).fill(0);
  return lights.map(function(element, index) {
    index += 1;
    return Math.pow(index, 2)    
  });
}


console.log(lightsOn(100)); // => [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

3) Fibonacci Numbers (Memoization)

My third problem that was quite tuff at first was the fibonacci algorithm with memoization.

Write a recursive function that computes the nth Fibonacci number, where nth is an argument to the function. Use memoization to improve performance.

First Step: Understand problem

The Fibonacci series is a sequence of numbers starting with 1 and 1 where each number is the sum of the two previous numbers. So third element is equal to 2, the fourth element is equal 3 and so on.
Memoization is a process of saving computed earlier answers for reuse.

Input: An integer that is position in Fibonacci sequence; a cache that remembers earlier outputs.

Output: An integer that is value of number at input position

Rules:

• first and second elements are equal to 1
• every next element is equal to the sum of two previous elements
• saving computed answer to reuse

Second step : Example / Test cases

fibonacci(1)   // 1
fibonacci(2)   // 1
fibonacci(3)   // 2
fibonacci(4)   // 3
fibonacci(5)   // 5
fibonacci(12)  // 144
fibonacci(20)  // 6765

Third step: Data Structure / Algorithm

To solve the problem I use arrays and recursion.
The recursive function is the concept that was quite complicated to me at first.
The recursive function is a function which calls itself, has ending condition and the result of that function is used in each next step.

Algorithm:

• check if input cache has some elements
  • if false create an empty cache
  • if true assign input cache to the new variable
• check if the cache has the number for input position
  • if true return that number
• else check if the position is smaller than 3
  • if true return 1;
• else sum the same function with position decrement by 1 and same function decrement by 2
• save the result of above to cache
• return called the position of the cache

Fourth step: Code

In the first step of my algorithm, I check if input cache have some content and reassign cache variable

cache = cache || [];

The I check if the cache has a number for the position which function was called.

 if (cache[position]) {
    return cache[position];
  }

If the cache hasn't that element function move one and check if the position is smaller than 3. We know that first two elements of the fibonacci sequence are 1 and 1.

if (position < 3) {
      return 1;

If the position is smaller than 3 then function return 1.

Next step if the position is greater than 2 is recursion. So the function calls itself with position argument decrement by 1, and then call itself with position decrement by 2.
Ending condition of the fibonacci function is position smaller than 3 that returns 1. So the function calls itself until sub-function return 1. Then it sums that result and assigns it to our cache array.

if (position < 3) {
      return 1;
    } else {
      cache[position] = fibonacci(position-1, cache) + fibonacci(position-2, cache);
    }

Full code looks like this:

function Fibonacci(position, cache) {
  cache = cache || [];
  if (cache[position]) {
    return cache[position];
  }
  else {
    if (position < 3) {
      return 1;
    } else {
      cache[position] = fibonacci(position-1, cache) + fibonacci(position-2, cache);
    }
  }
  return cache[position];  
}

console.log(fibonacci(1));  // 1
console.log(fibonacci(2));  // 1
console.log(fibonacci(3));  // 2
console.log(fibonacci(4));  // 3
console.log(fibonacci(5));  // 5
console.log(fibonacci(12));  // 144
console.log(fibonacci(20));  // 6765

Summary

So that was all PEDAC process. Don't rush to write your code.
Take time to understand your problem, write some test cases, edge cases, examples to clarify your understanding. If You understand a problem well choose adequate data structure and write an algorithm that helps you write a code. Be as detailed as your understanding requires. And then start writing your code.

That was a quite long post. I hope it will be helpful for solving your programmers problems.