challenge-115/abigail/node/ch-1.js


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#!/usr/local/bin/node

//
// See ../README.md
//

//
// Run as: node ch-1.js < input-file
//

  require ('readline')
. createInterface ({input: process . stdin})   
. on ('line', _ => check_for_cycl (_))
;


function check_for_cycl (line) {
    //
    // Read in the data, build a graph where the first and last
    // characters of the strings form the nodes, and we have a
    // directed edge from the beginning to the end of a string.
    //
    let strings = line . split (/\s+/)
    let nodes = {}   // Keep track of all the nodes
    let graph = {}
    strings . forEach (_ => {
        let first = _ . substr ( 0, 1)
        let last  = _ . substr (-1, 1)
        nodes [first] = 1
        nodes [last]  = 1
        if (!graph [first]) {
            graph [first] = {}    // No autovivification in Node.js
        }
        if (!graph [last]) {
            graph [last] = {}     // No autovivification in Node.js
        }
        graph [first] [last] = 1  // Add a node
    })


    //
    // Calculate the transitive closure of the graph using
    // the Floyd-Warshall algorithm
    //
    nodes = Object . keys (nodes)
    nodes . forEach (k => {
        nodes . forEach (i => {
            nodes . forEach (j => {
                if (!graph [i] [j] && graph [k] [j] && graph [i] [k]) {
                    graph [i] [j] = 1
                }
            })
        })
    })

    //
    // We have a loop iff there is at least one node which is
    // reachable from itself.
    //
    let out = 0
    nodes . forEach (i => {
        if (graph [i] [i]) {
            out = 1
        }
    })

    console . log (out)
}