2010-09-19

Scalaで順列と組合せ

Scala

List同士の結合は避けたのでそこそこ効率は良い・・と思う。
Rubyに入った重複版も書いてみた。

def permutation[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = {
  def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] =
    if (n == 0) Stream(ls)
    else {
      def g(s: Stream[A], s2: Stream[A]): Stream[Stream[A]] =
        if (s.isEmpty) Stream.Empty else (s #::: s2) #:: g(s.tail, s.head #:: s2)
      g(rest, Stream.empty).flatMap(s => f(s.head :: ls, s.tail, n - 1))
    }
  f(Nil, trv1.toStream, n)
}

def combination[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = {
  def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] =
    if (n == 0) Stream(ls)
    else if (rest.isEmpty) Stream.empty
    else f(rest.head :: ls, rest.tail, n - 1) #::: f(ls, rest.tail, n)
  f(Nil, trv1.toStream, n)
}

def repeatedPermutation[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] =
  if (trv1.isEmpty) Stream.empty else {
    def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] =
      if (n == 0) Stream(ls) else rest.flatMap(v => f(v :: ls, rest, n - 1))
    f(Nil, trv1.toStream, n)
  }

def repeatedCombination[A](trv1: TraversableOnce[A], n: Int): Stream[List[A]] = {
  def f(ls: List[A], rest: Stream[A], n: Int): Stream[List[A]] =
    if (n == 0) Stream(ls)
    else if (rest.isEmpty) Stream.empty
    else f(rest.head :: ls, rest, n - 1) #::: f(ls, rest.tail, n)
  f(Nil, trv1.toStream, n)
}

2010-09-16

Scalaで数独ソルバのワンライナー

Scala

scala -e "(Stream(args(0)) /: (0 to 80))((st, i) => st.flatMap(s => if (s(i) != '.') Stream(s) else ('1' to '9').toStream.filter(c => (0 to 8).forall(j => Seq(i - i % 9 + j, i % 9 + j * 9, i - i % 27 + j / 3 * 9 + i % 9 / 3 * 3 + j % 3).forall(s(_) != c))).map(s.updated(i, _)))).foreach(_ grouped 9 foreach println)" ..48...1767.9.....5.8.3...43..74.1...69...78...1.69..51...8.3.6.....6.9124...15..

3x3のチェックをもう少しどうにかしたい

2010-09-07

Scalaでカッコなし

Scala

今さらだけど
http://e-arrows.sakura.ne.jp/2010/08/is-lisp-really-has-too-many-parenthesis.html
スクリプト実行だと宣言無しにargsが使えたので、\uXXXXを使わなくてもカッコ0個にできた。

val fact: Int => Int = n => 1 to n product
val format: Int => String = n => this fact n formatted n + "! = %d"
val n = args.headOption map Integer.parseInt getOrElse 1
1 to n map format foreach println

formatのあたりが少し苦しい

2009-11-25

Scalaで非決定性計算

Scala

Scalaの練習に
http://faroffsea.blogspot.com/2006/12/haskell.html
こちらの

import　Control.Monad

solve　=　do　baker　<-　[1,　2,　3,　4,　5]
　　　　　　　　　　　cooper　<-　[1,　2,　3,　4,　5]
　　　　　　　　　　　fletcher　<-　[1,　2,　3,　4,　5]
　　　　　　　　　　　miller　<-　[1,　2,　3,　4,　5]
　　　　　　　　　　　smith　<-　[1,　2,　3,　4,　5]
　　　　　　　　　　　guard　$　distinct　[baker,　cooper,　fletcher,　miller,　smith]
　　　　　　　　　　　guard　$　baker　/=　5
　　　　　　　　　　　guard　$　cooper　/=　1
　　　　　　　　　　　guard　$　fletcher　/=　1　&&　fletcher　/=　5
　　　　　　　　　　　guard　$　miller　>　cooper
　　　　　　　　　　　guard　$　abs　(smith　-　fletcher)　/=　1
　　　　　　　　　　　guard　$　abs　(fletcher　-　cooper)　/=　1
　　　　　　　　　　　[baker,　cooper,　fletcher,　miller,　smith]

distinct　::　Eq　a　=>　[a]　->　Bool
distinct　[]　=　True
distinct　(x:xs)　=　all　(/=x)　xs　&&　distinct　xs

main　::　IO()
main　=　print　solve

これをScalaに移植してみる

import Math.abs

object Hoge {

  def slove() = {
    for {
      baker <- List(1, 2, 3, 4, 5)
      cooper <- List(1, 2, 3, 4, 5)
      fletcher <- List(1, 2, 3, 4, 5)
      miller <- List(1, 2, 3, 4, 5)
      smith <- List(1, 2, 3, 4, 5)
      if distinct(List(baker, cooper, fletcher, miller, smith))
      if baker != 5
      if cooper != 1
      if fletcher != 1 && fletcher != 5
      if miller > cooper
      if abs(smith - fletcher) != 1
      if abs(fletcher - cooper) != 1
    } yield List(baker, cooper, fletcher, miller, smith)
  }

  def distinct(a : List[Any]):Boolean = a match {
    case Nil => true
    case x::xs => xs.forall(_ != x) && distinct(xs)
  }

  def main(args : Array[String]) : Unit = {
    print(slove)
  }
}