gistfile1.d

module trainsearch;

void main() {
	int[][] paths;
	// There are only six paths through the
	// intersection that a train can take.
	/*
	paths ~= [2];
	paths ~= [3];
	paths ~= [4];
	paths ~= [2, 1, 4];
	paths ~= [4, 1, 3];
	paths ~= [3, 1, 2];
	*/
	/*
	paths ~= [327, 338];
	paths ~= [327, 344, 334];
	paths ~= [345, 334];
	paths ~= [345, 344, 330];
	paths ~= [331, 330];
	paths ~= [331, 344, 338];
	*/
	paths ~= [1, 2];
	paths ~= [1, 11, 4];
	paths ~= [3, 11, 10, 6];
	paths ~= [5, 10, 6];
	int[] entry_blocks;
	for auto path <- paths {
		int block = path[0];
		for int i <- entry_blocks if (i == block) break;
		then entry_blocks ~= block;
	}
	// What is a deadlock?
	// A deadlock is a state, created when multiple
	// trains enter the intersection at once, where no
	// train can claim the next area of its path.
	as_type x (int block, int train, bool enter, string delegate(x) info, x next)* block_actions;
	// continuation passing style
	void record_action(int block, int train, bool enter, void delegate() cont) {
		bool is_free = true;
		for (auto ptr = block_actions; ptr; ptr = ptr.next) {
			if (ptr.block == block) {
				if (ptr.enter) {
					is_free = false;
				} else {
					is_free = true;
				}
				break;
			}
		}
		alias leave = !enter;
		assert(!(leave && is_free), "tried to leave a block that was not in use");
		if (enter && !is_free) return;
		auto info = λ(type-of block_actions record) {
			return "Train $(record.train+1) enters block $(record.block).";
		};
		using scoped block_actions =
			&auto record = (block, train, enter, info, block_actions)
		{
			cont();
		}
	}
	alias TrainAction = void delegate(int train, void delegate());
	TrainAction make_action(int block, bool enter) {
		return new λ(int train, void delegate() cont) {
			record_action(block, train, enter, cont);
		}
	}
	// How does a train pass through the intersection?
	TrainAction[][] train_paths;
	for auto path <- paths {
		// if undo is true, undo the effect of the action.
		TrainAction[] actions;
		// First, it tries to claim all its blocks.
		for int block <- path {
			actions ~= make_action(block, true);
		}
		// Then, it releases them in the same order it entered.
		for int block <- path {
			actions ~= make_action(block, false);
		}
		train_paths ~= actions;
	}
	// How do we discover deadlocks?
	// We simply consider all possible combinations of
	// "trains wanting to take a path through the intersection"
	// - since there's only three entry blocks, there's only 8 possible
	// combinations - and for each of them, any possible
	// sequence of train movements.
	for int variant <- 0 .. (1 << entry_blocks.length) {
		struct Option {
			int[] blocks;
			TrainAction[] list;
		}
		Option[][] train_options;
		int[] used_blocks;
		for int idx <- ints && int block <- entry_blocks {
			if (variant & (1 << idx)) {
				Option[] alternatives;
				used_blocks ~= block;
				for auto action <- train_paths && auto path <- paths {
					if (path[0] == block) {
						alternatives ~= Option:(path, action);
					}
				}
				train_options ~= alternatives;
			}
		}
		int num_success_states = 0;
		void for_any_combination() {
			bool there_were_trains = false;
			bool one_could_move = false;
			for int train <- ints && ref options <- train_options {
				if (options.length > 1) {
					for int i <- 0..options.length {
						using scoped options = options[i..i+1] {
							auto info = new λ(type-of block_actions record) {
								return "Train $(record.train+1) chooses path $(options[0].blocks).";
							}
							using scoped block_actions =
								&auto record = (-1, train, false, info, block_actions)
							{
								for_any_combination();
							}
						}
					}
					return;
				}
				ref list = options[0].list;
				if (!list.length) continue;
				there_were_trains = true;
				auto dg = list[0];
				dg(train, λ{
					one_could_move = true;
					using scoped list = list[1..$] {
						for_any_combination();
					}
				});
			}
			if (!there_were_trains) {
				num_success_states ++;
				return;
			}
			if (one_could_move) {
				return;
			}
			writeln "Variant $variant: $(train_options.length) simultaneous trains, from $used_blocks.";
			writeln "There were trains, but none of them could move. Failure state.";
			writeln "The events leading up to this were:";
			void print_forwards(type-of block_actions action) {
				if (action.next) print_forwards(action.next);
				writeln "  $(action.info(action))";
			}
			print_forwards block_actions;
			for int train <- ints && auto options <- train_options {
				if (!options[0].list.length) continue;
				auto block = options[0].(blocks[$*2-list.length]);
				// Which train is using block?
				int responsible = -1;
				for (auto ptr = block_actions; ptr; ptr = ptr.next) {
					if (ptr.block == block) {
						assert(ptr.enter, "block is free, what happened here?!");
						responsible = ptr.train;
						break;
					}
				}
				assert(responsible != -1);
				writeln $ "Train $(train+1) wants to enter block "
					~"$block but it's blocked by train $(responsible+1).";
			}
			exit(1);
		}
		for_any_combination();
		writeln $ "Variant $variant: "
			~"$(train_options.length) simultaneous trains, from $used_blocks. "
			~"$num_success_states successful orderings.";
	}
	writeln "No possible deadlocks.";
}