ProjectEuler107

minimalNetwork.js

const fs = require('fs');
const emptyCell = '-';

async function main() {
    let networkMatrix = await readFile();
    let sortedValues = buildArray(networkMatrix);
    let initialSum = getSum(networkMatrix);
    await solve(networkMatrix, sortedValues);
    let reducedSum = getSum(networkMatrix);
    console.log('Result: ' + (initialSum - reducedSum));
}

function solve(networkMatrix, sortedValues) {
    for (let [value, row, col] of sortedValues) {
        networkMatrix[row][col] = emptyCell;
        networkMatrix[col][row] = emptyCell;
        let twoVertexStillReachable = false;
        try {
            const networkMatrixCopy = JSON.parse(JSON.stringify(networkMatrix));
            twoVertexStillReachable = canReachVertex(row, col, networkMatrixCopy);
        } catch { }
        if (!twoVertexStillReachable) { // restore the value
            networkMatrix[row][col] = value;
            networkMatrix[col][row] = value;
        }
    }
}

function buildArray(networkMatrix) {
    const networkMatrixCopy = JSON.parse(JSON.stringify(networkMatrix));
    let array = [];
    while (true) {
        let [row, col, max] = findMax(networkMatrixCopy);
        if (!max) {
            break;
        }
        array.push([max, row, col]);
    }
    return array;
}

function findMax(networkMatrix) {
    let row, col, max = -1;
    for (let r = 0; r < networkMatrix.length; r++) {
        for (let c = 0; c < networkMatrix.length; c++) {
            let currentNum = +networkMatrix[r][c];
            if (currentNum > max) {
                max = currentNum;
                row = r;
                col = c;
            }
        }
    }
    if (row > -1) {
        networkMatrix[row][col] = emptyCell;
        return [row, col, max];
    }
    return [null];
}

function readFile() {
    return new Promise((resolve, reject) => {
        fs.readFile('../p107_network.txt', 'utf8', (err, data) => {
            if (err) {
                reject(err);
                return;
            }
            resolve(data.split(/\r?\n/).filter(line => line && line.trim() != "").map(row => row.split(",")));
        });
    });
}

function canReachVertex(end, start, networkMatrix, prev) {
    if (networkMatrix[end][start] !== emptyCell) {
        return true;
    }
    for (let r = 0; r < networkMatrix.length; r++) {
        if (networkMatrix[r][start] == 'v') {
            r++;
        }
        if (networkMatrix[r][start] !== emptyCell && isNotEndpoint(r, networkMatrix) && r !== prev) {
            networkMatrix[r][start] = 'v';
            let reachable = canReachVertex(end, r, networkMatrix, start);
            if (reachable) {
                return reachable;
            }
        }
    }
    return false;
}

function isNotEndpoint(vertex, networkMatrix) {
    let count = networkMatrix.filter(row => row[vertex] !== emptyCell).length;
    return count > 1;
}

function getSum(networkMatrix) {
    let sum = 0;
    for (let row = 0; row < networkMatrix.length; row++) {
        sum += networkMatrix[row].filter(element => element !== emptyCell).reduce((a, b) => Number(a) + Number(b));
    }
    return sum / 2;
}

main();