[Scala] 2 not problem

3 not problem@ヒビルテ経由で知ったパズル。
3 not problem@パラメトロン計算機、参照の事。

　で、Scalaで解いてみた。
　最初はお約束としてNodeのcase classとしてAnd, Orとか作ってevalをパターンマッチとかで書いていたんだけど、それだと答えが出るのに30分ぐらい必要だったので、出力の組み合わせ８通りをList[Boolean]で持たせてみた結果、５分ぐらいで答えが出る様になった。多分、8bitなのでIntで表現すればもっと速くなるはずだが。
　もっと賢く解く方法がありそうだが、まぁ解けたのでこれで良しとする。

// Brute-force Solver for "The 2-NOTs problem"
// "Synthesize a black box which computes NOT-X, NOT-Y, and NOT-Z from X, Y, and Z,
// using an arbitrary number of ANDs and ORs, but only 2 NOTs."
// See http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item19
//
object TwoNots {
  // Possible combination of (X,Y,Z)
  val input:List[(Boolean,Boolean,Boolean)] =
    for(x <- List(false, true);
        y <- List(false, true);
        z <- List(false, true)) yield (x,y,z)
  // Node   : input=(X:Boolean, Y:Boolean, Z:Boolean) => output:Boolean
  // output : Node value for "input"
  // desc   : Description
  case class Node(val output:List[Boolean], val desc:String) {
    override def toString():String = desc
    def ===(that:Any) = that match {
      case Node(o, _) => output==o
      case _          => false
    }
    def =/=(that:Any) = !(this === that)
    def unary_~ :Node = Node(output.map{b:Boolean => !b}, "~["+this.desc+"]")
    def zipWithF(that:Node, f:(Boolean,Boolean)=>Boolean):List[Boolean] = (output zip that.output).map{t => f(t._1, t._2)}
    def *(that:Node):Node = Node(zipWithF(that, (_ && _)), this.desc + that.desc)
    def +(that:Node):Node = Node(zipWithF(that, (_ || _)), "("+this.desc +"+"+ that.desc+")")
    def memberOf_?(ns:List[Node]):Boolean = ns.exists(_ === this)
    def const_?():Boolean = (this === TrueNode) || (this === FalseNode)
  }
  val TrueNode:Node = Node(input.map{in => true}, "T")
  val FalseNode:Node = Node(input.map{in => false}, "F")
  val X:Node = Node(input.map{in => in._1}, "X")
  val Y:Node = Node(input.map{in => in._2}, "Y")
  val Z:Node = Node(input.map{in => in._3}, "Z")
  val notX:Node = Node((~X).output, "~X")
  val notY:Node = Node((~Y).output, "~Y")
  val notZ:Node = Node((~Z).output, "~Z")
  val XYZ:Node = Node((X*Y*Z).output, "XYZ")
  val X_Y_Z:Node = Node((X+Y+Z).output, "(X+Y+Z)")
  val XY_YZ_ZX:Node = Node((X*Y+Y*Z+Z*X).output, "(XY+YZ+ZX)")
  
  def append(ns:List[Node], n:Node):List[Node] = if (n.memberOf_?(ns) || n.const_?()) ns else n::ns
  def append(ns:List[Node], xs:List[Node]):List[Node] = xs.foldLeft(ns){(as:List[Node], b:Node) => append(as,b)}
  // Fixed point of f1,f2,... in fs
  def fixedPoint(ns:List[Node], fs:List[List[Node] => List[Node]]):List[Node] = {
    val ns1 = fs.foldLeft(ns){(as:List[Node], f:List[Node] => List[Node]) => append(as, f(as))}
    if (ns1.length==ns.length) ns else fixedPoint(ns1, fs)
  }
  def spanAnd(nodes:List[Node]):List[Node] = for(na <- nodes; nb <- nodes if (na =/= nb)) yield (na * nb)
  def spanOr(nodes:List[Node]):List[Node]  = for(na <- nodes; nb <- nodes if (na =/= nb)) yield (na + nb)
  def spanWithAndOr(nodes:List[Node]):List[Node] = fixedPoint(nodes, List(spanAnd, spanOr))
  def chooseNodeForNot(nodes:List[Node]):List[List[Node]] = for(n <- nodes) yield append(nodes, ~n)
  def satisfy_?(nodes:List[Node]):Boolean = notX.memberOf_?(nodes) && notY.memberOf_?(nodes) && notZ.memberOf_?(nodes)
  // Solving tactics:
  // (1) Start with initial nodes ( = initialNodes)
  // (2) Take any two nodes from initial nodes, and make AND and OR of them to add to lists. Repeat this procedure so that
  //     all possible combinations have been added. ( = spanWithAndOr(...) = n0)
  //     n0 contains no NOTs.
  // (3) Choose one node from n0, and add NOT of the chosen node to n0.  Span the nodes list with ANDs and ORs. ( = n1)
  //     n1 contains one NOT.
  // (4) Do same as above to obtain node list "n2", which contains two NOTs.  If the n2 contains all of ~X, ~Y, and ~Z,
  //     the n2 is a solution.
  def solve(initialNodes:List[Node]):List[(List[Node],List[Node],List[Node])] = {
    val n0 = spanWithAndOr(initialNodes)
    for(n1 <- chooseNodeForNot(n0).map{ns:List[Node] => spanWithAndOr(ns)};
        n2 <- chooseNodeForNot(n1).map{ns:List[Node] => spanWithAndOr(ns)} if satisfy_?(n2)) yield
        (n2.filter(_ === notX), n2.filter(_ === notY), n2.filter(_ === notZ))
  }
  def main(args : Array[String]) : Unit = {
      println("----"+(new java.util.Date()))
      // In principle, we can solve with initial=List(X,Y,Z), however, the answer becomes quite
      // ugly because X+Y+Z might be expressed as (X+Y)+Z. In order to see answers expressed in
      // a symmetric way, some nodes such as XYZ, XY+YZ+ZX, and X+Y+Z are added to initial nodes.  
      val initial:List[Node] = List(XYZ, XY_YZ_ZX, X_Y_Z, X, Y, Z)
      // val initial:List[Node] = List(X, Y, Z)
      for(answer <- solve(initial)) {
        println("~X = "+answer._1)
        println("~Y = "+answer._2)
        println("~Z = "+answer._3)
      }
      println("----"+(new java.util.Date()))
  }
}