debt-flow-algorithm.js

function minMaxIdx(arr) {
    let max = arr[0]
    let maxIdx = 0;
    let min = arr[0];
    let minIdx = 0;

    for(let i = 0; i< arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
            minIdx = i;
        } else if (arr[i] > max) {
            max = arr[i];
            maxIdx = i;
        }
    }

    return [maxIdx, minIdx];
}

class CashFlow {
    constructor() {
        this.debtLog = [];
        this.persons = {};
        this.personsIdx = 0;
        this.personsArray = [];
    }

    add(personA, personB, amount) {
        if (this.persons[personA] === undefined) {
            this.persons[personA] = this.personsIdx;
            this.personsArray.push(personA);
            this.personsIdx += 1;
        }
        if (this.persons[personB] === undefined) {
            this.persons[personB] = this.personsIdx;
            this.personsArray.push(personB);
            this.personsIdx += 1;
        }
        this.debtLog.push([personA, personB, amount]);
    }

    getDebtMap() {
        const debtMap = [];
        for(let i = 0; i < this.personsIdx; i++) {
            debtMap.push(new Array(this.personsIdx).fill(0));
        }
        for(let i = 0; i < this.debtLog.length; i++) {
            const [personA, personB, amount] = this.debtLog[i];
            debtMap[this.persons[personA]][this.persons[personB]] = amount;
        }
        return debtMap;
    }

    minCashFlow() {
        const graph = this.getDebtMap();
        const amount = new Array(this.personsIdx).fill(0);
        for(let i = 0; i < this.personsIdx; i++) {
            for (let j = 0; j < this.personsIdx; j++) {
                amount[i] += (graph[j][i] - graph[i][j]);
            }
        }
        let maxCredit, maxDebit;
        const cashFlow = {};
        do {
            const minMax = minMaxIdx(amount);
            maxCredit = minMax[0];
            maxDebit = minMax[1];
            const min = Math.min(-amount[maxDebit], amount[maxCredit]);
            if (min === 0) break;
            amount[maxCredit] -= min;
            amount[maxDebit] += min;
            cashFlow[this.personsArray[maxDebit]] = { [this.personsArray[maxCredit]]: min }
        } while(!(amount[maxCredit] === 0 && amount[maxDebit] === 0));

        return cashFlow;
    }
}

const cf = new CashFlow();

cf.add('C', 'A', 10);
cf.add('B', 'A', 10);
cf.add('D', 'A', 10);
cf.add('A', 'C', 10);

console.log(cf.getDebtMap());
console.log(cf.persons);
console.log(cf.minCashFlow());