The Crossing Problem

VRML crossing notes

Notes on creating VRML visualization of a crossing problem and an example.


      father   son1     son2                 /                           /
       ...                                 /                           /
       . .                                /                          /
       ...                               /                         /
        |       ...      ...            /                         /
     -------    . .      . .          /                          /
        |       ...      ...        / \  boat    /             /
        |        |        r|     /     \________/           /
        |     ------- --------         max load
       / \       |        |            200 lbs.
     /    \     / \      / \
       200      100      100
       lbs.     lbs.     lbs.

trip ==> crossings.

crossings ==> done.
crossings ==> do-crossing crossings

do-crossing ==> select-passengers check-load change-sides

Routines in my program

trip		do the full crossing problem

trip2		trip2 is a debugging tool

crossing	do the sequence of crossings

do_crossing	do a single crossing


init		starting values, all on side1, none on side2

done		succeed if boat and all passengers at side2

select_passengers pick subset of passengers and move


move_from	select passengers and do the move

stop_repeats	make sure we do not repeat a previous configuration

check_load	succeed if boat not overloaded

member		succeed if item is in List

subset		pick subset or test if a subset

member_out	remove item from ListOld giving ListNew

set_member	succeed if Set is found in list of sets

setminus	subtract out a set

setplus		add two sets

set_equal	test if two sets are equal

select_subset	select a subset

Source code for the crossing problem. A faster version of the code. Another version of the code.

Old transparencies for the crossing problem.