コンソールでライフゲーム(Ruby)

Ruby の Gem でコンソールをウィンドウのように使える 'curses' というのがあります。これを使ってみたくて、ライフゲームを書いてみました。Linux Mint 18.2, Ruby 2.3.3 で確認しています。(追記:Window 8.1, Ruby 2.2.2 [i386-mingw32] でも確認しました。)
 

 
Gem のインストールは $ gem install curses で OK です。


Gem 'curses' の使い方は下のリンク先でほぼ充分でした。

 

lifegame_console.rb

require 'curses'

class LifeGame
  class Field
    def initialize(width, height)
      @width, @height = width, height
      @window = Curses::Window.new(height, width, 0, 0)
      @window.timeout = 0    #キー入力をノンブロッキングにする
    end
    
    def generate(n)
      @field = Array.new(@height + 2) {Array.new(@width + 2, 0)}
      n.times {@field[rand(@height) + 1][rand(@width) + 1] = 1}
    end
    
    def show
      @window.clear
      @height.times do |h|
        @width.times do |w|
          if @field[h + 1][w + 1] == 1
            @window.attrset(Curses.color_pair(1))
            @window.attron(Curses::A_BOLD)
            @window.setpos(h, w)
            @window.addstr("*")
          end
        end
      end
      @window.refresh
    end
    
    def next
      tmp = Array.new(@height + 2) {Array.new(@width + 2, 0)}
      @height.times do |h|
        @width.times do |w|
          n = @field[h + 1][w] + @field[h + 1][w + 2] +
                @field[h][w + 1] + @field[h][w] + @field[h][w + 2] +
                @field[h + 2][w + 1] + @field[h + 2][w] + @field[h + 2][w + 2]
          if @field[h + 1][w + 1].zero?
            tmp[h + 1][w + 1] = 1 if n == 3
          else
            tmp[h + 1][w + 1] = 1 if n == 2 or n == 3
          end
        end
      end
      @field = tmp
    end
    
    def key_in
      key = @window.getch
      return false if key == " "
      if key == "e"
        Curses.close_screen
        exit
      end
      true
    end
  end
  
  def initialize(width, height)
    Curses.init_screen
    Curses.cbreak
    Curses.noecho
    Curses.start_color
    Curses.init_pair(1, Curses::COLOR_GREEN, Curses::COLOR_BLACK)
    Curses.curs_set(0)    #カーソルを表示しない
    @f = Field.new(width, height)
  end
  
  def main
    loop do
      @f.generate(180)
      while @f.key_in
        @f.show
        @f.next
        sleep(0.5)
      end
    end
  end
end

LifeGame.new(60, 20).main

スペースキーであたらしいライフゲームを始めます。終了は [e] または [Ctrl] + [C] で行って下さい。

以前に表示を GTK+ で行うライフゲームを書いています。

2枚のカードの間には?(Ruby)

前回のエントリの問題を教えられたサイトに、さらに次のような問題がありました。

1から7の数字を書いたカードが2枚ずつ計14枚ある。そしてこれを1列に並べ,2枚の1の間にはカードが1枚,2枚の2の間にはカードが2枚はさまれていて,同様に,3の間には3枚,4の間には4枚,5の間には5枚,6の間には6枚,7の間には7枚のカードがはさまれるように14枚のカードを並べて下さい。

http://www.ic-net.or.jp/home/takaken/pz/index2.html

 
これ、単純な問題なのだけれど、どうしてもわかりませんでした。で、答えを見てみたのですが、ちょっと感動しましたね。再帰を使ってこんなにシンプルに解けるのですか。元の回答は C言語で書かれていますが、Ruby に移植してみました。これは Ruby としてはめずらしく、C言語の方が単純ですね。

table = Array.new(14, 0)

card = lambda do |n|
  if n > 7
    p table
    exit
  else
    i, j = 0, n + 1
    while j < 14
      if table[i].zero? and table[j].zero?
        table[i] = table[j] = n
        card.call(n + 1)
        table[i] = table[j] = 0
      end
      i += 1
      j += 1
    end
  end
end

card.call(1)

教えられてみれば、じつによくできた解法ですね。
 
正解(のひとつ)はこれです。

[1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4]

ちなみに異なる解は全部で 52 個あります。

2つのバケツ問題(Ruby)

反復深化/アルゴリズム講座
おもしろそうな問題を見つけました。

8リットルと5リットルのふたつのバケツを使って1リットルの水を最短手順で川からくみあげて下さい。

http://www.ic-net.or.jp/home/takaken/pz/index3.html

 
Ruby で解いてみました。それぞれのバケツには、空にするかいっぱいに水を入れるか、もう一方に移し替えるかの 3通りの場合があります。すべての手順に 0~5 の番号を振ります。

8リットル: 空(0), 入れる(1), 8→5に移す(2)
5リットル: 空(3), 入れる(4), 5→8に移す(5)

 
最短手順なので、幅優先探索を使います。
bucket_problem.rb

def move(mass, f, t)
  if (a = mass - t) >= f
    t += f
    f = 0
  else
    t = mass
    f -= a
  end
  [f, t]
end


procedures = [[[1], 0, 0], [[4], 0, 0]]
loop do
  pr = procedures.shift
  
  case pr[0][-1]
  when 1 then pr[1] = 8
  when 4 then pr[2] = 5
  when 0 then pr[1] = 0
  when 3 then pr[2] = 0
  when 2
    pr[1], pr[2] = move(5, pr[1], pr[2])
  when 5
    pr[2], pr[1] = move(8, pr[2], pr[1])
  end
  
  if pr[1] == 1 or pr[2] == 1
    p pr[0]
    exit
  end
  
  6.times do |i|
    a = pr[0].dup
    next if a[-1] == i    #高速化用
    a << i
    procedures.push([a, pr[1], pr[2]])
  end
end

実行してみます。

$ time ruby bucket_problem.rb
[1, 2, 3, 2, 1, 2, 3, 2]

real	0m0.384s
user	0m0.364s
sys	0m0.016s

 
上の手順は翻訳するとこうなります。

手順 8L 5L
8Lに入れる 8 0
8→5 3 5
5Lを空 3 0
8→5 0 3
8Lに入れる 8 3
8→5 6 5
5Lを空 6 0
8→5 1 5

これで確かに 8L のバケツに 1L 残りました!
 
ちなみに、意味ある最長手順は [4, 5, 4, 5, 0, 5, 4, 5, 4, 5, 0, 5, 4, 5] です。また、8リットルと5リットルのバケツで4リットルを作るのにも挑戦してみて下さい。


汎用性のあるバージョンに書き換えてみました。ソースはこちらです。バケツの大きさと計る値を指定することができます。可能なすべての場合を出力し、無意味な解はできるだけ除きますが、一部冗長な解も出力してしまいますので注意して下さい。

飛車と角の利き(Ruby)

問題:

飛車と角を将棋盤(9×9)の上にひとつづつおきます。このとき、飛車か角によって(相手の)駒が取られる位置を、飛車と角の「利き」ということにします。
飛車の「利き」の上に角があるとき、その先の飛車の「利き」は(角にさえぎられて)ありません。角の場合も同様です。
飛車と角は重なりません。
飛車と角が採りうる位置をすべて採るとき、「利き」の総和は何個になるでしょうか。

 
Ruby で解いてみます。総当り法で、特に何のくふうもしていません。

class Field
  def clear
    a = Array.new(11, 1)
    @field = Array.new(9) {[1] + [0] * 9 + [1]}
    @field.unshift(a)
    @field.push(a)
  end
  
  def set(x, y, koma)
    @field[y][x] = koma
  end
  
  def get(x, y)
    @field[y][x]
  end
  
  def count
    counter = 0
    move_koma do |x, y|
      counter += 1 if get(x, y) == 4
    end
    counter
  end
end

def move_koma
  1.upto(9) do |y|
    1.upto(9) {|x| yield(x, y)}
  end
end

def set_kiki(x, y, dir, f)
  loop do
    x += dir[0]
    y += dir[1]
    a = f.get(x, y)
    return if a == 1 or a == 2 or a == 3
    f.set(x, y, 4)
  end
end


f = Field.new
counter = 0
move_koma do |xh, yh|
  move_koma do |xk, yk|
    next if xh == xk and yh == yk
    f.clear
    f.set(xh, yh, 2)
    f.set(xk, yk, 3)
    
    #飛車
    [[-1,  0], [1,  0], [0, -1], [0, 1]].each {|dir| set_kiki(xh, yh, dir, f)}
    #角
    [[-1, -1], [-1, 1], [1, -1], [1, 1]].each {|dir| set_kiki(xk, yk, dir, f)}
    
    counter += f.count
  end
end
puts counter    #=>149424

わざわざ(一部)オブジェクト指向プログラミングで解く必要はないのですが、この方が(自分に)見やすいかと思ってこうしました。

将棋盤(@field)の周囲には番兵を置いてあります。0 が空白、1 が番兵、2 が飛車、3 が角、4 が「利き」です。
 

 
 
よく似た問題に、チェスの「エイト・クイーン問題」というのがあります。過去記事で扱っているので、よろしければ御覧下さい。

Linux Mint(Ubuntu)で Radiko を録音する

インターネットでラジオが聴ける「Radiko」というサービスはよく知られていますが、その放送を録音するには色いろなやり方があるようです。さて、自分の使っている Linux ではどうやればできるのかなと調べてみたら、意外と簡単でした。Linux Mint 18.2 で確認しています。(後記:Ubuntu 17.10 でも確認しました。)


既にネット上にたくさん情報が上がっていますが、rec_radiko.sh というシェルスクリプトを使うのがもっとも簡単なようです。これは Gist に上がっているので、コピペするかダウンロードしておきます(作者に感謝です)。

それから、必要なライブラリを入れます。すべて apt-get で入ります。

$ sudo apt-get install rtmpdump swftools libxml2-utils ffmpeg libavcodec-extra57

自分の場合は rtmpdump と swftools 以外は既に入っていました。libavcodec は適宜最新バージョンを入れて下さい。

シェルスクリプトに実行権を与えます。

$ chmod 755 ./rec_radiko.sh

 
あとはシェルスクリプトを実行するだけです。Radiko への参加放送局は例えばここにあります。自分の住んでいるところは岐阜県なので、岐阜放送(GBS)をとりあえず 1分間録音してみます。

$ ./rec_radiko.sh GBS 1
RTMPDump v2.4
(c) 2010 Andrej Stepanchuk, Howard Chu, The Flvstreamer Team; license: GPL
WARNING: No application or playpath in URL!
Connecting ...
WARNING: Trying different position for server digest!
INFO: Connected...
ERROR: rtmp server sent error
ERROR: rtmp server requested close

あれれ、エラーが出ますね。よくわからないので、ぐぐってみました。すると、ここに、「東京に住んでいるのに北海道のラジオ局名が出る」というのがあったので、ここへ飛んでエリア判定をしてみました。すると、なんと「静岡県」に!(笑) どうもそういうことだったようですね。なので、とりあえず Radiko にはエリア判定の修正要求を出しておいて、ここでは静岡のラジオ局(SBS)を 1分間録音してみます。

$ ./rec_radiko.sh SBS 1
RTMPDump v2.4
(c) 2010 Andrej Stepanchuk, Howard Chu, The Flvstreamer Team; license: GPL
WARNING: No application or playpath in URL!
Connecting ...
WARNING: Trying different position for server digest!
INFO: Connected...
Starting Live Stream
For duration: 60.000 sec
INFO: Metadata:
365.962 kB / 60.03 sec
Download complete

OK ですね!


なお、これは現在放送中の番組しか録音できませんので、これで予約録音がしたいなら、PC を動かしたままにしておいて cron とか、別途録音用のサーバを立てるなどすることになります(Raspberry Pi を使っている人が目につきます)。これは別問題なのでここでは書きません。

また、エリア外の放送も録音したいという人がおられるかも知れませんが、さて Radiko 会員になってこの方法でできるのかは知りません。公開VPNサーバを使ったりすればできるようですが、そこまですることはないでしょう。というか、これはおすすめできないですね。


サブの PC をつけっぱなしにしておいて、cron で予約録音してみます。11月23日AM3:00~4:00 の静岡放送走れ!歌謡曲」を予約録音します。
~/.crontab

0 3 23 11 4 /home/***/Documents/rec_radiko.sh SBS 60

cron の登録。

$ crontab ~/.crontab

さて。どうでしょうか。(追記:うまくいきました。)

Ruby で png 画像を自力生成(その2)

前回 png 画像を生成してみた続き。
 
こんなの。

コードはこんな感じ(画像データの生成部分のみ)。前回エントリを参照。

width, height = 400, 400

raw_data = []
height.times do |h|
  ob = []
  width.times {|w| ob << [0, 0, ((w - width / 2) ** 2 + (h - height / 2) ** 2) % 256]}
  raw_data << ob
end

 
またこんなのも。

双曲線を使う。

  width.times {|w| ob << [0, ((w - width / 2) ** 2 - (h - height / 2) ** 2) % 256, 0]}

Ruby で png 画像を自力生成できるらしいですよ

このところ脳みそが腐って全然プログラミングとかできないのだが、Ruby 愛はちっとも減じていないので、他人のブログをパクってエントリを書きます。「パクって」はいい言葉じゃないですね。とにかく唐突に「png ruby」でぐぐってみましたら、Ruby コミッタのまめさんのブログがヒットしました。
だいぶ昔の記事ですね。ほほう、Rubypng 画像を生成するかあ。これはおもしろそうですね。png の生成は結構むずかしいらしいのですが、Ruby だとそんなにむずかしくないと。とりあえず、まめさんのコードをコピペ、実行してみます。赤色のグラデーションをもった画像を生成します。もともとは Ruby 1.9 用らしいですが、Ruby 2.3.3 でまったく修正なしに走りました。(Linux Mint 18.2)

コード(コピペほぼそのまま)。
gradation.rb

require "zlib"

width, height = 100, 20
depth, color_type = 8, 2

# グラデーションのベタデータ
line = (0...width).map {|x| [x * 255 / width, 0, 0] }
raw_data = [line] * height

# チャンクのバイト列生成関数
def chunk(type, data)
  [data.bytesize, type, data, Zlib.crc32(type + data)].pack("NA4A*N")
end

# ファイルシグニチャ
print "\x89PNG\r\n\x1a\n"

# ヘッダ
print chunk("IHDR", [width, height, depth, color_type, 0, 0, 0].pack("NNCCCCC"))

# 画像データ
img_data = raw_data.map {|line| ([0] + line.flatten).pack("C*") }.join
print chunk("IDAT", Zlib::Deflate.deflate(img_data))

# 終端
print chunk("IEND", "")

"zlib" ライブラリは標準添付ライブラリなので、Gem としてインストールする必要はありません。実行は

$ ruby gradation.rb > gradation.png

みたいな感じ。こうして生成された png 画像はこれだ!
 

 
小さいけれど、ちゃんと赤色のグラデーションとして生成されていますね。うーん、いいなあこれ。


ふつうのブログならこれを解説するわけだが、面倒なのでしない。というか、まめさんの説明がすごくわかりやすいので、自分のは不要なのである。といって、じつは自分はまめさんの記事を読んで密かにぐぐったので、それだけ書いておこう。

まず、標準添付ライブラリの "zlib" が話題になっているが、これって何か? これはここを見るといいですね。つまり zlib とは、データを圧縮するアルゴリズムであるそうだ。Linux では gzip コマンドというので使われているらしいが、しかしよく Windows で使われている zip ってやつとは関係ないらしい。zlib は「可逆圧縮」、つまり解凍すると完全にもとのデータが復元できるということで、じつは png 画像ファイルの圧縮もこれであり、そう、png は劣化しないのですね。これは皆んな知っているだろう。ちなみに jpg は劣化するのですね。というわけで、png 画像を作るには、メインの画像データは zlib で圧縮すればよいというわけである。そのためのライブラリなのだった。

あとひとつ。まめさんの「臼NG はみんな見たことあるはず」がわからなかった。「臼NG」である。自分は見たことがない。これはわからないということでぐぐったら、ここがヒットした。ははあ、ファイルシグニチャ*1の「\x89P」が Shift_JIS で「臼」なわけね。納得。ただし、これを LinuxRuby で実感してみようと思ったが、

require 'kconv'

puts "\x89PNG".tosjis.encode("UTF-8")     #=>臼NG

しかやり方がわからなかった。"kconv" を使うのは Ruby 2.3 っぽくないのだけれど*2。どうやるといいのかな。(つまりは、バイナリ→Shift_JISUTF-8 の変換を文字列ですること。これ、すごく時間をかけて調べたのだけれどわからなかった。もちろんマジックコメントを使えば簡単なのだが。)


自分も上のコードを少しだけ変えて、完全にランダムな色で打点した png 画像を作ってみた。コードは変更部分のみ。
random_color_png.rb

width, height = 100, 100

# グラデーションのベタデータ
raw_data = []
height.times do
  raw_data << width.times.with_object([]) do |i, ob|
    ob << [rand(256), rand(256), rand(256)]
  end
end

画像。
 


こんな具合ですね。

*1:png ファイルの先頭部分で、これは png ファイルですよという宣言。

*2:どうも最近の Ruby だと、エンコーディングをわざとまちがえて(笑)文字化けさせるということが想定されていないらしい。文字列が自分のエンコーディングの情報をもっています。で、バイナリから例えば UTF-8 へという無意味な変換ができないらしい。そういうことをやると Encoding::InvalidByteSequenceError が出ます。