1 files changed, 59 insertions, 1 deletions
diff --git a/graph.lua b/graph.lua
index 1feefd1..82b6a01 100755
--- a/graph.lua
+++ b/graph.lua
@@ -1,6 +1,7 @@
 #!/usr/bin/env lua
 local automaton = require "automaton"
 local generate = require "generate"
+local reading = require "reading"
 local init = automaton(generate.trange(1, 25))
 
 
@@ -14,6 +15,7 @@ local function node (graph, id)
 		outcoming = {},
 		incoming = {},
 		distance = {},
+		paths = {},
 	}
 	graph.nodes[id] = x
 	return x
@@ -58,6 +60,62 @@ 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
-	print(v.id, v.distance[3], v.distance[19])
+	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