## 1. Project Overview & Quickstart (dubzzz/CONTRIBUTING)

# CONTRIBUTING

Open-source repository dubzzz/CONTRIBUTING

### Repository Details
- **Repository:** [dubzzz/CONTRIBUTING](https://github.com/dubzzz/CONTRIBUTING)
- **Primary Language:** Code

*Note: High-volume repository documentation is actively indexed and synchronized by YakaAI.*

## 2. Official Technical Reference & Guides (dubzzz/dubzzz.github.io)

## File: README.md

# Various articles about computer science

## Testing

- Property based testing

---

## File: articles/2017-02-27_Return_true_to_win.md

# Breaking down *return true to win* using properties

The idea of *return true to win* exercises is to build a value such as a given function returns `true`. Values can be of any type but can also be restricted to objects, arrays, functions depending on the problem statement. 
This article focuses on applying property based testing to solve such problems.

Examples of such puzzles are available at: https://alf.nu/ReturnTrue

A proof of concept based on [fast-check](https://github.com/dubzzz/fast-check) framework is available at https://github.com/dubzzz/breaking-return-true-to-win/tree/master

## Property based testing

Property based testing originally born for testing reasons. Its purpose is to find out values that make a property fail. A property can be described as any statement like:

    Given inputs satisfying a pre-requisite,
    The statement is true

Whenever a failing input is encountered (ie. the statement is false), the framework shrinks it to the minimal failing input. It constitutes one of the most important and useful feature of this methodology as it gets automatically rid of all the unnecessary noise surrounding the failing case.

## Application to *return true to win*
  
*Return true to win* statements can easily be switched to a property based testing statement.

Let's take the following example:

Find a JavaScript expression such as: `x == !x`

Instead of looking for falsy values we look for truthy ones. So we just have to take the negative and we get the corresponding property.

## Implementation

Given that, implementation using [fast-check](https://github.com/dubzzz/fast-check) is quite straight forward. For instance, our implementation could have been the following:

```js
function negationEqualsOriginal(x) {
    return x == !x;
}
fc.assert(
    fc.property(
        fc.anything(),
        x => ! negationEqualsOriginal(x)
    )
);
```

Let's take a look at this implementation a bit closer:
- `fc.assert` is responsible to execute the property multiple times in an attempt to check for potential issues. It also handles the shrinking part in order to output values as small as possible (no need to have an object with hundreds of keys, if a single key makes it fail)
- `fc.property` declares the property in terms of what it takes for input and how to assess it worked properly
- `fc.anything()` is an arbitrary object, it is responsible to generate any possible object or primitive. We can use multiple arbitraries for a same property just by putting them directly after the first one. For more details on this, have a look to the [documentation of fast-check](https://github.com/dubzzz/fast-check/blob/master/README.md)
- `x => ! negationEqualsOriginal(x)` is the predicate that the framework expect to see always true. In our case we want it to find the case where it becomes falsy

What about shrinking?

In the example above both `[[[[undefined]]]] == ![[[[undefined]]]]`, `[undefined] == ![undefined]` or `[] == ![]` are `true` but due to shrinking the framework will only provide us the minimal failing example which would be the empty array in this case.

## Going further

Our approach is quite complete but it might accept false positives. Indeed, with the above construction we consider an exception as a `true`. Instead of simply taking the negation we should takes something like:

```js
const wrapIt = function(fn) {
    return (...args) => {
        try { return !fn(...args); }
        catch (err) { return true; }
    };
};
```

And replace `x => ! negationEqualsOriginal(x)` by `x => wrapIt(negationEqualsOriginal)(x)`.

## Conclusion

Using this technic we can easily solve problems that require to find out structures such as arrays, strings or objects. Making it work for examples with functions or manipulations of types through the usage of prototype would require more work and the creation of adapted arbitraries to generate the inputs.

The proof of concept is available on https://github.com/dubzzz/breaking-return-true-to-win

## Published on...

https://medium.com/@nicolasdubien/breaking-down-return-true-to-win-using-properties-1e2a3eac2a80

---

## File: drafts/Need_for_pure_random_generators.md

# Need for pure (functional) random generators

Pure random generators can be seen as the combination of two distincts areas of devlopment.
On one side, functional laguages where everything must be pure*.
On the other side, random number generators where the aim is to escape from determinism.

*pure: given an input `x` a function `f` should always return the same output value for `x`

By resorting to an example this story aims to convince of the value of such tool.
It describes the reasons that pushed me to write my own [pure PRNG library for JavaScript and TypeScript](https://github.com/dubzzz/pure-rand).

## Diving into the example

The project we are working on is: building a tic tac toe game for a single player against an IA.
Our IA is very basic, it acts by choosing at random one of the remaining cells of the grid.
We are really proud of our project but we already experienced multiple issues while trying to reproduce failing cases.

One of the main problem with random is that by definition it should not be predictible.
Hopefully computer science has pseudo random number generators or PRNG.
Those generators provide what seems to be perfectly random except that behind the hood they just do very deterministic operations.
A very simple PRNG might look like:

```javascript
class Random {
  constructor(seed) {
    this.last = seed;
  }
  nextInt (from, to) {
    const v = this.last % (to - from +1) +from;
    this.last = (97 * this.last + 11) % 997;
    return v;
  }
}
```

Even if they look very simple and too predictible, PRNG are really powerful.
The one above is really a too simple one but some PRNG are used for cryptography or security issues.
The latest are called cryptographic pseudo random generator or CPRNG.

For even greater entropy but no predictibility at all, there are hardware random generators.
They provide random based on the entropy of the system and its environment (mouse move, temperature, pressure...).
Their output is theoretically unpredictable at all and cannot be seeded in any mean.
They are definitely not a good candidate to help us in investigating the issues we described above: not able to reproduce the problem.

PRNG on the other hand and perfectly adapted to help us.
Given we refactored our code to use one of these we should be able to replay a game state.
In order to replay, we should be provided with the set of all moves done by the player and the initial seed.
Most of programming languages offer a random class that can be seeded easily.

## Going pure

Now that we have unlocked a way to reproduce our games, we want to go a bit further and start adding new features in the game.
The main feature we want to add is a simple undo-redo mechanism with unlimited number of undos.

In a way the implementation looks pretty simple.
We just have to cancel both IA and player move and it works fine.

In reality it does not work so well.
For instance, if we cancel a move and replay the same move we reach (possibly) another state.
Indeed each time call `next` method on classical PRNG we get another random value.
The only property we have is that the whole generated sequence will always be the same for one seed.

```javascript
// Game State: all moves
[]             // no one played
['0-0', '0-1'] // player played 0-0, IA played 0-1
[]             // player canceled
['0-0', '2-1'] // player played 0-0 again, we ask a new random value to the PRNG
```

So we have in a way to keep track of what was generated.
A clever developer might come with the idea: OK while the player does not change its mind by doing a really different move we just keep the steps we went by.

```javascript
// Game State: num moves, all moves
0, []             // no one played
2, ['0-0', '0-1'] // player played 0-0, IA played 0-1
0, ['0-0', '0-1'] // player canceled, we keep track of the steps just in case it played the same
2, ['0-0', '0-1'] // player played 0-0 again, we just take what we computed previously for IA
```

In reality it only postpone the problem. It makes it even more difficult to analyze.
Indeed, we just have to cancel, play a different move, cancel again and replay the first move to change the state again.

```javascript
// Game State: num moves, all moves
0, []             // no one played
2, ['0-0', '0-1'] // player played 0-0, IA played 0-1
0, ['0-0', '0-1'] // player canceled, we keep track of the steps just in case it played the same
2, ['0-1', '1-1'] // player played 0-1, IA played 1-1
0, ['0-1', '1-1'] // player canceled, we keep track of the steps just in case it played the same
2, ['0-0', '2-1'] // player played 0-0 again, we ask a new random value to the PRNG
```

Moreover, the whole debugging process described above becomes a nightmare as it has to keep in mind all the cancelations and replays that occurred. Indeed if you take a look to the line `2, ['0-1', '1-1'] // player played 0-1, IA played 1-1` you should see that it is the second time that the PRNG has been called while its only the first move of the IA.

Another solution or workaround to solve this whole problem, would be to re-seed the generator and replay all the moves from the very beginning each time we cancel. It should work, but the more we played steps the more it will take time to cancel one.

## Pure random generator

Before going further, let's just see how a pure random generator looks like.
It can be seen as a generator able to produce only a single value along with the next generator (for the next random number).
It's signature might look like:

```typescript
interface RandomGenerator {
    next(): [number, RandomGenerator]
}
```

If we apply it to the problem above we might be able to fix our problem more easily.
Indeed instead of keeping possible futures, we just have to store the generator along all the moves.
The game management might look like this:

```javascript
// Game State: all prng, all moves
[]            []             // no one played
[prng1, prng2]['0-0', '0-1'] // player played 0-0, IA played 0-1
[]            []             // player canceled, we keep track of the steps just in case it played the same
[prng1, prng3]['0-1', '1-1'] // player played 0-1, IA played 1-1
[]            []             // player canceled, we keep track of the steps just in case it played the same
[prng1, prng2]['0-0', '0-1'] // player played 0-0 again, we ask a new random value to the PRNG
```

---

## File: drafts/Property_based_testing.md

# What is Property Based Testing?
## Another test philosophy

Property based testing has become quite famous in functional world. Mainly introduced by **QuickCheck** framework in **Haskell**, it suggests another way to test software. It targets all the scope covered by example based testing: from unit tests to integration tests.

In order to introduce property based testing, this article will use [fast-check](https://github.com/dubzzz/fast-check) framework written for JavaScript and TypeScript but examples can easily be converted for other frameworks.

## Existing ways

Multiple ways are currently used in the industry in order to prove the correctness of a code.

Here are some of those technics:
- static code analysis: It provides useful hints on potential harmful usages of the language. It can prove very useful in typed languages by raising flags when it encounters an issue.
- example-based testing: It is certainly the most widespread way of testing. It relies on the fact that for a given set of inputs, the algorithm should produce an already known output. It goes far beyond unit tests as this method can also be part of integration, QA-testing...
- proved code: It proves the code mathematically by checking one by one, loop by loop that all the invariants stay true whatever the provided values.
- crash under random: It tends to make a program crash under random inputs - Monkey Testing - or random data - Fuzzing.

## Definition

Property based testing relies on properties. It checks that a function, program or whatever system under test abides by a fixed property. Most of the time, properties do not have to go into too much details about the output. They just have to check for useful characteristics that must be seen in the output.

A property is just something like:

    for all (x, y, ...)
    such as precondition(x, y, ...) holds
    property(x, y, ...) is true

Before explaining how a test executor will understand and execute it, here is a simple _hello world_ property:

    for all (a, b, c) strings
    the concatenation of a, b and c always contains b

In other words, without any precise knowledge of the shape and content of the strings `a`, `b` and `c` I can surely say that `b` is a substring of `a + b + c`.

The executor understanding of a property can be summarized as:

|Property   |Executor understanding |
|-----------|-----------------------|
|for all    |run it _multiple_ times (usually 100 times)|
|(x, y, ...)|generate random inputs based on specified generators (x, y, ... specifies the kind of input to be generated)|
|such as precondition(x, y, ...) holds|check pre-conditions (**failure**: go back to previous, not an error just an invalid entry)|
|property(x, y, ...) is true|run the test (**failure**: it is a counter-example, try to shrink the example)|

## Benefits

They are numerous advantages to this approach:

- Reproducible: each time it runs a property test, a seed is produced in order to be able to re-run the test again on the same datasets.
- Cover the scope of all possible inputs: it does not limit itself to restricted sets of inputs and can cover the whole range of strings, integers or whatever type required by the system under tests.
- Shrink the input in case of failure: whenever it fails, the framework tries to reduce the input to a smaller input. For instance: if the condition of the failure is the existence of a given character in a string it should return the one-character string having only this character.

It is also important to note that it does not - by any means - replace unit testing. It only provides an additional tool that might prove very efficient to reduce some boilerplate tests. 

## Shrinking through example

In order to get a better understanding of shrinking I will develop a bit more the example described above. Interactive code example is available on RunKit: https://runkit.com/dubzzz/contains-example

The property we wanted to check was the following:

    for all (a, b, c) strings
    the concatenation of a, b and c always contains b

Let's assume we have a function called `contains` doing the check. In [fast-check](https://github.com/dubzzz/fast-check) we would simply write:

```js
const fc = require('fast-check');

fc.assert(
    fc.property(
            fc.string(), fc.string(), fc.string(),
            (a, b, c) => contains(b, a+b+c))
);
```

Where:
- `fc.assert((, parameters))`: It executes the test and checks that the property stays true for all the `a, b, c` strings produced by the framework. In case of failure, it shrinks the input to the minimal failing example to help the user during its analysis. By default, it runs the property against 100 generated inputs.
- `fc.property(<...arbitraries>, )`: It describes the property. `arbitraries` are the instances responsible to build the inputs while `predicate` is the function doing the test against those inputs. `predicate` should either return a `boolean` or not return anything and throw in case of issue.
- `fc.string()`: It is an arbitrary able to generate and shrink random strings.

If you wonder what are the generated inputs you can replace `fc.assert` by `fc.sample` as follow:

```js
fc.sample(
    fc.property(
            fc.string(), fc.string(), fc.string(),
            (a, b, c) => contains(b, a+b+c))
);
```

You might get generated inputs like:

```
{"a":"=]n#","b":"bs;","c":",r="}
{"a":"CTh7kqc0<","b":"Lr/U+1L`MV","c":"''"}
{"a":"v3.=^>~GS","b":"","c":"0"}
{"a":"","b":"3i","c":"#AP"}
{"a":"N!dAvi","b":"[p23lh","c":"e"}
...
```

Let's suppose that we have the following implementation of `contains` which obviously does not work:

```javascript
const contains = (pattern, text) => {
    return text.substr(1).indexOf(pattern) !== -1;
};
```

The framework will generate multiple inputs and as soon as it finds a failing case it will start the shrinking process. If we take the example above, when running it locally I got a first failure for the entry `{"a":"","b":"I?29S\\~","c":""}`, then the shrinking path was the following:

```javascript
{"a":"","b":"I?29S\\~","c":""} // first failure encountered: start shrinking process
{"a":"","b":"","c":""}
{"a":"","b":"9S\\~","c":""}
{"a":"","b":"","c":""}
{"a":"","b":"\\~","c":""}
{"a":"","b":"","c":""}
{"a":"","b":"~","c":""}
{"a":"","b":"","c":""}
{"a":"","b":" ","c":""} // the last failing case
{"a":"","b":"","c":""}
```

## Going further

Property based testing is a useful and powerful tool. I personally used it against multiple problems going from testing famous npm repositories to personal snippets. Here are some of the interesting topics I covered with this kind of tool.

### Bug in famous npm packages: js-yaml

While [js-yaml](https://www.npmjs.com/package/js-yaml) is a 1 million downloads per day package, property based testing was able to find a problem in it. The story is available at https://github.com/nodeca/js-yaml/pull/398 and the test at https://runkit.com/dubzzz/multiple-properties-for-js-yaml

Basically I adopted a black-box technic to test it against the most simple property possible: whatever the object I convert into yaml, I should be able to have it back by reading the generated yaml.

### Scenario not covered by units

[Shadows of the knight](https://www.codingame.com/training/medium/shadows-of-the-knight-episode-1) is a programming puzzle available on [CodinGame](https://www.codingame.com/) platform.

While my implementation was passing all the tests provided by the platform, it contained a bug. The property based testing was able to find it.

The source code of the example is available at: https://runkit.com/dubzzz/codingame-example

### UI testing

Certainly one of the most surprising usage is to derive it for UI testing.
I do use it to replace QA checks sometimes and it works pretty well.

For instance I tested a 2048 written in Scala using this technic: https://dubzzz.github.io/scala-2048/

## Conclusion

I highly recommend that you give it a try on some snippets.

By using it you will see how simply it can be used to diagnose and find issues.
A next story should come soon to provide useful hints concerning how you can find efficient properties for your algorithms.
So stay tune and leave a comment if you liked it or have suggestions.