diff options
| -rwxr-xr-x | graph.lua | 110 |
1 files changed, 46 insertions, 64 deletions
@@ -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 |