dynamic_programming.ts

// Dynamic Programming Examples
// From FreeCodeCamp
// https://www.youtube.com/watch?v=oBt53YbR9Kk



// =========================== FIBONACCI ===========================

// Return the number of the fibonacci sequence at n.

const fib = (n: number, memo = new Map<number, number>()): number => {
    if(memo.has(n)) return memo.get(n)!;
    if(n <= 1) return 1;
    memo.set(n, fib(n - 1, memo) + fib(n - 2, memo));
    return memo.get(n)!;
};

// Tests:
// console.log(fib(0)); // 1
// console.log(fib(1)); // 1
// console.log(fib(8)); // 34
// console.log(fib(16)); // 1597
// console.log(fib(100)); // 573147844013817200000

// =================================================================





// ====================== GRID TRAVELER ============================ 

// Given an n x m grid, how many different paths can a traveler going
// from the top-left to the bottom right travel, if they can only
// move right or down.

const gridTraveler = (n: number, m: number, memo = new Map<string, number>()): number => {
    const sizeKey = `${n},${m}`;
    if(memo.has(sizeKey)) return memo.get(sizeKey)!;

    if(n === 0 || m === 0) return 0;
    if(n === 1 && m === 1) return 1;

    memo.set(sizeKey, gridTraveler(n - 1, m, memo) + gridTraveler(n, m - 1, memo));
    return memo.get(sizeKey)!;
};

// Tests:
// console.log(gridTraveler(1, 1)) // 1
// console.log(gridTraveler(2, 3)) // 3
// console.log(gridTraveler(3, 3)) // 6
// console.log(gridTraveler(8, 8)) // 3432
// console.log(gridTraveler(20, 20)) // 35345263800

// ================================================================= 





// ========================== CAN SUM ============================== 

// Returns true if you can generate target by summing values from
// the array numbers. You can use the same number from the array
// as many times as necessary.

const canSum = (target: number, numbers: number[], memo = new Map<number, boolean>()): boolean => {
    if(memo.has(target)) return memo.get(target)!;
    
    if(target === 0) return true;
    if(target < 0) return false;

    for(const number of numbers) {
        if(canSum(target - number, numbers, memo) === true) {
            memo.set(target, true);
            return true;
        }
    }

    memo.set(target, false);
    return false;
};

// Tests:
// console.log(canSum(8, [2, 3, 5])); // true
// console.log(canSum(7, [2, 3])); // true
// console.log(canSum(7, [3, 5])); // false
// console.log(canSum(300, [7, 14])); // false

// ================================================================= 





// =========================== HOW SUM =============================

// If target can be generated by summing any of the values in numbers,
// return a list of addends. If the target cannot be generated, return
// null. There may be multiple answers--any is fine.

const howSum = (target: number, numbers: number[], memo = new Map<number, number[] | null>()): number[] | null => {
    if(memo.has(target)) return memo.get(target)!;
    
    if(target === 0) return [];
    if(target < 0) return null;

    for(const number of numbers) {
        const result = howSum(target - number, numbers, memo);
        if(result !== null) {
            memo.set(target, [...result, number])
            return [...result, number];
        }
    }

    memo.set(target, null);
    return null;
}

// Tests:
// console.log(howSum(7, [2, 3])); // [3, 2, 2]
// console.log(howSum(7, [5, 3, 4, 7])); // [4, 3]
// console.log(howSum(7, [2, 4])); // null
// console.log(howSum(8, [2, 3, 5])); // [2, 2, 2, 2]
// console.log(howSum(300, [7, 14])); // null

// =================================================================





// ========================== BEST SUM =============================

// Return the shortest combination of numbers from the array that
// adds up to target. Return null if the target cannot be made with
// the numbers in the array.

const bestSum = (target: number, numbers: number[], memo = new Map<number, number[] | null>()): number[] | null => {
    if(memo.has(target)) return memo.get(target)!;
    
    if(target === 0) return [];
    if(target < 0) return null;

    let minArray = null;
    for(const number of numbers) {
        const result = bestSum(target - number, numbers, memo);
        
        if(result !== null) {
            const newArray = [...result, number];

            if(minArray === null || result.length < minArray.length)
                minArray = newArray;
        }
    }
    
    memo.set(target, minArray);
    return minArray;
}

// Tests:
// console.log(bestSum(7, [5, 3, 4, 7])); // [7]
// console.log(bestSum(8, [2, 3, 5])); // [3, 5]
// console.log(bestSum(8, [1, 4, 5])); // [4, 4]
// console.log(bestSum(100, [1, 2, 5, 25])); // [25, 25, 25, 25]

// =================================================================





// ======================== CAN CONSTRUCT ===========================

// Return true if target can be constructed using strings from the 
// array. Items from the array may be used as many times as necessary.

const canConstruct = (target: string, strings: string[], memo = new Map<string, boolean>()): boolean => {
    if(memo.has(target)) return memo.get(target)!;
    if(target === '') return true;

    for(const prefix of strings) {
        if(target.startsWith(prefix)) {
            if(canConstruct(target.slice(prefix.length), strings, memo)) {
                memo.set(target, true);
                return true;
            }
        }
    }

    memo.set(target, false);
    return false;
}

// Tests:
// console.log(canConstruct('skateboard', ['sk', 'b', 'oar', 'te', 'ate', 'd'])); // true
// console.log(canConstruct('skateboard', ['sk', 'b', 'oar', 'te', 'ate'])); // false
// console.log(canConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcdd'])); // true
// console.log(canConstruct('enterapotentpot', ['a', 'p', 'ent', 'enter', 'ot', 'o', 't'])); // true
// console.log(canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', ['e', 'ee', 'eee', 'eeee', 'eeeee'])); // false

// =================================================================





// ======================== COUNT CONSTRUCT =========================

// Return the number of ways that target can be constructed using the
// array of strings. Items in the array may be used more than once.

const countConstruct = (target: string, strings: string[], memo = new Map<string, number>()): number => {
    if(memo.has(target)) return memo.get(target)!;
    if(target === '') return 1;

    let numWays = 0;
    for(const prefix of strings) {
        if(target.startsWith(prefix)) {
            const childrenSum = countConstruct(target.slice(prefix.length), strings, memo);
            numWays += childrenSum;
        }
    }

    memo.set(target, numWays);
    return numWays;
}

// Tests:
// console.log(countConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'])); // 1
// console.log(countConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd', 'c'])); // 2
// console.log(countConstruct('aaa', ['a', 'a', 'a'])); // 27
// console.log(countConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl'])); // 2
// console.log(countConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', ['e', 'ee', 'eee', 'eeee', 'eeeee'])); // 0

// =================================================================





// ========================= ALL CONSTRUCT =========================

// Return a list of all the ways that target can be constructed using
// elements from the array. Elements may be used more than once.

const allConstruct = (target: string, strings: string[], memo = new Map<string, string[][]>()): string[][] => {
    if(memo.has(target)) return memo.get(target)!;
    if(target === '') return [[]];

    const result = []

    for(const prefix of strings) {
        if(target.startsWith(prefix)) {
            const waysToMakeChild = allConstruct(target.slice(prefix.length), strings, memo);
            const waysToMakeTarget = waysToMakeChild.map(way => [prefix, ...way]);
            result.push(...waysToMakeTarget);
        }
    }

    memo.set(target, result);
    return result;
}

// Tests:
// console.log(allConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd'])); // [['abc', 'def']]
// console.log(allConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd', 'c'])); // [['ab', 'c', 'def'], ['abc', 'def']]
// console.log(allConstruct('purple', ['purp', 'p', 'ur', 'le', 'purpl'])); // [['purp', 'le'], ['p', 'ur', 'p', 'le']]
// console.log(allConstruct('', ['foo', 'bar'])); // [[]]
// console.log(allConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', ['e', 'ee', 'eee', 'eeee', 'eeeee'])); // []

// =================================================================