「既約分数クイズ」を解く（Ruby, C言語）

ここのところで結城先生の「既約分数クイズ」のことを知りました。結城先生らしい「お話」仕立てですので、是非参照して頂きたいですが、簡単にいうと

問題：正の整数Nが与えられているとき、 以下の条件を満たす既約分数p/qを「すべて」求めるアルゴリズムを示してください。 条件は：

• p, qは整数(pは0以上で、qは1以上N以下).
• gcd(p, q) = 1 (pとqの最大公約数は1).
• 0 <= p/q <= 1.

http://www.hyuki.com/dig/frac.html

というものです。

Ruby で解いてみたのですが、これだとあっさり解けすぎますよね。結城先生はもっと考えてごらんということだと思います。

N = 10
p (1..N).flat_map {|q| (0..q).map {|p| Rational(p, q)}}.uniq

結果。

[(0/1), (1/1), (1/2), (1/3), (2/3), (1/4), (3/4), (1/5), (2/5), (3/5), (4/5),
 (1/6), (5/6), (1/7), (2/7), (3/7), (4/7), (5/7), (6/7), (1/8), (3/8), (5/8),
 (7/8), (1/9), (2/9), (4/9), (5/9), (7/9), (8/9), (1/10), (3/10), (7/10), (9/10)]

まだあまり慣れていない C言語で書いてみましょう。
irreducible_fraction_problem.c

#include <stdio.h>
#include <stdlib.h>

int n = 10;

int gcd(int p, int q) {
    if (!q) return p;
    return gcd(q, p % q);
}

int main () {
    int *a;
    int co = 2;
    a = malloc(sizeof(int) * n * n);
    
    a[0] = 0;
    a[1] = 1;
    
    for (int q = 1; q <= n; q++) {
        for(int p = 1; p <= q; p++) {
            if (gcd(p, q) != 1) continue;
            a[co++] = p;
            a[co++] = q;
        }
    }
    
    for (int i = 0; i <= co - 2; i += 2) {
        printf("%d/%d ", a[i], a[i + 1]);
    }
    
    printf("\n");
    free(a);
    
    return 0;
}

結果。

0/1 1/1 1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5
1/6 5/6 1/7 2/7 3/7 4/7 5/7 6/7 1/8 3/8 5/8
7/8 1/9 2/9 4/9 5/9 7/9 8/9 1/10 3/10 7/10 9/10

　
こんなのでどうですかね。なお gcd(int p, int q) は「ユークリッドの互除法」を使って p と q の最大公約数を求めます。

なお、結城先生の「解答編」もあります。こちらもどうぞ。

フォードの円、GTK+ で落書き10（Ruby）

いわゆる「フォードの円」というものを描いてみました。これについてはここで知ったものです。ありがとうございます。

Ruby で描きました。描画には自作の Gem 'oekaki' を使っています。


oekaki_sample10.rb

require 'oekaki'

Width, Height = 500, 500

Oekaki.app width: Width, height: Height do
  draw do
    color(0, 0, 0)
    rectangle(true, 0, 0, Width, Height)
    
    color(0, 65535, 0)
    r = Width / 2
    circle(false, 0, r, r)
    circle(false, 2 * r, r, r)
    
    (1..9).to_a.combination(2) do |p, q|
      x = p / q.to_f
      y = 1 / (2 * q ** 2).to_f
      wx, wy = Width * x, Height * y
      circle(false, wx, Height - wy, wy)
    end
  end
end

　
Gem 'oekaki' についてはこちら。
oekaki | RubyGems.org | your community gem host
GTK+でお絵かきしてみた（Ruby） - Camera Obscura

　
なお、Gem 'oekaki' のバージョンを 0.0.11 に上げました。

Tool#ciecle と Tool#timer_stop の二つのメソッドを追加しました。circle(fill, x, y, r, color = nil) は円を arc メソッドよりも簡単に書けるようにしただけです。(x, y) は中心の座標、r は半径です。timer_stop(id) は Gtk.timeout_remove(id) のエイリアスに過ぎません。

基数ソート（Ruby）

基数ソートは固定長の文字列のソートなどに使うアルゴリズムで、下の位（文字列の右の方）から順にソートしていって、すべての位をソートし終えたとき、全体のソートが終っているという方法です。個々のソートには高速な「計数ソート」を使うとよい（「安定的な」ソートを使わねばなりません）。

Ruby でコーディングしてみました。
radix_sort.rb

class Array
  def counting_sort
    #Integer{a1[], s, m, equal[]}, String{a2[], result[]}
    
    a1, a2 = self[0], self[1]
    s = a1.size
    m = a1.max + 1
    equal = Array.new(m, 0)
    
    s.times {|i| equal[a1[i]] += 1}
    
    equal[-1] = 0
    (m - 1).times {|i| equal[i] += equal[i - 1]}
    
    result = Array.new(s)
    s.times do |i|
      result[equal[a1[i] - 1]] = a2[i]
      equal[a1[i] - 1] += 1
    end
    result
  end
  
  def radix_sort
    #String{self[]} -> Integer{ar[]} >> [String]
    st = self
    n = st[0].length
    n.times do |i|
      ar = st.map {|x| x[n - 1 - i].bytes[0]}
      st = [ar, st].counting_sort
    end
    st
  end
end

st = []
9.times {st << ("0".."9").to_a.sample(5).join}

p st
p st.radix_sort

実行例。

$ ruby radix_sort.rb
["24685", "74186", "81935", "17042", "74395", "72506", "52381", "78359", "10372"]
["10372", "17042", "24685", "52381", "72506", "74186", "74395", "78359", "81935"]

アルゴリズムの基本

バケットソート（と計数ソート）（Ruby）

バケットソートはバケツソート、ビンソート、計数ソート（後記：計数ソートとバケットソートはちがう）などとも言います。非常に高速ですが、ソートされる対象は 0以上の整数値（またはそれに変換できるもの）であり、その最大値が大きくなるとメモリをバカ食いします。また、値に重複がない場合はここにあるように Ruby では

class Array
  def bucket_sort
    inject([]) {|mem, var| mem[var] = var; mem}.compact
  end
end

と驚異的にシンプルに書けますが、値の重複を許すとそんなに簡単ではないようです。

バケットソートについては小飼弾さんのブログ記事が啓蒙的です。

参考書の手続きを Ruby でコーディングしてみました。値が重複する場合も対応しています。

class Array
  def counting_sort
    #Integer{self[]} -> Integer{m, equal[], result}
    m = max + 1
    equal = Array.new(m, 0)
    size.times {|i| equal[self[i]] += 1}
    
    equal[-1] = 0
    (m - 1).times {|i| equal[i] += equal[i - 1]}
    
    result = Array.new(size)
    size.times do |i|
      result[equal[self[i] - 1]] = self[i]
      equal[self[i] - 1] += 1
    end
    result
  end
end

やっていることは、値の最大値 + 1 を m として、まず大きさ m の配列 equal を作り、値 a の（重複する）要素の個数を equal[a] に入れます。つまり、ソートすべき配列に 4の値が 3個あれば、equal[4] = 3 とするということです。

次に、値 a より小さいすべての要素の個数を equal[a - 1] に入れます。

最後に並べ直します。ソートすべき配列と同じ大きさの配列 result を作り、ソートすべき配列の i 番目の値 a が result[equal[a - 1]] に入ります。重複したものが重ねて入らないように equal[a - 1] をインクリメントします。これをすべての i について繰り返すと、result に答えが入っています。

バケットソート計数ソートは上を見てわかるとおり、「値の比較」というものをまったくやっていません。それが高速になる理由です。

※追記　どうやらこのソートはバケットソートではなく、計数ソートというべきのようです。日本語版 Wikipedia は記述がまちがっているようだ。計数ソートとバケットソートは同じではないらしい。計数ソートは「安定的な」ソートです。つまり重複部分で、オブジェクトなど、付随するデータの順序を変えません。

アルゴリズムの基本

　

※追記
ぐぐっていたらもっとシンプルな実装を見つけました。多少好みの書き方に直して下に記しておきます。（後記：これはバケットソートなんでしょうか、よくわかりません。）

class Array
  def bucket_sort
    m = max + 1
    equal = Array.new(m, 0)
    size.times {|i| equal[self[i]] += 1}
    
    result = []
    m.times do |i|
      equal[i].times {result << i}
    end
    result
  end
end

後半でループがネストしているのでサイズが大きくなると不利かなと思いましたが、ベンチマークしてみると、サイズが小さくても大きくてもこちらの方が若干速いようです。何といってもシンプルなので、こちらの方がいいですね。

ただひとつ気になるのは、こちらの実装だとサテライトデータ（ソートに付随するデータ）が扱えないのではないでしょうか（つまり、「安定的な」ソートではない）。最初の実装はサテライトデータを扱うことが可能です。

マージソートとクイックソートの比較（Ruby）

自分の実装で、マージソートとクイックソートのベンチマークをしてみました。
マージソートの実装はこれ、クイックソートのはこれ（いちばん下の実装）です。
　
マージソート。

クイックソート。

基本的にクイックソートの方が速いようである。

ベンチマーク。
bench_sorts.rb

require 'benchmark'

100.times do
  ar = (0..10_0000).to_a.shuffle
  Benchmark.bm 12 do |x|
    x.report("merge sort") {ar.merge_sort}
    x.report("quick sort") {ar.qsort}
  end
end

実行は $ ruby bench_sorts.rb > bench_sorts.txt。

Gnuplot でグラフ化。

require 'histogram/array'
require 'numo/gnuplot'

ar = open("bench_sorts.txt", &:readlines)
m = []
q = []
ar.each_slice(3) {|x| m << x[1]; q << x[2]}

pick_up = proc do |ar|
  ar.each_with_object([]) {|i, a| a << i.split(" ")[6].to_f}
end

mb, mf = pick_up.call(m).histogram
qb, qf = pick_up.call(q).histogram

Numo.gnuplot do
  set title: "merge sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_m.png'
  set style: [:fill, :solid, {border: -1}]
  plot mb, mf, w: :boxes, lc: {rgb: "orange"}
end

Numo.gnuplot do
  set title: "quick sort"
  set terminal: [png: {size: [400, 300]}]
  set output: 'sort_q.png'
  set style: [:fill, :solid, {border: -1}]
  plot qb, qf, w: :boxes, lc: {rgb: "orange"}
end

エイト・クイーン（8 queen）問題を Ruby で解いてみる

エイト・クイーン - Wikipedia

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

　
チェスの盤面は 8×8 であり、クイーンのコマは前後左右斜めにどれだけでも進むことができます。盤面上に 8つのクイーンを置くとき、どのクイーンも他のいずれにも取られないような配置を考えるわけです。

最初の駒は任意に与えられるものとしましょう。また、ひとつでも解が見つかれば終了することにします。考え方としては、人間がやる場合と似て、適当に一駒ずつ置いていき、失敗すればひとつ前に戻って置き直していくという方法を取ります。いわゆる「バックトラック法」というやつです。Ruby で解いてみました。下は回答のひとつです。

$ time ruby eight_queen.rb
@.......
......@.
....@...
.......@
.@......
...@....
.....@..
..@.....

real	0m0.077s
user	0m0.044s
sys	0m0.000s

eight_queen.rb

N = 8

class EightQueen
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
      @depth = 0
    end
    attr_accessor :x, :y, :parent, :depth
  end
  
  def initialize(x, y)
    @stack = [Step.new(x, y)]
  end
  
  def solve
    #Step{a, nxt}, Integer{y, board[][]}
    while (a = @stack.pop)
      y = a.y + 1
      board = get_board(a)
      N.times do |x|
        next if board[y][x] == 1
        nxt = Step.new(x, y)
        nxt.parent = a
        nxt.depth = a.depth + 1
        finish(nxt) if nxt.depth == N - 1
        @stack.push(nxt)
      end
    end
    raise "No answer."
  end
  
  def get_board(a)
    #board, d, x1, x2
    board = Array.new(N) {Array.new(N, 0)}
    begin
      N.times do |i|
        board[i][a.x] = 1
        board[i] = Array.new(N, 1) if i == a.y
        d = (i - a.y).abs
        next if d.zero?
        x1 = a.x - d
        x2 = a.x + d
        board[i][x1] = 1 if x1 >= 0
        board[i][x2] = 1 if x2 < N
      end
    end while (a = a.parent)
    board
  end
  
  def finish(a)
    bd = Array.new(N) {"." * N}
    while a
      bd[a.y][a.x] = "@"
      a = a.parent
    end
    bd.map {|x| puts x}
    exit
  end
end

EightQueen.new(rand(N), 0).solve

※追記（7/24）
コードを多少修正しました。また、すべてのパターン（92通り）も求めてみました。コードと結果は下の Gist に。実行時間は 0.1秒程度です。コードは上のものにほんの少し修正を加えただけです。
eight_queen_all.rb · GitHub
　
続編。
obelisk.hatenablog.com

与えられた迷路の最短経路を求める（Ruby）

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

さて試験問題です。
内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。

　
おもしろそうなので Ruby で解いてみました。もともとはここで知ったものです。
僕はまだまだ不勉強で A* も dijkstra も知りませんが（そのうちお勉強する予定）、ふつうに幅優先探索ですよね。

というわけでやってみました。先に出力を載せておきます。

$ time ruby solve_maze.rb
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

real	0m0.164s
user	0m0.072s
sys	0m0.012s

こんな感じで解けました。

コードは以下。上に書いたとおり、単純な幅優先探索です。もちろん幅優先探索は最短経路を与えます。
solve_maze.rb

class SolveMaze
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
    end
    attr_accessor :x, :y, :parent
    
    [:up, :down, :left, :right].each_with_index do |mt, i|
      define_method(mt) do
        a = [Step.new(x, y - 1), Step.new(x, y + 1),
             Step.new(x - 1, y), Step.new(x + 1, y)][i]
        a.parent = self
        a
      end
    end
  end
  
  def initialize
    @map = DATA.readlines
  end
  
  def get(st)
    @map[st.y][st.x]
  end
  
  def set(st, ch)
    @map[st.y][st.x] = ch
  end
  
  def go
    stack = [Step.new(1, 1)]
    
    while (a = stack.shift)
      [a.up, a.down, a.left, a.right].each do |nxt|
        case get(nxt)
        when "G" then finish(a)
        when " "
          set(nxt, "@")
          stack.push(nxt)
        end
      end
    end
  end
  
  def finish(a)
    @map.map! {|x| x.gsub(/@/, " ")}
    while a.parent
      set(a, "$")
      a = a.parent
    end
    @map.each {|x| puts x}
    exit
  end
end

SolveMaze.new.go

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

メインループは SolveMaze#go の while 文です。SolveMaze#finish は回答を出力して終了します。それぞれのステップをクラス（Step クラス）にするまでもなかったかも知れませんが、まあいいんじゃないでしょうか。

DRY原則を満たすためにちょっとだけメタプログラミングを使っている以外は、素直なコードではないかと思います。

僕などがいうまでもないのですが、幅優先探索が気になる方は、while (a = stack.shift) と stack.push(nxt) の部分に特に気をつけてコードを読んでみて下さい。ちなみに、この shift を pop に替えるだけで深さ優先探索になりますよ。これでも解は求められますが、一般に最短経路になりません。一行替えるだけでのちがい、やってみるとおもしろいと思います。

なお、Ruby コミッターの「まめめも」さんのコードはすごいです。え、こんなに短いの、という感じ。自分などはまだまだですね。

　

別解

別様に解いてみました（2018/12/12）。上の半分ほどの行数になっています。

solve_maze1.rb

Position = Struct.new(:x, :y, :parent)

field = DATA.readlines
start = Position.new
field.each_with_index {|l, i| start.x, start.y = (l.index("S") or next), i}
stack = [start]

# solve
finish = loop do
  po = stack.shift
  break po if field[po.y][po.x] == "G"
  [[1, 0], [0, -1], [-1, 0], [0, 1]].each do |dx, dy|
    nx, ny = po.x + dx, po.y + dy
    a = field[ny][nx]
    field[ny][nx] = "@" if a == " "
    stack << Position.new(nx, ny, po) if a == " " or a == "G"
  end
end

# 結果の表示
field.map! {|l| l.gsub("@", " ")}
prev = finish.parent
until prev == start
  field[prev.y][prev.x] = "$"
  prev = prev.parent
end
puts field

__END__
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************