Language: Clojure
Problem: Determine the optimal division of a list of trucks into
convoys so that they can cross a bridge in as little time as possible.
Some trucks need to cross a bridge. The order of the trucks is given.
Each truck has a weight and a speed. Several trucks can form a convoy
and cross the bridge at the same time if (1) those trucks are already
next to each other and (2) the total weight of the convoy is less than
what the bridge can bear. A convoy can cross a bridge in the same
amount of time as its slowest member would cross alone.
Example:
bridge_capacity: 100
trucks: [{weight: 40, crossing_time: 30}, {weight: 30,
crossing_time: 50}, {weight: 40, crossing_time: 20}]
In this example, we can divide up the trucks in four possible ways:
1) All at once - in which case the bridge collapses because 40+30+40 > 100
2) One at a time - in which case it takes 30+50+20=100 time to cross
3) Combine the first two - in which case it takes 50+20=70 time to cross
4) Combine the last two - in which case it takes 30+50=80 time to cross
The correct answer here is to combine the first two trucks for the
optimal time of 70.
This problem is easy to get started, with calculations about whether a
certain convoy is too heavy, or how long that convoy will take to
cross, but becomes more interesting as we find ways to decide how the
trucks should be divided into convoys. Once we have code that solves
the problem, we can also consider improvements for dealing with larger
number of trucks with reasonable calculation times.
I usually use the test framework that is built in to Clojure, but I
really enjoyed having tests run automatically with Jasmine at the
Coding Dojo. Lazytest also does that, and I would like to give it a
try. It turns out that the same person created both the standard
Clojure test framework, which I usually use, as well as Lazytest. The
following article from last summer explains his reasoning for starting
over with a new test framework.
http://stuartsierra.com/2010/07/05/lazytest-status-report
See you next week.
I just received a job offer, and will be starting my first full-time
Lisp job in just a couple of weeks (MCNA Dental, Ft Lauderdale). I
will be very busy with moving preparations and studying their
technology stack, so I won't have time for Coding Dojo anymore.
For anyone who is curious about Clojure, I highly recommend this website:
--
Jack Pines
407-595-5648
Blog: http://bidevadventures.blogspot.com<http://bidevadventures.blogspot.com>
Twitter: http://twitter.com/#!/BIDevAdventures<http://twitter.com/#!/BIDevAdventures>
LinkedIn: http://www.linkedin.com/pub/jack-pines/2/62/727<http://www.linkedin.com/pub/jack-pines/2/62/727>
Resume: http://goo.gl/XTpzK <http://goo.gl/XTpzK>