使用Ruby amb解决说谎者谜题

说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：五个女生参加一个考试，她们的家长对考试结果过分关注。为此她... 推广和普及Java技术，为国内众多的Java爱好者提供一个“平等

说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：

五个女生参加一个考试，她们的家长对考试结果过分关注。为此她们约定，在给家里写信谈到考试的时候，每个姑娘都要写一句真话和一句假话。下面是从她们的信里摘抄出来的句子： dedecms.com

Betty ： kitty考第二，我只考了第三

Ethel ：你们应该很高兴听到我考了第一，joan第二本文来自织梦

joan ：我考第三，可怜的Ethel垫底

织梦内容管理系统

kitty：我第二，marry只考了第四本文来自织梦

marry：我是第四，Betty的成绩最高。本文来自织梦

这五个姑娘的实际排名是什么？本文来自织梦

Ruby本来就有call/cc，因此也可以实现amb操作符，网上已经有一个实现了： copyright dedecms

class Amb
  class ExhaustedError < RuntimeError; end
  def initialize
    @fail = proc { fail ExhaustedError, "amb tree exhausted" }

织梦内容管理系统

  end
  def choose(*choices)
    prev_fail = @fail
    callcc { |sk|
      choices.each { |choice|
        callcc { |fk| copyright dedecms
          @fail = proc {
            @fail = prev_fail
            fk.call(:fail)
          }
          if choice.respond_to? :call
            sk.call(choice.call)
          else

内容来自dedecms

            sk.call(choice)
          end
        }
      }
      @fail.call
    }
  end
  def failure
    choose
  end

  def assert(cond)
    failure unless cond
  end
  alias :require :assert
end

内容来自dedecms

这一段代码与scheme宏实现amb是完全相同的：内容来自dedecms

(define amb-fail '*)

(define initialize-amb-fail 织梦好，好织梦
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb tree exhausted")))))

(initialize-amb-fail)
(define call/cc call-with-current-continuation)

内容来自dedecms

(define-syntax amb
(syntax-rules ()
((amb alt

)
     (let ((prev-amb-fail amb-fail))
       (call/cc
        (lambda (sk) copyright dedecms

          (call/cc
           (lambda (fk)
             (set! amb-fail
                   (lambda ()
                     (set! amb-fail prev-amb-fail)

织梦好，好织梦

(fk 'fail)))
(sk alt)))

(prev-amb-fail)))))))

回到谜题，从题意可知每个姑娘的两句话的异或结果为true，并且姑娘的排名肯定不会相同，因此定义两个辅助过程：

require 'amb'
def distinct?(items)
items.uniq==items

本文来自织梦

end
def xor(exp1,exp2)
(exp1 or exp2) and !(exp1 and exp2)
end

织梦内容管理系统

剩下的完全就是将题目翻译成代码即可了，没有多少可以解释的东西：

织梦内容管理系统

amb=Amb.new
betty=amb.choose(*[1,2,3,4,5])

内容来自dedecms

ethel=amb.choose(*[1,2,3,4,5])
joan=amb.choose(*[1,2,3,4,5])

织梦好，好织梦

kitty=amb.choose(*[1,2,3,4,5])
marry=amb.choose(*[1,2,3,4,5])

amb.require(xor(kitty==2,betty==3))
amb.require(xor(ethel==1,joan==2))
amb.require(xor(joan==3,ethel==5))
amb.require(xor(kitty==2,marry==4))

织梦好，好织梦

amb.require(xor(marry==4,betty==1))
amb.require(distinct?([betty,ethel,joan,kitty,marry]))
puts "betty:#{betty} ethel:#{ethel} joan:#{joan} kitty:#{kitty} marry:#{marry}"

织梦好，好织梦

答案就是：betty：3 ethel：5 joan：2 kitty：1 marry：4

内容来自dedecms

最后给出一个Prolog的解答：

dedecms.com

notmember(A,[]).
notmember(A,[B|L]):-
  A\==B,
  notmember(A,L).
distinct([A,B,C,D,E]):-
   notmember(A,[B,C,D,E]),
   notmember(B,[A,C,D,E]), 本文来自织梦
   notmember(C,[A,B,D,E]),
   notmember(D,[A,B,C,E]),
   notmember(E,[A,B,C,D]).
xor(Exp1,Exp2):-
   (Exp1;Exp2),\+ (Exp1,Exp2).
solve(Betty,Ethel,Joan,Kitty,Marry):-
   X=[1,2,3,4,5], 内容来自dedecms
   member(Betty,X),
   member(Ethel,X),
   member(Joan,X),
   member(Kitty,X),
   member(Marry,X),
   distinct([Betty,Ethel,Joan,Kitty,Marry]),
   xor(Kitty=:=2,Betty=:=3),
   xor(Ethel=:=1,Joan=:=2),

织梦内容管理系统

   xor(Joan=:=3,Ethel=:=5),
   xor(Kitty=:=2,Marry=:=4), 织梦好，好织梦
   xor(Marry=:=4,Betty=:=1).

本文来自织梦

复制地址和好友共享