格子点の列挙(Ruby)

格子点の列挙 - みずぴー日記
ここの問題で遊んでみました。

問題を再掲しておきます。

二次元平面上の格子点(X,Y座標がともに整数の点)を、原点から近い順に列挙してください。

同じ距離の点はどういう順番でも構いませんが、可能であればX軸に一番近い第一象限の点から原点を中心として反時計回りの順に列挙してください。 列挙の方法は、1行に一つの点の、X,Y座標を出力することとします。

http://d.hatena.ne.jp/mzp/20071006/lattice

 
結果の例(括弧をつけた出力にしました)。

( 3, -2)
(-6,  1)
(-5,  4)
( 4, -5)
( 5, -7)
(-9, -2)
(-2, -9)
( 7,  7)
(-8,  8)
( 8, -9)

 
コード。

class Complex
  include Comparable
  
  def <=>(a)
    f = ->(θ) {(θ < 0) ? 2 * Math::PI + θ : θ}
    
    l1, l2 = abs2, a.abs2
    θ1, θ2 = f.(angle), f.(a.angle)
    
    if    l1 > l2 then  1
    elsif l1 < l2 then -1
    elsif θ1 > θ2 then  1
    elsif θ1 < θ2 then -1
    else 0
    end
  end
  
  def to_s
    sprintf "(% 2d, % 2d)", real, imaginary
  end
end

ar = 10.times.map {Complex(rand(-9..9), rand(-9..9))}
puts ar.sort

いわゆる「宇宙船演算子」(<=>というやつ)を Complex クラスに定義して解いてみました。並べ替えはふつうに Array#sort でやっています。

ちょっとトリッキーですかね。

モジュール内の特定のメソッドだけ include する(Ruby)

Ruby のモジュールは include でメソッドを Mix-in できますが、定義したすべてのメソッドが include されてしまって、特定のものだけ include するわけにはいきません。そのくらいできそうなので何か簡単なやり方があるのかもしれません。とにかく、考えてみました。

まず、こんなメソッドを Object クラスと Module クラスに付け加えます。
add_methods.rb

class Object
  def add_methods(module_to_include, *method_names)
    method_names.each do |m|
      pr = module_to_include.method(m).to_proc
      define_method(m, &pr)
    end
  end
end

class Module
  def register_all_methods
    instance_methods.each do |m|
      module_function m
    end
  end
end

 
で、メソッドを定義するモジュールを書きます。そのとき、(必要な)すべてのメソッドを module_function で指定するか、上の register_all_methods をモジュールの最後に書きます。(すべて module_function で指定する場合は、register_all_methods メソッドを書く必要はありません。いちいち指定するのが面倒なので作りました。)

module A
  def run_f
    f
  end
  
  def run_g
    g
  end
  
  def f
    puts "f called"
  end
  
  def g
    puts "g called"
  end
  register_all_methods
end

 
Mix-in するモジュールとメソッドを add_methods() で指定します。すると指定されたメソッドだけ使えるようになります。

add_methods A, :run_f, :run_g

run_f    #=>f called
run_g    #=>g called
f        #=>`<main>': undefined local variable or method `f' for main:Object (NameError)

確かに指定されたメソッドだけ使えるようになっています。

クラスの中だとこんな風になります。

class B
  add_methods A, :run_f, :run_g
  def go
    run_f
    run_g
    f
  end
end

B.new.go

 
こんなことも可能。

c1 = Object.new
c2 = Object.new

class << c1
  add_methods A, :run_f
end

c1.run_f    #=>f called
c2.run_f    #=>`<main>': undefined method `run_f' for #<Object:***> (NoMethodError)

 
なお、これは上の例で例えばメソッド f を絶対に外から呼び出せないようにしたわけではなく、A.f などとすれば呼び出せてしまいます(まあしかし、モジュールが名前空間として使いやすくなったりとか、利点もあるのではないかと思います)。けれども、少なくとも間違えて f を呼び出す可能性はだいぶ低くなると思います。

そうそう、注意点ですが、これらと include を併用すると予期しづらい誤動作の原因になる可能性があります。まあ、そんなことをする意味はありませんが。
 

Gem化

Gem 'kaki-utils' に同梱しておきました(ver. 0.0.10)。使い方は

require 'kaki/utils/add_methods'

で Object#add_methods と Module#register_all_methods が使えます。

いわゆる「コンウェイのライフゲーム」をエディタ付きで実装してみた(Ruby)

20180415235457

これまで

などで「ライフゲーム」を実装してきましたが、フィールド・エディタが欲しくなったので作ってみました。Gtk2 を使っています。


Gem化してあるので、インストールして実行できます。Bundler かまたは $ gem install kaki-lifegame でインストールできます。実行はたんに

$ kaki-lifegame

か、Bundler を使っている人は

$ bundle exec kaki-lifegame

GUI が立ち上がります。Gem 'gtk2' が必要です。Linux Mint 18.3, Ruby 2.3.3 で確認しました。Windows 8.1, Ruby 2.2.2p95 (2015-04-13 revision 50295) [i386-mingw32] でも確認しましたが、格子の表示がおかしくなることがあるようです*1

使い方。

  • マウスのクリックでセルを ON/OFF できます。
  • マウスの左ボタンを押しながらドラッグすると連続的にセルを描くことができます。また、右ボタンを押しながらドラッグすると、連続的にセルを消すことができます。


  • 開始
    • 実行します。
  • 停止
    • 停止します。以下の機能はすべて停止中にのみ有効です。
  • 1ステップ進める
    • ステップ実行です。
  • ばらまく
    • 適当にセルを散布します。
  • 格子
    • 格子の表示を切り替えます。
  • 緑色/橙色
    • セルの色です。
  • 全クリア
    • すべてのセルを消します。
  • 一時保存
    • 一時的にフィールドを内部に保存します。
  • 復帰
    • 内部に保存したデータをフィールドに戻します。
  • ファイルに保存
    • フィールドをファイルに保存します。
  • ファイルの読み込み
    • ファイルに保存したフィールドのデータを読み込んで表示します。
  • 終了
    • 終了します。

 
実行動画を作ってみました。

 
ソースコードは以下です。
エディタ付きライフゲーム(Ruby) · GitHub
これだけでも実行できます。Gem のコードとはほんの一部だけちがいますが、本質的には同じです。

コーディングにはほぼ2日間ほどかかりました。Ruby/Gtk について調べるのに手間を食いました。Ruby ってのは書きやすくてホントすばらしい言語ですね。Rubyオブジェクト指向プログラミングの書きやすさは快感です。


※参考
ライフゲーム - 人工知能に関する断創録
 

追記(4/11)

機能をさらに追加しました。

  • 1ステップ戻る
    • ひとつ前のフィールドに戻ります。戻れるのは過去20ステップまでです。
  • ウェイト
    • ウェイトする時間を変更します。値が小さいほど更新が速くなります。なお、これは停止中でなくとも有効なボタンです。

Gem もアップデートしてバージョン0.0.3 になりました。Gem の更新は $ gem update kaki-lifegame、また Bundler を使っている人は $ bundle update kaki-lifegame です。
 

追記(4/15)

バージョン0.0.4 でデフォルトの画面を小さくし、画面の大小ボタンを付けました。

*1:バージョン0.0.2 で解消されました。Windows でもきちんと動作します。

和暦 (明治 大正 昭和 平成) と西暦の変換をおこなう(Ruby)

簡単な遊びのプログラムが作りたかったのでやってみました。Date クラスは使っていません。

こんな感じです。コマンドライン引数を指定します。

#西暦から和暦
$ ruby gengou.rb 2018
平成30年
$ ruby gengou.rb 1945
昭和20年
$ ruby gengou.rb 1912
明治45年
大正元年

#和暦から西暦
$ ruby gengou.rb m1
西暦1868年
$ ruby gengou.rb h30
西暦2018

明治はm、大正はt、昭和はs、平成はh で指定します。

コード。
gengou.rb

years_table = [[1868, 1912], [1912, 1926], [1926, 1989], [1989, 2019]]
period_names = %W(明治 大正 昭和 平成)
period_initials = %W(m t s h)

#西暦から和暦へ
year_to_period = ->(year) {
  year1 = 0
  years_table.each_with_index do |y, i|
    if y[0] <= year and year <= y[1]
      year1 = year - y[0] + 1
      year1 = "" if year1 == 1
      puts period_names[i] + "#{year1}"
    end
  end
  puts "その西暦はサポートしていません" if year1 == 0
}

#和暦から西暦へ
period_to_year = ->(period, year) {
  period.downcase!
  period_initials.each_with_index do |p_ini, i|
    if period == p_ini
      year1 = years_table[i][0] + year - 1
      st = if year1 > years_table[i][1]
        "#{period_names[i]}#{year}年はありません"
      else
        "西暦#{year1}"
      end
      puts st
    end
  end
}

if (m = /^(\d+)$/.match(ARGV[0]))
  year_to_period.(m[1].to_i)
elsif (m = /^([a-zA-Z])(\d+)$/.match(ARGV[0]))
  period_to_year.(m[1], m[2].to_i)
else
  puts "許されない入力です"
end

データを増やせばすべての元号に対応させることも可能です。ただ、頭文字の重複があるでしょうから、漢字で指定するようにしないといけませんね。

遊びですけれど、こういうのを書くには Ruby 最強じゃないですか? 書いていてチョー気持ちいいです。
かんたんな遊びのプログラミングいいですね。もっと題材を探したいです。


こんなのもどうぞ。
obelisk.hatenablog.com

Ruby でイケてないコードを→「いいね」→「スゲーいいね」にリファクタリング?

qiita.com
自分が「Ruby + リファクタリング」でぐぐると上のサイトがいちばん最初にヒットする。内容は題名どおり。添削者はすごい上級者プログラマらしい。添削された人には気の毒なのだけれど、勝手に引用してみる。まず「イケてない」コード。(ごめんなさい)

class OrdersReport
  def initialize(orders, start_date, end_date)
    @orders = orders
    @start_date = start_date
    @end_date = end_date
  end

  def total_sales_within_date_range
    orders_within_range = []
    @orders.each do |order|
      if order.placed_at >= @start_date && order.placed_at <= @end_date
        orders_within_range << order
      end
    end

    sum = 0
    orders_within_range.each do |order|
      sum += order.amount
    end
    sum
  end
end

class Order < OpenStruct
end

うーん、確かに読みにくいかなあ。でもわかるけれど。
RSpec テストコード。

require 'spec_helper'

describe OrdersReport do
  describe '#total_sales_within_date_range' do
    it 'returns total sales in range' do
      order_within_range1 = Order.new(amount:  5, placed_at: Date.new(2016, 10, 10))
      order_within_range2 = Order.new(amount: 10, placed_at: Date.new(2016, 10, 15))
      order_out_of_range  = Order.new(amount:  6, placed_at: Date.new(2016,  1,  1))
      orders = [order_within_range1, order_within_range2, order_out_of_range]

      start_date = Date.new(2016, 10,  1)
      end_date   = Date.new(2016, 10, 31)

      expect(OrdersReport.new(orders, start_date, end_date)
         .total_sales_within_date_range).to eq(15)
    end
  end
end

 
リファクタリング後。「スゲーいいね」のコード。

class OrdersReport
  def initialize(orders, date_range)
    @orders = orders
    @date_range = date_range
  end

  def total_sales_within_date_range
    total_sales(orders_within_range)
  end

  private

  def total_sales(orders)
    orders.map(&:amount).inject(0, :+)
  end

  def orders_within_range
    @orders.select { |order| order.placed_between?(@date_range) }
  end
end

class DateRange < Struct.new(:start_date, :end_date)
  def include?(date)
    (start_date..end_date).cover? date
  end
end

class Order < OpenStruct
  def placed_between?(date_range)
    date_range.include?(placed_at)
  end
end

添削者の言葉。

もう最初のコードと比べると可読性、単一責任、再利用性、疎結合、と全ての要素が満たされて格段に良くなっているのが分かる。ほとんどのメソッド内の行数が1行。(2行なのはinitializeのみ)気持ちいいぐらいに読みやすい。

https://qiita.com/jabba/items/e169adb2f33532c119cf

 
へー、プロの上級者はこんな風にリファクタリングするのだな。でも、自分みたいな初心者素人には謎すぎる。凝りすぎてキモい感じ。「気持ちいいぐらいに読みやすい」ともあまり思えない。まったく自分はセンスがないのだな。「可読性、単一責任、再利用性、疎結合」。確かに、ですな。

初心者素人ならこんな風に書くかも。マネしないように。

class OrdersReport
  def initialize(orders, start_date, end_date)
    @orders = orders
    @start_date = start_date
    @end_date   = end_date
  end

  def total_sales_within_date_range
    @orders.select {|od| @start_date <= od.placed_at and od.placed_at <= @end_date}
       .map(&:amount).inject(:+)
  end
end

class Order < OpenStruct
end

実質一行。あと、レシーバーが @orders で中身がわかるのに、ブロック変数まで order にするのは長くて自分には見にくい感じ。od で充分に思える。あとは select したら足すだけじゃね?

もちろん DateRange クラスを作ってもいいのだけれど、それは DRY 的に必要になってからでいいと思う。元をシンプルにしておけば改変もラク(select を置き換えればよいのが明白)。「不必要に将来の拡張性を考えない。それが必要になることはたぶんない。」「コードが短くなったら great ! といおう。」

自分に「スゲーいいね」のコードが見にくく感じるのは、置き換えるべき select が一般的な Enumerable なので、(ここでモンキーパッチはダメなので)そのためにいろいろいじらなくてはならないからである。そのために新たにクラスをひとつ追加し、メソッドも大幅に増やしている。これほどのことをするくらいなら、select のままではいけないのだろうか? プロってのはむずかしいな。


プログラミングにおいてデータ構造は決定的なファクタのひとつだが、この「スゲーいいね」では DateRange クラスというデータ構造を思いついたためにこうなった。結局、この決定がよいかどうかということなのではないか。


※追記(4/2)


植山類さんのこれで充分(そしてそちらの方がたぶんずっと速い)。じつは本文記事は植山さんの「教え」(?)みたいなのが頭にあったのですが、既に本人がお書きになっていました(^^; 自分の場合は Ruby の便利メソッドを使ってメソッドチェーンにしただけで、考え方は植山さんのコードとまったく同じ。植山さんのなら Ruby 以外でもだいたい似たように書けると思う。あと、もしこれだけというのなら OrdersReport クラスがいらないというのもそのとおりですね。

Go言語と Ruby で 8 queens 問題

Go で「8 queens 問題」を解いてみました。実際は n queens が解けます。

すべての解を出力します。num = 8 の場合、解は 92通りあります。こんな感じ。

------------------
n = 1
@.......
....@...
.......@
.....@..
..@.....
......@.
.@......
...@....
------------------
n = 2
@.......
.....@..
.......@
..@.....
......@.
...@....
.@......
....@...
------------------
(以下略)

 
コードはこんな感じです。
eight_queen.go

package main
import "fmt"
import "strings"

const num = 8
var count = 0

//出力
func putout(field []int) {
    count++
    fmt.Println("------------------")
    fmt.Printf("n = %d\n", count)
    st := strings.Repeat(".", num - 1)
    for _, queen := range field {
        fmt.Println(st[0: queen] + "@" + st[0: num - queen - 1])
    }
}

//ここまでの field で女王の置けるマス(空白)を探す(1なら置けない)
func get_space(field []int) [num]int {
    result := [num]int{}
    l := len(field)
    for i, queen := range field {
        result[queen] = 1
        dst := l - i
        if a := queen - dst; a >= 0  {result[a] = 1}
        if a := queen + dst; a < num {result[a] = 1}
    }
    return result
}

//メインの深さ優先探索
func solve(field []int) {
    if len(field) == num {
        putout(field)
    } else {
        for i, space := range get_space(field) {
            if space == 0 { solve(append(field, i)) }
        }
    }
}

func main () {
    solve([]int{})
}

実質的に solve() と get_space() の 2つのメソッドだけでシンプルに書けました。putout() は出力用です。たぶん、これはたいていの言語にそのまま移植できると思います。
 
結構うまく書けたのではないでしょうか。再帰的に深さ優先探索で解いています。

実行時間は num = 8 の場合ほぼ一瞬(0.01秒くらい)です。num = 15 の場合、最終的な解の個数だけ出力するように改変して(コード)実行すると

$ time ./eight_queen
2279184

real	0m17.135s
user	0m17.332s
sys	0m0.040s

となります。num = 17 で

$ time ./eight_queen
95815104

real	13m38.920s
user	13m42.884s
sys	0m1.228s

くらいが限界でしょうか。

Go で書くのは好きですね。コードの見た目がいいです。

※参考
これまでの試み。今回は以前とはだいぶちがったロジックで求めています。
エイト・クイーン(8 queen)問題を Ruby で解いてみる - Camera Obscura
ふたたび Ruby で 8 queen(関数型プログラミングっぽく) - Camera Obscura
Swift で 8queen 問題を解く - Camera Obscura
 

ちなみに Ruby だとこんな風に移植できますか。
eight_queen_another.rb

#ここまでの field で女王の置けるマス(空白)を探す(falseなら置けない)
def get_space(field)
  result = Array.new(N, true)
  l = field.size
  field.each_with_index do |queen, i|
    result[queen] = false
    dst = l - i
    result[queen - dst] = false if queen - dst >= 0
    result[queen + dst] = false if queen + dst <  N
  end
  result
end

#メインの深さ優先探索および出力
def solve(field)
  if field.size == N
    @count += 1
    puts "------------------"
    puts "n = #{@count}"
    field.each {|queen| puts ("." * (N - 1)).insert(queen, "@")}
  else
    get_space(field).each_with_index {|space, i| solve(field + [i]) if space}
  end
end

N = 8
@count = 0
solve([])

Ruby でカレンダーを出力してみた

特定の年と月を指定して、カレンダーを出力するプログラムを書いてみました。

標準添付ライブラリの Date クラスを使ってはつまらないので、自力で計算しました。
calender.rb

month_table = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

#うるう年か?
is_uruu = ->(year) {
  (year % 4 == 0 && year % 100 != 0) || year % 400 == 0
}

#西暦1年1月1日から何日目か(すべてグレゴリオ暦で計算)
days = ->(year, month, day) {
  uruu = ->(y) {
    y / 4 - y / 100 + y / 400
  }
  month_days = ->{
    month_table[0, month].inject(&:+) + (is_uruu.(year) && month > 2 ? 1 : 0)
  }
  y1 = year - 1
  y1 * 365 + uruu.(y1) + month_days.() + day - 1
}

#曜日の計算
week_number = ->(year, month, day) {
  (days.(year, month, day) + 1) % 7
}

#カレンダーの出力
Calender = ->(year, month) {
  gen = ->(from, to) {
    (from..to).map {|i| sprintf("%2d  ", i)}.join
  }
  putout = ->(i) {
    last = month_table[month]
    last += 1 if is_uruu.(year) && month == 2
    while i + 6 <= last
      puts gen.(i, i + 6)
      i += 7
    end
    st = gen.(i, last)
    puts st unless st.empty?
  }
  puts "#{year}/#{month}".center(27)
  puts "sun mon tue wed thu fri sat"
  w = week_number.(year, month, 1)
  puts "    " * w + gen.(1, 7 - w)
  putout.(8 - w)
}

実行例。

$ pry
[1] pry(main)> require "./calender"
=> true
[2] pry(main)> Calender[2018, 3]
          2018/3           
sun mon tue wed thu fri sat
                 1   2   3  
 4   5   6   7   8   9  10  
11  12  13  14  15  16  17  
18  19  20  21  22  23  24  
25  26  27  28  29  30  31  
=> nil
[3] pry(main)> Calender[1989, 1]
          1989/1           
sun mon tue wed thu fri sat
 1   2   3   4   5   6   7  
 8   9  10  11  12  13  14  
15  16  17  18  19  20  21  
22  23  24  25  26  27  28  
29  30  31  
=> nil
[4] pry(main)> Calender[1968, 7]
          1968/7           
sun mon tue wed thu fri sat
     1   2   3   4   5   6  
 7   8   9  10  11  12  13  
14  15  16  17  18  19  20  
21  22  23  24  25  26  27  
28  29  30  31  
=> nil
[5] pry(main)> Calender[2018, 2]
          2018/2           
sun mon tue wed thu fri sat
                 1   2   3  
 4   5   6   7   8   9  10  
11  12  13  14  15  16  17  
18  19  20  21  22  23  24  
25  26  27  28  
=> nil

 
なお、days.() 関数は西暦1年1月1日から何日目かを計算しますが、すべてグレゴリオ暦で計算しています。Ruby の Date クラスでは、それ以前のユリウス暦の期間を補正しているらしいので、こことはちがった値を出力します。なので厳密にいえば、このカレンダーはグレゴリオ暦に切り替わって以降の分しか正しい出力ではないことになります。なお、未来のカレンダーとしては正しいものを出力する筈です。

week_number.(year, month, day) はその日の曜日を出力します。日曜日は 0、月曜日は 1, ..土曜日は 6 という具合です。ソースの最後に

if __FILE__ == $0
  week_table = %W(日 月 火 水 木 金 土)
  puts week_table[week_number.(*ARGV.map(&:to_i))] + "曜日"
end

を加えると、

$ ruby calender.rb 2018 3 27
火曜日

という風にその日の曜日を出力することができます。


こんなのもどうぞ。
obelisk.hatenablog.com