k-prime sum problem with jasmine specs

A friend of mine liked a programing problem on Facebook. The header say something like: 90% of silicon valley engineers take more than 20 minutes to solve this problem. Sounds like an intrigue lure, huh? Not sure if they actually clicked like it or it's just Facebook that wants me to see. Anyway, I think it maybe fun to do some Javascript testing. This is not a code walk-through but rather a narrative of how I come to the final code. So you may want to read the code first. It is in the end.

Lets dive into to it, shall we? Following is the problem's description. I included it in the code in the very end.

The K-prime sum problem

Description

A number is called a k-primeSum if it can be represented as a sum of k (not necessarily distinct) prime numbers. Implement a function that checks if the given number is k-primeSum or not.

Example

For n = 9 and k = 3, the output should be
isKPrimeSum(n, k) = true.

We can represent 9 as 2 + 2 + 5.

Input/Output

• [time limit] 4000ms (js)

• [input] integer n

Constraints:
1 ≤ n ≤ 250.

• [input] integer k

Constraints:
1 ≤ k ≤ 5.

• [output] boolean

true if n is a k-primes sum, false otherwise.

Let me solve it

1. How do I know that I've solved it? I tested it, right?

How can I test it? I need to have it first! Here it is:

const isKPrimeSum = (n, k) -> { return true; }

The function isKPrimeSum receives 2 integers: n and k and returns a boolean: whether n is a sum of k primes.

I need to build cases which I know the correct answer!

This is about prime numbers so I need a prime numbers list. Well, that is easy.

let primes = [2, 3, 5, 7, 11]; //Prime numbers from the sky

There I have it. What next?

1.1 Simple test cases

As a rule of thumbs, simple cases go first. What is the easiest case?

A prime number is a 1-prime sum.

And here is the tests:

it('a prime is a sum of one prime number by the prime itself', () => {
  primes.forEach(prime => {
    let message = `Expect isKPrimeSum(${prime}, 1) to returns true because ${prime} is a prime!`;
    expect(isKPrimeSum(prime, 1)).toBe(true, message);
  });
});

Looks good, huh? For each prime number that I have, I expect isKPrimeSum(prime, 1) to return true. Otherwise, I will see messages telling me the function is failed with which inputs. I have multiple cases there. But I only write one test with multiple expectations. These messages will come in handy.

Getting this first test to pass is not very simple. Think about it. But I can't stop there. I need to add more nontrivial cases.

1.2 Lets get serious!

As I planed all along, let me build some problems that I know how to solve. I will start small.

Sum of 2 primes is 2-prime sum.

Lets check all pair of 2 primes. No need to be different primes. Here is it:

it('Sum of 2 primes is 2-prime sum', () => {
  primes.forEach(prime1 => {
    primes.forEach(prime2 => {
      let message = `Expect isKPrimeSum(${prime1 + prime2}, 2) to returns true because ${prime1 + prime2} = ${prime1} + ${prime2}`;
      expect(isKPrimeSum(prime1 + prime2, 2)).toBe(true, message);
    });
  })
});

Pretty obvious, huh? I input sums of 2 primes and expect isKPrimeSum to say it is 2-prime sum.

The test is nice excepts one thing. If prime1 + prime2 > (Maximum value of n that I need to solve), I don't have to solve it. I shouldn't expect my isKPrimeSum to return the correct answer. So, I need to know the limits. My test won't pass if my expectations are too high.

I leave the details to the code that I'll post later. Lets move on.

1.3 Got stuck! huh?

How can I continue to test this thing? I tried to go with all group of 3 primes but that is bad. The test run very slow. Think about it! The number of prime less than n is O(n/ln(n)). Then the number of 2 primes pair (no distinction) is O(n^2/ln(n)^2) which is big. Then the number of 3 primes pair is O(n^3/ln(n)^3) which is just huge!

It can get worse! Even if I can go with the k = 3 case. How about the k = 4 and the k = 5 cases? A little bigger cases?

I'll need to find other strategies to test this.

1.4 Randomization is the rescue!

It is best if I can cover all cases. But when I can't, some cases are just as good. The question is how to pick a set of good cases.

But I have no idea about what make a good case. I will go with randomization. When my test failed with some particular cases, I will know about that cases and I can capture these in a separated test for future regression. How nice!

The test go like this:

it('500 randomization test cases from 1 to 5 primes sum', () => {
  for(let testIndex = 0; testIndex < 500; testIndex ++) {
    let numberOfPrimes = getRandomInt(1, 5);
    let primeElements = [];
    for(let i = 0; i < numberOfPrimes; i++) {
      let index = getRandomInt(0, primes.length - 1);
      primeElements.push(primes[index]);
    }

    let sum = primeElements.reduce((a, b) => a + b, 0)
    if(sum < N_UPPER_BOUND) {
      let message = `Expect isKPrimeSum(${sum}, ${numberOfPrimes}) to returns true because ${sum} = ${primeElements.join(' + ')}`;
      expect(isKPrimeSum(sum, numberOfPrimes)).toBe(true, message);
    }  
  }
});

2. Lets get to the "real" code

Fortunately, the real code is much more simple than the tests so that I can keep this post focus about testing. Following are the highlights.

2.1 How to get lots of prime numbers?

So we need prime numbers, right? A quick and easy way to get many prime numbers at once is using a prime sieve. Following is the famous Sieve of Eratosthenes algorithm:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
      A[j] := false

Output: all i such that A[i] is true.

2.2 A short demo of Dynamic programming

But what I have is the opposite of what I need. I need to decide if a number n is a sum of k prime numbers. It is about breaking down n into k prime numbers. But what can I do with a list of prime numbers? I can only sum them up.

Well, if I can sum them up then sum them up. I know about Dynamic programming, right? Here it come:

Lemmas:

1. n is a k-prime sum number if one the following is true
   • k = 1 and n is a prime
   • (n - p) is a (k-1)-prime sum number for some prime p
2. n is a k-prime sum number only if one of 2 cases above is true.

The essential of Dynamic programing technique is how to capture the 2 lemmas above. But there I have it :). Proving these 2 is not the subject of this post.

That is it. Here is the code.

Actually, not that fast. Here is the fun part:

3. Why I need to test my code?

With the test in place, now I can refactor my code. Notice the code here:

for(let composite = i * i; composite < N_UPPER_BOUND; composite += i) {
  // Since `composite` is an composite number which is divisible by i, `composite` is NOT a 1-sum primes.
  // _memoize[1][composite] = KPrimeSumAtIndex.no; 
  _primeEratosthenes[composite] = KPrimeSumAtIndex.no; 
}

I think I can improve its performance by stop the for loop a bit earlier. I don't have to wait until composite get increase all the way up to N_UPPER_BOUND.

May be I can do this:

let limit = Math.round(Math.sqrt(N_UPPER_BOUND));
//> Now I only check up to limit which is less than N_UPPER_BOUND, huh?
for(let composite = i * i; composite < limit; composite += i) {
  _primeEratosthenes[composite] = KPrimeSumAtIndex.no; 
}

After I edit the code, the test run and it is still passing, yay!

How is it possible that I can stop the loop there? Actually, I my code works and I don't know why! Please share with me if you have clues.

4. Tests are code, refactor them too!

I edit the pen above in a very simple way. I increased N_UPPER_BOUND from 251 to 255551. Then my browser tab is dead!

Where is the problem? What is the most complex test?

It is the second test which have the biggest upper bound right?
I commented it out and I can now test a lot bigger number comparing to the original problem. And it is still fast.

But I decided that determination test is better than randomization test. So I limit the number of primes for the second test to 100:

it('Sum of 2 primes is 2-prime sum', () => {
  let smallPrimes = primes.slice(0, 100);
  smallPrimes.forEach(prime1 => {
    smallPrimes.forEach(prime2 => {
      if(prime1 + prime2 < N_UPPER_BOUND) {
        let message = `Expect isKPrimeSum(${prime1 + prime2}, 2) to returns true because ${prime1 + prime2} = ${prime1} + ${prime2}`;
        expect(isKPrimeSum(prime1 + prime2, 2)).toBe(true, message);
      }
    });
  });
});

Then I have it back again. Fast, useful tests. Here is the final code