#!/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