From: Jim Weirich <jim@...>
Date: 2006-03-16T22:20:12+09:00
Subject: Re: Constraint Processing (#70)

I've been having a lot of fun with this quiz.  Pit Capitain 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 Weirich (jim@weirichhouse.org).  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
  # <code>assert(false)</tt>.
  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 Weirich

-- 
Posted via http://www.ruby-forum.com/.