# Question 1

'use strict'

function checkCorrectness(syntax) {
    //Map out all closing and opening brackets
    const bracketMap = {
        ']': '[',
        ')': '(',
        '}': '{'
    }

    let stack = []

    for (let i = 0; i < syntax.length; i++) {
        const codeChar = syntax.charAt(i);
        //If it's a closing bracket, 
        // check if the top of the stack has the corresponding opening bracket
        if (bracketMap[codeChar]) {
            let topElement = stack.length > 0 ? stack.pop() : '#'
            //If it doesn't correspond, then it's not valid
            if (bracketMap[codeChar] !== topElement) {
                return false
            }
        // if the element is an opening bracket, push it in
        } else if (Object.values(bracketMap).includes(codeChar)) {
            stack.push(codeChar);
        }
        else {
            return false;
        }

    }


    //If the stack still has elements by the end of the counter, 
    //that means that some elements haven't been accounted for
    //Therefore, it's not valid
    return stack.length === 0

}

function correctness(roktx) {
    const ans = [];

    roktx.forEach(element => {
        ans.push(checkCorrectness(element) ? "YES" : "NO");
    });

    return ans;
}


function main() {

    let roktx = [
        "[]{}()",
        "[{]}",
        "[{}]{()}",
        "",
        "AA"
    ];
    console.log(correctness(roktx));

}

main();

# Question 2

'use strict'

function numberOfPayment(roktCoupons, k) {
    let hashMap = {},
        results = []

    for (let i = 0; i < roktCoupons.length; i++) {
        if (hashMap[roktCoupons[i]]) {
            results.push([hashMap[roktCoupons[i]], roktCoupons[i]])
        } else {
            hashMap[k - roktCoupons[i]] = roktCoupons[i];
        }
    }
    return results.length;
}

function main() {
    const roktCoupons = [6, 6, 3, 9, 3, 5, 1];
    console.log(numberOfPayment(roktCoupons, 12));
}

main();

# Question 3

'use strict'

function UnionFind(count) {
    this.roots = new Array(count);
    this.ranks = new Array(count);

    for (var i = 0; i < count; ++i) {
        this.roots[i] = i;
        this.ranks[i] = 0;
    }
}

var proto = UnionFind.prototype

Object.defineProperty(proto, "length", {
    "get": function () {
        return this.roots.length
    }
})

proto.makeSet = function () {
    var n = this.roots.length;
    this.roots.push(n);
    this.ranks.push(0);
    return n;
}

proto.find = function (x) {
    var x0 = x
    var roots = this.roots;
    while (roots[x] !== x) {
        x = roots[x]
    }
    while (roots[x0] !== x) {
        var y = roots[x0]
        roots[x0] = x
        x0 = y
    }
    return x;
}

proto.link = function (x, y) {
    var xr = this.find(x)
        , yr = this.find(y);
    if (xr === yr) {
        return;
    }
    var ranks = this.ranks
        , roots = this.roots
        , xd = ranks[xr]
        , yd = ranks[yr];
    if (xd < yd) {
        roots[xr] = yr;
    } else if (yd < xd) {
        roots[yr] = xr;
    } else {
        roots[yr] = xr;
        ++ranks[xr];
    }
}

function numGroups(input) {
    let pairs = [];
    // create pairs from 
    var forest = new UnionFind(input.length);
    for (let i = 0; i < input.length; i++) {
        for (let j = i; j < input.length; j++) {
            if (input[i][j] === 1) {
                forest.link(i, j);
            }
        }
    }

    return forest.roots.filter(function(elem, index, self) {
        return index === self.indexOf(elem);
    }).length;
}

function main() {

    const input = [
        [1, 1, 0, 0],
        [1, 1, 1, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 1]
    ];
    console.log(numGroups(input));
}

main();