Network Attach

index.html

<div id="mocha"></div>

network-attach.markdown

Network Attach

Nicola regularly inspects the local networks for security issues. He uses a smart and aggressive program which takes control of computers on the network. This program attacks all connected computers simultaneously, then uses the captured computers for further attacks. Nicola started the virus program in the first computer and took note of the time it took to completely capture the network. We can help him improve his process by modeling and improving his inspections.

We are given information about the connections in the network and the security level for each computer. Security level is the time (in minutes) that is required for the virus to capture a machine. Capture time is not related to the number of infected computers attacking the machine. Infection start from the 0th computer (which is already infected). Connections in the network are undirected. Security levels are not equal to zero (except infected).

Information about a network is represented as a matrix NxN size, where N is a number of computers. If tith computer connected with jth computer, then matrix[i][j] == matrix[j][i] == 1, else 0. Security levels are placed in the main matrix diagonal, so matrix[i][i] is the security level for the ith computer.

You should calculate how much time is required to capture the whole network in minutes.

Input: Network information as a list of lists with integers. Output: The total time of taken to capture the network as an integer. Precondition: 3 ≤ len(matrix) ≤ 10 matrix[0][0] == 0 all(len(row) == len(matrix[0]) for row in matrix) all(matrix[i][j] == matrix[j][i] for i in range(len(matrix)) for j in range(len(matrix))) all(0 < matrix[i][i] < 10 for i in range(1, len(matrix))) all(0 ≤ matrix[i][j] ≤ 1 for i in range(len(matrix)) for j in range(len(matrix)) if i != j)

A Pen by Vlad Bezden on CodePen.

License.

script.js

'use strict'

const INF = Number.MAX_SAFE_INTEGER

function Computer(id, securityLevel) {
  this.id = id
  this.securityLevel = securityLevel
  this.visited = false
  this.captureTime = INF
  this.nodes = []
}

/**
 * Creates link between computers
 * 
 * @param {Computer} computer - computer that link to be added to
 */
Computer.prototype.addEdge = function (computer) {
  this.nodes.push(computer)
}

/**
 * Finds computer by it's id
 * 
 * @param {Computer[]} computers - array of computers
 * @param {Number} id - id of the computer that needs to be found
 * @return {Computer} - found computer
 */
function getComputer(computers, id) {
  return computers.filter(x => x.id === id)[0]
}

/**
 * Finds candidate to be processed next in the graph. This logic is based on Dijkstra's shortest path algorithm
 * 
 * @param {Computer[]} candidate - array of candidates
 * @return {Computer} - candidate to be processed next
 */
function findCandidate(candidates) {
  candidates = candidates
    .filter(x => !x.visited)

  return candidates.length
    ? candidates.reduce((p, c) => (c.captureTime < p.captureTime ? p = c : p, p))
  : undefined        
}

/**
 * Creates computers and their dependencies on each other
 * 
 * @param {Number[][]} data - metrix representation of 0s and 1s of the network
 * @return {Computer[]} - array of computers on the network  
 */
function createGraph(data) {
  const computers = data[0].map((x, i) => {
    return new Computer(i, data[i][i])
  })

  computers.forEach((x, i) => {
    data[i].forEach((d, j) => {
      if (i != j && d != 0) {
        x.addEdge(getComputer(computers, j))
      }
    })
  })

  return computers
}

/**
 * Main driver of the program
 * 
 * @param {Number[][]} data - matrix of the computers and connections between them
 * @return {Number} - the minimum number of time to capture whole network
 */
function capture(data) {
  const graph = createGraph(data)
  let candidates = [],
      currentComputer = graph[0]

  currentComputer.captureTime = 0

  while (currentComputer) {
    currentComputer.visited = true

    currentComputer.nodes.forEach(x => {
      if (currentComputer.captureTime + x.securityLevel < x.captureTime) {
        x.captureTime = currentComputer.captureTime + x.securityLevel
      }
    })
    candidates = candidates.concat(...currentComputer.nodes)
    currentComputer = findCandidate(candidates)
  }

  return graph.slice(1)
    .reduce((p, c) => p > c.captureTime ? p : c.captureTime, 0)
}

mocha.setup('bdd')
const assert = chai.assert

describe('Assertions', () => {
  it('Base example', () => 
     assert.equal(capture([
    [0, 1, 0, 1, 0, 1],
    [1, 8, 1, 0, 0, 0],
    [0, 1, 2, 0, 0, 1],
    [1, 0, 0, 1, 1, 0],
    [0, 0, 0, 1, 3, 1],
    [1, 0, 1, 0, 1, 2]]), 8))

  it ('Low security', () => 
      assert.equal(capture([
    [0, 1, 0, 1, 0, 1],
    [1, 1, 1, 0, 0, 0],
    [0, 1, 2, 0, 0, 1],
    [1, 0, 0, 1, 1, 0],
    [0, 0, 0, 1, 3, 1],
    [1, 0, 1, 0, 1, 2]]), 4))

  it ('Small', () => 
      assert.equal(capture([
    [0, 1, 1],
    [1, 9, 1],
    [1, 1, 9]]), 9))

  console.log("Coding complete? Click 'Check' to review your tests and earn cool rewards!");
})

mocha.run()

scripts

<script src="https://cdnjs.cloudflare.com/ajax/libs/mocha/3.1.1/mocha.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/chai/3.5.0/chai.min.js"></script>

styles

<link href="https://cdnjs.cloudflare.com/ajax/libs/mocha/3.1.1/mocha.min.css" rel="stylesheet" />