DEV Community: Mateusz Niestrój

Problem solving process

Mateusz Niestrój — Fri, 01 Sep 2017 18:33:06 +0000

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.

Every problem has another solution

Mateusz Niestrój — Fri, 01 Sep 2017 08:59:22 +0000

Many ways of solving problems

When I am working on programming problems, I tend to fixed to first way to solve that problem that I have on my mind. Sometimes that is ok, and often the easiest way to solve that problem for me. But most time it is not the best and not the only way to do that.
So today I will present three easy problems with three different solutions to show you that there is always a few ways to provide another solution.

1) First Problem: Double Char

Our goal in that exercise is to find a function that takes a string as an argument and return the new string in which it doubles every character.

Let's look at test cases

repeater("Hello") // => "HHeelllloo"
repeater("We've been doubled") // => "WWee''vvee  bbeeeenn  ddoouubblleedd"

The first way to solve that problem is splitting our input string to an array, and then map elements of that array by using repeat function.

function repeater(string) {
  return string.split("").map(function(char) {
    return char.repeat(2);
  }).join("");
}
repeater("Hello") // => "HHeelloo"

String.prototype.repeat is a function that returns copies of string on which is called. These copies are equal to the integer number that was passed on as an argument.
After using repeat our string has elements with doubled string, so we join it to one string.

Another solution can be a solution that uses a for loop and Array.prototype.push function.

function repeater(string) {
  var stringArr = string.split("")
  var result = [];
  for (var i=0; i < stringArr.length; i++) {
    result.push(stringArr[i] + stringArr[i])
  }
  return result.join("")
}

repeater("Hello") // => "HHeelloo"

Like in the first solution we split input string to an array of characters and then we iterate through that array and for each element we push doubled element to result array. We return joined result array and we have the expected result.

Last way to solve this is a one-liner.

function repeater(string) {
  return string.replace(/./g, "$&$&");
}
repeater("We've been doubled") // => "WWee''vvee  bbeeeenn  ddoouubblleedd"

When we working with arrays we have regular expressions to our disposal. So here we use String.protorype.replace which takes a regular expression as a first argument, and as a second argument, it takes a string that replaces regexp specified as the first argument.

According to JavaScript docs $& pattern inserts the matched substring so we get our expected result.

2) Second Problem: Counting Up

We had strings so let's take some numbers.

Our goal here is to write a function that takes an integer argument, and returns an Array of all integers, in sequence, between 1 and the argument with the assumption that our input is always a valid integer greater than 0.

sequence(5) // [1, 2, 3, 4, 5]
sequence(3) // [1, 2, 3]

As input, we have an integer and as output, we want to have an array. So we have to find ways to create a sequence of elements.

One way to do that is using a loop.

function sequence(integer) {
  var i = 1;
  var result = [];
  while (i <= integer) {
    result.push(i);
    i++;
  }
  return result;
}
sequence(5) // [1, 2, 3, 4, 5]

This time we use a while loop. First we create a empty result array and then we set some variable with our iteration value. This variable should be equal to 1 because we want to return sequence from 1 to function input integer.

After that, we used Array.prototype.push in a loop until iteration value is equal to function input. At the end, we return our result.

In next solution, at first, we create an Array with a proper number of empty elements.

function sequence(number) {
  return Array(number).fill(1).map(function(v, i) {
    return v + i
  });
}
sequence(5) // [1, 2, 3, 4, 5]

To create the empty table we used Array(number) it creates a number of elements equal to the number value. After that, we using Array.prototype.fill function. We passed 1 as an input. fill takes as first argument a value of array element, so we fill our array with 1 in order to map that elements by adding an iteration value to value of the element which is a 1 in our case. So after each iteration, we increment the value by 1.

The third solution can be done with strings.

function sequence(number) {
  return "1".repeat(number).split("").map(function(_,i){
    return ++i;
  });
}
sequence(5) // [1, 2, 3, 4, 5]

That solution first takes random one character string that is repeat number times where the number is our input. Then that string is split by character to an array and then, every element of that array is mapped with the value of an incremented first number of iteration.

3) Third Problem: Name Swapping

In this task, we write a function that takes a first name, a space, and the last name passed as a single String argument, and returns a string that contains the last name, a comma, a space, and the first name.

swapName('Bill Gates') // 'Gates, Bill'

The first way to solve that is simple and with use of a method that we use earlier.

function swapName(string) {
  var nameArr = string.split(" ");
  return nameArr[1] + ", " + nameArr[0];
}
swapName('Bill Gates') // 'Gates, Bill'

This solution splits string to array of words and then simply return first second element of that string followed by comma followed by first element of splited string.

Second solution used Array.prototype.reverse function.

function swapName(name) {
  return name.split(' ').reverse().join(', ');
}
swapName('Bill Gates') // 'Gates, Bill'

As in the first example, we split the string to words. Because we know that we have only two elements in an array we can reverse it with reverse function and then join array elements with comma and whitespace as the separator.

The last solution is similar to the first. In this case, we get our array with regular expression and String.protoype.match function.

function swapName(string) {
  var nameArr = string.match(/\w+/g);
  return `${nameArr[1]}, ${nameArr[0]}`;
}
swapName('Bill Gates') // 'Gates, Bill'

match function take a regular expresion as an argument and return an array containing the entire match result. After we received an array we return a string with swapped elemnts of that array like in first example.

To add variety to this example I use a template string a technology from ES6 Standard, which allows us to embedded expressions right into the string.

Summary

That was very simple problems with a very simple solutions, but I hope I show you that even simple problems can have few ways of solving. Often that are ways that can learn us something new.