Problem Solving Patterns

Begin Programming with JavaScript Problem Solving Patterns

Until now, our focus has been on the technical aspect of programming. In this chapter, we’ll look at a few common coding problems and their solutions.

We will see a handful of examples in this chapter, so make sure you create a different folder for each example.

Mapping

Mapping means to take an array of data and transform each item to create a new array.

For example, given an array of string values, we want to get the size of each item:

image

The original array and the resulting array will contain the same number of items.

To solve this problem, we need to use a for loop to get the size of each string item and put them in a new array one by one:

let input = ["Java", "Python", "Ruby", "JavaScript", "C#"];
let output = [];
for(let i=0; i<input.length; i++){
  output[i] = input[i].length;
}
console.log(output);

unpack:

An output array is prepared before the loop begins. This is similar to getting the sum of a list of numbers.

This program doesn’t use prompt and alert. The input is hardcoded, and you can see the output only if you open the console in a browser. So technically this is not a real program, but it’s good for demonstration purposes.

We don’t actually change the original array, instead, we create a new array and put all the new data in the new array. This is true for all the examples in this chapter.

More Mapping

Another example, given an array of numbers, we want to round down each number to the nearest thousand.

image

The code is almost the same as the previous example except that the loop body is different:

let input = [1234, 2222, 3010];
let output = [];
for(let i=0; i<input.length; i++){
  output[i] = input[i] - input[i] % 1000;
}
console.log(output);

For the rounding, we’re using the modulo operator %. This operator will give us the remainder of the division between two numbers. For example, 10 % 4 will produce the remainder 2.

image

Another example, 1234 % 1000 will produce the remainder 234.

1234 % 1000 = 234

↓ But to get the rounded number, we need to subtract the remainder from the original number. For example, 1234 minus the remainder 234 will produce the final answer 1000.

1234 - 1234 % 1000 = 1000

The modulo operation is at the same precedence level as multiplication and division, so it gets processed before subtraction and addition.

Filtering

Filtering is similar to mapping in that a new array will be created. But different from mapping, the resulting array doesn’t always have the same number of items.

For example, given an array of numbers, we want only the numbers that are 10 or greater.

image

We’re using a conditional inside the loop to make sure only the right items get added to the new array.

let input = [90, 2, 10, 9, 8, 12];
let output = [];
for(let i=0; i<input.length; i++){
  if(input[i] >= 10){
    output.push(input[i]);
  }
}
console.log(output);

unpack:

The condition is using a new comparison operator >= called greater than or equal to. The condition will be true if the left value is greater than or equal to the right value.

Since the original array and the new array don’t always have the same size, we need to use the push method to add the items to the new array. This method puts a new item in the next available slot.

↓ We are using input[i] twice inside the loop.

To keep the code DRY and easier to read, we should create a variable so that we don’t have to repeat input[i] in multiple places. ↓

...
for(let i=0; i<input.length; i++){
  let item = input[i];
  if(item >= 10){
    output.push(item);
  }
}
...

More Filtering

Converting a normal array into a set is a common filtering problem. A set is a list that contains only unique items.

image

↑ The items that get into the set first will actually prevent any new and identical items to get in. As a result, all items that get added to the set are unique.

The code is almost the same as the previous example except that the condition is different.

let input = [1, 1, 2, 3, 3];
let output = [];
for(let i=0; i<input.length; i++){
  let item = input[i];
  if(output.indexOf(item) === -1){
    output.push(item);
  }
}
console.log(output);

unpack:

The indexOf method tells us the position of an item inside the array. It will return the index of an item if that item is found in the array, and it will return -1 if the item is not found.

This condition will be true only if an item with the same value is not already in the output array.

Reshaping

Reshaping means to turn an array of a certain structure into a different structure. For example, a simple array gets reshaped into a two-dimensional array.

From:

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

To:

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

This is common in web development where you might have a list of items to be presented in multiple rows.

image

↓ We start out with an empty currentRow array and an empty output array. Each repetition of the loop will push an item to the currentRow array. When the currentRow array is all filled up (3 items in this example), it gets added to the output array, then it gets reset to an empty array for the next row.

let input = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let output = [];
let currentRow = [];
for(let i=0; i<input.length; i++){
  currentRow.push(input[i]);
  if(currentRow.length === 3){
    output.push(currentRow);
    currentRow = []; // Reset
  }
}
console.log(output);

unpack:

The conditional is for adding the currentRow array to the output array only when currentRow is full.

Each reset will create a new array but still using the same variable currentRow.

Here’s a frame-by-frame illustration of how items are added to each sub-array, and how each sub-array is added to the main array.

Recap

Although not every single problem will be the same as the ones demonstrated here, there are two basic patterns that you’ll find in many other programs:

  • Create an empty array, and fill it up with data throughout the rest of the program.

  • Use conditional inside a loop, and the condition relies on each item in the array. Depending on the condition, each item will get treated differently.

Exercise

Given an array of numbers:

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

Write a program that can convert it to an array of three sub-arrays. The three sub-arrays include:

  1. an array of numbers lower than 5
  2. an array of numbers greater than 5
  3. and an array of numbers equal to 5
[
  [ 1, 2, 3, 3, 4 ],
  [ 6, 7, 8, 9 ],
  [ 5, 5 ]
]

This problem combines the characteristics of both filtering and reshaping.

You can use the example code as a starting point:

let input = [90, 2, 10, 9, 8, 12];
let output = [];
for(let i=0; i<input.length; i++){
  if(input[i] >= 10){
    output.push(input[i]);
  }
}
console.log(output);

Solution

let input = [ 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9 ];
let output = [[], [], []]
for(let i=0; i<input.length; i++){
  let item = input[i];
  if(item < 5){
    output[0].push(item);
  }
  else if(item > 5){    
    output[1].push(item);
  }
  else {
    output[2].push(item);
  }
}
console.log(output);

unpack:

Since we know it’s going to be three sub-arrays regardless of the input data, we can prepare three empty sub-arrays before the loop.

There are three groups of data, so the conditional statement has three branches.

To make the code more descriptive, we can use an object in place of the main array:

let input = [ 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9 ];

// CHANGE
let output = {
  lessThanFive: [],
  greaterThanFive: [],
  equalToFive: []
};

for(let i=0; i<input.length; i++){
  let item = input[i];
  if(item < 5){
    // CHANGE
    output.lessThanFive.push(item);
  }
  else if(item > 5){
    // CHANGE   
    output.greaterThanFive.push(item);
  }
  else {
    // CHANGE
    output.equalToFive.push(item);
  }
}
console.log(output);

In JavaScript, an object is also called an associative array. Different from a regular array, we’re using a name instead of an index number to refer to each item.

Each item in the object is called a property.