使用Ruby amb解决说谎者谜题
说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：五个女生参加一个考试，她们的家长对考试结果过分关注。为此她们约定，在给家里写信谈到考试的时候，每个姑娘都要写一句真话和一句假话。下面是从她们的信里摘抄出来的句子：
Betty : kitty考第二，我只考了第三
Ethel : 你们应该很高兴听到我考了第一，joan第二
joan : 我考第三，可怜的Ethel垫底
kitty: 我第二，marry只考了第四
marry: 我是第四，Betty的成绩最高。
这五个姑娘的实际排名是什么？
Ruby本来就有call/cc，因此也可以实现amb操作符，网上已经有一个实现了：
<div style="border: 1px solid #cccccc; padding: 4px 5px 4px 4px; background-color: #eeeeee; font-size: 13px; width: 98%;"><!---->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|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
if 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
页:
[1]