[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)
  }
}

[Project Euler] Problem 7

Project EulerのProblem 7。

　Problem 3で作った素数列のStreamは10001個の素数を計算させようとするとOutOfMemoryで落ちてしまった。本当はちゃんと理由を考えるべきだよなぁ。計算を遅延しているのは確かめたし、あとは実装上で非常にメモリ効率が悪いとかそういうのなのかなぁ。うぅぅむ、Streamへの理解が足りない様だ。
　とりあえず奇素数10000個のListを作れば良いので、下記の様に済ませた。計算時間は自機で15秒程度。

object P007 {
  def main(args:Array[String]) {
    println(new java.util.Date())
    val ps = primes(10000)
    println(ps(0))
    println(ps(9999))
    println(new java.util.Date())
  }
  def primes(num:Int):List[Int] = {
    def odds(n:Int):Stream[Int] = Stream.cons(n, odds(n+2))
    def primes2(ps:List[Int], ss:Stream[Int]):List[Int] = {
      if (ps.length >= num) ps
      else {
        val x = ss.head
        if (ps.forall(x%_!=0)) primes2(x::ps, ss.tail) else primes2(ps, ss.tail)
      }
    }
    primes2(Nil,odds(3))
  }
}

[Project Euler] Problem 6

Project EulerのProblem 6。

　本当は高校の数学を使って紙と鉛筆で解ける様な問題のはずなんだが、いざ解いてみようとすると案の定 k^2 の和の公式を忘れていて、k(k+1) の和の公式から作り直したりとか。手でこういう計算をしなくなってから長いからなぁ。

object P006 {
  def p006(n:Int):Int = sq(sum(List.range(1,n+1))) - sum(List.range(1,n+1).map(sq))
  def sum(xs:List[Int]):Int = xs.foldLeft(0)(_+_)
  def sq(x:Int):Int = x*x
  def main(args:Array[String]) {
    println(new java.util.Date)
    println(p006(10))
    println(p006(100))
    println(new java.util.Date)
    println(f(100))
  }
  def f(n:Int):Int = sq(n*(n+1)/2) - n*(n+1)*(2*n+1)/6
}

[Project Euler] Problem 5

Project EulerのProblem 5。

これはまぁ、1,2,...,20 の最小公倍数を求めれば良いだけの話。

object P005 {
  def gcd(a:Long, b:Long):Long = {
    if (a>b) gcd(b,a)
    else if (a==0) b
    else gcd(b%a, a) 
  }
  def lcd(a:Long, b:Long):Long = a/gcd(a,b)*b
  def p005(n:Int):Long = List.range(1, n+1).foldLeft(1L)(lcd(_,_))
  def main(args:Array[String]) {
    println(new java.util.Date)
    println(p005(10))
    println(p005(20))
    println(new java.util.Date)
  }
}

[Project Euler] Problem 4

Project EulerのProblem 4。

　最初に作ったコードはは3桁 x 3桁の2重ループで積を求めて、それが回文数になっているかをチェックし、積の大きさでソート、という解法で解きました。
　まぁ計算時間が１分以内ならどんな解き方でも良い様なものですが、最大の回文数を１つだけ求めれば良いならば、逆に大きな回文数から順に3桁 x 3桁になるか試した方が無駄が無い様にも思ったので次の様なコードに。ここでもStreamを作ってheadで最初の要素だけ求めます。
　この手のパズル的な問題を解く時には遅延リストは便利ですね。Haskellで解けばもっと楽なのだろうなぁ...。

object P004 {
  def main(args:Array[String]) {
    time({println(p004)})
  }
  val palins:Stream[Int] = 
    for(x <- Stream.range(9,0,-1);
        y <- Stream.range(9,-1,-1);
        z <- Stream.range(9,-1,-1)) 
      yield (100001*x + 10010*y + 1100*z)
  def f(n:Int):Stream[Tuple3[Int,Int,Int]] = {
    Stream.range(999,99,-1).filter{x => (n%x==0)&&(100<=n/x)&&(n/x<1000)}.map{x => (x,n/x,n)}
  }
  def p004:Tuple3[Int,Int,Int] = palins.flatMap(f).head
  def time(block:Unit) {
    val t0 = System.currentTimeMillis
    block
    println((System.currentTimeMillis-t0)+"msec")
  }
}

[Project Euler] Problem 3

　Project EulerのProblem 3。

　実のところ、素数列を求める必要は全く無く、単に奇数で順に割って行けば良いだけの問題だと思う。が、せっかくなのでStreamの使い方の勉強という事で、素数列のStreamを作る。

　Streamの使い方は、例えば下記の記事とかが参考になると思う。

• Lazyなリストの作り方 @ Onion開発再開しつつある日記
  
• Scalaで無限リスト：Haskellライクに @ Inforno

　基本的にStreamを使いたいケースというのは、(1)パズル系の問題を解く為に無限数列を作りたい、(2)入力やファイルとかで必要があるまで読み込みたく無い、のどっちかの場合かと思う。勿論、Streamはリストの様に扱え便利なので、ループとかイテレータじゃなくて遅延リストに表現したいという事。
　(1)の場合は、a_n → a_{n+1} = f(a_n) の様に書けるならば、val s = Stream.cons(a0, s.map(f))と書けば良い。Problem 2のような二項漸化式の場合は、s.zip(s.tail)の様な(a_n, a_{n+1})なタプルを作って計算というのが定番。
　(2)の例としては、例えばSimplifying JDBC @ Scala Wikiの例が実用例。JDBCのResultSetをStream[X]に変換するコードとして、

private def strm[X](f: RichResultSet => X, rs: ResultSet): Stream[X] = 
  if (rs.next) Stream.cons(f(new RichResultSet(rs)), strm(f, rs))
  else { rs.close(); Stream.empty };

の様に書かれている。rs.nextがtrueならばStreamの新しい要素xを作って、xとStreamの続きであるstrm(f,rs)自身のconsであるStream.cons(x, strm(f,rs))を返し、rs.nextがfalseになったらEmptyを返して終了。

　Problem 3のコードはこんな感じ。

object P003 {
  def main(args:Array[String]) {
    // println(primes.take(10).force) // -> List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
    // println(g(13195)) // -> List(29, 13, 7, 5)
    time({println(g(600851475143L))})
  }
  val odds:Stream[Long] = Stream.cons(3, odds.map(_+2))
  def sieve(xs:Stream[Long]):Stream[Long] = Stream.cons(xs.head, sieve(xs.tail.filter{_%(xs.head)!=0}))
  val primes:Stream[Long] = Stream.cons(2, sieve(odds))
  def f(n:Long, ps:Stream[Long], l:List[Long]):(Long,Stream[Long],List[Long]) = {
    if (n==1) (n,ps,l)
    else {
      val m = ps.head
      if (n%m==0) {
        f(n/m, ps, m::l)
      } else {
        f(n, ps.tail, l)
      }
    }
  }
  def g(n:Long):List[Long] = f(n, primes, Nil)._3
  def time(block:Unit) {
    val t0 = System.currentTimeMillis
    block
    println((System.currentTimeMillis-t0)+"msec")
  }
}

　Streamは実際に値が使われるまで計算されないので、デバッグプリントしたいときはtake(10)だけじゃなく、forceとかをつけないと駄目。
　oddsが奇数が無限に続くStreamで、sieveがエラトステネスの篩で素数だけにするフィルタ、primesが素数列です。あとこの問題は素因数分解の対象がIntじゃなくてLongでないと収まらない。最初はIntが駄目なのでBigIntで計算したけど実はLongなんてのもあったな、と計算時間を計るtimeを作っていて思い出したり。

[Project Euler] Problem 2

Project EulerのProblem 2。

Fibonacci数列というと、やはり遅延ストリームで表現するのがお約束ということで、Streamの使い方の復習。
Fibonacci数列と素数列はなんかイディオムとして覚えてもいいかもしれない。それが理解出来ればStreamが自由に扱える様な気がする。

fibはlazy valで宣言しなくてもOKだったが、なぜOKなのかについては自信が無い。

object P002 {
  val fib:Stream[Int] = Stream.cons(1, Stream.cons(2, (fib.zip(fib.tail)).map{x => x._1 + x._2}))
  def main(args:Array[String]) {
    println(fib.take(10)) // --> Stream(1, ?)
    println(fib.take(10).force) // --> List(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)
    println(fib.filter{x => x%2==0}.takeWhile{x => x<100}.foldLeft(0)(_+_))
    println(fib.filter{x => x%2==0}.takeWhile{x => x<4000000}.foldLeft(0)(_+_))
  }
}

なんかHaskellで書いたコードに比べると冗長な感じがする。Listと違ってStreamはシンタックスシュガーが弱いから仕方が無いが。

[Project Euler] Problem 1

Project EulerをScalaで挑戦してみることにしました。

　Project Eulerってのは数学っぽいプログラミングの問題が出題されているサイトです。「どう書く.org」の数学問題とかに割と近い。特に数学を専攻した人でなくても解けるし、コンピュータでの計算時間も賢くプログラミング出来れば１分以内ぐらいだそうです。
　問題は英語で出題されているけど、和訳サイトもあります。

　アカウントを作ってログインし、profileの画面で解いた問題を選択し、正しい答えを入力すると、その問題は回答済みとなります。とりあえずの目標は25問解いてLevel 1に昇格すること。200問解くとLevel 5なんだが、78人しかいない様子。

　Project Eulerの良いところは、Webサイトに答えを入力すると、正しいか間違っているかが判ることです。現実の問題は予め正解が判っている訳ではないのが、予め正解の判っている問題を解く学校の勉強と違うところだ、というのは良く聞く話ですが、逆に言うと正解の判らない問題を解くのは勉強方法としては効率が悪い訳です。その点でProject Eulerは勉強用に向いています。
　関数型言語（に限らずにCとかJavaとかプログラミング言語一般でも良いと思いますが）の入門用の例題としては良いのではないでしょうか。

　出来るだけ毎日１題づつ解いて行こうと思っています。

　Problem 1のコードはこんな感じで簡単に解けた。

object P001 {
  def main(args:Array[String]) {
    println(List.range(1,10).filter{x => (x%3==0)||(x%5==0)}.foldLeft(0)(_+_))
    println(List.range(1,1000).filter{x => (x%3==0)||(x%5==0)}.foldLeft(0)(_+_))
  }
}

　List.rangeで1, 2,..., 9という数値のリストを作り、filterで3または5の倍数を選択し、foldLeftで合計を求めます。まぁ割とScalaとか関数型言語での定番のイディオムなんじゃなかろうか。
　解法としては勿論、受験数学的に数列の和の公式とかを使って解いてもOKなんだけど、計算時間が１分以内ならばどんな解き方でもOKと考えることにして、素直に実装した。