tito.js

// Given a length and the constraints, ie, length 4, numbers 1, uppercase 2, lowercase 1.
// Find the kth password that matches these constraints from lexical ordering standpoint.
// So in the case of k=4; the first four passwords on this lexical ordering would be
// 1AAa->1AAb->1AAc->1AAd and that last password is your answer.
// Just to highlight the lexical ordering a little more;
// note the last password possible here would be zZZ9).
​
function charToDecimal(char) {
    const asciiRepresentation = char.charCodeAt(0);
    const firstSymbolSetSize = "9".charCodeAt(0) - "0".charCodeAt(0) + 1;
    const secondSymbolSetSize = "Z".charCodeAt(0) - "A".charCodeAt(0) + 1;
    if(asciiRepresentation >= "0".charCodeAt(0) && asciiRepresentation <= "9".charCodeAt(0)) {
        return asciiRepresentation - "0".charCodeAt(0);
    }
​
    if(asciiRepresentation >= "A".charCodeAt(0) && asciiRepresentation <= "Z".charCodeAt(0)) {
        return asciiRepresentation - "A".charCodeAt(0) + firstSymbolSetSize;
    }
​
    if(asciiRepresentation >= "a".charCodeAt(0) && asciiRepresentation <= "z".charCodeAt(0)) {
        return asciiRepresentation - "a".charCodeAt(0) + firstSymbolSetSize + secondSymbolSetSize;
    }
​
    return -1;
}
​
function toNumber(str) {
    return str.split("").map(charToDecimal);
}
​
function digitDecimalToChar(digitDecimal) {
    const firstSymbolSetSize = "9".charCodeAt(0) - "0".charCodeAt(0) + 1;
    const secondSymbolSetSize = "Z".charCodeAt(0) - "A".charCodeAt(0) + 1;
    if(digitDecimal >= charToDecimal("0") && digitDecimal <= charToDecimal("9")) {
        return String.fromCharCode(digitDecimal + "0".charCodeAt(0));
    }
​
    if(digitDecimal >= charToDecimal("A") && digitDecimal <= charToDecimal("Z")) {
        return String.fromCharCode(digitDecimal + "A".charCodeAt(0) - firstSymbolSetSize);
    }
​
    if(digitDecimal >= charToDecimal("a") && digitDecimal <= charToDecimal("z")) {
        return String.fromCharCode(digitDecimal + "a".charCodeAt(0) - firstSymbolSetSize - secondSymbolSetSize);
    }
​
    return "@";
}
​
function toString(number) {
    return number.map(digitDecimalToChar).join("");
}
​
function isNumberDigitType(digitDecimalRepresentation) {
    return digitDecimalRepresentation >= charToDecimal("0") && digitDecimalRepresentation <= charToDecimal("9");
}
​
function isUppercaseDigitType(digitDecimalRepresentation) {
    return digitDecimalRepresentation >= charToDecimal("A") && digitDecimalRepresentation <= charToDecimal("Z");
}
​
function isLowercaseDigitType(digitDecimalRepresentation) {
    return digitDecimalRepresentation >= charToDecimal("a") && digitDecimalRepresentation <= charToDecimal("z");
}
​
function addToDigit(digitDecimalRepresentation, k) {    
    if(isNumberDigitType(digitDecimalRepresentation)) {
        return {
            value: (digitDecimalRepresentation + k) % 10,
            rest: Math.floor((digitDecimalRepresentation + k)/ 10)
        };
    }
​
    if(isUppercaseDigitType(digitDecimalRepresentation)) {
        return {
            value: charToDecimal("A") + (digitDecimalRepresentation - charToDecimal("A") + k) % 26,
            rest: Math.floor((digitDecimalRepresentation - charToDecimal("A") + k) / 26)
        };
    }
​
    if(isLowercaseDigitType(digitDecimalRepresentation)) {
        return {
            value: charToDecimal("a") + (digitDecimalRepresentation - charToDecimal("a") + k) % 26,
            rest: Math.floor((digitDecimalRepresentation - charToDecimal("a") + k) / 26)
        };
    }
​
    return NaN;
}
​
function add(str, k) {
    const decimalRepresentation = toNumber(str);
    const result = [];
    let toAdd = k;
    const reversedDecimalRepresentation = decimalRepresentation.reverse();
    for(let i = 0; i < reversedDecimalRepresentation.length; i++) {
        const digit = reversedDecimalRepresentation[i];
        const additionResult = addToDigit(digit, toAdd);
        result.push(additionResult.value);
        toAdd = additionResult.rest;
    }
    return toString(result.reverse());
}
​
function factorial(num) {
    let result = 1;
    for (let i = 2; i <= num; i++) {
        result = result * i;   
    }
    return result;
}
​
function getSymbols(str) {
    const strArr = str.split("");
    const symbolLookup = strArr.reduce((acum, symbol, i) => {
        if(!acum[symbol]) {
            return {
                ...acum,
                [symbol]: {
                    firstSeen: i,
                    symbol,
                    count: 1
                }
            };
        }
​
        return {
            ...acum,
            [symbol]: {
                ...acum[symbol],
                count: acum[symbol].count + 1
            }
        };
    }, {})
    return Object.values(symbolLookup).sort((a,b) => a.firstSeen - b.firstSeen);
}
​
function getPermutationCountBasedOnSymbols(symbols) {
    let totalLength = 0;
    let repeteadSymbols = 1;
​
    for(let i = 0; i < symbols.length; i++) {
        const currentSymbol = symbols[i];
        totalLength += currentSymbol.count;
        repeteadSymbols *= factorial(currentSymbol.count);
    }
​
    return factorial(totalLength) / repeteadSymbols;
}
​
function nthPermutation(symbols, n) {
    let totalPermsCount = 0;
    const effectiveSymbols = symbols.filter(symbol => symbol.count > 0);
​
    if(n <= 0) {
        return ""; // wtf situation, should not happen but I will leave it here just in case (I don't want infinite recurssions)
    }
​
    if(effectiveSymbols.length === 0) {
        return ""; // wtf situation, should not happen but I will leave it here just in case (I don't want infinite recurssions)
    }
​
    if(effectiveSymbols.length === 1) {
        return effectiveSymbols[0].symbol.repeat(effectiveSymbols[0].count);
    }
​
    for(let i = 0; i < effectiveSymbols.length; i++) {
        const currentSymbol = effectiveSymbols[i];
        const symbolsCandidates = effectiveSymbols.map((symbol, j) => {
            if(j == i) {
                return {
                    ...symbol,
                    count: symbol.count - 1
                }
            }
            return symbol;
        });
        const permutationAmountForSymbol = getPermutationCountBasedOnSymbols(symbolsCandidates);
        totalPermsCount += permutationAmountForSymbol;
        if(n <= totalPermsCount) {
            return currentSymbol.symbol + nthPermutation(symbolsCandidates, n - (totalPermsCount - permutationAmountForSymbol));
        }
    }
    
    return null; // impossible to calculate nth permutation of that symbols
}
​
function getNthGroup(numbers, uppercase, lowercase, n) {
    const firstEncodedGroup = "1".repeat(numbers) + "2".repeat(uppercase) + "3".repeat(lowercase);
    const firstEncodedGroupSymbols = getSymbols(firstEncodedGroup);
    const perm = nthPermutation(firstEncodedGroupSymbols, n);
    return perm.split("").map(typeEncoded => {
                if(typeEncoded === "1") {
                    return "0"
                }
                if(typeEncoded === "2") {
                    return "A"
                }
                if(typeEncoded === "3") {
                    return "a"
                }
            }).join("");
}
​
function getMaxKPerGroup(numbers, uppercase, lowercase) {
    return Math.pow(10, numbers) * Math.pow(26, uppercase + lowercase);
}
​
function kthPassword(length, numbers, uppercase, lowercase, k) {
    if(length != numbers + uppercase + lowercase) {
        throw new Error("Not supported: length must be always the sum of numbers, uppercase, lowercase"); // TODO
        // This is actually very easy to solve though:
        // 1) if length < numbers + uppercase + lowercase then it is impossible to generate the password within those contrains
        // 2) if length > numbers + uppercase + lowercase then (thanks to the "at least" part in the task definition) prepend either '0', 'A' or 'a' chars until you get the desired length (it depends on which variable numbers, uppercase, lowercase has value > 0).
    }
    if(k < 1) {
        throw new Error("Not supported: k must be >= 1"); // Remove if you would like to use zero based k
    }
​
    const effectiveK = k - 1; // Remove if you would like to use zero based k
    const groupsAmount = factorial(length)/(factorial(numbers)*factorial(uppercase)*factorial(lowercase));
    const maxKPerGroup = getMaxKPerGroup(numbers, uppercase, lowercase);
    const selectedGroupIndex = 1 + Math.floor(effectiveK / maxKPerGroup) % groupsAmount; // the '% groupsAmount' is not really necessary if we are sure that k is not going to be bigger than the amount of possible passwords given the contrains
    const selectedGroupFirstPassword = getNthGroup(numbers, uppercase, lowercase, selectedGroupIndex);
    const effectiveKInsideTheGroup = effectiveK % maxKPerGroup;
    return add(selectedGroupFirstPassword, effectiveKInsideTheGroup);
}
​
// Examples:
function examples() {
    console.log(kthPassword(4,1,2,1,1)); // 0AAa
    console.log(kthPassword(4,1,2,1,2)); // 0AAb
    console.log(kthPassword(4,1,2,1,3)); // 0AAc
    console.log(kthPassword(4,1,2,1,4)); // 0AAd
    console.log(kthPassword(4,1,2,1,26)); // 0AAz
    console.log(kthPassword(4,1,2,1,27)); // 0ABa
    console.log(kthPassword(4,1,2,1,175759)); // 9ZZy
    console.log(kthPassword(4,1,2,1,175760)); // 9ZZz
    console.log(kthPassword(4,1,2,1,175761)); // 0AaA
    console.log(kthPassword(4,1,2,1,2109120)); // zZZ9
    console.log(kthPassword(15,5,7,3,1757632212358)); // 00000AIKVRSItkv
}
​
examples();