29 July, 2008

[Scala] Scala exercises for beginners

初心者の為の練習問題

 原文はScala exercises for beginnersを参照の事。
 関数型言語の初心者向けの良い課題だと思うのだが。...が、関数型言語に不慣れだと、そもそもどんな関数を作る事が期待されているのか判んないかもしれないなぁ。(メソッド名とか関数の型から大体の見当がつくかな?)
 ソースコード中の error("課題") の部分を自分の書いたコードで置き換える事が期待されています。
 初心者の回答を自動で採点する為に、scalacheck で回答の正当性を検証する為の方法を誰か解説しない?


// 下記の List のメソッドは使用してはならない:
// * length
// * map
// * filter
// * ::: (および ++ のようなその変形)
// * flatten
// * flatMap
// * reverse (および reverseMap, reverse_::: のような変形)
// これはまた、List に対する for-構文の使用も禁止している。
// 自分で書いた関数は使用して良い。例えば問題 2 では問題 1 あるいは問題 3 を使用して良い。
// 許可された既に存在するメソッドを適切に使用した場合は、エレガントさが評価される。
// 満点: 66点
object Exercises {
def succ(n: Int) = n + 1
def pred(n: Int) = n - 1
// Exercise 1 (問題 1)
// Relative Difficulty 1 (難易度: 1)
// Correctness: 2.0 (正しい回答に: 2.0 点)
// Performance: 0.5 (性能: 0.5 点)
// Elegance: 0.5 (エレガントさ: 0.5 点)
// Total: 3 (合計: 3)
def add(x: Int, y: Int): Int = error("課題: x, yは 0 または正の数と仮定せよ。Int に対する +, - の使用を禁止する。上述の succ/pred の使用のみ許す。")
// Exercise 2
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def sum(x: List[Int]): Int = error("課題")
// Exercise 3
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def length[A](x: List[A]): Int = error("課題")
// Exercise 4
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.0 mark
// Elegance: 1.5 marks
// Total: 7
def map[A, B](x: List[A], f: A => B): List[B] = error("課題")
// Exercise 5
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def filter[A](x: List[A], f: A => Boolean): List[A] = error("課題")
// Exercise 6
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def append[A](x: List[A], y: List[A]): List[A] = error("課題")
// Exercise 7
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def concat[A](x: List[List[A]]): List[A] = error("課題")
// Exercise 8
// Relative Difficulty: 7
// Correctness: 5.0 marks
// Performance: 1.5 marks
// Elegance: 1.5 mark
// Total: 8
def concatMap[A, B](x: List[A], f: A => List[B]): List[B] = error("課題")
// Exercise 9
// Relative Difficulty: 8
// Correctness: 3.5 marks
// Performance: 3.0 marks
// Elegance: 2.5 marks
// Total: 9
def maximum(x: List[Int]): Int = error("課題")
// Exercise 10
// Relative Difficulty: 10
// Correctness: 5.0 marks
// Performance: 2.5 marks
// Elegance: 2.5 marks
// Total: 10
def reverse[A](x: List[A]): List[A] = error("課題")
}

[Scala] 2 not problem

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

 で、Scalaで解いてみた。
 最初はお約束としてNodeのcase classとしてAnd, Orとか作ってevalをパターンマッチとかで書いていたんだけど、それだと答えが出るのに30分ぐらい必要だったので、出力の組み合わせ8通りをList[Boolean]で持たせてみた結果、5分ぐらいで答えが出る様になった。多分、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()))
}
}