「コマ大数学科」を Ruby で（3）

Ruby

marginalia.hatenablog.com
marginalia.hatenablog.com続きです。
　
引き続き
「コマ大数学科」に挑む
このサイトから問題を拝借いたします（ありがとうございます！）
　

法政に挑戦（2009/12/8）

問題：
行列 を５０個かけ合わせたとき、できる行列を求めてください。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0912.html#koma2

コード。

require 'matrix'
p Matrix[[1, 0.5], [0, 1]] ** 50    #=>Matrix[[1.0, 25.0], [0.0, 1.0]]

まあ素直に。
　

ラストナンバー（2010/1/20）

問題：
１から１００までの数から適当に２つを選び、その数を足して１引いた数を戻す、という操作を繰り返したとき最後に残る数を答えなさい。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai1001.html#koma4

コード。

ar = [*1..100]
ar += [ar.shift + ar.shift - 1] while ar.size > 1
puts ar.first    #=>4951

これは頭で考えないとつまらないですね。
　

16マス（2010/1/27）

問題：
４×４の１６マスに区切られた紙を２人に渡し、それぞれが渡された紙のマスを２つ塗りつぶす。２人の紙を表を上にしてどのように重ねても、塗りつぶされたマスが重ならない確率を求めなさい。
（紙を裏返すことはできないが回転させることはできる。また４隅は重ねるものとする。）

http://www.geocities.jp/tfujisaki2006/sugaku/komadai1001.html#koma5

コード。

table = [*0..15].combination(2).to_a
co = 0
rotate = ->(a) { a.map {|i| (i % 4) * 4 + 3 - i / 4} }
table.repeated_permutation(2) do |p1, p2|
  f = true
  consistent = ->(a, b) {f = false unless (a & b).empty?}
  4.times {consistent.(p1, p2 = rotate.(p2))}
  co += 1 if f
end
puts Rational(co, 14400)    #=>89/300

なお、配列 table のサイズは 120 であり、120 × 120 = 14400 です。最初は重複組み合わせで考えていて、これだと正しい確率にならないのですね。
　

カレンダー（2010/3/17）


問題：
タケシくんは今年の３月に毎週１回ずつ合計５回デートをします。 デートの曜日は月曜が１回、水曜が２回、土曜が１回、日曜が１回です。
タケシくんがデートする日付の数の和はいくつでしょう。

右のカレンダーは２０１０年３月のカレンダー

図はリンク先から拝借しました（ありがとうございます！）。コード。

result = []
[*1..31].combination(5) do |days|
  next unless days.map {|d| d / 7}.sort == [*0..4]
  next unless days.map {|d| d % 7}.sort == [0, 1, 3, 3, 6]
  result << days.inject(&:+)
end
puts result.uniq    #=>83

例によって brute-force です。というか、

puts 1 + 10 + 17 + 27 + 28    #=>83

でオシマイじゃね？
　

GCD（2010/6/2）

問題：
各桁の数字（0でない）が相異なる３桁の正の整数ｎがある。
ｎの各数字を並べてできる、６つの数の最大公約数をｇとする。
ｇとして考えられる最大の値を求めよ。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai1006.html#koma1

コード。

max = 0
[*1..9].combination(3) do |nums|
  x = nums.permutation.map {|n| n.join.to_i}.inject(&:gcd)
  max = x if x > max
end
puts max    #=>18

Ruby っぽいコードになりました。
　

エマープ素数（2010/10/13）

エマープ (emirp) 素数…素数の中で数字を逆に書いても素数になる数のこと。
たとえば「１３と３１」「３７と７３」などがエマープ素数である。
「emirp」は「prime：素数」を逆にしたもの。 ただし、逆に書いても同じになる素数（１０１など）は含まれない。
問題：３ケタのエマープ素数を３つ答えなさい。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai1010.html#koma1

コード。

def eratosthenes(n)
  ar = [*0..n]
  2.upto(Math.sqrt(n).to_i) do |i|
    next if ar[i].zero?
    2.upto(n / i) {|j| ar[i * j] = 0}
  end
  ar[2..-1].reject {|x| x.zero?}
end

table = eratosthenes(999).select {|x| x >= 100}
result = table.map do |num|
  r_num = num.to_s.reverse.to_i
  next if num >= r_num
  table.include?(r_num) ? [num, r_num] : nil
end.compact
p result

結果。

[[107, 701], [113, 311], [149, 941], [157, 751], [167, 761], [179, 971],
 [199, 991], [337, 733], [347, 743], [359, 953], [389, 983], [709, 907],
 [739, 937], [769, 967]]

これはプログラミング向きの問題ですね。「エラトステネスの篩」で３桁の素数をすべて求めてから解いています。
　

チャンパーノウン数（2011/2/9）

問題：
すべての自然数を順番につなげて書いていくとき、１万個目に書かれる 数字はいくつでしょう。
１，２，３，…と順番に書いていく。９までは一桁の数であるが、次の １０から２桁になるため、１０個目の数は「１」、１１個目の数は「０」 になる。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai1101.html#koma2

コード。

N = 10000
st = ""
1.step do |i|
  st += i.to_s
  if st.length >= N
    puts st[N - 1]    #=>7
    break
  end
end

　

必勝法 Part 6（2011/6/22）


問題：
ＡくんとＢくんが図のア～ケ９つのマスに１，３，４～１０の数字を交互に一つずつ入れていく。

ルール
・先手はＡくん。
・Ａくんは上段と下段に入れた数字（ア、イ、ウ、キ、ク、ケ）の合計を得点とする。
・Ｂくんは左列と右列に入れた数字（ア、エ、キ、ウ、カ、ケ）の合計を得点とする。
・２人のうち得点の多いほうが勝ちとする。

このとき先手のＡくんは、どのマス目にどの数字を入れると良いでしょうか。


アイウ
エオカ
キクケ
コード。これは Go で書きました。というか、最初は Ruby で書いたのだが、遅すぎて終わらない。まあ、min-max 法による brute-force なので、そんなことになるのですが。じつはもっとエレガントに解けます。

package main
import "fmt"

func delete(numbers []int, n int) (result []int) {
    for _, x := range numbers {
        if x == n {continue}
        result = append(result, x)
    }
    return
}

func try(numbers []int, table []int, turn bool, f func(int, ...int)) {
    for _, n := range numbers {
        for i, _ := range table {
            if table[i] != 0 {continue}
            table[i] = n
            score := min_max(delete(numbers, n), table, !turn)
            table[i] = 0
            f(score, i, n)
        }
    }
}

func min_max(numbers []int, table []int, turn bool) int {
    if len(numbers) == 0 {
        s1 := table[0] + table[1] + table[2] + table[6] + table[7] + table[8]
        s2 := table[0] + table[3] + table[6] + table[2] + table[5] + table[8]
        if s1 > s2 {return 1} else {return -1}
    }
    
    if turn {
        max := -10
        f := func(score int, a ...int) { if score > max {max = score} } 
        try(numbers, table, turn, f)
        return max
    } else {
        min := 10
        f := func(score int, a ...int) { if score < min {min = score} } 
        try(numbers, table, turn, f)
        return min
    }
}

func main() {
    f := func(score int, a ...int) {if score == 1 { fmt.Println([]int{score, a[0], a[1]}) }}
    try([]int{1, 3, 4, 5, 6, 7, 8, 9, 10}, make([]int, 9), true, f)
}

結果。

$ go build komadai1.go
$ time ./komadai1
[1 3 1]
[1 5 1]

real	2430m31.749s
user	2472m32.886s
sys	10m37.645s

つまり、ここでの回答どおり、「エまたはカに 1 を入れる」となりました。しかし Go で 40 時間もかかるとは…。