I’ve been having a lot of fun with this quiz. Pit C. sent me a
improved version of Amb that is more “Rubyish” and much easier to read
(my original was a direct translation of the scheme version). I’ve
added comments and a bit of polish to his cleanup, so here’s the new and
improved version of Amb along with another puzzle (just for fun).
– BEGIN AMB
#!/usr/bin/env ruby
Copyright 2006 by Jim W. ([email protected]). All rights
reserved.
Permission is granted for use, modification and distribution as
long as the above copyright notice is included.
Amb is an ambiguous choice maker. You can ask an Amb object to
select from a discrete list of choices, and then specify a set of
constraints on those choices. After the constraints have been
specified, you are guaranteed that the choices made earlier by amb
will obey the constraints.
For example, consider the following code:
amb = Amb.new
x = amb.choose(1,2,3,4)
At this point, amb may have chosen any of the four numbers (1
through 4) to be assigned to x. But, now we can assert some
conditions:
amb.assert (x % 2) == 0
This asserts that x must be even, so we know that the choice made by
amb will be either 2 or 4. Next we assert:
amb.assert x >= 3
This further constrains our choice to 4.
puts x # prints ‘4’
Amb works by saving a contination at each choice point and
backtracking to previousl choices if the contraints are not
satisfied. In actual terms, the choice reconsidered and all the
code following the choice is re-run after failed assertion.
You can print out all the solutions by printing the solution and
then explicitly failing to force another choice. For example:
amb = Amb.new
x = Amb.choose(*(1…10))
y = Amb.choose(*(1…10))
amb.assert x + y == 15
puts “x = #{x}, y = #{y}”
amb.failure
The above code will print all the solutions to the equation x + y ==
15 where x and y are integers between 1 and 10.
The Amb class has two convience functions, solve and solve_all for
encapsulating the use of Amb.
This example finds the first solution to a set of constraints:
Amb.solve do |amb|
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
puts x
end
This example finds all the solutions to a set of constraints:
Amb.solve_all do |amb|
x = amb.choose(1,2,3,4)
amb.assert (x % 2) == 0
puts x
end
class Amb
class ExhaustedError < RuntimeError; end
Initialize the ambiguity chooser.
def initialize
@back = [
lambda { fail ExhaustedError, “amb tree exhausted” }
]
end
Make a choice amoung a set of discrete values.
def choose(*choices)
choices.each { |choice|
callcc { |fk|
@back << fk
return choice
}
}
failure
end
Unconditional failure of a constraint, causing the last choice to
be retried. This is equivalent to saying
assert(false).
def failure
@back.pop.call
end
Assert the given condition is true. If the condition is false,
cause a failure and retry the last choice.
def assert(cond)
failure unless cond
end
Report the given failure message. This is called by solve in the
event that no solutions are found, and by +solve_all+ when no more
solutions are to be found. Report will simply display the message
to standard output, but you may override this method in a derived
class if you need different behavior.
def report(failure_message)
puts failure_message
end
Class convenience method to search for the first solution to the
constraints.
def Amb.solve(failure_message=“No Solution”)
amb = self.new
yield(amb)
rescue Amb::ExhaustedError => ex
amb.report(failure_message)
end
Class convenience method to search for all the solutions to the
constraints.
def Amb.solve_all(failure_message=“No More Solutions”)
amb = self.new
yield(amb)
amb.failure
rescue Amb::ExhaustedError => ex
amb.report(failure_message)
end
end
– END AMB
And a new puzzle to go along with the new version of Amb:
– BEGIN PUZZLE
#!/usr/bin/env ruby
Two thieves have being working together for years. Nobody knows
their identities, but one is known to be a Liar and the other a
Knave. The local sheriff gets a tip that the bandits are about to
commit another crime. When the sheriff arrives at the seen of the
crime, he finds three men, A, B, and C. C has been stabbed with a
dagger. He cries out, “A stabbed me” before anybody can say anything
else; then, he falls down dead from the stabbing.
Not sure which of the three men are the crooks, the sheriff takes
the two suspects to the jail and interrogates them. He gets the
following information.
A’s statements:
1. B is one of the crooks.
2. B?s second statement is true.
3. C was telling the truth.
B’s statements:
1. A killed the other guy.
2. C was killed by one of the thieves.
3. C?s next statement would have been a lie.
C’s statement:
1. A stabbed me.
The sheriff knows that the murderer is among these three people. Who
should the sheriff arrest for killing C?
NOTE: Liars always lie, knights always tell the truth and knaves
strictly alternate between truth and lies.
require ‘amb’
Some helper methods for logic
class Object
def implies(bool)
self ? bool : true
end
def xor(bool)
self ? !bool : bool
end
end
True if the given list of boolean values alternate between true and
false.
def alternating(*bools)
expected = bools.first
bools.each do |item|
if item != expected
return false
end
expected = !expected
end
true
end
A person class to keep track of the information about a single
person in our puzzle.
class Person
attr_reader :name, :type, :murderer, :thief
attr_accessor :statements
def initialize(amb, name)
@name = name
@type = amb.choose(:liar, :knave, :knight)
@murderer = amb.choose(true, false)
@thief = amb.choose(true, false)
@statements = []
end
def to_s
“#{name} is a #{type} " +
(thief ? “and a thief.” : “but not a thief.”) +
(murderer ? " He is also the murderer.” : “”)
end
end
Some lists used to do collective assertions.
people = Array.new(3)
thieves = Array.new(2)
Find all the solutions.
Amb.solve_all do |amb|
count = 0
Create the three people in our puzzle.
a = Person.new(amb, “A”)
b = Person.new(amb, “B”)
c = Person.new(amb, “C”)
people = [a, b, c]
Basic assertions about the thieves.
thieves = people.select { |p| p.thief }
amb.assert thieves.size == 2 # Only two thieves
amb.assert thieves.collect { |p| # One is a knave, the other a liar
p.type.to_s
}.sort == [“knave”, “liar”]
Basic assertions about the murderer.
amb.assert people.select { |p| # There is only one murderer
p.murderer
}.size == 1
murderer = people.find { |p| p.murderer }
amb.assert ! c.murderer # No suicides
Create the logic statements of each of the people involved. Note
we are just creating them here. We won’t assert the truth of them
until a bit later.
c1 = a.murderer # A stabbed me
c2 = case c.type # (hypothetical next statement)
when :knight
false
when :liar
true
when :knave
!c1
end
c.statements = [c1, c2]
b1 = a.murderer # A killed the other guy
b2 = murderer.thief # C was killed by one of the thieves
b3 = ! c2 # C’s next statement would have been
true
b.statements = [b1, b2, b3]
a1 = b.thief # B is one of the crooks
a2 = b2 # B’s second statement is true
a3 = c1 # C was telling the truth.
a.statements = [a1, a2, a3]
Now we make assertions on the truthfulness of each of persons
statements based on whether they are a Knight, a Knave or a Liar.
people.each do |p|
amb.assert(
(p.type == :knight).implies(
p.statements.all? { |s| s }
))
amb.assert(
(p.type == :liar).implies(
p.statements.all? { |s| !s }
))
amb.assert(
(p.type == :knave).implies(
alternating(*p.statements)
))
end
Now we print out the solution.
count += 1
puts “Solution #{count}:”
people.each do |p| puts p end
puts
end
– END PUZZLE
– Jim W.
