Solve the XKCD Bridge puzzle
$ ./bridge-test.rb
Loaded suite ./bridge-test
Started
C and D crossed over in 2 minutes.
D crossed back in 1 minutes.
A and B crossed over in 10 minutes.
C crossed back in 2 minutes.
D and C crossed over in 2 minutes.
-----------------------------------
Best cross is done in 17 minutes.
.
Finished in 0.002076 seconds.
1 tests, 1 assertions, 0 failures, 0 errors, 0 skips| #!/usr/bin/env ruby | |
| require './bridge' | |
| require 'test/unit' | |
| class BridgeTest < Test::Unit::TestCase | |
| def test_xkcd_bridge | |
| b = Bridge.new | |
| assert_equal(17, b.best) | |
| b.pp | |
| end | |
| end |
| #!/usr/bin/env ruby | |
| class Bridge | |
| def initialize | |
| @people = { 10 => "A", 5 => "B", 2 => "C", 1 => "D"} | |
| @best = 1.0/0 #Infinity | |
| @bestCrossHistory = "" | |
| cross(@people.to_a.map { |x| x.first }, [], 0, "") | |
| end | |
| def cross(origin, destination, memo, crossHistory) | |
| if origin.length > 1 | |
| for first,second in origin.combination(2) | |
| #Make copies of all the arguments | |
| newMemo = memo | |
| newCrossHistory = crossHistory | |
| o = Array.new(origin) | |
| d = Array.new(destination) | |
| d.push first | |
| d.push second | |
| newCrossHistory += @people[first] + " and " + @people[second] + " crossed over " | |
| o.delete first | |
| o.delete second | |
| newMemo += [first, second].max | |
| newCrossHistory += "in " + [first, second].max.to_s + " minutes.\n" | |
| if o.length > 0 | |
| o.push d.min | |
| newMemo += d.min | |
| newCrossHistory += @people[d.min] + " crossed back in " + d.min.to_s + " minutes.\n" | |
| d.delete d.min | |
| end | |
| cross(o, d, newMemo + 0, newCrossHistory) | |
| end | |
| else | |
| if memo < @best | |
| @best = memo | |
| @bestCrossHistory = crossHistory | |
| end | |
| end | |
| end | |
| def pp | |
| puts @bestCrossHistory | |
| puts "-----------------------------------" | |
| puts "Best cross is done in " + @best.to_s + " minutes." | |
| end | |
| def best | |
| return @best | |
| end | |
| end |