使用Ruby amb解决说谎者谜题-白红宇

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

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

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

Ethel : 你们应该很高兴听到我考了第一，joan第二

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

kitty: 我第二，marry只考了第四

marry: 我是第四，Betty的成绩最高。

这五个姑娘的实际排名是什么？

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

class

Amb

class

ExhaustedError

RuntimeError; end

def initialize

@fail

proc { fail ExhaustedError,

amb tree exhausted

}

end

def choose(

choices)

prev_fail

@fail

callcc {

choices.each {

choice

callcc {

@fail

proc {

@fail

prev_fail

fk.call(:fail)

}

choice.respond_to

:call

sk.call(choice.call)

else

sk.call(choice)

end

}

@fail.call

}

end

def failure

choose

end

def

assert

(cond)

failure unless cond

end

alias :require :

assert

end

这一段代码与scheme宏实现amb是完全相同的：

(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)

(define

syntax amb

(syntax

rules ()

((amb alt

)

(let ((prev

amb

fail amb

fail))

(call

(

lambda

(sk)

(call

(

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

exp2)

and

!(exp1

and

exp2)

end

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

amb

Amb.new

betty

amb.choose(

[

])

ethel

amb.choose(

[

])

joan

amb.choose(

[

])

kitty

amb.choose(

[

])

marry

amb.choose(

[

])

amb.require(xor(kitty

,betty

))

amb.require(xor(ethel

,joan

))

amb.require(xor(joan

,ethel

))

amb.require(xor(kitty

,marry

))

amb.require(xor(marry

,betty

))

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

最后给出一个Prolog的解答：

notmember(A,[]).

notmember(A,[B

L]):

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):

[

member(Betty,X),

member(Ethel,X),

member(Joan,X),

member(Kitty,X),

member(Marry,X),

distinct([Betty,Ethel,Joan,Kitty,Marry]),

xor(Kitty

,Betty

xor(Ethel

,Joan

xor(Joan

,Ethel

xor(Kitty

,Marry

xor(Marry

,Betty

文章转自庄周梦蝶，原文发布时间2008-11-15