This series of problem solving exercises are based on problems found on Codewars https://www.codewars.com/ or Hackerank https://www.hackerrank.com/dashboard.

What you should already know

You should have attended the previous two problem solving sessions. You will have learned the outline procedure for solving problems by:

  1. Understanding what the problem statement is asking you to do
  2. Using abstraction to identify what is important
  3. Using decomposition to break the problem down into smaller problems.
  4. Solve the smaller problems, one at a time

You will get more practice on that today.

What you'll learn

What you'll need

No specific tools are required, although you will need to make notes so either pencil and paper or a text editor on your laptop.

What you'll do

You will be presented with a problem. You will learn how to understand the problem and break the problem down into steps that help you work towards a solution.

Todays problem can be found here: https://www.codewars.com/kata/52de553ebb55d1fca3000371/train/javascript.

After the class finishes, you should submit a solution to the problem using the link above.

Story

We want to find the missing number in a list generated by an arithmetic progression.

Problem

An Arithmetic Progression (AP) is defined as one in which there is a constant difference between the consecutive terms of a given series of numbers. You are provided with consecutive elements of an Arithmetic Progression. There is however one hitch: exactly one term from the original series is missing from the set of numbers which have been given to you. The rest of the given series is the same as the original AP. Find the missing term.

You have to write a function that receives a list, the list size will always be at least 3 numbers. The missing term will never be the first or last one.

Example:

findMissing([1, 3, 5, 9, 11]) == 7;
  1. Make sure you understand the problem. Important terms in the problem specification are Arithmetic Progression, constant difference, and consecutive terms. Discuss your definitions of these term.
  2. Discuss any questions as a group and resolve any differences before continuing.

The example was:

findMissing([1, 3, 5, 9, 11]) == 7;
  1. What is the arithmetic progression used to generate this list?
  2. Why is 7 the missing number in this example?

The test page on codewars contains the following test:

describe("Example tests", function () {
  it("Testing with [1, 3, 4]", function () {
    assert.strictEqual(findMissing([1, 3, 4]), 2);
  });
});

This test says that for the list [1, 3, 4], the expected answer is 2.

  1. What is the arithmetic progression used to generate this list?
  2. Why is 2 the missing number in this example?
  3. Create another example using a different arithmetic progression

Here are the tests I am providing today:

describe("Arithmetic progression", () => {
  test("Testing with [1, 3, 4]", function () {
    expect(findMissing([1, 3, 4])).toBe(2);
  });

  test("Testing with [1, 3, 5, 9, 11]", function () {
    expect(findMissing([1, 3, 5, 9, 11])).toBe(7);
  });

  test("Testing with [1, 5, 9, 17]", function () {
    expect(findMissing([1, 5, 9, 17])).toBe(13);
  });

  test("Testing with [7, 14, 28, 35]", function () {
    expect(findMissing([7, 14, 28, 35])).toBe(21);
  });

  test("Testing with [1, 5, 7, 9]", function () {
    expect(findMissing([1, 5, 7, 9])).toBe(3);
  });

  // and a challenge: does your solution also pass these tests
  test("Testing with [[5, 0, -5, -15, -20]]", function () {
    expect(findMissing([5, 0, -5, -15, -20])).toBe(-10);
  });

  test("Testing with [[-5, -15, -20]]", function () {
    expect(findMissing([-5, -15, -20])).toBe(-10);
  });
});
  1. Make a list of all the features of the problem that look important. Ignore anything that you think is not essential to solving the problem.
  2. Discuss your solution to this step as a group. Does everyone have the same list of important elements or are there differences? Resolve your differences so everyone agrees what is important.

In an arithmetic progression we have:

  1. A starting number
  2. An ending number
  3. The difference between consecutive numbers in the full sequence is constant
  4. If we know the difference between consecutive numbers, we can predict the next number in the sequence

We can split our problem into TWO steps

Example One

Lets say we are given the list [1, 5, 7, 9]

Ex1, Step 1

In the full sequence [1, 3, 5, 7, 9], the difference is 2 (easy for us to see but not easy for a computer).

Ex 1, Step 2

To find the missing number, we start with the first item in the list, which is 1, add the difference (1 + 2) and expect the next value in the sequence to be 3. The next value is unexpectedly 5, so we know the missing number is 3.

Example Two

Lets say we are given the list [1, 3, 5, 9]

Ex 2, Step 1

In the full sequence [1, 3, 5, 7, 9], the difference is 2 (again, easy for us to see but not easy for a computer).

Ex 2, Step 2

To find the missing number, we start with the first item in the list, which is 1, add the difference (1 + 2) and expect the next value in the sequence to be 3. We repeat that exercise, adding 3 + 2 = 5 and then 5 + 2 = 7 until we see the unexpected value which is 9 and not 7. The missing value is 7.

In the full sequence [1, 3, 5, 7, 9], the difference is 2. We can also think of it as the "gaps" between terms being the list [2, 2, 2, 2]. Note that the length of the full sequence is 5 but the number of "gaps" is only 4 (ie, length of the list [2, 2, 2, 2]).

In the version we are given, with one value missing, [1, 5, 7, 9], the differences are [4, 2, 2]. The first difference is the largest one, so it is easy for us to see that there is a number missing from the sequence between 1 and 5.

Can we find an algorithm to calculate the difference?

Remember, the problem specification said:

The missing term will never be the first or last one.

This is important to our solution.

  1. How many ways can you find to compute the difference between terms from the given list (ie the list with one value missing)?
  2. We can reply on the first and last values as being present, so can you compute the difference using only the first and last values?

There is a way of computing the difference easily from the first and last value in the sequence. It relies on the fact that given the full sequence has len values in it, there are len - 1 "gaps" and this gap is constant (ie it is the same every time).

The full sequence is [1, 3, 5, 7, 9]

The gaps are [2, 2, 2, 2]. We could think of the range of the sequence (from start to finish) as being 2 + 2 + 2 + 2 = 8.

Another way of calculating the range of the sequence is to subtract the first value from the last value. In this example we get 9 - 1 = 8.

The range has to be shared equally across the four "gaps". To share 8 across four "gaps" we perform the division 8 / 4 = 2 and this value 2 is our difference.

Here is a fragment of code from step 1 of our solution:

const len = list.length; // remember the list has one item missing
const first = list[0];
const last = list[len - 1];
const range = last - first;
const difference = range / (len + 1 - 1);
// plus one because the list has a value missing and minus 1 to find the number of gaps
// we can simplify (len + 1 - 1) to len and use...
// const difference = range / len;

Can you write a solution to the whole problem now by adding the code for step 2? You can find some starter code here: starter-code.zip.

To use the starter code:

  1. Extract the zip file into a folder
  2. Open that folder in VS Code
  3. From VS code, open a new terminal in that folder.
  4. In the terminal type the command npm install
  5. To test your code run the command npm test.