RMagick で LoadError

RMagick に関して次のエラーが出た。Ubuntu 18.10, Ruby 2.3.4。

AOJ（問題集）2

AIZU ONLINE JUDGE: Programming Challenge
　

0011 Drawing Lots

given = $<.readlines
lines = [*0..given.first.to_i]
given.drop(2).map {|x| x.split(",").map(&:to_i)}.each do |a, b|
  lines[a], lines[b] = lines[b], lines[a]
end
puts lines.drop(1)

0012 A Point in a Triangle

$<.readlines.each do |l|
  x1, y1, x2, y2, x3, y3, xp, yp = l.split.map(&:to_f)
  xa, ya = xp - x1, yp - y1
  xb, yb = x3 - x1, y3 - y1
  xc, yc = x2 - x3, y2 - y3
  r = xb * yc - xc * yb
  s = (yc * xa - xc * ya) / r
  u = (xb * ya - yb * xa) / r
  t = u / s
  puts((0 < s and s < 1 and 0 < t and t < 1) ? "YES" : "NO")
end

0013 Switching Railroad Cars

stack = []
while (n = $<.gets)
  n = n.to_i
  if n.zero?
    puts stack.pop
  else
    stack << n
  end
end

0014 Integral

L = 600
$<.readlines.map(&:to_i).each do |d|
  puts (1..L / d - 1).map {|i| (i * d) ** 2 * d}.sum
end

0015 National Budget

$<.readlines.drop(1).map(&:to_i).each_slice(2) do |a, b|
  st = (a + b).to_s
  puts((st.length <= 80) ? st : "overflow")
end

0016 Treasure Hunt

x, y = 0, 0
θ = 90
loop do
  given = $<.gets.split(",").map(&:to_i)
  break if given == [0, 0]
  x += given[0] * Math.cos(Math::PI * θ / 180)
  y += given[0] * Math.sin(Math::PI * θ / 180)
  θ -= given[1]
end
puts x.to_i
puts y.to_i

0017 Caesar Cipher

def decode(st, n)
  trans = ->(b) {(a = b - n) < 97 ? a + 26 : a}
  st.bytes.map {|b| (b.between?(97, 122) ? trans.(b) : b).chr}.join
end

words = %w(the this that)
table = (0..25).map do |i|
  words.map {|w| w.bytes.map {|b| ((a = b + i) > 122 ? a - 26 : a).chr}.join}
end

$<.readlines.each do |st|
  st.chomp!
  n = 0
  table.each_with_index do |ws, i|
    ws.each {|w| n = i if st.include?(w)}
  end
  puts decode(st, n)
end

0018 Sorting Five Numbers

puts $<.gets.split.map(&:to_i).sort {|a, b| b <=> a}.join(" ")

0019 Factorial

puts (1..$<.gets.to_i).inject(&:*)

0020 Capitalize

puts $<.gets.chomp.upcase

AOJ（問題集）1

AIZU ONLINE JUDGE: Programming Challenge
　

0000 QQ

9.times do |i|
  9.times {|j| puts "#{x = i + 1}x#{y = j + 1}=#{x * y}"}
end

0001 List of Top 3 Hills

puts $<.readlines.map(&:to_i).sort {|a, b| b <=> a}.take(3)

0002 Digit Number

$<.readlines.each do |l|
  puts Math.log10(l.split.map(&:to_i).sum).to_i + 1
end

0003 Is it a Right Triangle?

$<.readlines.drop(1).each do |l|
  a, b, c = l.split.map(&:to_i).sort
  puts((a * a + b * b == c * c) ? "YES" : "NO")
end

0004 Simultaneous Equation

$<.readlines.each do |l|
  a, b, c, d, e, f = l.split.map(&:to_i)
  r = a * e - b * d
  x = (c * e - b * f) / r.to_f
  y = (a * f - c * d) / r.to_f
  x = x.abs if x == 0
  y = y.abs if y == 0
  printf("%.3f %.3f\n", x, y)
end

0005 GCD and LCM

$<.readlines.each do |l|
  a, b = l.split.map(&:to_i)
  puts "#{a.gcd(b)} #{a.lcm(b)}"
end

0006 Reverse Sequence

puts $<.gets.chomp.reverse

0007 Debt Hell

debt = 10_0000
$<.gets.to_i.times do
  debt = debt * 1.05
  debt = (debt / 1000).ceil * 1000
end
puts debt

0008 Sum of 4 Integers

require 'set'

$<.readlines.map(&:to_i).each do |n|
  s = Set.new
  l = n / 4
  l = (l < 10) ? l : 9
  (0..l).each do |a|
    (a..9).each do |b|
      (b..9).each do |c|
        d = n - a - b - c
        if c <= d and d <= 9
          s += [a, b, c, d].permutation.to_a
        end 
      end
    end
  end
  puts s.size
end

これで 0.28秒。

$<.readlines.map(&:to_i).each do |n|
  co = 0
  10.times do |a|
    10.times do |b|
      10.times do |c|
        10.times do |d|
          co += 1 if a + b + c + d == n
        end
      end
    end
  end
  puts co
end

これで 0.09秒。わざわざ工夫しないほうが速かった。
　

0009 Prime Number

$<.readlines.map(&:to_i).each do |n|
  ar = (0..n).to_a
  2.upto(Math.sqrt(n).to_i) do |i|
    next if ar[i].zero?
    2.upto(n / i) {|j| ar[i * j] = 0}
  end
  co = 0
  ar[2..-1].each {|i| co += 1 if i.nonzero?}
  puts co
end

4.04秒もかかってしまった。

N = 999_999
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

$<.readlines.map(&:to_i).each do |n|
  co = 0
  ar[2..-1].each do |i|
    break if i > n
    co += 1 if i.nonzero?
  end
  puts co
end

よく考えたらその都度ふるいを実行することはなかった。これでも 2.5秒。
　

0010 Circumscribed Circle of a Triangle

$<.readlines.drop(1).each do |l|
  x1, y1, x2, y2, x3, y3 = l.split.map(&:to_f)
  a = x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)
  b1 = x1 * x1 + y1 * y1
  b2 = x2 * x2 + y2 * y2
  b3 = x3 * x3 + y3 * y3
  x = (b1 * (y2 - y3) + b2 * (y3 - y1) + b3 * (y1 - y2)) / (2 * a)
  y = (b1 * (x3 - x2) + b2 * (x1 - x3) + b3 * (x2 - x1)) / (2 * a)
  r = Math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
  printf("%.3f %.3f %.3f\n", x, y, r)
end

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

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 時間もかかるとは…。

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

marginalia.hatenablog.com続きです。

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

フラッグ（2008/9/11）

問題：
１ｍ間隔で一列に１３本並んだ旗をどこか１箇所の旗のところに集めたい。１度に１本の旗しか持てないときに最短の移動距離で集めるためにはどの旗に何ｍの移動距離で集めれば良いでしょう。ただし１番目の旗の場所をスタート地点とする。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0809.html

コード。

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]

これはプログラミングで解くような問題ではないですね。簡単すぎる。
　

コマ大番外編…平成教育委員会ＳＰ（2008/8/31）

問題： 図の○の中に１から７までの数字を入れ、直線で結ばれた３つの数字の和（全部で５列ある）が全て等しくなるとき、赤い丸に入る数字と等しい和を答えなさい。

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

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

一見 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）

問題：
１から６までのトランプ２４枚を使い、２人が交互に１枚ずつ取り、２人の取ったカードの合計を先に３１にした方が勝ち、というゲームをする。（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）

問題：
それぞれ１から８までの数字が書かれた８枚のカードをシャッフルして、次の条件で順番に赤と青の箱に入れていく。

１枚目は赤の箱に入れる。
２枚目以降は
それまでで出たカードのいずれよりも大きい数字ならば赤の箱に入れる。
それ以外なら青の箱に入れる。

全てのカードを入れ終えたとき、青にカードが１枚だけ入っている確率を求めよ。

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）

問題：　上の図のような４×５の十畳分の部屋に 畳を１０枚敷き詰める方法は何通りあるでしょう。 （上下、左右にひっくり返すことで変わる敷き詰め方は 別の敷き詰め方とします）

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

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）

問題：
魔法Ａ，魔法Ｂを使える魔法使いがいます。

魔法Ａは「全てのイチゴ」それぞれを「イチゴとバナナ」に変える。
魔法Ｂは「全てのバナナ」それぞれを「イチゴとバナナ」に変える。

今イチゴとバナナが１個ずつある状態から魔法Ａ，魔法Ｂを何回か かけたところイチゴが１５個、バナナが８７７個になった。二つの 魔法は合計何回かけたでしょう。

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）

問題：
左右２列に８個ずつの穴がある靴に靴ひもを通すときの最短の長さを求めよ。
ただし、それぞれの穴から必ず反対の列にひもを渡すことが必要である。（渡す穴の一方が同じ列、他方が反対の列というのでもよい。）

左右の穴の間隔は２、各列の穴の間隔は１とする。また結び目までの長さも含める。

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）

問題：　５枚のカードの表（白）と裏（黒）にそれぞれ０から９までの数字を一つずつかかれています。この５枚のカードを横一列に並べて以下の条件が成り立つとき、最初に見えていた（表５つ）の数字を答えなさい。

５枚とも表の状態		見えている５つの数字の合計は１９
左の３枚を裏返す		見えている５つの数字の合計は２０
右の３枚を裏返す		見えている５つの数字の合計は３５
左の４枚を裏返す		見えている５つの数字の合計は１１
右の４枚を裏返す		見えている５つの数字の合計は３１

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

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

コード。

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）

問題：　約数の個数が２８個ある最小の自然数ｎを求めなさい。

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)

問題： ある区画に２５個のビルが５行５列の正方形状に並んで建っています。 右の図は真上から見たビルを表しています。 １．ビルは１～５階建てのいずれか。 ２．同じ行、同じ列でビルの階数は全て異なる。 ３．矢印の数字はその方向から見えるビルの個数。（高いビルの奥にある低いビルは見えないという意味です。） 以上の条件を満たすとき、中央のマス目のビルは何階でしょう？

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

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

コード。

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

簡単ですね。
　

アインシュタインに挑戦

問題： 右の図の四角の中に１～９の数字をひとつずつ入れ、図の７つの三角形の頂点にある３つの数の和が等しくなるようにしなさい。 （赤の大きさの三角形４つと青の大きさの三角形３つ）

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

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

コード。

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

コード。

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 が分数を標準で扱えるのが効いていますね。

Linux Mint 19 で MG5600 が使えなくなった

Linux Mint を 19 にアップグレードしたところ、キヤノンのプリンタ MG5600 が使えなくなった。ドライバが古くなったのか調べたが、どうもよくわからない。

うんこな電子メール(2)

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

izu-mix.comプログラミングで解けそうな問題だけ解いています。
　

#001 フィボナッチ数列

問題：
15段の階段を上るとき、1段上るか、2段上るか、2通りの方法を組み合わせて登ると、何通りの登り方があるか。

コード。

def fib(n)
  return 1 if n == 1
  return 2 if n == 2
  fib(n - 1) + fib(n - 2)
end

puts fib(15)    #=>987

#042 ミッシングナンバー

問題：
ホテルの部屋の扉に4と9を使わないで1号室から番号をつけていくと500番目の部屋は何号室か？

コード。

def room(goal)
  room_number = 1
  n = 0
  loop do
    n += 1 if room_number.to_s.scan(/[49]/).empty?
    return room_number if n == goal
    room_number += 1
  end
end

puts room(500)    #=>875

#117 バスケットボール

問題：
バスケットボールの得点は、フリースローが1点、スリーポイントラインの内側からだと2点、外側からだと3点入ります。ちょうど得点が10点になるまでの得点経過は何通りあるでしょうか？

コード。

def point(n)
  case n
  when 1 then 1
  when 2 then 2
  when 3 then 4
  else
    point(n - 1) + point(n - 2) + point(n - 3)
  end
end

puts point(10)    #=>274

考え方は「#001 フィボナッチ数列」の場合と同じ。
　

#029 カタラン数

問題：
10人が円卓に座って1人ずつ握手をするとき、全員の手が交差しないように握手する仕方は全部で何通りあるか？

コード。

def count(n)
  case
  when n.odd?  then 0
  when n.zero? then 1
  else
    result = 0
    2.step(n, 2) {|i| result += count(i - 2) * count(n - i)}
    result
  end
end

puts count(10)    #=>42

これだと n = 30 くらいが限界なので、メモ化するとよい。メモ化すると例えば n = 200 くらいでも一瞬。ちなみに count(200) = 896519947090131496687170070074100632420837521538745909320 である。
　

#020 ラマヌジャン

問題：
　10軒以上、50軒以内の家が並んでおり、1から順に番号がつけてある。
　左右の端から順番に番号を足していったとき（すなわち、1から順に足していくのと、大きい方の数字から順に足していくとき）、合計がちょうど同じになる家があったとき、その家の番号を答えよ。

コード。

def find(n)
  (1..n).each do |i|
    return [n, i] if (1..i).inject(:+) == (i..n).inject(:+)
  end
  nil
end

p( (10..50).map {|i| find(i)}.compact )    #=>[[49, 35]]

つまり、49軒あったときの35番目の家。
　

#012 1000

問題：
　1～1000の数字が振られている1000個の電球がある。すべてOFFの状態から始めて、1回目の操作で1の倍数の電球のスイッチのON/OFFを切り替え、2回目の操作では2の倍数の電球のON/OFFを切り替える。
　このように、n回目の操作でnの倍数の電球のON/OFFを切り替える操作を、1000回目までおこなったとき、最後にONの状態の電球の数は何個か。

コード。

N = 1000
table = Array.new(N + 1, false)
(1..N).each {|n| n.step(N, n) {|i| table[i] = !table[i]} }
puts table.count(true)    #=>31

素直すぎるくらい素直なコードですね。
　

#196 和と積

問題：
足し合わせても掛け合わせても同じ数になる5つの正の整数と、その数を答えなさい。

5つの数を a, b, c, d, e とおくとき、a ≦ b ≦ c ≦ d ≦ e としてよいのでそうすると、明らかに 1 ≦ e ≦ 5 である（a + b + c + d + e ≦ 5e より 5 ≦ abcd）。よって超素直にコードを書くと

N = 5
(1..N).each do |e|
  (1..e).each do |d|
    (1..d).each do |c|
      (1..c).each do |b|
        (1..b).each do |a|
          sum = a + b + c + d + e
          p [[a, b, c, d, e], sum] if sum == a * b * c * d * e
        end
      end
    end
  end
end

結果は

[[1, 1, 2, 2, 2], 8]
[[1, 1, 1, 3, 3], 9]
[[1, 1, 1, 2, 5], 10]

となる。さすがにコードが素朴すぎるという向きもあるかも知れないので、ちょっと工夫して

N = 5
def loop(last, args)
  if args.size == N
    sum = args.inject(&:+)
    p [args, sum] if sum == args.inject(&:*)
  else
    (1..last).each {|i| loop(i, [i] + args)}
  end
end

loop(N, [])

とすると高級に見えるかも知れない。確かにこちらだといくつの整数でもできるという利点がある。例えば N = 13 とするとこんな結果

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3], 18]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 5], 20]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 7], 21]
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 13], 26]

になる。ただしこれだとこの N = 13 くらいが限度なので、さらにこうしてみる。

N = 100
def loop(last, args)
  product = args.inject(&:*) || 0
  return if product > N ** 2    #枝刈り
  if args.size == N
    p [args, product] if product == args.inject(&:+)
  else
    (1..last).each {|i| loop(i, [i] + args)}
  end
end

loop(N, [])

途中で「枝刈り」するのである。これだったら N = 100 でも計算できる。

でもこれ、N個だけ数があるとき、最大のそれが N 以下ってちょっと微妙かな。証明できるか？
　

#038 モンモール問題

問題：
6人でプレゼント交換するとき、6人とも自分のプレゼントをもらわない組み合わせは全部で何通りあるか求めよ。

コード。

N = 6
co = 0
[*0...N].permutation do |presents|
  catch(:jump) do
    presents.each_index {|i| throw(:jump) if presents[i] == i}
    co += 1
  end
end
puts co    #=>265

プログラミングで解くと特にむずかしくもないが、紙と鉛筆で解くのはかなりむずかしい。上のリンク先も参照されたい。

---

ここからは
「コマ大数学科」に挑む
このサイトから問題を拝借いたします（ありがとうございます！）。でもこれ「Yahoo!ジオシティーズ」のホームページなのですが、サービス終了で消えちゃうのでしょうか。もったいないなあ。。。
　

2007年10月3日放送　第3問

問題：
直径ＡＢの円とＡの地点に点Ｐがある。直径（線分）ＡＢが円に沿って等速で一回転する間に点ＰもＡからＢへ等速で移動する。このときの点Ｐの軌跡を書きなさい。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0710.html

お絵かきですね。これは自作の Gem 'oekaki' を使ってアニメーションしてみましょう。

黄色い点が点A、緑の点が点P です。

コード。

require 'oekaki'

class Vector
  def scrn() [150 + self[0], 150 - self[1]] end
end

R = 130         #円の半径
Steps = 200.0   #全ステップ数
agl_step = 2 * PI / Steps
rad_step = R * 2 / Steps

pa = ->(n) {Vector[cos(agl_step * n), sin(agl_step * n)] * R}
pb = ->(n) {Vector[cos(PI + agl_step * n), sin(PI + agl_step * n)] * R}
pp = ->(n) {
  a, b = pa.(n), pb.(n)
  a + (b - a) / (2 * R) * rad_step * n
}

Oekaki.app do
  white  = color(0xffff, 0xffff, 0xffff)
  yellow = color(0xffff, 0xffff, 0)
  green  = color(0, 0x8000, 0)
  n = 0
  
  draw do
    clear(color(0xffff, 0xe709, 0xd65c))
    circle(false, 150, 150, R, white)
  end
  
  id = timer(50) do
    circle(true, *pa.(n).scrn, 3, yellow)
    circle(true, *pp.(n).scrn, 3,  green)
    n += 1
    timer_stop(id) if n > Steps
    true
  end
end

関数 pa.(n), pb.(n), pp.(n) はそれぞれ n ステップ目の点A, B, P の位置を返します。
　
Gem 'cairo' を使って GIFアニメにしてみました。こちらの方がきれいかな。

画像生成のためのコードはこちら。
　

順列組み合わせ（2007/11/6）

問題：
１枚５００円のチケットを買うために、５００円しか持っていない人６人と１０００円札しか持っていない人６人、合わせて１２人が並んでいます。しかし、いまチケット売り場にはつり銭がありません。

つり銭に不足が無いようにチケットを販売できる１２人の並び方は全部で何通りあるでしょうか？
ただし、各６人の並ぶ順序は考えなくてもよい。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0711.html

コード。

N = 12
co = 0

def check(visitor500)
  stock = 0
  N.times do |i|
    if visitor500.include?(i)
      stock += 1
    else
      stock -= 1
      return false if stock < 0
    end
  end
  true
end

[*0...N].combination(6) do |vst|
  co += 1 if check(vst)
end
puts co    #=>132

考え方としては、まず 12人の中から 500円しかもっていない 6人の位置を選んで vst に入れます。そして、check(vst) でその並び方でチケットが全員に売れるかチェックしています。メソッド内の変数 stock は売り場にある 500円玉の数です。
この方法はいわゆる brute-force（総当り）ですね。リンク先ではもっと上手いやり方で考えています。
　

サイコロ（2007/12/19）

問題： 図のような三角形が並んだ線の上にサイコロの出た目に従って動くことにする。三回サイコロを振ったとき中央の赤い丸に戻る確率を求めよ。

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

table = [[0, 1], [1, 0], [1, -1], [0, -1], [-1, 0], [-1, 1]]
co = 0

[*0...6].repeated_permutation(3) do |pips|
  x, y = 0, 0
  pips.each do |pip|
    x += table[pip][0]
    y += table[pip][1]
  end
  co += 1 if x.zero? and y.zero?
end
puts Rational(co, 6 ** 3)    #=>1/18

変数 table には、出たサイコロの目に対応する移動方向を定義しています。変数 pips に 3回サイコロを投げて出た目が入ります。6 ** 3 というのは、サイコロの出方の総数です。つまり、サイコロの目の 6とおりから 3つを重複を許して選ぶ順列の数です。
　

「ハノイの塔」の二重版（2007/12/28）

問題：
A, B, C の三本の棒があって、中央に穴の空いた大きさのちがう円盤を挿すことができます。異なる大きさの 5枚の円盤が、Aの棒に必ず下の円盤の方が大きくなるように挿してあり、まったく同じものが Cの棒にも挿さっています。
さて、ここで 1回につき 1度円盤を動かせるとして、ここでも大きい円盤は必ず小さい円盤の下になるように動かすとき、すべてを Bの棒に移すには最低何回円盤を動かさねばならないでしょうか。なお、（2枚ずつある）同じ大きさの円盤はどちらが上下でもかまいません。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0712.html

コード。

def hanoi1(n, from1, to, from2)
  if n == 1
    @procedure << "#{from1}→#{to}"
    @procedure << "#{from2}→#{to}"
  else
    hanoi2(n - 1, from1, to, from2)
    @procedure << "#{from1}→#{to}"
    hanoi(n - 1, from2, from1, to)
    @procedure << "#{from2}→#{to}"
    hanoi(n - 1, from1, to, from2)
  end
end

def hanoi2(n, from, via, to)
  if n == 1
    @procedure << "#{from}→#{to}"
  else
    hanoi1(n - 1, from, via, to)
    @procedure << "#{from}→#{to}"
    hanoi(n - 1, via, to, from)
  end
end

def hanoi(n, from, to, via)
  if n == 1
    @procedure << "#{from}→#{to}"
    @procedure << "#{from}→#{to}"
  else
    hanoi(n - 1, from, via, to)
    hanoi(1, from, to, via)
    hanoi(n - 1, via, to, from)
  end
end

@procedure = []
hanoi1(5, :A, :B, :C)
puts @procedure.size    #=>96

これはかなり複雑です。元記事を参照してみて下さい。
　

虫食い算（2008/3/5）

問題： 右の図の四角の中に０～９の数字を一つずつ入れて計算式が成り立つようにする。このとき、ある数字だけがこの四角に入らない。その数字を答えよ。

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

def number(ar)
  result = 0
  ar.reverse.each_with_index {|n, i| result += n * 10 ** i}
  result
end

a = [*0..9]
pool = []
a.permutation(9) do |d|
  next if d[0].zero? or d[4].zero? or d[7].zero?
  n1 = number(d[0..3])
  n2 = number(d[4..6])
  n3 = number(d[7..8])
  pool += a - d if n1 + n2 + n3 == 2008
end
puts pool.uniq    #=>8

工夫のないコードですね。時間も（自分の環境で）6.5秒くらいかかっています。もっといいやり方を考えるべきですね。というか、いいやり方を考えるとそのまま解けてしまうのだが（笑）。
なお、上の虫食い算に適合する解は 468とおりもあります。それらがすべて 8 を欠いているというのはおもしろいですね。

すこし改良してみた。

def number(ar)
  result = 0
  ar.each_with_index {|n, i| result += n * 10 ** i}
  result
end

a = [*0..9]
pool = []
a.permutation(9) do |d|
  next if d[6].zero? or d[8].zero?
  next unless d[3] == 1 or d[3] == 2
  next unless (d[0] + d[4] + d[7]) % 10 == 8    #高速化
  n1 = number(d[0..3])
  n2 = number(d[4..6])
  n3 = number(d[7..8])
  pool += a - d if n1 + n2 + n3 == 2008
end
puts pool.uniq    #=>8

変更点は三つありますが、わかるかな。これでおおよそ 1.3秒ほどに縮まりました。
　

フーリエ（2008/3/19）

問題： 右の図の一番下の四角に１～９の異なる数字を一つずつ入れて 隣り合う２つの数字の和を上の四角に書き込んで、一番上の四角の和が１００になる場合、一番下の四角の和の最小値を求めなさい。

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

def upper_rows(line)
  if line.size == 1
    line[0] == 100
  else
    upper_rows( line.each_cons(2).map {|a| a[0] + a[1]} )
  end
end

puts [*1..9].permutation(5).map {|l| upper_rows(l) ? l.inject(&:+) : nil}.compact.min
#=>24

何だか我ながら再帰＋ Ruby らしいコードになりすぎていて、ちょっとわかりにくいくらいですね。これはよいコードなのでしょうか。短いことは短いですけれども。ただ、やっていることは単純で、ふつうの brute-force です。

それにしても、Ruby の Enumerator, Enumerable はすごいな…。よくできている。関数型っぽい。
　

ペル方程式（2008/6/12）

問題：
同じ大きさの正方形の形に並んでいる兵士の軍団が６０あります。
ここに王様１人が加わり、1つの大きな正方形に並べなおすことができるとき、王様を含めた全体の人数は何人か？

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0806.html

コード。

answer = 0
1.step do |i|
  answer = i * i * 60 + 1
  n = Math.sqrt(answer)
  break if (n - n.to_i).zero?
end
puts answer    #=>961

プログラミングで解くと簡単になってしまう問題。しかし、1.0 のような Float を整数と判断してくれる組み込みメソッドはないようだな。
よく考えてみたら、i が自然数のとき、必ず Math.sqrt(i * i) == i が成り立たないと上のコードは成立しないな。どうなのだろう。

というわけで簡単に調べてみた。以下のコードを実行する。i = 1 から順に調べていって、成り立たない i が出てくれば終了する。

1.step do |i|
  if Math.sqrt(i * i) == i
    print "\e[1Gtrue: i = #{i}"
  else
    puts "\e[1Gfalse: i = #{i}"
    exit
  end
end

とりあえず i = 100590651（約1億）まで調べてみて成り立つことがわかった。まあ少なくともこのあたりまでの数なら、使って大丈夫なことがわかった。
　

自然数（2008/8/7）

問題：
いくつかの連続した自然数の和が１０００になりました。
このときの連続した自然数を求めなさい。

http://www.geocities.jp/tfujisaki2006/sugaku/komadai0808.html

さて、この問題は少し考えてみた。高校数学でやるとおり、j から始めて n 個だけ続く自然数の和を考えて
　　
である。これより
　　
だから、n は 2 以上の自然数なので 2 ≦ n ≦ 44 とわかる。上の式を j について解くと
　　
が自然数になればよい。まあ、もうこれならプログラミングでやらなくとも解けますよね。いちおうコード。

(2..44).each do |n|
  j = 1000.0 / n + (1 - n) / 2.0
  k = j.to_i
  printf("%3d ~ %3d\n", k, k + n - 1) if j > 0 and (j - k).zero?
end

結果。

198 ~ 202
 55 ~  70
 28 ~  52

となる。でも、これもおっかなびっくりの浮動小数点演算なのだよね。答えはいちおう正しいけれど、確信がもてない。

brute-force の整数の演算でやれば確実であるので、やってみる。n の範囲が定まっているので、j の範囲を定めることができて 2 ≦ j ≦ 499 である（理由は省略）。なので、こんなコードが書ける。

(2..44).each do |n|
  (2..499).each do |j|
    printf("%3d ~ %3d\n", j, j + n - 1) if n * (n + 2 * j - 1) == 2000
  end
end

先ほどと同じ答えが出る。これは確実な答えであり、また時間も充分短い（自分の環境で 0.1秒未満）。

よく考えてみたら、Rational を使えば最初のコードで厳密に解けますね。

(2..44).each do |n|
  j = Rational(1000, n) + Rational(1 - n, 2)
  k = j.to_i
  printf("%3d ~ %3d\n", k, k + n - 1) if j > 0 and (j - k).zero?
end

魔法陣（2008/8/21）

	１０		８
９		７
	１５		１

問題：
四角に１から１６までの数字を一つずつ入れ、縦・横・対角線の４つの数字の和が等しくなるようにしなさい。またこの魔方陣の特徴をできるだけ挙げよ。 http://www.geocities.jp/tfujisaki2006/sugaku/komadai0808.html

コード。

numbers = [2, 3, 4, 5, 6, 11, 12, 13, 14, 16]    #残っている数字
table = [nil, nil, nil, nil, nil, 10, nil, 8, 9, nil, 7, nil, nil, 15, nil, 1]    #魔法陣

def check(table, idx)
  x, y = idx % 4, idx / 4
  sum_x = sum_y = sum_l = 0
  4.times do |i|
    sum_x = sum_x + table[y * 4 + i] rescue nil
    sum_y = sum_y + table[i * 4 + x] rescue nil
    sum_l = sum_l + table[(3 - i) * 4 + i] rescue nil
  end
  return false if sum_x and sum_x != @sum
  return false if sum_y and sum_y != @sum
  return false if sum_l and sum_l != @sum
  true
end

def doit(nums, table)
  if nums.empty?
    p table.each_slice(4).to_a
  else
    nums.each do |n|
      idx = table.find_index(nil)
      table[idx] = n
      doit(nums - [n], table) if check(table, idx)
      table[idx] = nil
    end
  end
end

numbers.each do |i|
  table[0] = i
  @sum = (0..3).map {|j| table[j * 4 + j]}.inject(&:+)
  doit(numbers - [i], table)
end

結果。2とおりあります。

[[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]
[[16, 5, 2, 11], [3, 10, 13, 8], [9, 4, 7, 14], [6, 15, 12, 1]]

バックトラック法で求めているのですが、かなり面倒なコードになってしまいました。もっとすっきり書けないか。

考え方としては、まず左上隅のマスを埋めて、対角線の和（変数 @sum）を求めます。あとは、まだ使っていない数字（配列 nums に入っている）を魔法陣にひとつ入れて、check() メソッドを呼んでその場所にその数字を置いてよいか調べ、true が返れば更にマスを埋めていきます。それの繰り返しで、使っていない数字がなくなれば完成であり、魔法陣を出力してさらに他の解を探します。
　

祝！１００回 花の東大生数学祭り 第１問（2008/8/28）

問題：
図のＡからＲまでの道で各点を１回ずつ通る道を見つけなさい。

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

table = {:A=>[:B, :C, :E, :K], :B=>[:A, :D, :F], :C=>[:A, :E, :I, :J, :Q],
 :D=>[:B, :H], :E=>[:A, :C, :I, :H], :F=>[:B, :G, :K], :G=>[:H, :N, :L, :F, :O],
 :H=>[:E, :I, :N, :G, :D], :I=>[:C, :E, :J, :N, :H], :J=>[:C, :I, :N],
 :K=>[:A, :F, :O, :R], :L=>[:G, :M, :R], :M=>[:L, :Q], :N=>[:I, :J, :H, :G, :Q],
 :O=>[:K, :G, :P], :P=>[:O, :R], :Q=>[:C, :N, :M, :R]}

solve = ->(route) {
  now = route[-1]
  if now == :R
    p route if route.size == 18
  else
    table[now].each do |nxt|
      solve.(route + [nxt]) unless route.include?(nxt)
    end
  end
}
solve.([:A])

結果。

[:A, :B, :D, :H, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :B, :D, :H, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :B, :D, :H, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :B, :D, :H, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :B, :D, :H, :I, :E, :C, :J, :N, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :B, :D, :H, :N, :J, :I, :E, :C, :Q, :M, :L, :G, :F, :K, :O, :P, :R]
[:A, :C, :E, :I, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :C, :Q, :M, :L, :G, :N, :J, :I, :E, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :C, :Q, :M, :L, :G, :N, :J, :I, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :I, :J, :C, :Q, :M, :L, :G, :N, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :H, :D, :B, :F, :K, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :E, :C, :I, :J, :N, :Q, :M, :L, :G, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :E, :C, :J, :I, :N, :Q, :M, :L, :G, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :E, :I, :C, :J, :N, :Q, :M, :L, :G, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :E, :I, :N, :J, :C, :Q, :M, :L, :G, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :I, :E, :C, :J, :N, :Q, :M, :L, :G, :O, :P, :R]
[:A, :K, :F, :B, :D, :H, :N, :J, :I, :E, :C, :Q, :M, :L, :G, :O, :P, :R]

答えは一とおりではなかったようですね。単純なバックトラック法で求めています。

続きもどうぞ。
marginalia.hatenablog.com

linuxBean のインストール

　
linuxBean は日本で開発されているディストリビューションでしたが、いまは開発が止まっているようです。しかし（開発者とは別の）奇特な方が Ubuntu 16.04 対応版を配布しておられるので、いまでも一応使うことができます。ダウンロードは以下からできます。
http://simosnet.com/livecd/linuxbean/
最新版は linuxbean-16.04-20180131.iso のようなので、これをダウンロードしました。

インストールは他の Debian 系のディストリビューションとほとんど同じです。ただし、「ファイルのコピーが完全に終わるまでは、最後の [続ける] のボタンを押すな」というようなメッセージがでます。どういうことなのかこれだけではよくわかりませんが、タイムゾーンの設定のあとにユーザー名などを登録する画面があって、そこの [続ける] のボタンのことのようです。自分は最初ふつうにこのボタンを押したところ、インストールがクラッシュしました。なので、もう一度やり直してその画面に来たときは、デバイスへのアクセスが完全に終了するまでは [続ける] を押さずにしてやってみたところ、うまくインストールされました。ここはちょっとわかりにくいので注意です。

インストールが終了して再起動したら、まずはネット接続します。これは他の Ubuntu 系の設定と同じで、Wi-Fi のパスワードを入れるだけです。
事前に追加インストールするソフトなどを訊いてくるので、選択して実行します。自分は日本語入力は fcitx-mozc、ブラウザは chromium を追加インストールしました。その他は適当に選択します。終了後はログアウト→ログイン。
日本語入力を fcitx-mozc に設定します。
ああそうだ、もちろん
$ sudo apt update
$ sudo apt upgrade
は忘れずに。

ホームフォルダを英語化します。
$ env LANGUAGE=C LC_MESSAGES=C xdg-user-dirs-gtk-update

Ruby をインストールする。
Linux Mint に rbenv で Ruby を入れる - Camera Obscura

システムモニターをインストール。
$ sudo apt-get install gnome-system-monitor

Haskell 覚え書き

• 等しくない 3 /= 5

• 内包表記

ghci> [x * y | x <- [2,5,10], y <- [8, 10, 11], x * y > 50]
[55,80,100,110]

• asパターン

firstLetter :: String -> String
firstLetter "" = "Empty String."
firstLetter all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]

• let 式

ghci> let (a, b, c) = (1, 2, 3); d = 4 in (a + b + c) * d
24

• ラムダ式

ghci> map (\x -> x + 3) [1,6,3,2]
[4,9,6,5]