challenge-115/abigail/lua/ch-1.lua


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

#!/opt/local/bin/lua

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

--
-- Run as: lua ch-1.lua < input-file
--

for line in io . lines () do
    local graph = {}
    local nodes = {}
    for s in line : gmatch ("%S+")
    do  local first = s : sub ( 1,  1)
        local last  = s : sub (-1, -1)
        if   graph [first] == nil
        then graph [first] =  {}
        end
        graph [first] [last] = 1
        nodes [first] = 1
        nodes [last]  = 1
    end

    --
    -- Make sure all entries exists, as lua doesn't autovivify
    --
    for node1 in pairs (nodes)
    do  for node2 in pairs (nodes)
        do  if   graph [node1] == nil
            then graph [node1] = {}
            end
            if   graph [node1] [node2] == nil
            then graph [node1] [node2] = 0
            end
        end
    end

    --
    -- Calculate the transitive closure
    --
    for k in pairs (nodes)
    do  for i in pairs (nodes)
        do  for j in pairs (nodes)
            do  if   graph [i] [j] == 0 and graph [k] [j] == 1 and
                                            graph [i] [k] == 1
                then graph [i] [j] = 1
                end
            end
        end
    end

    --
    -- We have a loop iff there is a node which is reachable from itself
    --
    local out = 0
    for i in pairs (nodes)
    do  if   graph [i] [i] == 1
        then out = 1
        end
    end

    print (out)
end