Hatena::ブログ(Diary)

みずぴー日記

2010-12-25(土)

リストモナドを使ってみる

| リストモナドを使ってみる - みずぴー日記 を含むブックマーク

このエントリはScala Advent Calendar jp 2010 : ATNDの25日のものです。

メリークリスマス! クリスマスは楽しくみんなでパズルを解いて遊びましょう。

パズルみたいな探索問題をScalaで解く場合は、リストモナドを使うとキレイに書けます。

例: SEND+MORE=MONEY

例として覆面算を解いてみましょう。

f:id:mzp:20101225212219g:image

各アルファベットに異なる数字が割り当てれる。その数字は何か?

ただし最上位桁が0ではない。

普通にforループを使って解くと、ネストの深さが酷いことになります:)。

// int(1,2,3)を123にする関数
def int(xs : Int*) : Int =
  xs.foldLeft(0)( _ * 10 + _)

// SEND+MORE=MONEYの答えを探索する
def solve : (Int,Int,Int) = {
  for( s <- 0 to 9)
    for( e <- 0 to 9)
      for( n <- 0 to 9)
          ................
                for( y <- 0 to 9)
                  if(s != 0 && m != 0 && int(s,e,n,d) + int(m,o,r,e) == int(m,o,n,e,y))
                    return (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y))
}

これをリストモナドを使って書くと次のようになります。あいかわらずforを使ってるように見えるかもしれませんが、それは幻想です:)。

def solve : Seq[(Int, Int,Int)] = {
  val digits = 0 to 9
  for {
    // sは0〜9のどれか
    s <- digits
    // eは0〜9からsをのぞいたもののどれか
    e <- digits diff List(s)
    // nは0〜9からsとeをのぞいたもののどれか
    n <- digits diff List(s, e)
    // dは(ry
    d <- digits diff List(s, e, n)
    m <- digits diff List(s, e, n, d)
    o <- digits diff List(s, e, n, d, m)
    r <- digits diff List(s, e, n, d, m, o)
    y <- digits diff List(s, e, n, d, m, o, r)
    // sは0ではない
    if s != 0
    // mも0ではない
    if m != 0
    // SEND+MORE == MONEYを満すかどうかをチェック
    if int(s, e, n, d) + int(m, o, r, e) == int(m, o, n, e, y)
  } yield (int(s, e, n, d) , int(m, o, r, e) , int(m, o, n, e, y))
}

ネストが浅くなって超クール!

適当な解説

  • 「sは0〜9のどれか」のようなあいまい性を含んだままプログラムが書ける非決定計算というパラダイムがあります。
  • リストモナドを使うと、この非決定計算をScalaに持ち込むことができます。
  • しかもfor構文のおかげて、わりと自然な感じに書くことができます。

まとめ

Scalaで探索問題を書くときはリストモナドが便利だよ!

selvaggioselvaggio 2010/12/26 03:22 こういうのみるといつも思うんだけど、探索効率とかどうなの?

mzpmzp 2010/12/26 09:42 あわせてよみたい http://www.itpl.co.jp/ocaml-nagoya/?%A5%CD%A5%BF%B5%AD%CF%BF%B8%CB%2FSEND%2BMORE%3DMONEY
Prologはつよかった。

selvaggioselvaggio 2010/12/30 20:13 ぱねぇっす

2010-09-28(火)

クイックソート

| クイックソート - みずぴー日記 を含むブックマーク

30分プログラム、その803。

qsort.scm - みずぴー日記をまたやってみた。

使い方

scala> QSort.sort(List(1,5,4,0,3))
res2: List[Int] = List(0, 1, 3, 4, 5)

ソースコード

object QSort {
  def sort[A <% Ordered[A]](xs : List[A]) : List[A] = {
    xs match {
      case Nil =>
	Nil
      case x::xs => {
	val (ys, zs) = xs.partition(_ < x)
	sort(ys) ++ List(x) ++ sort(zs)
      }
    }
  }
}

参考

2010-08-22(日)

ローマ数字の変換

| ローマ数字の変換 - みずぴー日記 を含むブックマーク

30分プログラム、その797。anarchy golf - Roman numeralにインスパイアされました。

ローマ数字をIntに変換します。面倒だったので、I,V,Xにしか対応していません。

使い方

scala> Roman.toInt("II")
res39: Int = 2

scala> Roman.toInt("IIV")
res40: Int = 3

scala> Roman.toInt("XIV")
res38: Int = 14

ソースコード

object Roman {
  val map = Map('I' -> 1,
		'V' -> 5,
		'X' -> 10)

  def toInt(s : String) : Int =
    s.foldRight((0,0)){ case (c, (m, current)) =>
      val n = map(c)
      if(n < m){
	(m, current - n)
      }else{
	(n max m, current + n)
      }
    }._2
}

参考

2010-08-02(月)

Excel順ソート

| Excel順ソート - みずぴー日記 を含むブックマーク

30分プログラム、その790。AAがZのあとにでてくるExcel順ソートを書いてみました。

Excelの列ラベルはZのあとにAAがでてくるから、辞書順ソートじゃうまくいかないよねー、というお話。@さんのつぶやきにインスパイアされた気がするけれど、あらためて探したらみつからなった。

使い方

scala> List("a","b","aa","zz","c").sort(excelCompare(_,_))
res17: List[java.lang.String] = List(a, b, c, aa, zz)

ソースコード

def excelCompare(x : String, y : String) : Boolean = {
  val x_len = x.size
  val y_len = y.size
  if(x_len == y_len){
    x < y
  }else{
    x_len < y_len
  }
}

println(excelCompare("a","b"))
println(excelCompare("a","c"))
println(excelCompare("a","aa"))
println(excelCompare("z","aa"))

List("a","b","aa","zz","c").sort(excelCompare(_,_))

参考

iPhone4 useriPhone4 user 2010/08/03 23:10 Utmxp-1.00 で検索したらここに来ました。。
utmxp-1.00 ってアカウント何ですか?

mzpmzp 2010/08/05 21:40 検索するとここがでてきますね。でも知らないです。

2010-07-07(水)

n乗根を求めてみた。

| n乗根を求めてみた。 - みずぴー日記 を含むブックマーク

30分プログラム、その781。n乗根を求めてみた。

n乗根なんてどうやって求めるんだろう、と思って調べてみたけど、ニュートン法で解いてた。あああ、なるほど。

使い方

scala> NthRoot.nthRoot(4,2)
res7: Double = 2.0000000929222947

scala> NthRoot.nthRoot(8,3)
res8: Double = 2.000000001071189

ソースコード

import scala.math

object NthRoot{
  def newton[T](improve : T => T, good : (T,T) => Boolean, init : T) : T = {
    val next = improve(init)
    if(good(init, next))
      next
    else
      newton(improve,good,next)
  }

  def nthRoot(x : Double, n : Int) : Double = {
    newton((y : Double) => ((n-1)*y + x / math.pow(y,n-1))/n,
	   (x : Double, y : Double) => math.abs(x - y) < 0.001,
	   x)
  }
}

参考

2010-06-25(金)

ScalaでHadoopを使ってみた。

| ScalaでHadoopを使ってみた。 - みずぴー日記 を含むブックマーク

大名古屋ことGoogle グループの宿題で「Hadoopを動かしてみること」というのがあったので、試してみました。Javaを使う気にはならないので、Scalaで。

コード

Hadoopの2章のコードを素直に写経する。一ファイル一クラスの制限がないのはいいね。

import java.util.Iterator
import org.apache.hadoop.fs.Path
import org.apache.hadoop.io._
import org.apache.hadoop.mapred._

class MapExample extends MapReduceBase with Mapper[LongWritable,Text,Text,IntWritable] {
  def map(key      : LongWritable,
	  value    : Text,
	  output   : OutputCollector[Text,IntWritable],
	  reporter : Reporter ) {
    val xs = value.toString.split(":")
    val year = xs(0)
    val temp = xs(1).toInt

    output.collect(new Text(year),new IntWritable(temp))
  }
}

class ReduceExample extends MapReduceBase with Reducer[Text, IntWritable, Text, IntWritable] {
  implicit def j2s(value: java.util.Iterator[IntWritable]) : scala.Iterator[Int] =
    new scala.Iterator[Int] {
      def hasNext = value.hasNext
      def next = value.next.get
    }

  def reduce(key      : Text,
	     values   : Iterator[IntWritable],
	     output   : OutputCollector[Text,IntWritable],
	     reporter : Reporter) {
    val max : Int = values.reduceLeft(Math.max(_,_))
    output.collect(key, new IntWritable(max))
  }
}

object HadoopExample {
  def main(args : Array[String]){
    if(args.length != 2){
      System.err.println("Usage: max <input path> <output path>")
      System.exit(-1)
    }

    val conf : JobConf = new JobConf( Class.forName("HadoopExample") )
    conf.setJobName("max")

    FileInputFormat .addInputPath ( conf, new Path(args(0)) )
    FileOutputFormat.setOutputPath( conf, new Path(args(1)) )

    conf.setMapperClass(classOf[MapExample])
    conf.setReducerClass(classOf[ReduceExample])

    conf.setOutputKeyClass(classOf[Text])
    conf.setOutputValueClass(classOf[IntWritable])

    JobClient.runJob(conf)
  }
}

サンプルファイル

入力ファイルは、Hadoop本のやつを単純化しました。年とその年の気温のペアのつもり。

2010:30
2010:31
2010:32
2010:33
2010:34
2010:30
2009:25
2009:24
2009:23
2009:26
2008:10

コンパイル

#!/bin/sh
HADOOP_HOME=/opt/manual/hadoop
rm *.jar
mkdir -p classes

scalac -classpath ${HADOOP_HOME}/lib/commons-logging-1.0.4.jar:${HADOOP_HOME}/lib/commons-cli-1.2.jar:$HADOOP_HOME/hadoop-0.20.2-core.jar -d classes hadoop_example.scala
jar -cvf hadoop-example.jar -C classes .

実行

scala-object.jarを$HADOOP_HOME/libにコピーしてやる。

#!/bin/sh
rm -rf output
hadoop jar ./hadoop-example.jar HadoopExample sample.txt output
cat output/*

2010-06-02(水)

「ASCII Starts」をやってみる

| 「ASCII Starts」をやってみる - みずぴー日記 を含むブックマーク

30分プログラム、その769。anarchy golf - ASCII Starsをやってみました。

わりと素直に書けちゃったので、特に語ることないです。

使い方

scala> show(4)
res16: String =
   *
  ***
 *****
*******
 *****
  ***
   *

ソースコード

def wrap(s : String) =
  "*%s*".format(s)

def pad(w : Int, s : String) : String = {
  val left = ( w - s.size ) / 2
  "%s%s%s".format(" " * left, s, " " * (w - s.size - left))
}

def cross(n : Int) : List[String] = {
  val single = List("*")
  if(n == 1)
    single
  else
    single ++ cross(n-1).map(wrap(_)) ++ single
}

def show(n : Int) : String = {
  cross(n).map(pad(2*n-1, _)).mkString("\n")
}

参考

2010-05-09(日)

標準入力を指定行数ごとに分割するプログラム

| 標準入力を指定行数ごとに分割するプログラム - みずぴー日記 を含むブックマーク

30分プログラム、その765。標準入力を指定行数ごとに分割するプログラムを作ってました。

SeqとIteratorの違いで多いに苦しみました。ドキュメントはまったく読んでないのですが挙動と名前から類推するに、

xs.take(n)

xsがSeqならxsは変化せずに、Iteratorなら指す先が変化するみたいです。

Iteratorのほうが効率がいい気がしたのですが、使いこなせる気がしなかったのでSeqで書きました。

使い方

$ jot 100 | scala Split 3 "test-%d.tmp"
$ ls test-*.tmp
test-0.tmp   test-15.tmp  test-21.tmp  test-28.tmp  test-4.tmp
test-1.tmp   test-16.tmp  test-22.tmp  test-29.tmp  test-5.tmp
test-10.tmp  test-17.tmp  test-23.tmp  test-3.tmp   test-6.tmp
test-11.tmp  test-18.tmp  test-24.tmp  test-30.tmp  test-7.tmp
test-12.tmp  test-19.tmp  test-25.tmp  test-31.tmp  test-8.tmp
test-13.tmp  test-2.tmp   test-26.tmp  test-32.tmp  test-9.tmp
test-14.tmp  test-20.tmp  test-27.tmp  test-33.tmp
$ cat test-0.tmp
1
2
3
$ cat test-1.tmp
4
5
6

ソースコード

import scala.io.Source
import java.io.FileWriter

object Split {
  def partition[T](n : Int, xs : Seq[T]) : Pair[Seq[T], Seq[T]] =
    (xs.take(n), xs.drop(n))

  def split[T](n : Int, xs : Seq[T]) : List[Seq[T]] = {
    val (ys, zs) = partition(n, xs)
    if( zs.isEmpty )
      List(ys)
    else
      ys :: split(n, zs)
  }

  def main(args : Array[String]) {
    val count = args(0).toInt
    val templ = args(1)
    val lines = split(count,
		      List.fromIterator(Source.fromInputStream(System.in).getLines))
    for((xs,n) <- lines.zipWithIndex){
      val path = templ.format(n)
      val writer = new FileWriter(path)
      for(x <- xs){
	writer.write(x)
      }
      writer.close
    }
  }
}

参考

2010-04-15(木)

文字列の反転

| 文字列の反転 - みずぴー日記 を含むブックマーク

30分プログラム、その757。anarchy golf - Mirroring Characterにインスパイアされて、文字列の反転をやってみました。

基本的にreverseと同じですが、括弧だけは対応するものに置き換えるようです。例えば、"f(x)"を反転させると"(x)f"になります。

使い方

scala> mirror("f(x)")
res13: String = (x)f

scala> mirror("#include <stdio.h>")
res14: String = <h.oidts> edulcni#

ソースコード

val map : List[Pair[Char,Char]] = List('(' -> ')',
				       '{' -> '}',
				       '<' -> '>')

def mirrorChar( c : Char) = {
  map.flatMap{case (left, right) =>
    if(c == left)
      List(right)
    else if(c == right)
      List(left)
    else
      List()
  } match {
    case List(x) => x
    case List()  => c
  }
}

def mirror(s : String) : String =
  s.map(mirrorChar(_)).reverse.mkString

参考

2010-04-03(土)

md5sumの計算

| md5sumの計算 - みずぴー日記 を含むブックマーク

30分プログラム、その750。md5sumの計算をやってみました。

java.security.MessageDigestを使えば楽に計算できます。

ただ、InputStreamのreadにwhileを使っているのがイケてない気がしてます。InputStreamをSeq[Byte]に変換できたらクールなのになぁ。

使い方

$ scala Md5sum md5sum.scala
a4d430e5775936a87538f3260b32baef

# 参考
$ md5sum md5sum.scala
a4d430e5775936a87538f3260b32baef  md5sum.scala

ソースコード

import java.security.MessageDigest
import java.io._
object Md5sum {

  def md5sum(input : InputStream) = {
    val digest = MessageDigest.getInstance("md5")
    var byte = input.read()
    while(byte != -1) {
      digest.update( byte.toByte )
      byte = input.read()
    }
    digest.digest()
  }

  def hexdigest(xs : Seq[Byte]) =
    xs.map((n : Byte) => "%02x".format(n & 0xff)).mkString

  def main(args: Array[String]) {
    for(arg <- args)
      println(hexdigest(md5sum(new FileInputStream(arg))))
  }
}

参考