2012年5月29日火曜日

Project Euler-Problem11をgroovyで解いてみる

問題

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

上の 20 × 20 の数字のなか、赤くマークされた数字の積は 26 × 63 × 78 × 14 = 1788696 となる。

上下左右斜めのいずれかの方向で連続する4つの数字の積のうち最大のものを求めよ。

問題を解いたプログラム

ベタベタな感じでしかとけません・・・。
def input = [
        [8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 8],
        [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, 8, 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, 9, 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, 9, 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, 8, 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, 8, 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]]

def size = 20
def ret = (0..<size).findResults {row ->
  (0..<size).findResults {col ->
    [
            col < 17 ? (input[row][col..<col + 4]).inject(1) {n1, n2 -> n1 * n2} : 0,
            col < 17 && row < 17 ? [input[row][col], input[row + 1][col + 1], input[row + 2][col + 2], input[row + 3][col + 3]].inject(1) {n1, n2 -> n1 * n2} : 0,
            col >= 3 && row < 17 ? [input[row][col], input[row + 1][col - 1], input[row + 2][col - 2], input[row + 3][col - 3]].inject(1) {n1, n2 -> n1 * n2} : 0,
            row < 17 ? [input[row][col], input[row + 1][col], input[row + 2][col], input[row + 3][col]].inject(1) {n1, n2 -> n1 * n2} : 0
    ].max()
  }.max()
}.max()
println(ret)

2012年5月27日日曜日

Project Euler-Problem10をgroovyで解いてみる

問題

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

問題を解いたプログラム

処理時間はものすごくかかります。(3分弱かな)
import common.Prime

def prime = new Prime()
def sum = prime.primes(2000000).sum()
println "sum = ${sum}"

Primeクラスはのprimesはiteratorを返すようにしてます。
package common

class Prime {

  def primes(int max) {
    return new Iterator<Long>() {

      def primes = []

      boolean hasNext() {
        def start = primes ? primes.max() + 1 : 2
        def result = (start..max).findResult {
          if (isPriem(it)) {
            it
          }
        }
        if (result) {
          primes << result
          primes.last() < max
        } else {
          false
        }
      }

      Long next() {
        primes.last()
      }

      void remove() {
        throw new UnsupportedOperationException()
      }

      private def isPriem(int num) {
        if (num == 2) {
          true
        } else if (num % 2 == 0) {
          false
        } else {
          def sqrt = Math.sqrt(num).toInteger()
          primes.findResult(true) {
            if (it > sqrt) {
              true
            } else if (num % it == 0) {
              false
            }
          }
        }
      }
    };
  }
}

[Oracle]PL/SQLで範囲を指定してループ

昇順でループ

1から5までの範囲で昇順にループされます。
begin
    for i in 1 .. 5
    loop
        dbms_output.put_line(i);
    end loop;
end;

降順でループ

reverseキーワードを指定すると降順にループできます。
begin
    for i in reverse 1 .. 5
    loop
        dbms_output.put_line(i);
    end loop;
end;

ちなみに、降順でループさせたい時に範囲を「最大値 .. 最小値」と指定してもループ処理がおこなわれないのできをつける。

2012年5月14日月曜日

[Oracle]文字列のtrim

trim(rtrim,ltrim)の使い方。
-- スペースをtrim
select trim('  aa  ') from dual;

-- 指定した文字をtrim
-- bothを指定しているので、前後両方がtrim対象
select trim(both 'b' from 'bbaabb') from dual;

-- leadingを指定しているので、前方がtrim対象
select trim(leading 'b' from 'bbaabb') from dual;
-- leadingを使うならば、ltrimを使ったほうが良い
select ltrim('bbaabb', 'b') from dual;

-- trailingを指定しているので、後方がtrim対象
select trim(trailing 'b' from 'bbaabb') from dual;
-- trailingを使うならばrtrimを使ったほうが良い
select rtrim('bbaabb', 'b') from dual;

2012年5月13日日曜日

Project Euler-Problem9をgroovyで解いてみる

問題

ピタゴラスの三つ組(ピタゴラスの定理を満たす自然数)とはa<b<cで
a² + b² = c²
を満たす数の組である.

例えば, 3² + 4² = 9 + 16 = 25 = 5²である.

a + b + c = 1000となるピタゴラスの三つ組が一つだけ存在する. このa,b,cの積を計算しなさい.

問題を解いたプログラム

aとbをループでまわして、cは計算で求めてと単純な感じで。無駄にループしてない文そこまで遅くない。
def ret = (1..999).findResult { a->
  ((a + 1) .. 1000).findResult() {b ->
    def c = 1000 - a - b
    if (a * a + b * b == c * c) {
      a * b * c
    }
  }
}
println "ret = ${ret}"

[Groovy]booleanを返す式

Javaと比べて、オブジェクトの状態チェック(nullや空かなど)が簡単にできる。

//******************************************************************************
// 文字列
//******************************************************************************
assert !null      // nullはfalse
assert !''        // 空文字もfalse
assert 'a'        // 1文字以上あるとtrue
assert """
"""               // 改行があるからtrue

//******************************************************************************
// 数値
//******************************************************************************
assert !0         // 0はfalse
assert 0.1        // 非0はtrue
assert 1L         // 非0はtrue

//******************************************************************************
// コレクション系
//******************************************************************************
assert ![]        // 空のリストはfalse
assert ![:]       // 空のMapはfalse
assert [1]        // 要素があるのでtrue
assert [1:1]      // 要素があるのでtrue

//******************************************************************************
// オブジェクト
//******************************************************************************
assert new Object()           // null意外なのでtrue
assert !new Object() {        // asBooleanでfalseを返しているので、常にfalse
  boolean asBoolean() {false}
}

2012年5月12日土曜日

Project Euler-Problem8をgroovyで解いてみる

問題

以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する。そのような積の中で最大のものの値はいくらか

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

EX 6桁の数123789なら、1*2*3*7*8と2*3*7*8*9の二通りとなり、後者の2*3*7*8*9=3024が最大の積となる。

問題を解いたプログラム

Iteratorで連続する5つの数字の積を返して、その最大値を求めてます。
String.metaClass.next = {int size ->
  def str = delegate.toString().replaceAll(/\r|\n/, "")
  if (size > str.size()) {
    return null
  }
  new Iterator<Integer>() {
    def result = []
    def pos = 0
    boolean hasNext() {
      pos < str.size()
    }
    Integer next() {
      if (result.isEmpty()) {
        (str[0..<size]).each {result << it.toInteger()}
        pos = 5
      } else {
        result.remove(0)
        pos <= str.size() ? result.add(str[pos++].toInteger()) : null
      }
      result.inject(1) {n1, n2 -> n1 * nn}
    }

    void remove() {
      throw new UnsupportedOperationException("unsupported remove.")
    }
  }
}
def input = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
"""

println(input.next(5).inject(0) {max, n -> Math.max(max, n)})

[Oracle]LPADとRPAD

LPADもRPADも使い方は同じ。

第一引数

文字列

第二引数

桁数

第三引数(任意)

桁を揃えるために使う文字列。指定しなかった場合はスペースになる。

使用例

-- 左スペース埋めで10桁にする
select '[' || lpad('hoge', 10) || ']' from dual
-- 右スペース埋めで10桁にする
select '[' || rpad('hoge', 10) || ']' from dual

-- スペース以外を使用する場合は、3番目にその値を指定する。
select '[' || lpad('hoge', 10, '.') || ']' from dual
select '[' || lpad('hoge', 10, '.') || ']' from dual

-- 3番目には、2文字以上の値も指定できる。
-- この場合は、変換後の値は「abhoge」となる。(指定した値より長くなることなハイ)
select '[' || lpad('hoge', 6, 'abc') || ']' from dual

-- そもそも指定した文字が、サイズより小さい場合は切り捨てられる。
select '[' || lpad('hoge', 1, 'abc') || ']' from dual

2012年5月5日土曜日

Project Euler-Problem7をgroovyで解いてみる

問題

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。

10001 番目の素数を求めよ。

問題を解いたプログラム

なんのひねりもないコードですが・・・
def primes = []
def num = 2;
while (primes.size() < 10001) {
  if (!primes.find {num % it == 0}) {
      primes << num
  }
  num++
}
println primes.last()

2012年5月4日金曜日

Groovyでカリー化

クロージャのcurryメソッドを使うとカリー化ができる。
def sum = {n1, n2 -> n1 + n2}
def curry = sum.curry(100)  // 最初のパラメータを100で固定してカリー化
println curry(100)  // 200
println curry(200)  // 300

Project Euler-Problem6をgroovyで解いてみる

問題

最初の10個の自然数について、その和の二乗と、二乗数の和は以下の通り。

1² + 2² + ... + 10² = 385
(1 + 2 + ... + 10)² = 3025
これらの数の差は 3025 - 385 = 2640 となる。

同様にして、最初の100個の自然数について和の二乗と二乗の和の差を求めよ。

問題を解いたプログラム

ありきたりな感じに、1から100までの和の二乗と、1から100までのそれぞれの二乗の和を求めてから差をもとめてるだけ。
def ret = (long) Math.pow((1..100).sum(), 2) - (1..100).inject(0) {n1, n2 -> n1 + (int) Math.pow(n2, 2) }
println "ret = $ret"

2012年5月2日水曜日

Project Euler-Problem5をgroovyで解いてみる

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。

では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

問題を解いたプログラム

最小公倍数を求めていって、結果をだしいます。
流れとしては、下のような感じになっています。
1と2→2
2と3→6
6と3→6
6と4→12
〜省略〜
12252240と19→232792560
232792560と20→232792560

private int lcm(int n1, int n2) {
  def ret = n1
  while (ret % n2 != 0) {
    ret += n1
  }
  return ret
}
def ret = (1 .. 20).inject(1) {n1, n2 -> lcm(n1, n2) }
println "ret = $ret"