並べ替えの繰り返し（Ruby）

アルゴリズム・パズルです。

問題。

1~9 のカードを横一列に適当に並べ替えます。そこからスタートして、左端のカードの数字の枚数だけ、左からカードを取って逆順にし、また置き直します。例えば [4, 5, 6, 7, 8, 9, 1, 2, 3] だったら [7, 6, 5, 4, 8, 9, 1, 2, 3] とします。これを繰り返すと、左端が 1 になったら終了することがわかります。
さて、終了するまでの手順がもっとも長くなる初期配置を与えなさい。

　
Ruby で解きます。
q40.rb

def try(order, co)
  8.times do |i|
    if order[i + 1] == i + 2
      tmp = order[0, i + 2].reverse + order[(i + 2)..-1]
      try(tmp, co + 1) unless tmp[0] == 1
    end
  end
  @max, @result = co, order if @max < co
end

@max = 0
[*2..9].permutation(8) {|ar| try([1] + ar, 0)}
p [@max, @result]

終了した配置から逆に求めていきます。
結果。

$ time ruby q40.rb
[30, [6, 1, 5, 9, 7, 2, 8, 3, 4]]

real	0m0.599s
user	0m0.596s
sys	0m0.000s

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

Ruby でファイル転送のコマンドを作る

ローカルネットワーク内に何台か PC があるので、Ruby でファイル転送を行うことを考えました。SSH でやってもよいのですが、一台の PC に Linux をマルチブートしているので、面倒なので Ruby でやります。セキュリティは何も考えていないので、当り前ですが絶対にインターネットに出てはいけません。というか、ローカルでも可能な限り SSH（scp コマンド）でやった方がいいと思います（参考）。

使い方はこんな感じ。受け手側（もちろんこちらを先に実行して下さい）。

$ file_transfer trans
IPアドレス: 192.168.11.6
[192.168.11.2:34098] からの接続を了承しました
spline_curve.png を受信中です...
spline_curve.png の受信が完了しました

送り手側。

$ file_transfer trans 192.168.11.6 spline_curve.png
spline_curve.png を送信中です...
spline_curve.png の送信が完了しました

　
コードはこんな感じです。基本的にここのコードを流用させて頂きました（ありがとうございます！）。
file_transfer

#!/usr/bin/env ruby
require 'socket'
require 'thor'

class FileTransfer < Thor
  desc 'trans', "Transfer a file."
  def trans(*args)
    send_file = lambda do |host, name|
      puts "#{name} を送信中です..."
      open(name, "rb") do |file|
        size = File.size(name)
        sock = TCPSocket.open(host, 7413)
        sock.puts "PUT_FILE #{name} #{size}"
        sock.write(file.read)
        sock.close
      end
      puts "#{name} の送信が完了しました"
    end
    
    receive_file = lambda do
      print "IPアドレス: "
      ip_ad = Socket.getifaddrs.select {|x| x.addr.ipv4?}
      puts ip_ad.select {|x| x.addr.ip_address.include?("192.168")}[0].addr.ip_address
      
      s0 = TCPServer.open(7413)
      loop do
        Thread.start(s0.accept) do |sock|
          puts "[#{sock.peeraddr[3]}:#{sock.peeraddr[1]}] からの接続を了承しました"
          while (m = /^PUT_FILE\s+(\S+)\s+(\d+)$/.match(sock.gets.chop))
            name, size = File.basename(m[1]), m[2]
            puts "#{name} を受信中です..."
            open("#{name}", "wb") do |file|
              file.write(sock.read(size.to_i))
            end
            puts "#{name} の受信が完了しました"
          end
          puts "[#{sock.peeraddr[3]}:#{sock.peeraddr[1]}] からの接続が拒否されました"
          sock.close
        end
      end
    end
    
    
    host, file_name = args
    
    if file_name
      send_file.call(host, file_name)
    else
      receive_file.call
    end
  end
end

FileTransfer.start

コマンド化は Gem 'thor' で行っているので、これをインストールする必要があります。そして、ファイルに実行権を与えて、/usr/local/bin などにコピーして下さい。なお、ポート番号など細かいところは適宜各自の環境に合わせて下さい。

なお、rbenv を利用して Ruby をインストールされている方は、シェバング行を

#!/home/***/.rbenv/versions/2.3.3/bin/ruby

のように変更して下さい。もちろん「***」や Ruby のバージョンの部分は適宜自分の環境に合わせて下さい。

※参考
お手軽ファイル転送 - Usipedia
Ruby 2.1.0 では Socket.getifaddrs で簡単にインターフェイスのアドレスを取れる
Ruby の Thor でコマンドを作る - Marginalia
　

※追記
このままだとバイナリファイルや（ネストした）ディレクトリが送れなかったりするので、改良版を作りました。
obelisk.hatenablog.com

7セグメントコードの反転（Ruby）

デジタル表示で 0~9 の数字を表示させることを考えます。数字はディスプレイの 7つの場所の on, off で表示することになります。このとき、二つの数字を連続して表示するとして、7つの場所の on, off の切り替わりが出来るだけ少なくなるような順番を考えます。つまりその場所で、できるだけ on なら on、off なら off のままになるようにするということです。

0~9 の数字を適当な順番ですべて一度ずつ表示させるとき、on, off の切り替え数の和の最小値を求めよという問題です。

q38.rb

pattern = [0b1111110, 0b0110000, 0b1101101, 0b1111001, 0b0110011,
           0b1011011, 0b1011111, 0b1110000, 0b1111111, 0b1111011]
@table = {}
[*0..9].combination(2) do |i, j|
  @table[[i, j]] = ("%07b" % (pattern[i] ^ pattern[j])).count("1")
end

@min = Float::INFINITY

def count(not_used, co, order)
  i = order[-1]
  not_used -= [i]
  if not_used.empty?
    @min = co
    p [order, co]
  end
  not_used.each do |j|
    pair = (i < j) ? [i, j] : [j, i]
    sum = co + @table[pair]
    next if sum >= @min
    count(not_used, sum, order + [j])
  end
end

count([*0..9], 0, [0])
puts @min

結果。

$ time ruby q38.rb
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 28]
[[0, 1, 2, 3, 4, 5, 6, 7, 9, 8], 27]
[[0, 1, 2, 3, 4, 5, 6, 8, 7, 9], 26]
[[0, 1, 2, 3, 4, 5, 6, 8, 9, 7], 23]
[[0, 1, 2, 3, 5, 6, 8, 9, 4, 7], 21]
[[0, 1, 2, 8, 6, 5, 9, 3, 7, 4], 20]
[[0, 1, 3, 2, 8, 6, 5, 9, 4, 7], 19]
[[0, 1, 4, 7, 3, 2, 8, 6, 5, 9], 18]
[[0, 1, 4, 7, 3, 9, 5, 6, 8, 2], 17]
[[0, 1, 7, 3, 2, 8, 6, 5, 9, 4], 16]
[[0, 2, 3, 5, 6, 8, 9, 4, 1, 7], 15]
[[0, 2, 8, 6, 5, 9, 3, 7, 1, 4], 14]
[[0, 8, 6, 5, 9, 4, 1, 7, 3, 2], 13]
13

real	0m0.611s
user	0m0.608s
sys	0m0.000s

最小値は 13 になります。まず、すべての組の数字の on, off の切り替え数を先に計算しておいて、@table に格納します。あとはすべての順列の場合を再帰で求めています。その際、途中で和が暫定的な最小値 @min の値に等しくなるかそれを超えた場合、それ以上の探索は無用なので打ち切って高速化します。自分の環境では 0.6秒くらいで求まりました。
　

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

Ruby のブロックはクロージャである

Ruby の Proc（あるいは lambda） がクロージャであることは周知ですよね。クロージャの例は JavaScript の関数で、他にもクロージャをサポートしている言語はいまやふつうです。クロージャは、中の変数の値を保持します。例えば Ruby で

x = 0
f = proc {x + 1}

p f.call    #=>1

x += 1
p f.call    #=>2

確かに Proc 内部の x の値が保持されていますね。

ここでブロックですが、ブロックは Proc として実装されています。ならば、ブロックもクロージャで、値を保持するのではないか？
というわけで確かめてみました。

def a(&bk)
  p bk.call
  return bk
end

x = 0
b = a {x + 1}    #=>1

x += 10
p b.call       #=>11

おお、やはりブロックは値を保持しています。ということは、ブロックはクロージャですね！

なお、メソッド a 内の return は不要ですが、わかりやすいように敢て付けておきました。

スプライン曲線を描く（Ruby）

複数の点をなめらかにつなぐ「スプライン曲線」を描いてみました。全体的に下のサイトを参考にしました（ありがとうございます！）
Ruby - ３次スプライン補間！ - mk-mode BLOG
　
gnuplot で出力してみるとこんな感じです。

　
spline_curve.rb

require 'numo/gnuplot'
require 'matrix'

class SplineCurve
  def initialize(step)
    @step = step    #補完する点の間隔
  end
  
  def generate(points)
    @xs, @ys = points.transpose
    @n = @xs.size - 1
    
    #h, w, v
    h = calc_h
    w = calc_w(h)
    v = calc_v(h, w)
    
    #a, b, c, d
    b = v[0..-2].map {|x| x / 2}
    d = @ys[0..-2]
    a, c = [], []
    @n.times do |i|
      dx = @xs[i + 1] - @xs[i]
      a << (v[i + 1] - v[i]) / (6 * dx)
      c << (@ys[i + 1] - @ys[i]) / dx - dx * (2 * v[i] + v[i + 1]) / 6
    end
    
    Enumerator.new do |yl|
      @xs.each_cons(2).with_index do |xi, i|
        x = xi[0]
        while x < xi[1]
          y = proc do
            dx = x - @xs[i]
            a[i] * dx ** 3 + b[i] * dx ** 2 + c[i] * dx + d[i]
          end
          
          yl << [x, y.call]
          x += @step
        end
        x = xi[1]
        yl << [x, y.call]
      end
    end
  end
  
  def calc_h
    (0...@n).map {|i| @xs[i + 1] - @xs[i]}
  end
  
  def calc_w(h)
    (1...@n).map do |i|
      6 * ((@ys[i + 1] - @ys[i]) / h[i] - (@ys[i] - @ys[i - 1]) / h[i - 1])
    end
  end
  
  def calc_v(h, w)
    m = Array.new(@n - 1) {[0] * (@n - 1)}
    (@n - 1).times do |i|
      m[i][i] = 2 * (h[i] + h[i + 1])
      next if i.zero?
      m[i - 1][i] = h[i]
      m[i][i - 1] = h[i]
    end
    [0] + Matrix[*m].lup.solve(w).to_a + [0]
  end
end


if __FILE__ == $0
  points = [[0.0, 0.8], [2.0, 3.2], [3.0, 2.8], [5.0, 4.5], [7.0, 2.5], [8.0, 1.9]]
  x, y = SplineCurve.new(0.1).generate(points).to_a.transpose
  
  Numo.gnuplot do
    set title: "Spline Curve"
    set terminal: "png"
    set output: "spline_curve.png"
    unset :key
    plot [x, y, w: :l],
         [*points.transpose, w: :points, pt: 7, lc: [rgb: "orange"], pointsize: 2]
  end
end

points が点の座標を入れた配列を与えます。SplineCurve#generate はスプライン補完された点の座標 [x, y] を順に与える Enumerator を返します。ここでは to_a して一気に配列にしているので、あまり意味はないですが。

コンソールでライフゲーム（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.3)
      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 個あります。