Simplified graph preparation and transversal methods

1 files changed, 46 insertions, 64 deletions

diff --git a/graph.lua b/graph.lua
index 82b6a01..2b756d4 100755
--- a/graph.lua
+++ b/graph.lua
@@ -5,61 +5,38 @@ 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
+local function add_node (graph, id)
+	local node = graph[id]
+	if node then
+		return node
 	end
-	x = {
+	node = {
 		id = id,
 		outcoming = {},
 		incoming = {},
-		distance = {},
 		paths = {},
 	}
-	graph.nodes[id] = x
-	return x
+	graph[id] = node
+	return node
 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)
+		local a = add_node(graph, src)
+		local b = add_node(graph, dst)
 		a.outcoming[kind] = b
 		b.incoming[kind] = a
 	end
 end
 
 
-local graph = {
-	nodes = {},
-}
+local graph = {}
 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,
@@ -77,45 +54,50 @@ local function trigram (path)
 end
 
 
-local function generate_paths (start, dest)
-	local queue = {{node=start, path={}, left=3}}
-	local paths = {}
+local function shallow_copy (obj)
+	local new = {}
+	for k, v in ipairs(obj) do
+		new[k] = v
+	end
+	return new
+end
+
+
+local function generate_paths_from (start, length)
+	local queue = {{node=start, length=0, path={}}}
 	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
+		local entry = table.remove(queue, 1)
+		if entry.length == length then
+			local paths = entry.node.paths[start.id] or {}
+			table.insert(paths, entry.path)
+			entry.node.paths[start.id] = paths
 		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})
+		if entry.length < length then
+			for kind, node in pairs(entry.node.incoming) do
+				local path = shallow_copy(entry.path)
+				table.insert(path, 1, kind)
+				table.insert(queue, {node=node, length=entry.length + 1, path=path})
 			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))
+local function error_no_path_between (start, dest)
+	if not start.paths[dest.id] then
+		io.stderr:write(string.format("cannot move from %d to %d\n", start.id, dest.id))
 	end
-	if #v.paths[19] < 1 then
-		io.stderr:write(string.format("cannot move from %d to %d\n", v.id, 19))
+end
+
+
+generate_paths_from(graph[3], 3)
+generate_paths_from(graph[19], 3)
+for _, node in ipairs(graph) do
+	for target, paths in pairs(node.paths) do
+		for _, path in ipairs(paths) do
+			print(string.format("%d,%d,%d,%s,%s,%s", node.id, target, trigram(path), path[1], path[2], path[3]))
+		end
 	end
+	error_no_path_between(node, graph[3])
+	error_no_path_between(node, graph[19])
 end