Bạn có chắc chắn muốn xóa bài viết này không ?

Bạn có chắc chắn muốn xóa bình luận này không ?

#
**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

goodcases.

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:

`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`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