程序员量子力学-海森堡式BUG
软件中的质量属性(一)

用编程的思路模拟解决脑筋急转弯问题

posted @ 2014年4月03日 21:33 in 软件开发 with tags javascript , 1168 阅读
分享到: 更多

前些日子看了可汗学院的这个关于诚实人和说谎者的脑筋急转弯问题,我觉得如果能用程序来模拟,那一定很有趣。

这个题目是这样的,有两扇门,一扇通往天堂,一扇通往地狱,你要做出选择打开那扇门。门口各有一个人,他们都知道门后面的情况,其中一个总是说实话,而另一个总是撒谎。你可以问他们问题。要怎样问问题,才能做出正确的选择?

在揭开答案之前,我们先看看我是如何用JavaScript来模拟这个问题的。

function Game() {
  var destinations = ["Heaven", "Hell"];
  var gates = {}, persons = {};

  function Gate() {
    var val = undefined;
    return {
      value: function(_) {
        if (!arguments.length) {
          return val;
        }
        val = _;
      },
      open: function() {
        if (val === destinations[0]) {
          console.log("Happy Ending!");
        } else {
          console.log("You Die!");
        }
      }
    }
  }

  function Behavior(isLier) {
    var tellTruth = function(info) {
      return info;
    };
    var tellLie = function(info) {
      var index = destinations.indexOf(info);
      if (index === 0) {
        return destinations[1];
      } else {
        return destinations[0];
      }
    };
    return isLier ? tellLie : tellTruth;
  }

  function Person(gate, behavior) {
    return {
      ask: function() {
        return behavior.call(this, gate.value());
      }
    }
  }

  function Init() {
    gates.A = Gate();
    gates.B = Gate();

    if (Math.random() > 0.5) {
      gates.A.value(destinations[0]);
      gates.B.value(destinations[1]);
    } else {
      gates.A.value(destinations[1]);
      gates.B.value(destinations[0]);
    }

    if (Math.random() > 0.5) {
      persons.A = Person(gates.A, Behavior(true));
      persons.B = Person(gates.B, Behavior(false));
    } else {
      persons.A = Person(gates.A, Behavior(false));
      persons.B = Person(gates.B, Behavior(true));
    }
  }

  Init();

  return {
    open: function(gateName) {
      gates[gateName].open();
    },
    ask: function(personName) {
      return persons[personName].ask();
    }
  }
}

 

程序主要有以下方法:

  • Gate

    Gate方法负责创建们,每扇门提供两个方法, value方法负责读写们的内容,open方法检查开门后的结果。如果是天堂,则打印“Happy Ending”, 游戏成功;如果是地狱则打印“You Die”,游戏失败。

  • Behavior

    Behavior是对说谎和说实话这两种行为的抽象。返回两个不同的方法,说谎的行为总是返回和原本信息不一致的信息,而说实话则返回原本的信息。

  • Person

    Person方法负责创建人,并关联人所在的门,指定人的行为。

  • Init

    Init方法随机初始化门和人

  • Game

    Game方法是最外层的闭包,他暴露出游戏者可以调用的两个方法,问问题和开门。因为Person和Gate都在闭包里所以游戏者无法获得任何相关的信息,只能通过ask方法来问问题。

调用以下方法来运行游戏:

var g = Game();
console.log(g.ask("A"));
console.log(g.ask("B"));

 

因为A和B有一个人说谎,所以条用的结果是他们都说自己后面的门是“天堂”,或者都说是“地狱”。

于是无论打开A还是B,游戏者都只有50%的概率获胜。

好了,现在是揭晓答案的时候了,这道题,游戏者需要这样问,“如果问另外一个人你后面的门后是什么,他会怎么说?”会有两种情况:

  • 问诚实人说谎者怎么回答他后面的门是什么,因为说谎者会说谎话,而诚实的人会原封不动的返回这个回答,所以提问者会得到错误的答案

  • 问说谎者诚实人怎么回答他后面的门是什么,因为说谎者会说谎话,他会把诚实人的正确答案变成谎话回答,所以答案还是错误的。

那么我们要怎样修改我们的程序呢?

其实改动很简单,首先要增强Person方法

function Person(gate, behavior) {
    return {
      ask: function(aGate) {
        if(!aGate) {
          return behavior.call(this, gate.value());
        } else {
          return behavior.call(this, aGate.value());
        }
      },
      askBy: function(accordingTo) {
        return behavior.call(this, accordingTo.ask(gate));
      }
    }
  }

 

在Person方法中增强ask方法,暴露门的信息,也就是说每个人不但知道自己的门后的东西是什么,也能回答另一扇门后是什么。所以通过参数传递门的引用。这里我们可以看出,在前一版中假定人和门之间的耦合关系是不成立的,其实完全应该可以帮人和门解耦。

另外增加了askBy方法,这个方法会去问另一个人,我给你的门后面的信息,然后用自己的行为返回出去。

除了扩展Person,我们还要扩展Game返回的对象,增加新的提问方式:

  return {
    open: function(gateName) {
      gates[gateName].open();
    },
    ask: function(personName) {
      return persons[personName].ask();
    },
    askBy : function(personName, byName) {
      return persons[personName].askBy(persons[byName]);
    }
  }

 

这样,新暴露的askBy方法就可以正确的找到错误的门了(听上去很绕口)

增强后的代码如下:

function Game() {
  var destinations = ["Heaven", "Hell"];
  var gates = {}, persons = {};

  function Gate() {
    var val = undefined;
    return {
      value: function(_) {
        if (!arguments.length) {
          return val;
        }
        val = _;
      },
      open: function() {
        if (val === destinations[0]) {
          console.log("Happy Ending!");
        } else {
          console.log("You Die!");
        }
      }
    }
  }

  function Behavior(isLier) {
    var tellTruth = function(info) {
      return info;
    };
    var tellLie = function(info) {
      var index = destinations.indexOf(info);
      if (index === 0) {
        return destinations[1];
      } else {
        return destinations[0];
      }
    };
    return isLier ? tellLie : tellTruth;
  }

  function Person(gate, behavior) {
    return {
      ask: function(aGate) {
        if(!aGate) {
          return behavior.call(this, gate.value());
        } else {
          return behavior.call(this, aGate.value());
        }
      },
      askBy: function(accordingTo) {
        return behavior.call(this, accordingTo.ask(gate));
      }
    }
  }

  function Init() {
    gates.A = Gate();
    gates.B = Gate();

    if (Math.random() > 0.5) {
      gates.A.value(destinations[0]);
      gates.B.value(destinations[1]);
    } else {
      gates.A.value(destinations[1]);
      gates.B.value(destinations[0]);
    }

    if (Math.random() > 0.5) {
      persons.A = Person(gates.A, Behavior(true));
      persons.B = Person(gates.B, Behavior(false));
    } else {
      persons.A = Person(gates.A, Behavior(false));
      persons.B = Person(gates.B, Behavior(true));
    }
  }

  Init();

  return {
    open: function(gateName) {
      gates[gateName].open();
    },
    ask: function(personName) {
      return persons[personName].ask();
    },
    askBy : function(personName, byName) {
      return persons[personName].askBy(persons[byName]);
    }
  }
}

 

调用以下代码来问新的问题:

var g = Game();
console.log(g.askBy("A","B"));
console.log(g.askBy("B","A"));

 

游戏者只要打开和回答不一致的门就可以马上升入天堂!

通过这个例子,我们发现对Behavior的抽象对进一步问题的扩展起到了很大的帮助。这也展现了基于Function编程的灵活性,不难想象,如果我们把说谎者和诚实人按照面向对象的方式来构造,而不是把说谎还是说真话作为行为注入到一般的人上,对新的问题的扩展将会比较困难。


分享到: 更多
Avatar_small
Emma 说:
2023年1月24日 03:09

This brain teaser was a great challenge that I thought would be cool to tackle with programming. I was intrigued by the idea of using programming concepts to simulate and solve the problem, and real estate Bexar County I'm glad I was able to do it. It was a great learning experience and I'm sure it's something I'll be able to apply to other problems in the future.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter