[Coq] Coq'Art Reading in Tokyo ?

ところで東京近辺でSpringerのCoq本Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructionsに興味のある人っています？
何人かいるようならば読書会でもとか思うのですが。なお、私は素人で型理論の専門家とかではありません。なので他人に教える程の知識は無く、一緒に勉強する感じになってしまいますが。
逆に既に本を読んでいるとかで、私が参加しても構わないグループとかありましたら声をかけて下さい。

[Coq] Coq'Art Chap.1

Interactive Theorem Proving and Program Development; Coq'Art: The Calculus of Inductive Constructionsを読み始める事にしました。

Chap.1ではinsertion sortを例にしてCoqの解説が行われています。そこで、Appendixのinsertion sortのコードをCoqIdeに入力してみました。実際に証明が自分で出来る様になるのは将来の課題として、とりあえずCoqでの開発の流れを追ってみます。
なお証明自体はinsertionv8.vにあります。

まず、list Zがソートされた状態を定義するsorted : list Z -> Propを定義します。こんな感じです。

Inductive sorted : list Z -> Prop :=
  | sorted0 : sorted nil
  | sorted1 : forall z:Z, sorted (z :: nil)
  | sorted2 : forall (z1 z2:Z) (l:list Z), 
       z1 <= z2 -> sorted (z2 :: l) -> sorted (z1 :: z2 :: l).

sortedは定義なのでこれ自体は証明の対象ではありません。

これを用いて、

Theorem sorted_inv : 
  forall (z:Z) (l:list Z), sorted (z :: l) -> sorted l.

を証明します。

次いで、並べ替えであることを示すequivを定義します。まず、リストのなかの出現数を示す

Fixpoint nb_occ (z:Z) (l:list Z) {struct l} : nat :=
  match l with
  | nil => 0%nat
  | (z' :: l') =>
      match Z_eq_dec z z' with
      | left _ => S (nb_occ z l')
      | right _ => nb_occ z l'
      end
  end.

を定義します。このnb_occは定義なので証明しません。

これを使って、

Definition equiv (l l':list Z) := forall z:Z, nb_occ z l = nb_occ z l'

を定義します。これ自体も証明しません。

nb_occ, equivの定義から、下記の補題を証明します。

Lemma equiv_refl : 
  forall l:list Z, equiv l l.
Lemma equiv_sym : 
  forall l l':list Z, equiv l l' -> equiv l' l.
Lemma equiv_trans : 
  forall l l' l'':list Z, equiv l l' -> equiv l' l'' -> equiv l l''.
Lemma equiv_cons : 
  forall (z:Z) (l l':list Z), equiv l l' -> equiv (z :: l) (z :: l').
Lemma equiv_perm : 
  forall (a b:Z) (l l':list Z), equiv l l' -> equiv (a :: b :: l) (b :: a :: l').

次いで、実際にinsertion sortを行う関数aux : Z -> list Z -> list Zを定義します。

Fixpoint aux (z:Z) (l:list Z) {struct l} : list Z :=
  match l with
  | nil => z :: nil
  | cons a l' =>
      match Z_le_gt_dec z a with
      | left _ =>  z :: a :: l'
      | right _ => a :: (aux z l')
      end
  end.

auxがinsertion sortの性質を持っている事を示す補題、つまりauxの結果がequivであること、sortedであることを証明します。

Lemma aux_equiv : 
  forall (l:list Z) (x:Z), equiv (x :: l) (aux x l).
Lemma aux_sorted : 
  forall (l:list Z) (x:Z), sorted l -> sorted (aux x l).

最後に、sort:list Z -> list Zを定義というか、sortされた出力の存在を証明します。

Definition sort :　forall l:list Z, {l' : list Z | equiv l l' /\ sorted l'}.

証明を追いきれてないのですが、どうもexists (aux a l')の様に、実例を示して存在を証明するみたいにauxを使っているようです。

----

sorted, nb_occ, equivは定義なので証明の対象ではありません。
aux, sortは成果物として得る、証明済みのプログラムです。sortを満たす具体的なl'の値としてauxを使った式を与えます。その値がl'の条件を満たす事はaux_equiv, aux_sortedから保証されます。

一般的に

• 仕様を表す様な述語(X -> Prop)を書く。仕様に関する補題も証明しておく。
  
• 解を与える様な関数を書く。
  
• その関数の出力が仕様を満たす事を証明する。
  

とかすれば良い様に見えます。

----

ある程度、この本を読み終わった後で、またこのプログラムを振り返ってみたいと思います。

[Haskell][RWH] Chapter 1

RWHのChapter 1を読む。

• not equalは!=ではなく/=。


• temporary definitionをletで。例えば、ghci> let e = exp 1とか。


• ghci> :info []とかすれば、[]の情報が調べられる。


• ghci> :set +tで型情報を表示する。解除は:unset +t。:type itでunsetしても簡単に調べられる。


• itで前の計算結果を参照出来る。

簡単にHaskellのプログラムを書くにはinteractを使えば良いらしい。
main = interact f 但し、fはString -> Stringな関数。これで標準入力から読んで標準出力に書けば良い。

% cat WC.hs
main = interact wordCount
where wordCount input = show (length (lines input)) + "\n"
%

Prelude> :info interact
interact :: (String -> String) -> IO () -- Defined in System.IO

実行は
% runghc WC.hs < quux.txt

Exerciseはとりあえずこんな感じ？

main = interact wordCount
    where wordCount input = numLines input ++ "\t" ++ numWords input ++ "\t" ++ numChars input ++ "\n"
          numLines input = show (length (lines input))
          numWords input = show (length (words input))
          numChars input = show (length input)

[Scala] map and flatMap on scala.Function1

scala.Function1 lacking @ λ Tony’s blog λ

Scalaの関数の型の scala.Function1 にもっと便利な機能を、という話。
mapはともかくflatMapをこうやって定義するのか、というのはなんか勉強になったので、メモ代わりに。
同様に S combinator というのも自分ではなんか巧く使えないものなので参考になるなぁ、と。on は普通に便利かも。

[Misc] These days...

Project Eulerはその後も細々と解いてはいるのだが、いちいち解法をblogに書くのが面倒になって更新をさぼってました。あと１問でLevel 2なんだけどなー。

　あと、Scala勉強会＠関東2の準備が忙しかったりとか。仕事でのプレゼンは勿論あるけど、私的な勉強会でのプレゼンはこれが始めてで、なんていうか仕事とは別の緊張感がありますね。つまり仕事と違って、「実は自分は良く解ってなくて外しているんじゃないかしらん」みたいな不安とか。

そういえばそろそろReal World Haskellの発売ですね。東京近辺で興味がある人がいれば是非とも読書会とか検討しません？

[Project Euler] Problem 22

Problem 22

　この問題では、入力データをコードに直接貼付けず、ファイルから読み込むようにする必要がある。
　ファイルからデータをどう読み込むかだが、scala.io.Source.fromFile("filename").getLines で行単位で読み込めるイテレータを生成するので、それを使うのが楽だと思う。（本当はそういう目的のライブラリでは無い様にも思うのだが...。）
　names.txt がどこに置かれているのかというと、Eclipse上のプロジェクトProjectEuler下の、srcの下の、パッケージP020の下に、names.txtが置かれているので、filenameとしては"src/P020/names.txt"になった。

object P022 {
  def main(args:Array[String]) {
    val line:String = scala.io.Source.fromFile("src/P020/names.txt").getLines.next
    val names1:List[String] = line.split(",").map{s => s.substring(1, s.size-1)}.toList
    val names2:List[(String,Int)] = names1.sort{(a,b) => a.compareTo(b)<0}.zipWithIndex.map{t => (t._1, t._2+1)}
    println(names2.head) // (AARON,1)
    def f(t:Tuple2[String,Int]):Int = t match {
      case (s,i) => i * s.toCharArray.map{c => c-'A'+1}.foldLeft(0)(_+_)
    }
    println(f(names2.head)) // (AARON,1)
    println(names2.map(f).foldLeft(0)(_+_))
  }
}

[Project Euler] Problem 21

Problem 21

素数リストとかは過去の問題のを使い回し。

object P021 {
  val initPrimes:List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
                              31, 37, 41, 43, 47, 53, 59, 61, 67, 
                              71, 73, 79, 83, 89, 97, 101)
  def primes(init:List[Int]):List[Int] = {
    def min(a:Int, b:Int) = if (a<b) a else b
    def sq(a:Int) = a*a
    init ::: List.range(init.last+1, min(100000,sq(init.last))).filter{x => init.forall{x%_!=0}}
  }
  val primeList:List[Int] = primes(primes(initPrimes))
  def factors(n:Int):List[Tuple2[Int,Int]] = {
    def g(n:Int, p:Int, c:Int):Tuple2[Int,Int] = if (n%p==0) g(n/p, p, c+1) else Tuple2(n,c)
    def f(n:Int, ps:List[Int], ts:List[Tuple2[Int,Int]]):List[Tuple2[Int,Int]] = (n,ps) match {
      case (1,_) => ts
      case (_,Nil) => error("n="+n)
      case (_, a::as) if n%a==0 => {
        val z = g(n,a,0)
        f(z._1, as, Tuple2(a,z._2)::ts)
      }
      case (_, a::as) => f(n, as, ts)
    }
    f(n, primeList, Nil)
  }
  def sumDiv(ts:List[Tuple2[Int,Int]]):Int = {
    def pow(a:Int, b:Int):Int = b match {
      case 0 => 1
      case _ => pow(a,b-1)*a
    } 
    def f(t:Tuple2[Int,Int]):Int = {
      List.range(0, t._2 +1).map{pow(t._1, _)}.foldLeft(0)(_+_)
    }
    ts.map(f).foldLeft(1)(_*_)
  }
  def sumDivisors(n:Int):Int = sumDiv(factors(n))-n
  def main(args:Array[String]) {
    println(sumDivisors(220))
    println(sumDivisors(284))
    val l = List.range(2,10000).filter{a => {
      val b=sumDivisors(a)
      val c=sumDivisors(b)
      val r=(a!=b)&&(a==c)
      if (r) println(a+"<->"+b)
      r
    }}
    println(l)
    println(l.foldLeft(0)(_+_))
  }
}

---
　ここまでProject Eulerを解いてきて思ったのだが、組み込みライブラリとか言語仕様で、

• アノテーションを付けるだけで関数の値をメモ化してくれる。
  
• とりあえず1,000,000以下の素数は予め計算されている。
  
• 内部でIntの計算が桁溢れしたら勝手にLong -> BigInt と桁を増やしてくれるような数値型。
  
• 素因数分解も組み込み関数で用意されている。
  

とかだと、かなり楽が出来るのになぁ...。

[Project Euler] Problem 20

Problem 20

BigIntegerを使うだけ。

object P020 {
  def main(args:Array[String]) {
    def fact(n:Int):BigInt = n match {
      case 0 => new BigInt(java.math.BigInteger.ONE)
      case _ => new BigInt(java.math.BigInteger.valueOf(n))*fact(n-1)
    }
    val r = fact(100).toString.toCharArray.map{c => c-'0'}.foldLeft(0)(_+_)
    println(r)
  }
}

[Project Euler] Problem 19

Problem 19

難しくは無いはずなんだが、1900を1990と入力していたtypoの為でなかなか正解に辿り着けなかった。

object P019 {
  def isLeap(y:Int):Boolean = y match {
    case _ if y%400==0 => true
    case _ if y%100==0 => false
    case _ if y%4==0   => true
    case _             => false
  }
  def daysOfMonth(y:Int, m:Int):Int = m match {
    case 9 => 30
    case 4 => 30
    case 6 => 30
    case 11 => 30
    case 2 => if (isLeap(y)) 29 else 28
    case _ => 31
  }
  def daysInYear(y:Int):Int = if (isLeap(y)) 366 else 365
  def daysFrom1Jan1900(year:Int, month:Int, day:Int):Int =
    List.range(1900,year).map{y => daysInYear(y)}.foldLeft(0)(_+_) +
    List.range(1,month).map{m => daysOfMonth(year,m)}.foldLeft(0)(_+_) +
    (day-1)
  val day0Jan1900:Int = daysFrom1Jan1900(1900,1,0) // Sunday
  def dayOfTheWeek(year:Int, month:Int, day:Int):Int = (daysFrom1Jan1900(year,month,day)-day0Jan1900)%7
  def main(args:Array[String]) {
    println(dayOfTheWeek(1901,1,1))
    println(dayOfTheWeek(2000,12,1))
    println(
      (for(y <- List.range(1901,2001); m <- List.range(1,13))
       yield dayOfTheWeek(y,m,1)).filter{_==0}.size)
  }
}

[Project Euler] Problem 18

Problem 18

n段目では、(n-1)段目で左右を選ぶ選択で大きな方を選ぶ、というのを再帰的にやれば良いが、計算時間を減らす為に、Problem 15と同様にメモ化する。

import scala.collection.mutable.HashMap
object P018 {

  val input:Array[String] = Array(
"75",
"95 64",
...中略...
"63 66 04 68 89 53 67 30 73 16 69 87 40 31",
"04 62 98 27 23 09 70 98 73 93 38 53 60 04 23") // y=0
  val data:Array[Array[Int]] = input.map{s => s.split(" ").map{x => x.toInt}}
  val height = input.size
  def value(x:Int,y:Int):Int = data(height-1-y)(x)
  val map:HashMap[Tuple2[Int,Int],Int] = new HashMap()
  def search(x:Int,y:Int):Int = map.get(Tuple2(x,y)) match {
    case Some(x) => x
    case None => (x,y) match {
      case (_,0) => {
        val v = value(x,y)
        map.put(Tuple2(x,y),v)
        v
      }
      case _ => {
        val s0 = value(x,y)
        val s1 = search(x,y-1)
        val s2 = search(x+1,y-1)
        val v = if (s1>s2) s0+s1 else s0+s2
        map.put(Tuple2(x,y),v)
        v
      }
    }
  }
  def main(args:Array[String]) {
    println(search(0,height-1))
  }
}

[Project Euler] Problem 17

Problem 17

綴りが間違っていると正解が出ないので、念のために数詞を調べ直したりとか、英語を使ってない我々にはそれだけで敷居が高い問題。
この手の問題を解く時は、match-case構文を便利だと特に感じる。

object P017 {

  val digitOne:List[String] = List("", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine")
  val teens:List[String] = List("", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen")
  val digitTen:List[String] = List("", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety")
  def toEnglish(n:Int):String = n match {
    case 1000 => "one thousand"
    case _ if (n/100 != 0) => digitOne(n/100)+" hundred" + (if (n%100==0) "" else " and "+toEnglish(n%100))
    case _ if (10<n)&&(n<20) => teens(n-10)
    case _ => Tuple2(n/10, n%10) match {
      case (a,0) => digitTen(a)
      case (0,b) => digitOne(b)
      case (a,b) => digitTen(a)+"-"+digitOne(b)
    }
  }
  def countLetter(s:String) = s.split("[ -]").map{s => s.length}.foldLeft(0)(_+_)
  def main(args:Array[String]) {
    /*
    println(List(1,9,10,11,19,20,21,99).map{x => Tuple3(x,toEnglish(x),countLetter(toEnglish(x)))})
    println(List(100,101,110,111,120,121,199).map{x => Tuple2(x,toEnglish(x))})
    println(List(200,201,210,211,299).map{x => Tuple2(x,toEnglish(x))})
    println(List(900,901,910,911,999,1000).map{x => Tuple2(x,toEnglish(x))})
    */
    println(List(342,115).map{x => Tuple3(x,toEnglish(x),countLetter(toEnglish(x)))})
    println(List.range(1,1001).map{x => countLetter(toEnglish(x))}.foldLeft(0)(_+_))
  }
}

[Project Euler] Problem 16

Problem 16

java.math.BigIntegerを使うだけ。

object P016 {
  def main(args:Array[String]) {
    val v2 = new BigInt(java.math.BigInteger.valueOf(2L))
    val r = v2.pow(1000).toString.toCharArray.map{c => c-'0'}.foldLeft(0)(_+_)
    println(r)
  }
}

[Project Euler] Problem 15

Problem 15

これも計算機を使わないで解いた方が速い問題。
n x n grid で考えると、2n ステップの中から n 個右を選ぶということだから、
_{2n}C_n を計算すればいい。つまり、(2n)! / (n!)^2 。

もうちょっと計算機っぽく考えると、nx x ny のグリッドの場合、最初に右に行くか下に行くかで、
f(nx,ny) = f(xn-1,ny) + f(xn,ny-1)
但し、
f(0,_) = f(_,0) = 1
を解けば良いが、最初の式は実は _nC_r = _{n-1}C_r + _{n-1}C_{r-1} の事である。
実際にはこのままではf(nx,ny)回の関数呼び出しが発生するので、メモ化する。

import scala.collection.mutable.HashMap
import java.math.BigInteger

object P015 {
  val map:HashMap[Tuple2[Int,Int],Long] = new HashMap()
  def f(nx:Int, ny:Int):Long = map.get(Tuple2(nx,ny)) match {
    case Some(x) => x
    case None => {
      val z:Long = (nx,ny) match {
        case (0,_) => 1
        case (_,0) => 1
        case (x,y) => f(x-1,y) + f(x,y-1)
      }
      val zz = map.put(Tuple2(nx,ny),z)
      z
    }
  }
  def main(args:Array[String]) {
    println(f(20,20))
    println(40L/20*39*38/19*37*36/18*35*34/17*33*32/16*31*30/15*29*28/14*27*26/13*25*24/12*23*22/11*21/10/9/8/7/6/5/4/3/2/1)
  }
}

[Project Euler] Problem 14

Problem 14

　有名なCollatz問題。最初はListを使っていたのだがOutOfMemoryになるので普通に命令型っぽいプログラムになっている。

object P014 {
  def collatz(n:Long):Int = {
    def f(n:Long, c:Int):Int = {
      if (n==1L) c
      else if (n%2L==0) f(n/2, c+1)
      else f(3L*n+1, c+1)
    }
    f(n,1)
  }
  def mx(a:Tuple2[Long,Int], b:Tuple2[Long,Int]):Tuple2[Long,Int] = if (a._2 > b._2) a else b
  def maxLength(m:Int):Tuple2[Long,Int] = {
    var ts:Tuple2[Long,Int] = Tuple2(0L,0)
    for(x <- List.range(1, m)) {
      val c:Int = collatz(x)
      if (ts._2 < c) {ts = Tuple2(x,c)}
    }
    ts
  }
  def main(args:Array[String]) {
    println(collatz(13L))
    println(maxLength(1000000))
  }
}

[Project Euler] Problem 13

Problem 13

文字列 -> BigInt の変換をして和を取るだけ。

import java.math.BigInteger

object P013 {
  val input:Array[String] = Array(
"37107287533902102798797998220837590246510135740250",
  ...中略...
"53503534226472524250874054075591789781264330331690")
  def main(args:Array[String]) {
    val sum:BigInt = input.map{s => new BigInt(new BigInteger(s))}.foldLeft(new BigInt(BigInteger.ZERO))(_+_)
    println(sum)
    println(sum.toString.substring(0,10))
  }
}

[Project Euler] Problem 12

Problem 12

　最初に素数列を作成するのに結構時間がかかる気がする。今回は最初10000以下の素数のリストを作り、エラーが出たので30000まで作った。
　約数の数は素因数分解して各素数の指数から求められるのを使う。

object P012 {
  val maxRange = 30000
  def primes(init:List[Int]):List[Int] = {
    def min(a:Int, b:Int) = if (a<b) a else b
    def sq(a:Int) = a*a
    init ::: List.range(init.last+1, min(maxRange,sq(init.last))).filter{x => init.forall{x%_!=0}}
  }
  val primeList = primes(primes(List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
                              53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101)))
  val emptyFactors = primeList.map{x => 0}
  def factor(n:Int):List[Int] = {
    def f(x:Int, fs:List[Int], ps:List[Int]):List[Int] = (x,fs,ps) match {
      case (1,_,_) => fs
      case (_,Nil,_) => error("fs empty:x="+x)
      case (_,_,Nil) => error("ps empty:x="+x)
      case (y,a::as,b::bs) if y%b==0 => f(y/b, (a+1)::as, ps)
      case (y,a::as,b::bs)           => a::f(y,as,bs)
    }
    f(n, emptyFactors, primeList)
  }
  def numFactors(n:Int):Int = factor(n).foldLeft(1){(a,b) => a*(b+1)}
  def triangle(n:Int):Int = n*(n+1)/2
  def main(args:Array[String]) {
    println(primeList.length)
    println(numFactors(28))
    val t:Tuple3[Int,Int,Int] =
      Stream.range(1,maxRange).map{x => Tuple3(x,triangle(x),numFactors(triangle(x)))}.filter{x => x._3>500}.head
    println(t)
    println(factor(triangle(t._1)).zip(primeList).filter{t => t._1 != 0}.map{x => x._2+"^"+x._1})
  }
}

[Project Euler] Problem 11

Problem 11

表をArray[Array[Int]]に変換、４つの並びを(x,y)のTuple2のListとして表現し、全組み合わせ ( List[List[Tuple2[Int,Int]]]) から積が最大になるものを選択する。

object P011 {
  val input:Array[String] = Array(
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08",
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00",
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65",
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91",
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80",
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50",
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70",
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21",
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72",
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95",
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92",
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57",
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58",
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40",
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66",
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69",
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36",
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16",
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54",
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48")
  val table:Array[Array[Int]] = input.map{x => x.split(" ").map{_.toInt}}
  def v(x:Int, y:Int):Int = table(y)(x)
  val xscan:List[List[Tuple2[Int,Int]]] = 
    for(y <- List.range(0,20); x0 <- List.range(0,20-4)
    ) yield for(x <- List.range(x0, x0+4)) yield (x,y)
  val yscan:List[List[Tuple2[Int,Int]]] = 
    for(x <- List.range(0,20); y0 <- List.range(0,20-4)
    ) yield for(y <- List.range(y0, y0+4)) yield (x,y)
  val diagscan1 = 
    for(x0 <- List.range(0,20-4); y0 <- List.range(0,20-4)
    ) yield for(i <- List.range(0,4)) yield (x0+i, y0+i)
  val diagscan2 = 
    for(x0 <- List.range(0,20-4); y0 <- List.range(0,20-4)
    ) yield for(i <- List.range(0,4)) yield (x0+3-i, y0+i)
  def f(ps:List[Tuple2[Int,Int]]):Long = ps.foldLeft(1L){(a,t) => a * v(t._1,t._2)}
  val result = (xscan ::: yscan ::: diagscan1 ::: diagscan2).sort{(a,b) => f(a)>f(b)}.head
  def main(args:Array[String]) {
    println(result)
    println(result.map{t => v(t._1,t._2)})
    println(f(result))
  }
}

[Project Euler] Problem 10

Problem 10

　2000000以下の素数を得るには1415以下の素数が判れば良く、1415以下の素数を得るには37以下の素数が判れば良く、37以下の素数を知るには7以下の素数が2,3,5,7であることを知っていればOKである。
　という訳で、エラトステネスの篩を三段重ねにしてみた。

object P010 {
  def main(args:Array[String]) {
    val maxRange = 2000000
    def primes(init:List[Int]):List[Int] = {
      def min(a:Int, b:Int) = if (a<b) a else b
      def sq(a:Int) = a*a
      init ::: List.range(init.last+1, min(maxRange,sq(init.last))).filter{x => init.forall{x%_!=0}}
    }
    println(new java.util.Date())
    val ps1 = List(2,3,5,7)
    val ps2 = primes(ps1)
    println(ps2.last)
    val ps3 = primes(ps2)
    println(ps3.last)
    val ps4 = primes(ps3)
    println(ps4.last)
    println(ps4.foldLeft(0L)(_+_))
    println(new java.util.Date())
  }
}

[Project Euler] Problem 9

Project EulerのProblem 9。実は簡単に手で解ける問題。

a^2 + b^2 = c^2 を満たす a,b,c は、一般性を失わずに、
a = m^2 - n^2, b= 2mn, c = m^2 + n^2 (m > n)
と書ける事が判っている。
a + b + c = 1000 より、m(m+n) = 500 となる。
500 の約数は、(1,2,4,5,10,20,25,50,100,125,250,500) で、
m+n > m, m > n を使うと、m = 20, n = 5。

object P009 {
  def main(args:Array[String]) {
    println(new java.util.Date)
    val result = for(a <- List.range(1,1000);
        b <- List.range(a,1000-a);
        c = 1000 - a - b
        if a*a + b*b == c*c
    ) yield (a,b,c,a*b*c)
    println(result)
    println(new java.util.Date)
  }
}

[Project Euler] Problem 8

Project EulerのProblem 8。

特に工夫せずに、文字列からList[Int]に変換、頭から要素を５つ取り出して、１文字ずらして次へ、という感じ。

object P008 {
  def c2i(c:Char):Int = c - '0'
  val data:List[Int] = {(
"73167176531330624919225119674426574742355349194934"+
"96983520312774506326239578318016984801869478851843"+
"85861560789112949495459501737958331952853208805511"+
"12540698747158523863050715693290963295227443043557"+
"66896648950445244523161731856403098711121722383113"+
"62229893423380308135336276614282806444486645238749"+
"30358907296290491560440772390713810515859307960866"+
"70172427121883998797908792274921901699720888093776"+
"65727333001053367881220235421809751254540594752243"+
"52584907711670556013604839586446706324415722155397"+
"53697817977846174064955149290862569321978468622482"+
"83972241375657056057490261407972968652414535100474"+
"82166370484403199890008895243450658541227588666881"+
"16427171479924442928230863465674813919123162824586"+
"17866458359124566529476545682848912883142607690042"+
"24219022671055626321111109370544217506941658960408"+
"07198403850962455444362981230987879927244284909188"+
"84580156166097919133875499200524063689912560717606"+
"05886116467109405077541002256983155200055935729725"+
"71636269561882670428252483600823257530420752963450")}.toCharArray().toList.map(c2i)
  def mul(cs:List[Int]):Int = cs match {
      case List(a,b,c,d,e) => a*b*c*d*e
      case _               => -1
    }
  def f(max:Int, list:List[Int]):Int = {
    if (list.length<5) max
    else {
      val a = mul(list.take(5))
      if (a>max) f(a, list.tail)
      else f(max, list.tail)
    }
  }
  def main(args:Array[String]) {
    println(new java.util.Date)
    println(f(-1,data))
    println(new java.util.Date)
  }
}