Java进阶：使用Ruby amb解决说谎者谜题

goodluck

<p >说谎者谜题是sicp4.3.2小节的一道题目，题目本身不难：<p >五个女生参加一个考试，她们的家长对考试结果过分关注。为此她们约定，在给家里写信谈到考试的时候，每个姑娘都要写一句真话和一句假话。下面是从她们的信里摘抄出来的句子：<p >Betty : kitty考第二，我只考了第三<p >Ethel : 你们应该很高兴听到我考了第一，joan第二<p >joan :   我考第三，可怜的Ethel垫底<p >kitty:  我第二，marry只考了第四<p >marry: 我是第四，Betty的成绩最高。<p >这五个姑娘的实际排名是什么？<p ><p >Ruby本来就有call/cc，因此也可以实现amb操作符，网上已经有一个实现了：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"  bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>class Amb  class ExhaustedError &lt; RuntimeError; end  def initialize    @fail = proc { fail ExhaustedError, &quot;amb tree exhausted&quot; }  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 :assertend</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >这一段代码与scheme宏实现amb是完全相同的：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"  bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>(define amb-fail '*)(define initialize-amb-fail  (lambda ()    (set! amb-fail      (lambda ()        (error &quot;amb tree exhausted&quot;)))))(initialize-amb-fail)(define call/cc call-with-current-continuation)(define-syntax amb  (syntax-rules ()    ((amb alt )     (let ((prev-amb-fail amb-fail))       (call/cc        (lambda (sk)          (call/cc           (lambda (fk)             (set! amb-fail                   (lambda ()                     (set! amb-fail prev-amb-fail)                     (fk 'fail)))             (sk alt)))                           (prev-amb-fail)))))))</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >回到谜题，从题意可知每个姑娘的两句话的异或结果为true，并且姑娘的排名肯定不会相同，因此定义两个辅助过程：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"  bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>require 'amb'def distinct?(items)  items.uniq==itemsenddef xor(exp1,exp2) (exp1 or exp2) and !(exp1 and exp2)end</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >剩下的完全就是将题目翻译成代码即可了，没有多少可以解释的东西：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"  bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>amb=Amb.newbetty=amb.choose(*[1,2,3,4,5])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 &quot;betty:#{betty} ethel:#{ethel} joan:#{joan} kitty:#{kitty} marry:#{marry}&quot;</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >答案就是：<p ><p >betty:3 ethel:5 joan:2 kitty:1 marry:4   <p ><p >最后给出一个Prolog的解答：<p ><ccid_nobr><table width="400" border="1" cellspacing="0" cellpadding="2"  bordercolorlight = "black" bordercolordark = "#FFFFFF" align="center"><tr><td bgcolor="e6e6e6" class="code" ><pre><ccid_code>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],   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).</ccid_code></pre></td></tr></table></ccid_nobr><br><p ><p >< align=right></P><p align="center"></p></p>