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.