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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#!/usr/bin/env lua
local automaton = require "automaton"
local generate = require "generate"
local reading = require "reading"
local init = automaton(generate.trange(1, 25))
local function node (graph, id)
local x = graph.nodes[id]
if x then
return x
end
x = {
id = id,
outcoming = {},
incoming = {},
distance = {},
paths = {},
}
graph.nodes[id] = x
return x
end
local function add_edges (graph, state, kind)
for dst, src in ipairs(state) do
local a = node(graph, src)
local b = node(graph, dst)
a.outcoming[kind] = b
b.incoming[kind] = a
end
end
local graph = {
nodes = {},
}
add_edges(graph, init:left(), "left")
add_edges(graph, init:right(), "right")
add_edges(graph, init:pivot(), "centre")
add_edges(graph, init:up(), "up")
add_edges(graph, init:down(), "down")
local function calculate_distances_from (start)
local visited = {}
local queue = {{node=start, distance=0}}
while #queue > 0 do
local step = table.remove(queue, 1)
if not visited[step.node.id] then
step.node.distance[start.id] = step.distance
for _, x in pairs(step.node.incoming) do
table.insert(queue, {node=x, distance=step.distance+1})
end
visited[step.node.id] = true
end
end
end
calculate_distances_from(graph.nodes[3])
calculate_distances_from(graph.nodes[19])
local map = {
centre = 0,
up = 1,
right = 2,
down = 3,
left = 4,
}
local function trigram (path)
return reading.trigram_to_value(
map[path[1]],
map[path[2]],
map[path[3]])
end
local function generate_paths (start, dest)
local queue = {{node=start, path={}, left=3}}
local paths = {}
while #queue > 0 do
local step = table.remove(queue, 1)
if step.node.distance[dest.id] == 0 and step.left == 0 then
if trigram(step.path) < 83 then
table.insert(paths, step.path)
end
end
for kind, x in pairs(step.node.outcoming) do
local distance = x.distance[dest.id]
if not distance then
error "must calculate distances first"
end
local left = step.left - 1
if left >= distance then
local path = {}
for i, v in ipairs(step.path) do
path[i] = v
end
table.insert(path, kind)
table.insert(queue, {node=x, path=path, left=left})
end
end
end
start.paths[dest.id] = paths
end
for _, v in ipairs(graph.nodes) do
generate_paths(v, graph.nodes[3])
generate_paths(v, graph.nodes[19])
--- To reliably "encrypt" arbitrary message we must be able to move from any slot to both output slots in exactly
--- three moves avoiding generating trigrams with values above 82.
if #v.paths[3] < 1 then
io.stderr:write(string.format("cannot move from %d to %d\n", v.id, 3))
end
if #v.paths[19] < 1 then
io.stderr:write(string.format("cannot move from %d to %d\n", v.id, 19))
end
end
|
