Implement iterative version of recursive algorithm using stack.

variations.spec.js

import {differenceWith, isEqual} from "lodash";

export type BitArray = (0 | 1)[];

/**
 * Your task is to implement iterative version of recursive algorithm 
 * that generates all binary numbers (called "variations" here)
 * in the form (0 | 1)[] for given length, but which aren't starting 
 * with given `ignoredPattern` (see FIXME below).
 *
 * For example, having `length = 3` and `ignoredPattern = [1, 0]`
 * the result would be: [
 *       [0, 0, 0],
 *       [0, 0, 1],
 *       [0, 1, 0],
 *       [0, 1, 1],
 *       // [1, 0, 0], <-- REMOVED
 *       // [1, 0, 1], <-- REMOVED
 *       [1, 1, 0],
 *       [1, 1, 1],
 * ]
 * For more explanation, see tests below.
 *
 * @param length The number of bits (the length of the binary number)
 * @param ignoredPattern The pattern of ignored numbers
 */
function variations(length: number, ignoredPattern: BitArray = []) {
    // return variationsRecursiveOptimized(length, ignoredPattern)
    return variationsIterative(length, ignoredPattern)
}

/**
 * Recursive variant - optimized using closure (recursion with side effects)
 */
function variationsRecursiveOptimized(length: number, ignoredPattern: BitArray = []) {
    const result: BitArray[] = [];
    if (length > 0) {
        generate(0, [])
    }
    return result;

    function generate(depth: number, variation: BitArray) {
        if (ignoredPattern.length && isEqual(variation, ignoredPattern)) {
            return;
        }
        if (depth === length) {
            result.push(variation)
        } else {
            generate(depth + 1, [...variation, 0]);
            generate(depth + 1, [...variation, 1])
        }
    }
}

/**
 * Iterative variant - iterating recursion using stack
 */
function variationsIterative(length: number, ignoredPattern: BitArray = []) {
    // ... FIXME ...
    return [];
}

/* Tests */

it('should return no variations', () => {
    expect(variations(0)).toEqual([]);
});

describe('1-length variations', () => {
    it('should get 1-length variations', () => {
        expect(variations(1)).toEqual([
            [0],
            [1]
        ]);
    });

    it('should get 1-length variations without [1]', () => {
        expect(variations(1, [1])).toEqual([
            [0],
        ]);
    });

    it('should get 1-length variations without [0]', () => {
        expect(variations(1, [0])).toEqual([
            [1],
        ]);
    });
});

describe('2-length variations', () => {
    it('should get 2-length variations', () => {
        expect(variations(2)).toEqual([
            [0, 0],
            [0, 1],
            [1, 0],
            [1, 1]
        ]);
    });

    it('should get 2-length variations without [0, *]', () => {
        expect(variations(2, [0])).toEqual([
            [1, 0],
            [1, 1],
        ]);
    });

    it('should get 2-length variations without [0, 0]', () => {
        expect(variations(2, [0, 0])).toEqual([
            [0, 1],
            [1, 0],
            [1, 1]
        ]);
    });

    it('should get 2-length variations without [0, 1]', () => {
        expect(variations(2, [0, 1])).toEqual([
            [0, 0],
            [1, 0],
            [1, 1],
        ]);
    });

    it('should get 2-length variations without [1, *]', () => {
        expect(variations(2, [1])).toEqual([
            [0, 0],
            [0, 1],
        ]);
    });

    it('should get 2-length variations without [1, 0]', () => {
        expect(variations(2, [1, 0])).toEqual([
            [0, 0],
            [0, 1],
            [1, 1],
        ]);
    });

    it('should get 2-length variations without [1, 1]', () => {
        expect(variations(2, [1, 1])).toEqual([
            [0, 0],
            [0, 1],
            [1, 0],
        ]);
    });
});

it('should get 3-length variations', () => {
    expect(variations(3)).toEqual([
        [0, 0, 0],
        [0, 0, 1],
        [0, 1, 0],
        [0, 1, 1],
        [1, 0, 0],
        [1, 0, 1],
        [1, 1, 0],
        [1, 1, 1],
    ]);
});

it('should get 4-length variations', () => {
    expect(variations(4)).toEqual([
        [0, 0, 0, 0],
        [0, 0, 0, 1],
        [0, 0, 1, 0],
        [0, 0, 1, 1],
        [0, 1, 0, 0],
        [0, 1, 0, 1],
        [0, 1, 1, 0],
        [0, 1, 1, 1],
        [1, 0, 0, 0],
        [1, 0, 0, 1],
        [1, 0, 1, 0],
        [1, 0, 1, 1],
        [1, 1, 0, 0],
        [1, 1, 0, 1],
        [1, 1, 1, 0],
        [1, 1, 1, 1],
    ]);
});

describe('5-length variations', () => {

    const all5LengthVariations = [
        [0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1],
        [0, 0, 0, 1, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 1, 0, 0],
        [0, 0, 1, 0, 1],
        [0, 0, 1, 1, 0],
        [0, 0, 1, 1, 1],
        [0, 1, 0, 0, 0],
        [0, 1, 0, 0, 1],
        [0, 1, 0, 1, 0],
        [0, 1, 0, 1, 1],
        [0, 1, 1, 0, 0],
        [0, 1, 1, 0, 1],
        [0, 1, 1, 1, 0],
        [0, 1, 1, 1, 1],
        [1, 0, 0, 0, 0],
        [1, 0, 0, 0, 1],
        [1, 0, 0, 1, 0],
        [1, 0, 0, 1, 1],
        [1, 0, 1, 0, 0],
        [1, 0, 1, 0, 1],
        [1, 0, 1, 1, 0],
        [1, 0, 1, 1, 1],
        [1, 1, 0, 0, 0],
        [1, 1, 0, 0, 1],
        [1, 1, 0, 1, 0],
        [1, 1, 0, 1, 1],
        [1, 1, 1, 0, 0],
        [1, 1, 1, 0, 1],
        [1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1],
    ]

    it('should get 5-length variations', () => {
        expect(variations(5)).toEqual([
            ...all5LengthVariations
        ]);
    });

    all5LengthVariations.forEach(variation => {
        it(`should get 5-length variations without ${JSON.stringify(variation)}`, () => {
            expect(variations(5, variation as BitArray)).toEqual(
                differenceWith(all5LengthVariations, [
                    variation
                ], isEqual)
            );
        });
    })

    it('should get 5-length variations without [0, *, *, *, *]', () => {
        expect(variations(5, [0])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 1],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 1],
                [0, 0, 1, 0, 0],
                [0, 0, 1, 0, 1],
                [0, 0, 1, 1, 0],
                [0, 0, 1, 1, 1],
                [0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [0, 1, 0, 1, 0],
                [0, 1, 0, 1, 1],
                [0, 1, 1, 0, 0],
                [0, 1, 1, 0, 1],
                [0, 1, 1, 1, 0],
                [0, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 0, *, *, *]', () => {
        expect(variations(5, [0, 0])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 1],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 1],
                [0, 0, 1, 0, 0],
                [0, 0, 1, 0, 1],
                [0, 0, 1, 1, 0],
                [0, 0, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 0, 0, *, *]', () => {
        expect(variations(5, [0, 0, 0])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 1],
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 0, 0, 0, *]', () => {
        expect(variations(5, [0, 0, 0, 0])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 0, 0, 0],
                [0, 0, 0, 0, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 0, 0, 1, *]', () => {
        expect(variations(5, [0, 0, 0, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 0, 1, 0],
                [0, 0, 0, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 0, 1, *, *]', () => {
        expect(variations(5, [0, 0, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 0, 1, 0, 0],
                [0, 0, 1, 0, 1],
                [0, 0, 1, 1, 0],
                [0, 0, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 1, 0, *, *]', () => {
        expect(variations(5, [0, 1, 0])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [0, 1, 0, 1, 0],
                [0, 1, 0, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 1, 1, *, *]', () => {
        expect(variations(5, [0, 1, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 1, 1, 0, 0],
                [0, 1, 1, 0, 1],
                [0, 1, 1, 1, 0],
                [0, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, *, *, *, *]', () => {
        expect(variations(5, [1])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 0, 0, 0, 0],
                [1, 0, 0, 0, 1],
                [1, 0, 0, 1, 0],
                [1, 0, 0, 1, 1],
                [1, 0, 1, 0, 0],
                [1, 0, 1, 0, 1],
                [1, 0, 1, 1, 0],
                [1, 0, 1, 1, 1],
                [1, 1, 0, 0, 0],
                [1, 1, 0, 0, 1],
                [1, 1, 0, 1, 0],
                [1, 1, 0, 1, 1],
                [1, 1, 1, 0, 0],
                [1, 1, 1, 0, 1],
                [1, 1, 1, 1, 0],
                [1, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, 1, *, *, *]', () => {
        expect(variations(5, [1, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 1, 0, 0, 0],
                [1, 1, 0, 0, 1],
                [1, 1, 0, 1, 0],
                [1, 1, 0, 1, 1],
                [1, 1, 1, 0, 0],
                [1, 1, 1, 0, 1],
                [1, 1, 1, 1, 0],
                [1, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, 1, 1, *, *]', () => {
        expect(variations(5, [1, 1, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 1, 1, 0, 0],
                [1, 1, 1, 0, 1],
                [1, 1, 1, 1, 0],
                [1, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, 1, 1, 1, *]', () => {
        expect(variations(5, [1, 1, 1, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 1, 1, 1, 0],
                [1, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, 0, *, *, *]', () => {
        expect(variations(5, [1, 0])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 0, 0, 0, 0],
                [1, 0, 0, 0, 1],
                [1, 0, 0, 1, 0],
                [1, 0, 0, 1, 1],
                [1, 0, 1, 0, 0],
                [1, 0, 1, 0, 1],
                [1, 0, 1, 1, 0],
                [1, 0, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [1, 1, *, *, *]', () => {
        expect(variations(5, [1, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [1, 1, 0, 0, 0],
                [1, 1, 0, 0, 1],
                [1, 1, 0, 1, 0],
                [1, 1, 0, 1, 1],
                [1, 1, 1, 0, 0],
                [1, 1, 1, 0, 1],
                [1, 1, 1, 1, 0],
                [1, 1, 1, 1, 1],
            ], isEqual)
        );
    });

    it('should get 5-length variations without [0, 1, *, *, *]', () => {
        expect(variations(5, [0, 1])).toEqual(
            differenceWith(all5LengthVariations, [
                [0, 1, 0, 0, 0],
                [0, 1, 0, 0, 1],
                [0, 1, 0, 1, 0],
                [0, 1, 0, 1, 1],
                [0, 1, 1, 0, 0],
                [0, 1, 1, 0, 1],
                [0, 1, 1, 1, 0],
                [0, 1, 1, 1, 1],
            ], isEqual)
        );
    });
});