Solution to the infamous bridge problem
Scala Shell
Latest commit e407ee7 Jan 27, 2014 @ebowman Gentle refactoring
Permalink
Failed to load latest commit information.
project Upgraded to sbt 0.13.1 & scala 2.10.3 Jan 26, 2014
src Gentle refactoring Jan 27, 2014
.gitignore cleaning up Apr 15, 2011
LICENSE Ready to push to GitHub Jul 3, 2011
People.txt Gentle refactoring Jan 27, 2014
README.md Update README Jan 26, 2014
build.sbt Upgraded to sbt 0.13.1 & scala 2.10.3 Jan 26, 2014

README.md

Memory-Efficient Bridge Solver

15 April 2011 (Updated 3 July 2011) 26 January 2014 (Upgraded to scala 2.10.3 & sbt 0.13.1)

Inspired by Logic Programming in Scala, Part 1, this program reads a configuration file listing some people, and how long each of them takes to cross the bridge, and solves the problem, indicating what is the minimum amount of time the people can take to cross the bridge, then prints all the solutions.

First, update People.txt to contain the people and walking times you want. A line starting with #, or that otherwise can't be parsed reasonably, is ignored, mostly.

./sbt

You'll get the sbt shell, then you can do:

> run People.txt

and it should should download everything needed, and run the program.

A nice hard input to solve is this:

Alice 7
Bob 11
Candace 9
Dave 6
Eric 10
Fred 5
George 5
Henry 9

...which took around 15 minutes. Using the other implementations to solve this input tends to exhaust memory; this version is extremely memory efficient.

Note there is a code snippet from Pavel Fatin's blog, for generating prime numbers. It is (c) 2011 by Pavel Fatin and is used with permission.

Enjoy.