Solving connected sums

connected_sum.js

'use strict';

/**
 * 
 * @param {Array<[number, number]>} list_of_vertices
 * @returns {Array<Set<number>>}
 */
function get_connected_vertices(list_of_vertices) {
    console.log('Input: ', list_of_vertices);
    /**
     * @type {Array<Set<number>>}
     */
    const connections_list = [];

    /**
     * 
     * @param {[number, number]} edges
     */
    function isInConn(...edges) {
        let isIn = -1;
        for(let _index = 0; _index < connections_list.length; _index++)
        {
            const connection_list_item = connections_list[_index];
            if (edges.some(edge => connection_list_item.has(edge)))
            {
                isIn = _index;
                break;
            }
        }

        return isIn;
    }

    // walk each vertice

    list_of_vertices.forEach(([edgeA, edgeB]) => {
        let connIndex = -1;
        connIndex = isInConn(edgeA, edgeB);
        if (connIndex > -1) 
        {
            connections_list[connIndex].add(edgeA);
            connections_list[connIndex].add(edgeB);
            return;
        }

        // add to a new conn
        connections_list.push(new Set([edgeA, edgeB]));
        
    });

    // console.log('All connections: ', Array.from(connections_list));

    return Array.from(connections_list);
}

/**
 * 
 * @param {number} no_nodes 
 * @param {Array<[number, number]>} edges_list 
 */
function solve_connected_sums(no_nodes, edges_list) {
    const all_nodes = Array(no_nodes).fill(1).map((_, index) => index + 1);

    const connected_vertices = get_connected_vertices(edges_list);
    const lonely_nodes = all_nodes.filter(node => !connected_vertices.some(_connection => _connection.has(node)));
    const connection_lengths = [...(connected_vertices.map(vertice => vertice.size))];

    return connection_lengths.reduce((acc, curr) => acc = acc + Math.ceil(Math.sqrt(curr)), lonely_nodes.length * Math.ceil(Math.sqrt(1)));
}

console.log(solve_connected_sums(4, [[1, 2], [1, 4]]));
console.log(solve_connected_sums(8, [[8, 1], [5, 8], [7, 3], [8, 6]]));

connected_sum.MD

Connected Sum

A screenshot can be found here

Images

• https://media.cheggcdn.com/media/b9d/b9d19b2f-e7e9-43ed-80a8-f5cc4cbe8654/phplW5wFH.png
• https://media.cheggcdn.com/media/027/027c0228-323d-43ee-b9dd-a766b1548eb0/phpY2i471.png
• https://media.cheggcdn.com/media/f14/f1469362-2e60-44b8-9e91-db999d3002ed/phpvzNLiP.png

The question seems to have changed though

Problem Definition

You get a list of vertices V ([x, y], [a, z], [x, a]) where a, x, y, z are nodes Where Vn represents a line connecting say x and z The goal is to:

• Find all connections
• All lonely nodes

My proposal

• Have two cursors
• Have a list of connections
• The first walking through the list:
  • Pick an element, if it doesnt exist already in the connections list (and the second item also doesnt), create a new set in that list
  • If one of the elements exist in the connections list, simply add the other to that set

Improvements

• Looking up if the node exists in a vertice (if its connected): Sort the array first, then compare Max() and node
• Use a generator (or iterator) to generate the node space from the number of nodes

Updated to check for the existence of a node in a connected vertice in one pass