Windows フリーゲーム「Almagest」を Linux で遊ぶ

20181210015655

ゲーム HP。
Almagest -Overture-
以下よりダウンロードする。
「Almagest -Overture-」ターン制SFシミュレーションゲーム - 窓の杜
 
lzh ファイルは Linux ではそのままでは解答できないので、ここでは lhasa を入れてみる。

$ sudo apt install lhasa

これで解凍できる。ver 3.04 の差分フォルダもダウンロードした場合は、手作業で差分ファイルを差し替える(参照)。

実行はふつうに

$ wine Almagest-1.exe

でよい。特にインストールとかはされない。
 
Linux Mint 19, wine-3.0 で動作確認。
 
※参考
Almagest -Overture- - Wikipedia
Almagestとは (アルマゲストとは) [単語記事] - ニコニコ大百科
Almagest Wiki - Front Page

はがきデザインキット2019 を Ubuntu 18.10 にインストール

20181209212302

以前に郵便局の「はがきデザインキット」を Ubuntu にインストールする記事(参照)を書いたのですが、その手順が古くなったので再挑戦です。

まずは Wine が使えるか調べます。「Wine」とは LinuxWindows のソフトを動かすためのアプリです。

$ wine --version

Command 'wine' not found, but can be installed with:

sudo apt install wine            
sudo apt install wine-development

というわけで入っていないので、表示されたとおりにやります。

$ sudo apt update
$ sudo apt install wine-stable

あとで必要なのでやっておきます。

$ sudo apt install samba
$ sudo apt install winbind

Wine がインストールされているか確認します。

$ wine --version
wine-3.18 (Ubuntu 3.18-2)

このままだと文字化けします。なので

$ sudo apt install winetricks
$ winetricks allfonts

を実行します(参照)。終了後、

$ winecfg

で文字化けがなければ OK です。これで Wine のインストールが完了しました。


つぎに Abode Air をインストールします。ここから「手順1」は「Windows」、「手順2」は「Adobe AIR 31.0 for Win64」を選択し、「今すぐダウンロード」をクリックします。念のため

$ sudo apt install mono-complete

をしておいてから、ダウンロードした exe ファイルを

$ wine AdobeAIRInstaller.exe

で実行。インストーラーがうまく働いていないように見えますが、フリーズ後に [Ctrl] + [C] をして(うまくいかなければプロセスを終了させる)上記コマンドを再実行すると、インストール済の表示が出れば OK です。


最後にここから「はがきデザインキット」をダウンロード。zip ファイルを解凍して design_kit.air を右クリック、[他のアプリケーションで開く]→[Adobe AIR Application Installer] を選択して実行すると、インストールされる筈です。お疲れ様でした!

AOL(問題集)4

AIZU ONLINE JUDGE: Programming Challenge
 

0031 Weight

def measure(object, weight, result = [])
  return result.join(" ") if weight.zero?
  result.unshift(weight) if (object / weight).nonzero?
  measure(object % weight, weight / 2, result)
end

$<.readlines.map(&:to_i).each {|ob| puts measure(ob, 512)}

 

0032 Plastic Board

rectangle = lozenge = 0

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |a, b, c|
  rectangle += 1 if a * a + b * b == c * c
  lozenge   += 1 if a == b
end
puts rectangle, lozenge

 

0033 Ball

def try(balls, b ,c)
  return 1 if balls.empty?
  nxt = balls.first
  bl = balls.drop(1)
  if nxt > b and nxt > c
    try(bl, nxt, c) + try(bl, b, nxt)
  elsif nxt > b
    try(bl, nxt, c)
  elsif nxt > c
    try(bl, b, nxt)
  else
    0
  end
end

$<.gets.to_i.times do
  balls = $<.gets.split.map(&:to_i)
  puts try(balls.drop(1), balls.first, 0).nonzero? ? "YES" : "NO"
end

読み込みに readlines を使ったらエラーが出る。gets を使ったコードに替えたら正解になった。非本質的なところで延々と悩まされた。
 

0034 Railway Lines

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |given|
  ls = given.first(10)
  v1, v2 = given.last(2)
  s = Rational(v1 * ls.sum, v1 + v2)
  l = 0
  ls.each_with_index do |ln, i|
    next if s > (l += ln)
    puts i + 1
    break
  end
end

 

0035 Is it Convex?

$<.readlines.map {|l| l.split(",").map(&:to_r)}.each do |given|
  f = (given + given.first(4)).each_slice(2).each_cons(3).map do |a, b, c|
    (c[0] - a[0]) * (b[1] - a[1]) - (c[1] - a[1]) * (b[0] - a[0]) > 0
  end
  puts((f.all? or f.none?) ? "YES" : "NO")
end

 

0036 A Figure on Surface

L = 8
table = [["11", "11"], ["1", "1", "1", "1"], ["1111"], ["01", "11", "10"],
         ["110", "011"], ["10", "11", "01"], ["011", "110"]]
table.map! {|pt| [pt.size, l = pt.first.length, pt.join("0" * (L - l))]}

$<.readlines.chunk {|l| !!l.match(/^\d/) || nil}
  .map {|a| a.last.map(&:chomp).join}.each do |field|
  table.each_with_index do |ary, k|
    y, n, pt = ary
    (L + 1 - y).times do |i|
      (L + 1 - n).times do |j|
        puts "ABCDEFG"[k] if field[i * L + j, pt.length] == pt
      end
    end
  end
end

 

0037 Path on a Grid

given = $<.readlines.map {|l| l.chomp.chars.map(&:to_i)}
yoko = 0.step(8, 2).map {|i| given[i]}
tate = 1.step(8, 2).map {|i| given[i]}.transpose
dirs = "LRUD"
go = nil
route = ""
f = false

get_yoko = ->(x, y, dir) {
  if dir == 0
    if tate[x][y] == 1
      go.(x, y, 3)
    elsif x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    elsif y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    else
     go.(x, y, 1)
    end
  else
    if y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    elsif x <= 3 and yoko[y][x] == 1
      go.(x, y, 1)
    elsif tate[x][y] == 1
      go.(x, y, 3)
    else
      go.(x, y, 0)
    end
  end
}

get_tate = ->(x, y, dir) {
  if dir == 2
    if x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    elsif y > 0 and tate[x][y - 1] == 1
      go.(x, y, 2)
    elsif yoko[y][x] == 1
      go.(x, y, 1)
    else
      go.(x, y, 3)
    end
  else
    if x <= 3 and yoko[y][x] == 1
      go.(x, y, 1)
    elsif y <= 3 and tate[x][y] == 1
      go.(x, y, 3)
    elsif x > 0 and yoko[y][x - 1] == 1
      go.(x, y, 0)
    else
      go.(x, y, 2)
    end
  end
}

go = ->(x, y, dir) {
  return if x.zero? and y.zero? and f
  f = true
  route += dirs[dir]
  if dir <= 1
    get_yoko.(x + dir * 2 - 1, y, dir)
  else
    get_tate.(x, y + dir * 2 - 5, dir)
  end
}

go.(0, 0, 1)
puts route

何だか全然よくないコード。もっと考えたい。
 

0038 Poker Hand

def same_numbers(ary, result = [])
  return result.sort if ary.empty?
  a = ary.first
  co = ary.count(a)
  result << co if co > 1
  same_numbers(ary - [a], result)
end

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |hand|
  puts case same_numbers(hand)
  when [4]    then "four card"
  when [2, 3] then "full house"
  when [3]    then "three card"
  when [2, 2] then "two pair"
  when [2]    then "one pair"
  else
    hand.sort!
    if hand.sum == (hand.first + 2) * 5 or hand == [1, 10, 11, 12, 13]
      "straight"
    else
      "null"
    end
  end
end

 

0039 Roman Figure

table = {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, nil => 0}

count = ->(roman, number = 0) {
  return number if roman.empty?
  a, b = table[roman.first], table[roman[1]]
  number += if a >= b
    r = roman.drop(1)
    a
  else
    r = roman.drop(2)
    b - a
  end
  count.(r, number)
}

$<.readlines.map(&:chomp).each {|roman| puts count.(roman.chars.map(&:to_sym))}

暗黙の Proc化(Ruby)

[1] pry(main)> (1..4).map {|i| i + 3}
=> [4, 5, 6, 7]

これと

[2] pry(main)> (1..4).map(&->(i) {i + 3})
=> [4, 5, 6, 7]

は同じ。引数での & は Proc をブロックに変換するから。(正確にはさらにそれを暗黙に .call() している。)


では、

[3] pry(main)> (1..4).map(&3)
TypeError: wrong argument type Integer (expected Proc)

はもちろんエラーになるよね。でも、この &3 のとき、3 は Proc でないので、暗黙に 3 を to_proc しようとしている。それを示してみよう。

Integer クラスにこうモンキーパッチしてみる。

[4] pry(main)> class Integer
[4] pry(main)*   def to_proc  
[4] pry(main)*     ->(i){i + self}    
[4] pry(main)*   end    
[4] pry(main)* end  
=> :to_proc

Integer を Proc化するのである。すると、

[5] pry(main)> (1..4).map(&3)
=> [4, 5, 6, 7]

おお、先ほどと同じだ。つまり、ここでは暗黙に 3 を to_proc しているのである。うーん、すごいですなあ。

つまり、オブジェクトに to_proc を定義しておくと、このような遊び(?)ができるわけです。可読性がなにですが。

AOL(問題集)3

AIZU ONLINE JUDGE: Programming Challenge
 

0021 Parallelism

$<.readlines.drop(1).map {|a| a.split.map(&:to_r)}.each do |x1, y1, x2, y2, x3, y3, x4, y4|
  puts((x2 - x1) * (y4 - y3) == (x4 - x3) * (y2 - y1) ? "YES" : "NO")
end

単純な問題なのに、自分の解き方ではどうしてもダメだったので、他の人のを参考に。to_f じゃなくて to_r がミソなのかなあ。
 

0022 Maximum Sum Sequence

while (n = $<.gets.to_i).nonzero?
  given = (1..n).map {$<.gets.to_i}
  max = -Float::INFINITY
  n.times do |i|
    sum = 0
    (i...n).each do |j|
      sum += given[j]
      max = sum if sum > max
    end
  end
  puts max
end

 

0023 Circles Intersection

$<.readlines.drop(1).map {|a| a.split.map(&:to_f)}.each do |xa, ya, ra, xb, yb, rb|
  l = Math.sqrt((xb - xa) ** 2 + (yb - ya) ** 2)
  r = ra - rb
  puts case
       when l < r  then 2
       when l < -r then -2
       when l > ra + rb then 0
       else 1
       end
end

 

0024 Physical Experiments

$<.readlines.map(&:to_r).each do |v|
  puts((1 + 1/98r * v ** 2).ceil)
end

 

0025 Hit and Blow

$<.readlines.map {|a| a.split.map(&:to_i)}.each_slice(2) do |a, b|
  a1, b1 = [], []
  hit = 0
  a.each_index do |i|
    if a[i] == b[i]
      hit += 1
    else
      a1 << a[i]
      b1 << b[i]
    end
  end
  blow = a1.size - (a1 - b1).size
  puts "#{hit} #{blow}"
end

 

0026 Dropping Ink

L = 10
table = [a = [[0, 0], [0, -1], [1, 0], [0, 1], [-1, 0]],
         b = a + [[1, -1], [1, 1], [-1, 1], [-1, -1]],
         b + [[0, -2], [2, 0], [0, 2], [-2, 0]]]
field = Array.new(L) {Array.new(L, 0)}

set = ->(x, y) {
  return if x < 0 or x >= L or y < 0 or y >= L
  field[y][x] += 1
}

$<.readlines.map {|l| l.split(",").map(&:to_i)}.each do |x, y, s|
  table[s - 1].each {|dx, dy| set.(x + dx, y + dy)}
end
f = field.flatten
puts f.count(0)
puts f.max

 

0027 What day is today?

require 'date'
table = %w(Sunday Monday Tuesday Wednesday Thursday Friday Saturday)

loop do
  month, day = $<.gets.split.map(&:to_i)
  break if month.zero?
  puts table[Date.new(2004, month, day).wday]
end

 

0028 Mode Value

field = Array.new(101, 0)
$<.readlines.map(&:to_i).each {|n| field[n] += 1}
m = field.max
field.each_with_index {|n, i| puts i if m == n}

 

0029 English Sentence

counts = Hash.new(0)
max = [0, nil]

$<.gets.split.map(&:downcase).each do |word|
  counts[word] += 1
  l = word.length
  max = [l, word] if l > max.first
end
h = counts.invert
puts "#{h[h.keys.max]} #{max.last}"

 

0030 Sum of Integers

loop do
  n, s = $<.gets.split.map(&:to_i)
  break if n.zero? and s.zero?
  puts [*0..9].combination(n).map {|numbers| numbers.sum == s}.count(true)
end

RMagick で LoadError

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

/home/tomoki/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rmagick-2.16.0/lib/rmagick_internal.rb:12:in `require': libMagickCore-6.Q16.so.3: cannot open shared object file: No such file or directory - /home/tomoki/.rbenv/versions/2.3.4/lib/ruby/gems/2.3.0/gems/rmagick-2.16.0/lib/RMagick2.so (LoadError)

 
ここにあるように

$ gem pristine rmagick

で直った。

AOL(問題集)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

AOL(問題集)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)

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

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)

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

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)

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

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)


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

右のカレンダーは2010年3月のカレンダー

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

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でない)が相異なる3桁の正の整数nがある。
nの各数字を並べてできる、6つの数の最大公約数をgとする。
gとして考えられる最大の値を求めよ。

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) 素数素数の中で数字を逆に書いても素数になる数のこと。
たとえば「13と31」「37と73」などがエマープ素数である。
「emirp」は「prime:素数」を逆にしたもの。 ただし、逆に書いても同じになる素数(101など)は含まれない。
問題:3ケタのエマープ素数を3つ答えなさい。

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]]

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

チャンパーノウン数(2011/2/9)

問題:
すべての自然数を順番につなげて書いていくとき、1万個目に書かれる 数字はいくつでしょう。
1,2,3,…と順番に書いていく。9までは一桁の数であるが、次の 10から2桁になるため、10個目の数は「1」、11個目の数は「0」 になる。

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)


問題:
AくんとBくんが図のア~ケ9つのマスに1,3,4~10の数字を交互に一つずつ入れていく。

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

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


コード。これは 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)

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

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]

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

コマ大番外編…平成教育委員会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)

問題:
1から1億までの数字を書いたときに現れる数字の全ての和を求めなさい。

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)

問題:
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)

問題:
たろうくんは1から順に1,2,3…とある数までを黒板に書きました。
じろうくんはその中の1個の数を消してしまいました。すると残りの数の平均は590/17になりました。
じろうくんの消した数はいくつですか?

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)

問題: 約数の個数が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)

問題:
3辺の長さが整数の直角三角形があります。3辺のうち2つの辺の長さが素数であり、3辺の長さの和が132のとき、3辺のそれぞれの長さを求めなさい。

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

簡単ですね。
 

アインシュタインに挑戦

問題:
右の図の四角の中に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)

問題:
ある線分の2等分点、3等分点、4等分点と順に新しい等分点にだけ印をつけていきます。15等分点に印を付けたとき、新たに増える印の数を答えなさい。

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)

問題:
1辺の長さ1の正方形のタイル800枚を隙間なく並べて縦25、横32の長方形を作ります。
この長方形の対角線1本が通過するタイルの枚数を求めなさい。

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