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