「コマ大数学科」を Ruby で(2)
marginalia.hatenablog.com続きです。
引き続き
「コマ大数学科」に挑む
このサイトから問題を拝借いたします(ありがとうございます!)
フラッグ(2008/9/11)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0809.html
1m間隔で一列に13本並んだ旗をどこか1箇所の旗のところに集めたい。1度に1本の旗しか持てないときに最短の移動距離で集めるためにはどの旗に何mの移動距離で集めれば良いでしょう。ただし1番目の旗の場所をスタート地点とする。
コード。
N = 13 def try(i) length = i - 1 (2..N).each do |j| length += (j - i).abs * 2 end length end p (1..N).map {|i| [i, try(i)]}.sort_by(&:last).first #=>[7, 78]
これはプログラミングで解くような問題ではないですね。簡単すぎる。
コマ大番外編…平成教育委員会SP(2008/8/31)
問題: 図の○の中に1から7までの数字を入れ、直線で結ばれた3つの数字の和(全部で5列ある)が全て等しくなるとき、赤い丸に入る数字と等しい和を答えなさい。 |
require 'set' table = [[4, 5, 6], [0, 1, 4], [0, 2, 5], [0, 3, 6]] answer = Set.new [*1..7].permutation.each do |nominee| sum = nominee[1] + nominee[2] + nominee[3] catch(:jump) do table.each do |positions| throw(:jump) unless positions.map {|i| nominee[i]}.inject(&:+) == sum end answer << [nominee.first, sum] end end puts answer #=>#<Set: {[4, 12]}>
これも、わざわざプログラミングで解かなくても…という感じ。いや、結構むずかしいかな。
億(2008/11/13)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0811.html
1から1億までの数字を書いたときに現れる数字の全ての和を求めなさい。
一見 Ruby で解くのは容易そうである。こんな風に。
answer = 0 (1..1_0000_0000).each do |n| answer += n.to_s.chars.map(&:to_i).inject(&:+) end puts answer
しかしこれは、実際は(時間がかかりすぎるので)フリーズします。なので、少し考える必要がある。n 桁以下のすべての数に現れる数字の和を sum(n) とおくと、漸化式
が sum(1) = 1 + 2 + … + 9 = 45 として成立するので(理由は考えてみよう。ヒントは最上位とそれ以外を分ける)、こんなコードが得られる。
def sum(n) return 45 if n == 1 sum(1) * 10 ** (n - 1) + 10 * sum(n - 1) end puts 1 + sum(8) #=>3600000001
つまり、答えは 36億1 ですね。これなら 100億まででも 1000兆まででも簡単である。
なお、上の漸化式は一般項を求めることができて、
となります。ヒントは漸化式の両辺を 10 の n - 1 乗で割るとよい。
31(2008/11/20)
問題:
1から6までのトランプ24枚を使い、2人が交互に1枚ずつ取り、2人の取ったカードの合計を先に31にした方が勝ち、というゲームをする。(31を超えたら負け。)このゲームで先手が勝つためには始めに何を取ればよいか。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0811.html
これはむずかしい。手作業で解くのはとてもではないがつらい。
しかしプログラミングでもかなりむずかしい感じである。「min-max 法」でやってみる。コード。
Goal = 31 initial_cards = (1..6).flat_map {|i| [i] * 4} def delete(cards, n) idx = cards.find_index(n) cards[0...idx] + cards[idx + 1..-1] end def min_max(cards, turn, sum) return (turn ? -10 : 10) if sum == Goal return (turn ? 10 : -10) if sum > Goal children = cards.uniq if turn max = -100 children.each do |ch| score = min_max(delete(cards, ch), !turn, sum + ch) max = score if score > max end max else min = 100 children.each do |ch| score = min_max(delete(cards, ch), !turn, sum + ch) min = score if score < min end min end end p (1..6).map {|i| [i, min_max(delete(initial_cards, i), false, i)]}
先手の手番で turn = true になります。勝った方に 10 ポイント、負けた方に -10 ポイントの評価をしています。最初に先手の手番を与えているので、次は後手(turn = false)になります。
結果。
$ time ruby solve.rb [[1, 10], [2, 10], [3, -10], [4, -10], [5, 10], [6, -10]] real 4m40.226s user 4m40.188s sys 0m0.004s
よって、先手が勝利するのは 1, 2, 5 のいずれかを選んだときになります。自分の環境で 4分40秒ほどかかっています。
パフォーマンスを改善してみる。新しい配列を生成しないように、データ構造を書き換えます。コード。
N = 6 Goal = 31 initial_cards = [4] * N def min_max(cards, turn, sum) return (turn ? -10 : 10) if sum == Goal return (turn ? 10 : -10) if sum > Goal if turn max = -100 N.times do |i| next if cards[i].zero? cards[i] -= 1 score = min_max(cards, !turn, sum + i + 1) cards[i] += 1 max = score if score > max end max else min = 100 N.times do |i| next if cards[i].zero? cards[i] -= 1 score = min_max(cards, !turn, sum + i + 1) cards[i] += 1 min = score if score < min end min end end result = [] N.times do |i| initial_cards[i] -= 1 result << [i + 1, min_max(initial_cards, false, i + 1)] initial_cards[i] += 1 end p result
結果。
$ time ruby solve.rb [[1, 10], [2, 10], [3, -10], [4, -10], [5, 10], [6, -10]] real 1m24.899s user 1m24.876s sys 0m0.024s
3.3 倍ほど高速化しました。
もう一つのオイラー数(2008/12/11)
問題:
それぞれ1から8までの数字が書かれた8枚のカードをシャッフルして、次の条件で順番に赤と青の箱に入れていく。1枚目は赤の箱に入れる。
2枚目以降は
それまでで出たカードのいずれよりも大きい数字ならば赤の箱に入れる。
それ以外なら青の箱に入れる。全てのカードを入れ終えたとき、青にカードが1枚だけ入っている確率を求めよ。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0812.html#koma2
コード。
co = 0 [*1..8].permutation do |deck| red, blue = [deck.shift], [] while (card = deck.shift) if card > red.max red << card else blue << card end end co += 1 if blue.size == 1 end puts Rational(co, 40320) #=>1/1440
簡単ですね。なお、8! = 40320 です。
畳(2009/2/4)
問題: 上の図のような4×5の十畳分の部屋に 畳を10枚敷き詰める方法は何通りあるでしょう。 (上下、左右にひっくり返すことで変わる敷き詰め方は 別の敷き詰め方とします)
initial_room = Array.new(20, false) co = 0 try = ->(room) { i = room.find_index(false) if i if i % 4 != 3 and !room[i + 1] room[i] = room[i + 1] = true try.(room) room[i] = room[i + 1] = false end if i < 16 and !room[i + 4] room[i] = room[i + 4] = true try.(room) room[i] = room[i + 4] = false end else co += 1 end } try.(initial_room) puts co #=>95
左上隅から順に畳を敷き詰めていきます。深さ優先探索で求めています。
魔法使い(2009/3/5)
問題:
魔法A,魔法Bを使える魔法使いがいます。魔法Aは「全てのイチゴ」それぞれを「イチゴとバナナ」に変える。
魔法Bは「全てのバナナ」それぞれを「イチゴとバナナ」に変える。今イチゴとバナナが1個ずつある状態から魔法A,魔法Bを何回か かけたところイチゴが15個、バナナが877個になった。二つの 魔法は合計何回かけたでしょう。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0903.html#koma1
コード。
s, b = 15, 877 sn = bn = 0 A = ->{b -= s; sn += 1} B = ->{s -= b; bn += 1} until s == 1 and b == 1 (s < b) ? A.() : B.() end puts sn + bn #=>66
逆から考えるとよいですね。たとえば A の魔法をかける前は、イチゴの数だけバナナが少なくなっています(イチゴの数は変わりません)。なので、魔法をかけたあとのバナナの方がイチゴより数が大きくないと、A の魔法をかけることはできません。
靴ひも問題(2009/2/12)
問題:
左右2列に8個ずつの穴がある靴に靴ひもを通すときの最短の長さを求めよ。
ただし、それぞれの穴から必ず反対の列にひもを渡すことが必要である。(渡す穴の一方が同じ列、他方が反対の列というのでもよい。)左右の穴の間隔は2、各列の穴の間隔は1とする。また結び目までの長さも含める。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0902.html#koma2
非常にむずかしい問題で、番組で正解が出たのが驚きです。
コード。
N = 8 initial_holes = Array.new(N * 2, false) @min = Float::INFINITY def distance(a, b) a, b = b, a if a > b return b - a if (a < N and b < N) or (a >= N and b >= N) b -= N Math.sqrt(4 + (a - b) ** 2) end def try(from, before, holes, length) return if @min < length if holes.all? length += distance(@start, from) @min = length if length < @min else holes.each_index do |to| next if holes[to] or (from < N and before < N and to < N) or (from >= N and before >= N and to >= N) holes[to] = true try(to, from, holes, length + distance(from, to)) holes[to] = false end end end (0...(N * 1/2r).ceil).each do |i| initial_holes[i] = true try(@start = i, N, initial_holes, 0) initial_holes[i] = false end puts @min
結果。
$ time ruby solve.rb 25.41640786499874 real 45m24.468s user 45m24.376s sys 0m0.032s
正解が出ていますが、45分もかかりました。アルゴリズムとしてはそれほどむずかしいことをやっているわけではありません。
これは是非元記事を参照して頂きたいですね。
カックロ(2009/5/14)
問題: 5枚のカードの表(白)と裏(黒)にそれぞれ0から9までの数字を一つずつかかれています。この5枚のカードを横一列に並べて以下の条件が成り立つとき、最初に見えていた(表5つ)の数字を答えなさい。
5枚とも表の状態 | 見えている5つの数字の合計は19 | |
左の3枚を裏返す | 見えている5つの数字の合計は20 | |
右の3枚を裏返す | 見えている5つの数字の合計は35 | |
左の4枚を裏返す | 見えている5つの数字の合計は11 | |
右の4枚を裏返す | 見えている5つの数字の合計は31 |
table1 = [[0, 1, 2, 3, 4], [5, 6, 7, 3, 4], [5, 6, 2, 8, 9], [0, 1, 7, 3, 9], [0, 6, 2, 8, 4]] table2 = [19, 20, 35, 11, 31] [*0..9].permutation.each do |cards| f = table1.map.with_index do |a, i| a.map {|b| cards[b]}.inject(&:+) == table2[i] end.all? p cards[0, 5] if f end
結果。
$ time ruby solve.rb [3, 1, 9, 2, 4] real 0m23.629s user 0m23.612s sys 0m0.016s
単純な brute-force なので、時間がかかっています。
消えた数(2009/6/4)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0906.html#koma1
たろうくんは1から順に1,2,3…とある数までを黒板に書きました。
じろうくんはその中の1個の数を消してしまいました。すると残りの数の平均は590/17になりました。
じろうくんの消した数はいくつですか?
コード。
class Rational def integer?() (self - to_i).zero? end end 2.step do |i| x = Rational(i * (i + 1), 2) - Rational(590 * (i - 1), 17) if 0 < x and x <= i and x.integer? p [x.to_i, i] #=>[55, 69] break end end
つまり答えは 55。簡単ですね。
早稲田に挑戦(2009/6/18)
問題: 約数の個数が28個ある最小の自然数nを求めなさい。
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0906.html#koma3
コード。
def divisors(n) (1..n).select {|i| (n % i).zero?} end 1.step do |i| if divisors(i).size == 28 puts i #=>960 break end end
これも極簡単ですね。
ビル(2009/6/25)
問題: ある区画に25個のビルが5行5列の正方形状に並んで建っています。 右の図は真上から見たビルを表しています。 1.ビルは1~5階建てのいずれか。 2.同じ行、同じ列でビルの階数は全て異なる。 3.矢印の数字はその方向から見えるビルの個数。(高いビルの奥にある低いビルは見えないという意味です。) 以上の条件を満たすとき、中央のマス目のビルは何階でしょう? |
N = 5 def product(n, f = true) result = [] [*1..N].permutation do |buildings| copied = buildings.dup buildings.reverse! unless f visible = [] loop do visible << (a = buildings.shift) break if buildings.empty? buildings = buildings.drop_while {|b| a > b} end result << copied if visible.compact.size == n end result end lines1 = product(3) lines2 = lines1 & product(2, false) lines3 = product(4) def set_field(field, n, line) setted = field.dup N.times do |i| pos = yield(n, i) return nil unless setted[pos].zero? or setted[pos] == line[i] setted[pos] = line[i] end setted end def set_col(field, n, line) set_field(field, n, line) {|n, i| n + N * i} end def set_row(field, n, line) set_field(field, n, line) {|n, i| i + N * n} end field = Array.new(N * N, 0) selected_fields = [] lines2.each do |l1| fld1 = set_col(field, 1, l1) lines1.each do |l2| next unless (fld2 = set_col(fld1, 3, l2)) lines3.each do |l3| next unless (fld3 = set_col(fld2, 4, l3.reverse)) lines3.each do |l4| next unless (fld4 = set_row(fld3, 1, l4.reverse)) selected_fields += lines3.map {|l5| set_row(fld4, 3, l5)}.compact end end end end def settable?(field, pos) check = ->(row) { s = row.reject(&:zero?) s.size == s.uniq.size } x, y = pos % N, pos / N row = field[y * N , N] col = x.step(N * N - 1, N).map {|i| field[i]} return false unless check.(row) and check.(col) return true if row.include?(0) or col.include?(0) return false if row.sort != [*1..N] return false if col.sort != [*1..N] true end def doit(field) pos = field.find_index(0) if pos new_field = field.dup N.times do |i| new_field[pos] = i + 1 doit(new_field) if settable?(new_field, pos) end else pp field.each_slice(N).to_a end end selected_fields.each {|f| doit(f)}
結果。
[[4, 1, 3, 2, 5], [5, 4, 1, 3, 2], [3, 5, 2, 1, 4], [1, 2, 4, 5, 3], [2, 3, 5, 4, 1]]
つまり答えは「2」です。プログラミングで解かない方が簡単かも知れませんね。解けるけれど、プログラミングには苦手な感じの問題です。
原始ピタゴラス数(2009/7/23)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0907.html#koma4
3辺の長さが整数の直角三角形があります。3辺のうち2つの辺の長さが素数であり、3辺の長さの和が132のとき、3辺のそれぞれの長さを求めなさい。
コード。
require 'prime' L = 132 def prime_check(*args) args.combination(2) do |i, j| return true if Prime.prime?(i) and Prime.prime?(j) end false end 1.upto(L / 3) do |a| a.upto(L) do |b| c = L - a - b next unless b < c and c <= L - 2 next unless prime_check(a, b, c) p [a, b, c] if a * a + b * b == c * c #=>[11, 60, 61] end end
簡単ですね。
アインシュタインに挑戦
問題: 右の図の四角の中に1~9の数字をひとつずつ入れ、図の7つの三角形の頂点にある3つの数の和が等しくなるようにしなさい。 (赤の大きさの三角形4つと青の大きさの三角形3つ) |
table = [[0, 2, 3], [1, 4, 5], [3, 4, 6], [6, 7, 8], [0, 1, 6], [2, 4, 7], [3, 5, 8]] [*0..8].permutation do |field| sum = table[0].map {|i| field[i]}.inject(&:+) f = table[1..-1].map do |t| t.map {|i| field[i]}.inject(&:+) == sum end.all? p field if f end
結果。
[1, 6, 9, 5, 2, 7, 8, 4, 3] [1, 8, 9, 5, 4, 3, 6, 2, 7] [1, 9, 6, 8, 2, 4, 5, 7, 3] [1, 9, 8, 6, 4, 2, 5, 3, 7] [2, 7, 9, 4, 5, 3, 6, 1, 8] [2, 9, 7, 6, 5, 1, 4, 3, 8] [3, 4, 7, 5, 2, 9, 8, 6, 1] [3, 7, 4, 8, 2, 6, 5, 9, 1] [3, 7, 8, 4, 6, 2, 5, 1, 9] [3, 8, 7, 5, 6, 1, 4, 2, 9] [4, 3, 9, 2, 5, 7, 8, 1, 6] [4, 9, 3, 8, 5, 1, 2, 7, 6] [6, 1, 7, 2, 5, 9, 8, 3, 4] [6, 7, 1, 8, 5, 3, 2, 9, 4] [7, 2, 3, 5, 4, 9, 6, 8, 1] [7, 3, 2, 6, 4, 8, 5, 9, 1] [7, 3, 6, 2, 8, 4, 5, 1, 9] [7, 6, 3, 5, 8, 1, 2, 4, 9] [8, 1, 3, 4, 5, 9, 6, 7, 2] [8, 3, 1, 6, 5, 7, 4, 9, 2] [9, 1, 2, 4, 6, 8, 5, 7, 3] [9, 1, 4, 2, 8, 6, 5, 3, 7] [9, 2, 1, 5, 6, 7, 4, 8, 3] [9, 4, 1, 5, 8, 3, 2, 6, 7]
答えは 24とおりあります。これもブログラミングだと簡単ですね。単純な brute-force ですが。
ファレイ数列(2009/11/11)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0911.html#koma2
ある線分の2等分点、3等分点、4等分点と順に新しい等分点にだけ印をつけていきます。15等分点に印を付けたとき、新たに増える印の数を答えなさい。
コード。
require 'set' set = Set.new generate = ->(n) { (1...n).map {|i| Rational(i, n)} } 2.upto(14) {|i| set += generate.(i)} n = set.size set += generate.(15) puts set.size - n #=>8
ダイアゴナル(2009/11/25)
問題:
http://www.geocities.jp/tfujisaki2006/sugaku/komadai0911.html#koma4
1辺の長さ1の正方形のタイル800枚を隙間なく並べて縦25、横32の長方形を作ります。
この長方形の対角線1本が通過するタイルの枚数を求めなさい。
コード。
W, H = 32, 25 def y(x) Rational(H * x, W) end def cross?(px, py) y1 = y(px) return true if py < y1 and y1 < py + 1 y1 = y(px + 1) return true if py < y1 and y1 < py + 1 false end co = 0 0.upto(H - 1) do |y| 0.upto(W - 1) do |x| co += 1 if cross?(x, y) end end puts co #=>56
Ruby が分数を標準で扱えるのが効いていますね。