DEV Community: Yigal Ziskand

Palindrom implementation with TDD'sh approach

Yigal Ziskand — Sun, 27 Jun 2021 21:39:52 +0000

Disclaimer

Before we start i would like to make a disclaimer - we are not going to dig into the holly war of speed vs quality in software development terms, neither we will be comparing tests approaches.

Motivation

We want to find a handy approach for testing our code - some magical way that won't require spending extra time and afford for testing.

Basic Idea

Let's break down the way we (or should i say i...) usually approach new problem.

acknowledge the problem by going over it's details
figure out the way to solve the problem - logical solution
provide code implementation for the logical solution
validate solution correctness

Hmm... let's try to switch step 3 and 4 and see what we got

acknowledge the problem by going over it's details
figure out the way to solve the problem - logical solution
validate solution correctness
provide code implementation for the logical solution

Sweet! So this is how it works! Simply do the tests before you write your code...
Hmmm, hold on a second - what do we test exactly, there's no code to test yet... weird situation...

Well... The answer is a bit philosophical - after we accomplished step 1 & 2 you should find yourself in the position where we have a complete logical solution to the problem and by saying that - you know the exact logical flow and its logical boundaries!

That is exactly what we need!

First we will write tests for the logical solution! Then we will execute the tests (and surprisingly they will fail... i guess it makes scene, since there is no actual code implementations at this point)
And finally, in order to make the tests pass we will add the code implementation.

This way we can be sure that our code implementation does exactly what we had targeted in step 2

Example (Numerical Palindrome)

Let's peek up a problem of defining numerical Palindrome Object which is self sufficient in a way that:

it can be created with any input type
it can be questioned on its value
it can return whether it is a valid numerical palindrome

So let's break it down into 1,2,3,4 steps:

The details of the description are the following:
- input type: any
- the object should manage it's internal state
- provide public methods
  - getter(): returns initial input values
  - isValid(): return boolean
Pseudo code for logical solution:

    // provided in requirements
    if user_input not number return false
    // negative number cant be palindrome
    if user_input is less then 0 return false
    // any positive number in range of 1 to 10 is valid palindrome
    if user_input is in range of 1..10 return user_input

    // if number is bigger then 10, 
    // then we shall gradually divide our initial user_input into
    // left-comparison half & right-comparison half
    // once we divided into two halfs
    // we shall compare the halfs and return the comparison result
    while left-comparison-half > right-comparison-half
        // collect the most right number from user_input
        // to the right-comparison half
        right-comparison-half: collect user_input's most right number

        // remove the most right number from the left-comparison half
        left-comparison-half: = remove user_input's most right number


    // compare the collected halfs and return the result
    return left-comparison-half === right-comparison-half

Let's write our expectation from the logical solution

I am using Jest library npm i -D jest
You might find useful to adjust your test command to watch over the files so the tests will be re-executed on every file change
"scripts": { "clear_jest": "jest --clearCache", "test": "jest --watchAll --verbose" },

describe("Numeric Palindrome", () => {
    it.todo("should be initialized with any input type")
    it.todo("should be able to manage it's state")
    it.todo("validation method should be defined")
    it.todo("return false if data is not numeric")
    it.todo("return false if negative number")
    it.todo("return false if data is 10 dividable")
    it.todo("return true if data is smaller then 10")
    it.todo("return true if legal palindrome")
    it.todo("return false if not legal palindrome")
})

Great start!

It's important to mention that no matter how scary-spaghetti our code will be, we know one thing for sure - it will be well defined Palindrome!

- Let's make our first test fail, by modifying

it.todo("should be initialized with any input type")

- into:

    it("should be initialised with any input type",
        () => {
            const palindromInstances = [
                new Palindrome("abc"),
                new Palindrome(),
                new Palindrome(1),
                new Palindrome({})
            ]

            palindromInstances.forEach(instance => expect(instance).toBeDefined())
        }
    );

and if we look at our test result we will find the exact reasons

Yes, of course we should create a proper Palindrome class and define it's constructor, so lets do it

class Palindrome {
    constructor() { }
}

module.exports = Palindrome

and of course don't forget to import it into our test

const Palindrome = require('./numeric-palindrome')

describe("Numeric Palindrome", () => {

Well done, we got our first test fulfilled. Let's continue with the next one...
- modify:

it.todo("should be able to manage it's state")

- into:

    it("should be able to manage it's state", () => {
        const palindromeOne = new Palindrome('1');
        const palindromeTwo = new Palindrome();
        const palindromeThree = new Palindrome(1);

        expect(palindromeOne).toHaveProperty("data", "1");
        expect(palindromeTwo).toHaveProperty("data", "");
        expect(palindromeThree).toHaveProperty("data", 1);
    })

check why the test failed and adjust the Palindrome implementation with a getter method and a default value

class Palindrome {
    constructor(userInput = '') {
        this._data = userInput
    }

    get data() {
        return this._data
    }
}

Yaay - the test passes, Let's move to the next one...
- modify:

it.todo("validation method should be defined")

- into:

    it("validation method should be defined", () => {
        const palindrome = new Palindrome()

        expect(palindrome.isValid()).toBeDefined()
    })

and of course it fails... So let's fix it

class Palindrome {
    constructor(userInput = '') {
        this._data = userInput
    }

    get data() {
        return this._data
    }

    isValid() {
        return false
    }
}

Good job, we've made it again... Let's move on
- modify:

it.todo("return false if data is not numeric")

- into:

   it("return false if data is not numeric", () => {
        const notNumeric = [new Palindrome("a"), new Palindrome(), new Palindrome({})]

        notNumeric.forEach(x => expect(x.isValid()).toBeFalsy())
    })

check the failed test and fix the implementation....

class Palindrome {
    constructor(userInput = '') {
        this._data = userInput
    }

    get data() {
        return this._data
    }

    isValid() {
        if (!Number.isInteger(this._data)) {
            return false
        }

        return true
    }
}

and once again, let's go into our next test requirement
- modify:

it.todo("return false if negative number")

- into:

 it("return false if negative number", () => {
     const negativeNumber = new Palindrome(-1)

     expect(negativeNumber.isValid()).toBeFalsy()
 })

check the failed test and fix the implementation....

isValid() {
        if (!Number.isInteger(this._data)) {
            return false
        }

        if (this._data < 0) {
            return false
        }

        return true
    }

Well i think at this point you got the idea of how it works and how it looks...

In summery:
- Create the test that should checking some condition in your logical solution
- Execute it and check the failing reasons
- Adjust the code implementation so the test pass
- And don't forget to refactor

Code Snippet

I did not refactor the code at any point so every additional line is followed by the corresponded test requirement - i hope this way you can follow the test-fail-implement process easier

// requiriments
const Palindrome = require('./numeric-palindrome')

describe("Numeric Palindrome", () => {
    it("should be initialised with any input type",
        () => {
            const palindromInstances = [
                new Palindrome("abc"),
                new Palindrome(),
                new Palindrome(1),
                new Palindrome({})
            ]

            palindromInstances.forEach(instance => expect(instance).toBeDefined())
        }
    );
    it("should be able to manage it's state", () => {
        const palindromeOne = new Palindrome('1');
        const palindromeTwo = new Palindrome();
        const palindromeThree = new Palindrome(1);

        expect(palindromeOne).toHaveProperty("data", "1");
        expect(palindromeTwo).toHaveProperty("data", "");
        expect(palindromeThree).toHaveProperty("data", 1);
    })
    it("validation method should be defined", () => {
        const palindrome = new Palindrome()

        expect(palindrome.isValid()).toBeDefined()
    })
    it("return false if data is not numeric", () => {
        const notNumeric = [new Palindrome("a"), new Palindrome(), new Palindrome({})]

        notNumeric.forEach(x => expect(x.isValid()).toBeFalsy())
    })
    it("return false if negative number", () => {
        const negativeNumber = new Palindrome(-1);

        expect(negativeNumber.isValid()).toBeFalsy();
    })
    it("return false if data is 10 devidable", () => {
        const tenDivision = [new Palindrome(10), new Palindrome(20), new Palindrome(150)];

        tenDivision.forEach(sample => expect(sample.isValid()).toBeFalsy())
    })
    it("return true if data is smaller then 10", () => {
        const underTen = [new Palindrome(1), new Palindrome(2), new Palindrome(9)];

        underTen.forEach(sample => expect(sample.isValid()).toBeTruthy())
    })
    it("return false if not legal palindrome", () => {
        const invalidPalindromes = [new Palindrome(1112), new Palindrome(112), new Palindrome(12)]

        invalidPalindromes.forEach(sample => expect(sample.isValid()).toBeFalsy())
    })
    it("return true if legal palindrome", () => {
        const validPalindromes = [new Palindrome(111), new Palindrome(11), new Palindrome(1)]

        validPalindromes.forEach(sample => expect(sample.isValid()).toBeTruthy())
    })
})

// implementation
class Palindrome {
    constructor(userInput = '') {
        this._data = userInput
    }

    get data() {
        return this._data
    }

    isValid() {
        if (!Number.isInteger(this._data)) {
            return false
        }

        if (this._data < 0) {
            return false
        }

        if (this._data % 10 === 0) {
            return false
        }

        if (this._data < 10) {
            return true
        }

        let leftPart = this.data
        let rightPart = 0

        while (leftPart > rightPart) {
            // reserve extra space for additional number
            rightPart *= 10
            // add the most right number
            rightPart += leftPart % 10
            // remove the most right number from the left-part
            leftPart = Math.trunc(leftPart / 10)
        }

        // compare left and right parts in case left and right part have equal number of digits
        // compare left and right parts in case right part has collected the digit in the middle
        return leftPart === rightPart || leftPart === Math.trunc(rightPart / 10)
    }
}

module.exports = Palindrome

Repo

https://github.com/ziskand/code-katas

Resources

Maze generator with DFS

Yigal Ziskand — Sat, 29 May 2021 21:11:57 +0000

Motivation

Maze or in other term labyrinth followed by wiki definition:

A maze is a path or collection of paths, typically from an entrance to a goal.

We want to use our knowledge from BFS + DFS recap and figure out a way to apply DFS algorithm in maze generation.

Basic Idea

There are multiple approaches to generate different kinds of labyrinth. Each solution has it's unique requirements and different methodology in algorithm's implementation.

In our case we want to find a way to "transform" an empty space to a valid maze.
Let's try to break down what we just said into requirements.

Valid maze:
- maze should have well defined border (width and height will be just enough for us)
- our maze should have entrance and goal (connected by generated path)
- path generation logic should not be applied outside of the predefined border
- the path (entrance -> goal) should not be boring...

Now when we finally have some basic requirements let's figure out how to match DFS algorithm (that works with tree structured data-sets) and our tree data-set.

Question: Hmmm... hold on a second! We don't have any tree structured data-set, all we have is an empty space... and what are we searching exactly - we remember that DFS is meant for searching, right?

Answer: Well it's partially correct...
We kind of reversing initial purpose of the algorithm - since we don't search for any particular thing, but instead we benefit DFS's approach of reaching the deepest node whenever possible and exploring all valid children of the current place...

The logic is quite simple - if i sit in the middle of a class i have four other students around me (front, back, left and right). If i switch places with the studen on my right side suddenly i have 3 new students sitting around me, now if i switch places again... got it, right?
The result of successful execution will be tree structured data-set of all visited places or in other words - labyrinth path.

Digging Deeper into the details:
Let's figure out a way to treat provided empty space as a world where DFS can be completely functional.
Remember that our requirement to empty space was it's high & width? It comes handy if we want to divide our empty-space into something DFS can handle.

Let's define a logical variable step step = 10 - this variable will help us with multiple calculations.
Now we can claim that our empty-space with height=100 and width=100 can be interpreted as walkable space or in other terms - 10 steps from border to border.
Great! It means that in order to navigate from one point to another we can use steps, for example:

navigate right move: from(x, y) -> to(x + step, y)
navigate left move: from(x, y) -> to(x - step, y)

Now when we have a "walkable" space - we can apply our DFS and discover all possible steps that we can walk to.

Every performed step should be "marked" as visited so we wont enter the infinite loop...
For that purpose we will use Set() and collected each place we visit there (and of course anything within this Set should not be reused again)

Pseudo Code

    // ------ //
    // preset //
    // ------ //

    // empty field for maze generation
    space = {height: 100, width: 100}
    // navigation mean
    step = 10;
    // navigation space limits
    minLimit = 0
    maxLimit = space.Max - step // assuming that width = height

    // initial place - to start maze generation
    firstPlace = (50, 50)

    // --------- //
    // algorithm //
    // --------- //

    // initial step of storing first node - tree root
    collection = stack.push(firstPlace)

    // initialize iteration loop
    do:
        place = stack.pop()
        if place has neighbors:
            checkPotentialNeighbors([up, right, down, left]):
            shuffle([up, right, down, left])  // <-- shuffle result to achive "turn right turn left" effect
            for neighbor in [right, down, up, left]:
                if neigbout <= maxLimit && neighbour >= minLimit:
                    if neighbor not in visitedPlacesSet:
                        stack.push(neighbor)
                        visitedPlacesSet.add(neighbor)
    // termination condition
    while stack not empty

Code Snippet

Maze Generation - (DFS)

import Stack from "./Stack.js";
import Cell from "./Cell.js";   
import Config from  "./Config.js"

const shuffle = (a) => {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
};

const DFS = async ({ root }, dataPoints) => {
        const stack = new Stack();
        const visitedNodes = new Set();

        // add enterance & exit nodes
        const enterance = new Cell(Config.minPosition, Config.minPosition);
        const exit = new Cell(Config.maxPosition, Config.maxPosition);
        visitedNodes.add(enterance);
        visitedNodes.add(exit);
        // Svelte store - (reactive observer)
        await dataPoints.update((visited) => (visited = [...visited, enterance]));
        await dataPoints.update((visited) => (visited = [...visited, exit]));

        let node;

        if (!root) {
            return;
        }

        stack.push(root);

        while (stack.size() > 0) {
            node = stack.pop();

            // find all valid children of the node
            let nodeChildren = [];
            // first child
            if (node.y - Config.step <= Config.maxPosition
                    && node.y - Config.step >= Config.minPosition) {
                nodeChildren.push(new Cell(node.x, node.y - Config.step));
            }
            // second child
            if (node.x + Config.step <= Config.maxPosition 
                    && node.x + Config.step >= Config.minPosition) {
                nodeChildren.push(new Cell(node.x + Config.step, node.y));
            }
            // third child
            if (node.x - Config.step >= Config.minPosition 
                    && node.x - Config.step <= Config.maxPosition) {
                nodeChildren.push(new Cell(node.x - Config.step, node.y));
            }
            // fourth child
            if (node.y + Config.step >= Config.minPosition 
                    && node.y + Config.step <= Config.maxPosition) {
                nodeChildren.push(new Cell(node.x, node.y + Config.step));
            }

            let validChildren = nodeChildren.filter(
                (cell) => !visitedNodes.has(JSON.stringify(cell))
            );

            shuffle([...validChildren]).forEach((cell) => {
                if (!visitedNodes.has(JSON.stringify(cell))) {
                    stack.push(cell);
                    visitedNodes.add(JSON.stringify(cell));
                }
            });

            if (validChildren.length !== 0) {
                // Svelte store - (reactive observer)
                await dataPoints.update((visited) => (visited = [...visited, node]));
            }
        }
    };

Cell - logical containner to carry the location data

class Cell {
    constructor(x, y) {
        this.recX = x;
        this.recY = y;
    };

    get x() {
        return this.recX;
    }

    get y() {
        return this.recY;
    }
}

Stack - interface implementation of [push, pop size] functionality

class Stack {
    constructor() {
        this.items = new Array();
    }

    push(item) {
        this.items.push(item);
    }

    pop() {
        return this.items.pop();
    }

    size() {
        return this.items.length;
    }
}

Example

Live example with all the snippets from above is available on DFS Maze Generator (Svelte REPL)
Additionally if you want to tweak the code locally - the source is available in github.

BFS, DFS tree-traversing (7 min recap)

Yigal Ziskand — Tue, 25 May 2021 12:25:58 +0000

Motivation

Let's begin our recap with understanding algorithm's names first.

DFS - stays for depth-first-search while BFS means breadth-first-search.

If you pay close attention to the names you will see that both of them ends up with SEARCH term.
Yes, you guess right - we can use both of them in order to perform search on tree structured data-sets.

Basic Idea

The basic idea applied in DFS is to reach the deepest node in the graph whenever possible while BFS prioritizes wide-level node visiting approach.

In other words DFS will perform iterations in [TOP -> BOTTOM] order while BFS will iterate in side-to-side approach [LEFT -> RIGHT] or [RIGHT -> LEFT].
Due to their different approaches on iteration order - both of them utilize different data-structures - in case of BFS we shall use Queue and DFS implementation can benefit from Stack

Two words on Queue & Stack that i think important for further reading.

Queue is an abstract data type and its purpose is to store data in FIFO (first in - first out) order.
Stack is an abstract data type as well that stores data in LIFO (last in - first out) order.

We will implement our BFS & DFS example on binary tree which is a valid data structure with the only difference (from our perspective) - any tree's node can have at most two children nodes.

Pseudo Code

Abstract Search Approach

    // initial step - storing root node
    collection = collection.putItem(tree_root)

    // initialize iteration loop
    do:
        node = collection.getItem()
        if node has children:
            collection.storeChildren(node.children)
    // termination condition
    while collection not empty

Code Snippet

BFS

    const BFS = async ({ root }, collection) => {
        if (!root) {
            return;
        }        

        const queue = new Queue();
        let node;

        queue.enqueue(root);

        while (queue.size() > 0) {
            node = queue.dequeue();

            if (node.l_child) {
                queue.enqueue(node.l_child);
            }

            if (node.r_child) {
                queue.enqueue(node.r_child);
            }

            // This line should be replaces by any logical operation you want to perform on the node's value, ex: sum
            // In my particular example i use Svelte's store (kind of observer pattern) to collect node's value
            await collection.update(collectedData => collectedData = [...collectedData, node.value]);
        }
    }

DFS

    const DFS = async ({ root }, collection) => {
        if (!root) {
            return;
        }

        const stack = new Stack();
        let node;

        stack.push(root);

        while (stack.size() > 0) {
            node = stack.pop();

            if (node.l_child) {
                stack.push(node.l_child);
            }

            if (node.r_child) {
                stack.push(node.r_child);
            }

            // the same explanation as for BFS (above)
            await collection.update(collectedData => collectedData = [...collectedData, node.value]);
        }
    }

Queue

    class Queue {
        constructor() {
            this.items = new Array();
        }

        enqueue(item) {
            this.items.unshift(item);
        }

        dequeue() {
            return this.items.pop();
        }

        size() {
            return this.items.length;
        }
    }

Stack

    class Stack {
        constructor() {
            this.items = new Array();
        }

        push(item) {
            this.items.push(item);
        }

        pop() {
            return this.items.pop();
        }

        size() {
            return this.items.length;
        }
    }

Technically we did not have to implement neither Stack nor Queue for BFS, DFS search - we could just use regular Array and be happy with it... but i believe that by implementing Queue, Stack interface we can enjoy more readable code at the end.

Notes

Both of the algorithms will perform equally in big O perspective and in worst case it will be equal to O(n) - meaning that all nodes of the data-set were visited.
In case we have some knowledge regarding our data-set - we can benefit better results from each:
- If required data is stored in a deep (far from the root) node - then DFS would give better results.
- Looking for the shortest path between nodes will perform better with BFS.
In average comparison DFS will consume less memory then BFS.

Example

As always i have sketched some clickable example with all the snippets from above.
Tree Traversing (Svelte REPL)

Clean Code with Currying (3 min recap)

Yigal Ziskand — Sun, 23 May 2021 12:48:41 +0000

Motivation

In order to improve code readability currying technique may be applied.

By modifying our code with such technique we shall gain cleaner and more readable function names.

As a result our code-base will became easier to maintain.

Basic Idea

There are multiple principles where currying technique may be utilized... We will look into one particular example of implementation with the almighty closures.
As we claimed above - utilizing currying should improve our code readability, so let's try to modify some imaginary tax calculations function (function expects two input parameters and provides an output of total calculation).
It's declaration could probably look like this getPriceWithTax(price, tax) and the actual function call would look like getPriceWithTax(50, 10) - yeah... its less explicable once we don't see the actual input parameter names...

We going to apply currying technique to improve the readability so our code could become something like getPriceWithTax10(price), getPriceWithTax5(price), getPriceWithTax20(price) and etc...

I believe you got the idea.

Pseudo Code

    // utilize currying technique
    taxCalculation = (tax)

    // improve core readability
    getPriceWithTax10 = taxCalculation(10)

    // enjoy the improved redability
    priceTaxBy10 = getPriceWithTax10(price);

Code Snippet

    const taxCalculation = (tax) => (price) => price + price * tax / 100;

    const price = 100;

    const getPriceWithTax10 = taxCalculation(10);
    const getPriceWithTax5 = taxCalculation(5);
    const getPriceWithTax20 = taxCalculation(20);

    const priceTaxBy10 = getPriceWithTax10(price);
    const priceTaxBy5 = getPriceWithTax5(price);
    const priceTaxBy20 = getPriceWithTax20(price);

Example

Svelte REPL is such a joy to play with... - so I've sketched a clickable example with the code snippet from above

(for those who loves clickable stuff)

JS Currying (Svelte REPL)

Resources

Bubble Sort (3 min recap)

Yigal Ziskand — Sat, 22 May 2021 13:15:30 +0000

Motivation

It's shiny benefit is it's implementation simplicity, but be aware (it comes with a heavy price) it should not be applied on large datasets since its performance is O(n)^2 which is quite... terrible...

Basic Idea

The basic idea is very simple - we should go over each item in our collection by comparing the current item with its right closes neighbor.
In case we find that the left item is bigger then right one [left > right] - we simply switch their places and continue to the next neighbors.

This way we make sure that the biggest number is always BUBBLED UP to the most right place.
If we continue this procedure for each item in the collection then we can claim that we have incrementally sorted collection of items

Pseudo Code

done = false
while !done
    done = true
    for i = 0 .. items.length
        if items[i] > items[i + 1]
            swap(a[i], a[i + 1])
            done = false

Code Snippet

  let dataSet = [1, 6, 2, 3, 4, 5, 7];

  const bubbleSort = () => {
    let done = false;
    while (!done) {
      done = true;

      for (let i = 0; i < dataSet.length; i++) {
        if (dataSet[i] && dataSet[i + 1] && dataSet[i] > dataSet[i + 1]) {
          [dataSet[i], dataSet[i + 1]] = [dataSet[i + 1], dataSet[i]];

          done = false;
        }
      }
    }
  };

Example

Since Svelte compiler allows us to write almost identical to standard JS - i have sketched a simple example of the algorithm triggered by a button click.
BubbleSort (Svelte REPL)