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, 9, 3];
    paths ~= [1, 9, 5];
    paths ~= [4, 9, 5];
    paths ~= [4, 9, 2];
    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.";
}