2018-09-07

ランダムかつ重複しないように文字列を生成する（Ruby）

Ruby

あることのために必要だったので、複数の文字列をランダムかつ重複しないように生成するメソッドを書いてみました。

こんな感じです。

$ irb
irb(main):001:0> require_relative "generate_random_strings"
=> true
irb(main):002:0> Utils.generate_random_strings(40)
=> ["kk", "cm", "aq", "vf", "zf", "uh", "qv", "pv", "bb", "jp", "td", "ri", "mr",
    "hq", "gy", "pe", "ta", "ot", "ob", "km", "zu", "cz", "sf", "qo", "zt", "uq",
    "tc", "fd", "xq", "ki", "po", "w", "dj", "ks", "mw", "am", "zr", "az", "iy", "gv"]

重複しない 40個の文字列（アルファベット小文字）が生成されて Array で返ります。文字の長さは最小になるようになっているので、長さ 1 と 2 の文字列が入り混じっています。

文字列の長さを指定して呼ぶこともできます。

irb(main):003:0> Utils.generate_random_strings(40, 4)
=> ["bakz", "aipi", "prgo", "cwfw", "qqkv", "lgtt", "neid", "jjjz", "cjst", "tdfd",
    "sguf", "nkqk", "bvpl", "tldk", "qszi", "qfvj", "mnjy", "epsd", "abix", "ldap",
    "lijm", "jqzl", "gclu", "fxxe", "tcxc", "rayu", "rcsn", "aitp", "focj", "ngxd",
    "ouxc", "reze", "svxc", "ppaz", "roeb", "qgdt", "mhdw", "ewap", "fxjb", "mmrx"]

長さ 4 のランダムな文字列が 40個返りました。

コード。
generate_random_strings.rb

module Utils
  def repeated_permutation(a, b)
    a ** b
  end
  
  def generate_random_strings(num, string_length = nil)
    table = [*"a".."z"]
    limit = [0, 26, 702, 18278, 475254, 12356630]
    result = []
    generate_string1 = ->(n, l) {
      st = ""
      l.times do
        a, n = n % 26, n / 26
        st = table[a] + st
      end
      st
    }
    generate_string2 = ->(n) {
      idx = limit.find_index {|i| i > n}
      generate_string1.(n - limit[idx - 1], idx)
    }
        
    if string_length and 26 < string_length
      raise "Given length of strings too big."
    end
    
    num_table = Set.new
    if string_length
      n = Utils.repeated_permutation(26, string_length)
      raise "Given length of strings too small." if n < num
      while num_table.size < num
        num_table << rand(n)
      end
      num_table.each {|i| result << generate_string1.(i, string_length)}
    else
      idx = limit.find_index {|i| i >= num}
      raise "Result Array too big." unless idx
      while num_table.size < num
        num_table << rand(limit[idx])
      end
      num_table.each {|i| result << generate_string2.(i)}
    end
    result
  end
  module_function :repeated_permutation, :generate_random_strings
end

Gem 化

Gem 'kaki-utils' に同梱しました。$ gem install kaki-utils や Bundler でインストールできます。

$ bundle exec irb
irb(main):001:0> require 'kaki/utils'
=> true
irb(main):002:0> Utils.generate_random_strings(40)
=> ["qv", "kj", "wf", "ch", "ds", "hp", "ro", "oj", "xa", "dz", "vv", "zz", "fh",
    "rf", "tr", "gw", "cf", "yx", "ep", "pr", "tl", "sn", "ar", "ao", "ij", "pl", "my",
    "gy", "sk", "yk", "to", "hq", "wj", "vf", "jh", "pu", "cg", "gq", "wu", "dx"]

みたいな感じ。

2018-09-03

Ruby/Rouge でコードをシンタックスハイライトした HTML と CSS を出力させる

Ruby Gem

Ruby コードを HTML化して、ついでにシンタックスハイライトもできるようにできないか、やってみました。

画像だとこんな感じです。全体はこういう風です。

RubyGem 'rouge' というものを使いました。インストールはふつうに $ gem install rouge とかBundler でどうぞ。

とりあえず HTML と CSS を吐かせるのにかなり苦労しました。上の HTML, CSS ファイルはこんなコードで出力しています。
rouge_sample.rb

require 'rouge'

source = File.read('oekaki_sample16.rb')
formatter = Rouge::Formatters::HTML.new
lexer = Rouge::Lexers::Ruby.new

html = formatter.format(lexer.lex(source))
css = Rouge::Themes::ThankfulEyes.render(scope: '.highlight')

html1 = <<EOS
<!DOCTYPE html>
<html lang="ja">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Syntax-Highlight</title>
<head>
<link rel="stylesheet" type="text/css" href="rouge_sample1.css">
<style type="text/css">
pre.highlight {
  font-family: Liberation Mono, Consolas, monospace, sans-serif;
  font-size: 86%;
  padding: 10px;
  line-height: 1.1em;
}
</style>
</head>
<body>

<pre class="highlight">
EOS
html = html1 + html + "</pre>\n\n</body>\n</html>"

open("rouge_sample1.html", "w") {|io| io.write(html)}
open("rouge_sample1.css",  "w") {|io| io.write(css)}

色の付け方は Rouge::Themes::ThankfulEyes のところで指定しています。ここでは ThankfulEyes を選んでいますが、Colorful, Github など、いろいろ選べます。詳しくはこちらを見て下さい。
また、表示させるソースの種類はRouge::Lexers::Ruby.new で指定しています。これなら Ruby ですね。他のものはこちらを見て下さい。たいていのものはあるのではないでしょうか。

2018-08-30

円落下の JavaScript 版

JavaScript

obelisk.hatenablog.comここの JavaScript 版です。ボタンをクリックしてみて下さい。

コード。

<script type="text/javascript">
function circleFall(width, height) {
    var w = window.open("", null, "width=" + width + ",height=" + height);
    w.focus();
    w.document.open();
    var st = `
    <!DOCTYPE html>
    <html lang="ja">
    <title>Canvas</title>
    <body style="margin: 0; overflow: hidden;">
    <canvas id="circleFallCanvas" width="${width}" height="${height}"></canvas>
    </body>
    </html>
`;
    w.document.write(st);
    w.document.close();
    
    var canvas = w.document.getElementById("circleFallCanvas");
    var wd = w.innerWidth; var ht = w.innerHeight;    //Chrome は 0 を返す
    if (wd != 0) {width  = wd;}
    if (ht != 0) {height = ht;}
    canvas.width  = width;
    canvas.height = height;
    var context = canvas.getContext("2d");
    
    var max_r, min_r, colorMax, maxNum;
    max_r = 40; min_r = 10;
    colorMax = 256;
    maxNum = 60;
    
    var Circle = function(f) {
        function rnd(num) {return Math.random() * num;}
        
        this.maxR = rnd(max_r - min_r) + min_r;
        this.x = rnd(width);
        this.color = "rgb(" + String(rnd(colorMax)) + "," + String(rnd(colorMax)) +
                          "," + String(rnd(colorMax)) + ")";
        this.fallStep = rnd(3) + 1;
        this.r = 1;
        this.r_step = rnd(0.8) + 0.2;
        if (f) {
            this.y = rnd(height);
        } else {
            this.y = -rnd(max_r);
        }
        
        this.paint = function() {
            context.beginPath();
            context.fillStyle = this.color;
            context.arc(this.x, this.y, this.r, 0, 2 * Math.PI);
            context.fill();
            this.y += this.fallStep;
            this.r += this.r_step;
            if (this.r > this.maxR || this.r < 1) {this.r_step *= -1}
            if (this.y > height + max_r) {return true}
            return false;
        }
    }
    
    var circles = [];
    for (var i = 0; i < maxNum; i++) {circles[i] = new Circle(true);}
    
    window.draw = function() {
        context.fillStyle = "black";
        context.fillRect(0, 0, width, height);
        
        for (var i = 0; i < maxNum; i++) {
            if (circles[i].paint()) {circles[i] = new Circle(false);}
        }
    }
    
    var id = setInterval("draw()", 80);
    function bul() {clearInterval(id);}
    w.onbeforeunload = bul;
}
</script>
<form><input type="button" value="アニメーション" onclick="circleFall(1000, 700)">
 <input type="button" value="（小さい版）" onclick="circleFall(800, 600)"></form>

2018-08-25

Ruby で関数型プログラミングっぽく（コピペ） + Haskell 版

Ruby アルゴリズム・パズル Haskell

parrot.hatenadiary.jpここのブログ記事を読んで感銘を受けました。だからこれを読んでもらえればよいのですが、せっかくなのでコピペしておきます。元記事に感謝です。

まずは問題。

ある数字にそれを逆に並べた数字を足すという計算を、
回文数（上から読んでも下から読んでも同じ数）になるまで繰り返すとき、
もっとも計算回数を要する二桁の数を答えなさい
　
例：ab+ba=123の場合、123+321=444で回文数なので、2回となる
https://parrot.hatenadiary.jp/entry/20110302/1299051431

　
Ruby コードです。多少自己流に書き直しました。

reverse_num = ->(num) {num.to_s.reverse.to_i}
is_palindrome = ->(num) {num == reverse_num.(num)}
execute = ->(count, num) {
  r = num + reverse_num.(num)
  is_palindrome.(r) ? count : execute.(count + 1, r)
}

result = (10..99).map{|n| [n, execute.(1, n)]}
max_count = result.map(&:last).max
result.select{|r| r.last == max_count}.each{|r| puts "num:#{r.first} count:#{r.last}"}

結果。89 と 98 ですね。24回繰り返しています。

$ time ruby palindrome_num.rb
num:89 count:24
num:98 count:24

real	0m0.091s
user	0m0.076s
sys	0m0.012s

　
いや、すばらしい。
　

Haskell 版

頑張って Scala ならぬ Haskell で同様のことをやってみました。
palindrome_num.hs

reverseNum :: Int -> Int
reverseNum num = read $ reverse $ show num

isPalindrome :: Int -> Bool
isPalindrome num = (num == reverseNum num)

execute :: Int -> Int -> Int
execute count num = if isPalindrome r
                    then count
                    else execute (count + 1) r
                        where r = num + reverseNum num
                        
main :: IO ()
main = putStr $ unlines $ map toS $ [r | r <- result, last r == maxCount]
           where result = [[n, execute 1 n] | n <- [10..99]]
                 maxCount = maximum $ map last result
                 toS [a, b] = "num:" ++ show a ++ " count:" ++ show b

こんなのでいいのかな。
結果。

$ time ./palindrome_num
num:89 count:24
num:98 count:24

real	0m0.003s
user	0m0.000s
sys	0m0.000s

当然のことながら瞬殺ですな。

しかし、Ruby でも結構関数型っぽく書けますね。ほとんどそのまま Haskell になるじゃん。自分は Ruby で慣れているので、Ruby の方が見やすいくらいだ。以下の記事もよろしければどうぞ。
obelisk.hatenablog.com

すごいHaskellたのしく学ぼう!

作者:Miran Lipovača
発売日: 2012/05/23
メディア: 単行本（ソフトカバー）

追記（2020/12/4）

Ruby 版後半があまり美しくないので、少し凝ってみる。

module Enumerable
  def max_select
    pool = []
    max_num = -Float::INFINITY
    each do |i|
      n = yield(i)
      if n > max_num
        max_num = n
        pool = [i]
      elsif n == max_num
        pool << i
      end
    end
    [max_num, pool]
  end
end

Enumerable#max_selectは、ブロックの返り値の最大値（max_num）を求めて、そのような最大値になるようなものをレシーバーからコレクトし（pool）、[max_num, pool]を返すメソッド。例えばこんな風に使える。ローマ字化した県名のうち、もっとも文字数が長いもの。

url = "https://gist.githubusercontent.com/koseki/38926/raw/671d5279db1e5cb2c137465e22424c6ba27f4524/todouhuken.txt"
prefectures = URI.open(url).each_line.map {|l| l.chomp.split.last}
prefectures.max_select(&:size)
#=>[9, ["fukushima", "yamanashi", "hiroshima", "yamaguchi", "tokushima", "kagoshima"]]

9文字が最大値だとわかる。

まあ、他に使いみちがあるかどうかわからないものだが（笑）、これを使って以下のように。

reverse_num = ->(num) {num.to_s.reverse.to_i}
is_palindrome = ->(num) {num == reverse_num.(num)}
execute = ->(num, count = 1) {
  r = num + reverse_num.(num)
  is_palindrome.(r) ? count : execute.(r, count + 1)
}

count, numbers = (10..99).max_select(&execute)
puts "max count: #{count}"
puts "number: #{numbers}"

ちょっと関数型プログラミングっぽいかも知れない笑。

2018-08-25

Ruby/SDL を使ってみる

Ruby Gem

これまで Ruby で画面に線を引いたり円を描いたりするのに、自作の Gem 'oekaki' を使ってきましたが、その中では Gem 'gtk2' を使っていて、たかがお絵かきに GTK+ を使うのは大袈裟すぎるようにも思われたので、Ruby/SDL を使ってみることにしました。Linux MInt 18.3, Ruby 2.5.1 で確認しています。（SDL と SGE が入れば、Windows や Mac でも動く筈です。）

まずは SDL のインストールが必要です。Linux では apt-get で入ります。libsdl2-2.0 は既に入っているかもしれません。

sudo apt-get install libsdl2-2.0 libsdl-sge-dev

お絵かきをするには特に SGE（SDL Graphics Extension）が必要です。SDL 2.0 の日本語リファレンスはここにあります。

Ruby/SDL をインストール。gem install rubysdl でよいです。もちろん Bundler で入れてもかまいません。Ruby/SDL のリファレンス・マニュアルはここにあります。簡単なサンプルはこちらもどうぞ。

サンプルとして、Gem 'oekaki' で描いた（参照）のと同様のデモを載せておきます。複数の円が拡大縮小しながら落下していきます。

コード。簡単なライブラリのようなもの。
sdl_draw.rb

require 'sdl'

def draw(width, height, &blk)
  SDL.init(SDL::INIT_VIDEO)
  screen = SDL::Screen.open(width, height, 16, SDL::SWSURFACE)
  SDL::WM::set_caption("SDL", "")
  
  class << screen
    def color(r, g, b)
      format.map_rgb(r, g, b)
    end
  end
  
  Thread.new {screen.instance_eval(&blk)}
  
  loop do
    while (event = SDL::Event.poll)
      case event
      when SDL::Event::Quit
        exit
      end
    end
    sleep 0.2
  end
end

　
サンプル。
sdl_sample3.rb

require_relative 'sdl_draw'

Width, Height = (ARGV.size == 2) ? ARGV.map(&:to_i) : [1000, 700]
Max_r, Min_r = 40, 10
ColorMax = 256
MaxNum = 60

class Circle
  def initialize(ob)
    @slot = ob
    renewal
    @y = rand(Height)
  end
  
  def renewal
    @max_r = rand(Min_r..Max_r)
    @x =  rand(Width)
    @y = -rand(@max_r)
    @color = @slot.color(rand(ColorMax), rand(ColorMax), rand(ColorMax))
    @fall_step = rand(1..4)
    @r = 1
    @r_step = rand(0.2..1.0)
  end

  def paint
    @slot.draw_circle(@x, @y, @r, @color, true, true)
    @y += @fall_step
    @r += @r_step
    @r_step *= -1 if @r > @max_r or @r < 1
    renewal if @y > Height + Max_r
  end
end


draw(Width, Height) do
  circles = Array.new(MaxNum) { Circle.new(self) }
  black = color(0, 0, 0)
   
  loop do
    fill_rect(0, 0, Width, Height, black)
    circles.each(&:paint)
    flip
    sleep(0.08)
  end
end

Ruby/SDL、シンプルでよいですね。これからも使ってみたいです。
　

Gem 'oekaki' 版の動画です。こんな感じ。

　

追記（10/22）

実行時に

uninitialized constant SDL::Mixer (NameError)

のエラーが出る場合は、

$ sudo apt-get install libsdl-mixer1.2 libsdl-mixer1.2-dev

でライブラリを入れてから、Gem を再インストールしてみて下さい。

2018-08-20

交差せずに一筆書き（Ruby）

Ruby アルゴリズム・パズル

問題：
長方形状に横 5 個、縦 4 個の格子点が全部で 20個、等間隔に並んでいます。このすべての格子点を一筆書き（交差してはならない）で辿るとすると、その辿り方は全部で何とおりあるでしょうか。
ただし進む方向は上下左右のみで、また始点と終点が反対になっているだけで同じパターンは除外することにします。

　
Ruby で解いてみます。
q62.rb

m, n = 5, 4
count = 0

solve = ->(x, y, history) {
  if history.size == m * n
    count += 1
  else
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dir|
      x1, y1 = x + dir[0], y + dir[1]
      next if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or history.include?([x1, y1])
      solve.(x1, y1, history + [[x1, y1]])
    end
  end
}

m.times do |x|
  n.times {|y| solve.(x, y, [[x, y]])}
end
puts count / 2

結果。

$ time ruby q62.rb
1006

real	0m2.004s
user	0m1.992s
sys	0m0.012s

単純な深さ優先探索で求めています。ひとつのパターンに付き始点と終点を入れ替えたものが存在するので、最後に結果を半分にします。
　

別解（9/27）

上のコードは配列 history の処理が重いので、多少改変してみました。
q62b.rb

m, n = 5, 4
count = 0
field = Array.new(n) {Array.new(m, 0)}

solve = ->(x, y, num) {
  field[y][x] = 1
  if num == m * n
    count += 1
  else
    [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dir|
      x1, y1 = x + dir[0], y + dir[1]
      next if x1 < 0 or x1 >= m or y1 < 0 or y1 >= n or field[y1][x1].nonzero?
      solve.(x1, y1, num + 1)
    end
  end
  field[y][x] = 0
}

m.times do |x|
  n.times {|y| solve.(x, y, 1)}
end
puts count / 2

これだと結果はこうなります。

$ time ruby q62b.rb
1006

real	0m0.468s
user	0m0.464s
sys	0m0.004s

およそ 4.3倍高速化しています。
　

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

作者: 増井敏克
出版社/メーカー: 翔泳社
発売日: 2015/10/16
メディア: Kindle版
この商品を含むブログ (9件) を見る

2018-08-13

Ruby でファイル転送（改良版）

Ruby

obelisk.hatenablog.comローカルエリア内に PC が散らばっているので以前ファイル転送のコマンドを作ったのですが、1つのファイルしか転送できないとか、バイナリファイルは転送できないなど使いにくいところがあったので、それらに対応してみました。本当は SSH でやるのがいいのだけれど、一台の PC に Linux をマルチブートしているので厄介なのです。

ネストしたディレクトリもバイナリファイルも転送できるようにしました。

使用例はこんな感じ。受け手（サーバー）側（こちらを先に実行する）。

$ file_transfer
IPアドレス: 192.168.11.7
[192.168.11.3:54902] からの接続を了承しました
ディレクトリ with_else を作成しました。
[192.168.11.3:54904] からの接続を了承しました
with_else-0.0.1.gem を受信中です...
with_else-0.0.1.gem の受信が完了しました
[192.168.11.3:54906] からの接続を了承しました
with_else.gemspec を受信中です...
with_else.gemspec の受信が完了しました
[192.168.11.3:54908] からの接続を了承しました
README を受信中です...
README の受信が完了しました
[192.168.11.3:54910] からの接続を了承しました
ディレクトリ lib を作成しました。
[192.168.11.3:54912] からの接続を了承しました
with_else.rb を受信中です...
with_else.rb の受信が完了しました
[192.168.11.3:54914] からの接続を了承しました
[192.168.11.3:54916] からの接続を了承しました
すべての受信が終了しました。

　
送り手（クライアント）側。

$ file_transfer 192.168.11.7 with_else
ディレクトリ with_else の処理をしています...
with_else-0.0.1.gem を送信中です...
with_else.gemspec を送信中です...
README を送信中です...
with_else-0.0.1.gem の送信が完了しました
with_else.gemspec の送信が完了しました
README の送信が完了しました
ディレクトリ lib の処理をしています...
with_else.rb を送信中です...
with_else.rb の送信が完了しました
すべての送信が終了しました。

ちゃんとディレクトリが送れていますね。ディレクトリ名のところをファイル名に変更すれば、1ファイルの転送ももちろんできます。また、

$ file_transfer 192.168.11.7 oekaki/lib oekaki_sample21.rb ../color_p.sh

などのように、複数ファイル（ディレクトリ）の指定や相対パスでの指定もできます。
　

コードはこんな具合です。
file_transfer

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

def file_send
  host = ARGV[0]
  q = Queue.new
  30.times {q.push(:unlock)}    #スレッド数の最大値を30にする
  
  send_file = ->(name) {
    q.pop
    Thread.new(name) do |fname|
      puts "#{fname} を送信中です..."
      open(fname, "rb") do |file|
        size = File.size(fname)
        TCPSocket.open(host, 7413) do |sock|
          sock.set_encoding('ASCII-8BIT')
          sock.puts "File/#{fname}/#{size}"
          sock.write(file.read(size))
        end
      end
      puts "#{fname} の送信が完了しました"
      q.push(:unlock)
    end
  }
  
  send_directory = ->(dname) {
    handle_dir = ->(st) {
      TCPSocket.open(host, 7413) do |sock|
        sock.set_encoding('ASCII-8BIT')
        sock.puts st
        sock.gets.chomp
      end
    }
    
    Dir.chdir(dname)
    handle_dir.("Mkdir/#{dname}")
    puts "ディレクトリ #{dname} の処理をしています..."
    
    threads = []
    dirs = []
    Dir.glob("*").each do |fname|
      if File.directory?(fname)
        dirs << fname
      else
        threads << send_file.(fname)
      end
    end
    ThreadsWait.all_waits(*threads)
    
    dirs.each {|dname| send_directory.(dname)}
    handle_dir.("Dirup")
    Dir.chdir("..")
  }
  
  fnames = ARGV[1..-1].map {|fn| File.expand_path(fn)}
  raise "No files or directorys." if fnames.empty?
  while (fname = fnames.shift)
    Dir.chdir(File.dirname(fname))
    fname = File.basename(fname)
    if File.file?(fname)
      send_file.(fname).join
    else
      send_directory.(fname)
    end
  end
  puts "すべての送信が終了しました。"
end

def receive
  print "IPアドレス: "
  ip_ad = Socket.getifaddrs.select {|x| x.addr.ipv4?}
  puts ip_ad.map {|x| x.addr.ip_address}.select {|x| x.include?("192.168")}[0]
  
  s = TCPServer.open(7413)
  
  q = Queue.new
  Thread.new do
    q.pop
    () until Thread.list.size <= 2
    puts "すべての受信が終了しました。"
    exit
  end
    
  loop do
    Thread.new(s.accept) do |sock|
      puts "[#{sock.peeraddr[3]}:#{sock.peeraddr[1]}] からの接続を了承しました"
      sock.set_encoding('UTF-8')
      ar = sock.gets.chomp.split('/')
      case ar[0]
      when "File"
        fname, size = ar.drop(1)
        puts "#{fname} を受信中です..."
        open("#{fname}", "wb") do |file|
          file.write(sock.read(size.to_i))
        end
        puts "#{fname} の受信が完了しました"
      when "Mkdir"
        begin
          Dir.mkdir(ar[1])
        rescue
          puts "ディレクトリが作成できません。"
          sock.close
          exit 1
        end
        Dir.chdir(ar[1])
        puts "ディレクトリ #{ar[1]} を作成しました。"
        sock.puts :done
      when "Dirup"
        Dir.chdir("..")
        sock.puts :done
      when "End"
        q.push :end
        sock.puts :done
      else
        raise "error: 予期せぬコマンドです。"
      end
      sock.close
    end
  end
end

if ARGV.size.zero?
  receive
else
  file_send
end

Thread を使ってみたのですが、同期を取るのに苦労しました。並行プログラミングはむずかしい。
それから、set_encoding() で 'ASCII-8BIT' で送って 'UTF-8' に復号しているのは、socket でマルチバイト文字がそのまま送れないため。ファイル名やディレクトリ名にマルチバイト文字が使ってある場合に対応しています。
　
コマンドとして使うなら、

$ chmod 755 file_transfer
$ sudo cp file_transfer /usr/local/bin

とでもして下さい（Linux の場合）。

自分では便利に使っています。100MB くらいまでの転送なら意外と使い物になるなという感じ。