/**********************************************************/
/** IMPLEMENTATION OF MY ALGORITHM (DYNAMIC PROGRAMMING) **/
/**********************************************************/
const getTotalMinDist = (a, b) => {
    let count = 0

    const m = a.length
    const n = b.length

    // Create MinDist table
    let minDist = new Array(n).fill(0).map(() => new Array(m))

    // Helper functions so that we can use 1-based indices instead of 0-based indices
    const getMinDist = (i, j) => {
        // Implement the base case here itself instead of filling the table for convenience
        if (j == m + 1)
            return {dist: 0, subseq: []}
        else
            return minDist[i - 1][j - 1]
    }
    const setMinDist = (i, j, dist, subseq) => {minDist[i - 1][j - 1] = {dist: dist, subseq: subseq}}
    const getA = (i) => a[i - 1]
    const getB = (i) => b[i - 1]

    // Fill minDist in the correct order using the recurrence relation
    for (let j = m; j >= 1; j--) {
        for (let i = 1; i <= j + n - m; i++) {
            // Keep track of the subsequence that produced the minimum L1 distance
            let min_dist = Infinity
            let min_index = -1
            let min_next_subseq = []

            // This for loop iterates through the parameters to the min function in my answer
            for (let next_i_start = i; next_i_start <= j + n - m; next_i_start++) {
                // Recursive step from my answer
                let cur_dist = getMinDist(next_i_start + 1, j + 1).dist + Math.abs(getA(j) - getB(next_i_start))

                if (cur_dist < min_dist) {
                    min_dist = cur_dist
                    min_index = next_i_start
                    min_next_subseq = getMinDist(next_i_start + 1, j + 1).subseq
                }
            }

            // Set this entry of the table to the minimum distance found
            //  as well as the value of b at the index chosen + the rest of the optimal subsequence after that point
            setMinDist(i, j, min_dist, [getB(min_index)].concat(min_next_subseq))
        }
    }

    return getMinDist(1, 1)
}

/*******************************/
/** BRUTEFORCE IMPLEMENTATION **/
/*******************************/
const bruteForceGetTotalMinDist = (a, b) => {
    // Recursively try every combination of a.length indices of b
    //   remaining_indices: number of indices left to determine
    //   indices: an ordered list of indices into b, the function will find the minimum L1 distance to a while
    //            considering only all subsequences of b that contain the values of b at these indices
    const tryCombinations = (remaining_indices, indices) => {
        // If there are no more indices left to pick (we have picked a.length indices into b)
        if (remaining_indices == 0) {
            // Computes the L1 distance between a and the subsequence of b given by the indices array
            let dist = a.map((a_val, a_index) => Math.abs(a_val - b[indices[a_index]])).reduce((x, y) => x + y)

            // Return the L1 distance along with the sequence that produced that distance
            return {dist: dist, subseq: indices.map((i) => b[i])}
        }

        // Otherwise, add another index to our current selection of indices for the
        //  subsequence of b and recursively find the minimum L1 distance
        let min_dist = {dist: Infinity}

        for (let i = 0; i < b.length; i++) {
            // If i is an index that can be inserted into indices array
            //  by virtue of the array being empty, or i being greater than the last element
            if (indices.length == 0 || i > indices[indices.length - 1]) {
                let new_indices = indices.slice()
                new_indices.push(i)

                let result = tryCombinations(remaining_indices - 1, new_indices)
                if (result.dist < min_dist.dist)
                    min_dist = result
            }
        }

        return min_dist
    }

    return tryCombinations(a.length, [])
}

// Run both of them with randomized arrays a lot of times to gain confidence that my answer is correct
let numErrors = 0

for (let i = 0; i < 100000; i++) {
    const a = new Array(7).fill(0).map(() => Math.floor(Math.random() * 50))
    const b = new Array(15).fill(0).map(() => Math.floor(Math.random() * 50))

    bruteForceSolution = bruteForceGetTotalMinDist(a, b)
    dynamicProgSolution = getTotalMinDist(a, b)

    // A lazy way to check for equality of two objects in JS (only works sometimes, this is one of those times)
    if (JSON.stringify(bruteForceSolution) != JSON.stringify(dynamicProgSolution))
        numErrors++
}

console.log("Number of errors: " + numErrors)