チャーチ数の簡単な計算（Ruby）

Wikipedia の OCaml の項目を読んでいたら、OCaml ではチャーチ数の計算がきれいに書けることを知った。

let zero f x = x
let succ n f x = f (n f x)
let one = succ zero
let two = succ (succ zero)
let add n1 n2 f x = n1 f (n2 f x)
let to_int n = n (fun k -> k+1) 0
let _ = print (add (succ two) two)

ほう、さすがである。

では我が Ruby では似たようなことは可能であるのか。OCaml ほど簡潔ではないが、可能である。『アンダースタンディング・コンピュテーション』という名著を参考に書いてみる。

$ pry
[1] pry(main)> zero = -> f { -> x { x } }
=> #<Proc:0x000055918b649bb0@(pry):1 (lambda)>
[2] pry(main)> def to_integer(n) n.(-> k { k + 1 }).(0) end
=> :to_integer
[4] pry(main)> to_integer(zero)
=> 0
[5] pry(main)> succ = -> n {-> f {-> x { f.(n.(f).(x)) } } }
=> #<Proc:0x000055918b3654f8@(pry):5 (lambda)>
[6] pry(main)> one = succ.(zero)
=> #<Proc:0x000055918b7143b0@(pry):5 (lambda)>
[7] pry(main)> to_integer(one)
=> 1
[8] pry(main)> two = succ.(one)
=> #<Proc:0x000055918b7653a0@(pry):5 (lambda)>
[9] pry(main)> to_integer(two)
=> 2
[10] pry(main)> add = -> m {-> n { n.(succ).(m) } }
=> #<Proc:0x000055918b7b8528@(pry):10 (lambda)>
[11] pry(main)> to_integer(add.(succ.(two)).(two))
=> 5

うーむ、これが 3 + 2 か…。
　

アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

何度でも書くけれども、名著である。この本はコード例が Ruby。もはやこういう本が Ruby で書かれることはなくなったな…。Ruby != Rails と思っておられる方にはおすすめである。もちろん、Rubyist だけに独占させておくのはもったいない本なのであるが。

「Ruby初心者向けのプログラミング問題」を解いてみる

blog.jnito.comやってみました。

カレンダー作成問題

ここで似たようなことをやっているので省略。（ただし、Date クラスは使っていません。）
　

カラオケマシン問題

class KaraokeMachine
  Key = %w(C C# D D# E F F# G G# A A# B)
  def initialize(melody)
    @scaned = melody.scan(/C#|D#|F#|G#|A#|C|D|E|F|G|A|B| |\|/)
  end
  
  def transpose(n)
    @scaned.map do |k|
      idx = Key.index(k)
      idx ? Key[(idx + n) % Key.size] : k
    end.join
  end
end

ビンゴカード作成問題

stock = 5.times.map {|i| (i * 15 + 1..(i + 1) * 15).to_a.shuffle}
table = 5.times.map do
  5.times.map {|i| stock[i].shift}
end
table[2][2] = ""
table = ([%w(B I N G O)] + table).map do |row|
  row.map {|x| "%2s" % x}.join(" | ")
end
puts table

出力例。

 B |  I |  N |  G |  O
15 | 28 | 32 | 58 | 68
 8 | 27 | 35 | 49 | 73
12 | 18 |    | 47 | 64
 1 | 21 | 42 | 56 | 62
 3 | 25 | 38 | 52 | 75

ボーナスドリンク問題

class BonusDrink
  def self.total_count_for(amount)
    drink = ->(left, drinked) {
      return drinked if left.zero?
      i = left / 3
      d = i.zero? ? left : i * 3    #今回飲む本数
      drink.(left - d + i, drinked + d)
    }
    drink.(amount, 0)
  end
end

puts BonusDrink.total_count_for(100)    #=>149

再帰で解いています。
残りが3本より少なければそのまま飲みます。3本以上なら、3の倍数本だけ飲めるだけ飲んで、(いま飲んだ本数÷3)本だけ追加します。残り0本ならば終了します。
　

電話帳作成問題

class NameIndex
  ADan = %w(ア カ サ タ ナ ハ マ ヤ ラ ワ ン)
  def self.create_index(names)
    table = Hash.new([])
    names.each do |name|
      ADan.each_cons(2) do |be, ed|
        table[be] += [name] if (be...ed).include?(name[0])
      end
    end
    table.each_value {|v| v.sort!}
    table.map {|k, v| [k, v]}.sort
  end
end

NameIndex.create_index(['キシモト', 'イトウ', 'ババ', 'カネダ', 'ワダ', 'ハマダ'])

行単位、列単位で合計値を求めるプログラム

module SumMatix
  extend self
  
  def output(input)
    result = calc(input)
    length = result.last.map {|x| x.to_s.size}
    result.map do |row|
      row.map.with_index {|x, i| x.to_s.rjust(length[i])}.join("| ")
    end
  end
  
  def calc(input)
    tmp = input.map {|row| row + [row.sum]}
    last = tmp.first.each_index.map do |i|
      tmp.map {|row| row[i]}.sum
    end
    tmp + [last]
  end
end

実行例。

input = [
    [ 9, 85, 92, 20],
    [68, 25, 80, 55],
    [43, 96, 71, 73],
    [43, 19, 20, 87],
    [95, 66, 73, 62]
]
puts SumMatix.output(input)

  9|  85|  92|  20|  206
 68|  25|  80|  55|  228
 43|  96|  71|  73|  283
 43|  19|  20|  87|  169
 95|  66|  73|  62|  296
258| 291| 336| 297| 1182

ガラケー文字入力問題

module KeitaiMessage
  Allocation = [%W(. , ! ? #{" "}), %W(a b c), %W(d e f), %W(g h i), %W(j k l),
                %W(m n o), %W(p q r s), %W(t u v), %W(w x y z)]
  def self.key_in(input)
    result = ""
    input.chars.chunk_while {|i, j| i == j}.reject {|x| x[0] == "0"}.each do |line|
      group = Allocation[line.first.to_i - 1]
      result += group[(line.size - 1) % group.size]
    end
    result = result[0...-1] if input[-1] != "0"
    result
  end
end

puts KeitaiMessage.key_in("440330555055506660")    #=>hello

正しく問題のとおりにするなら、入力が例えば "5" の場合、何も出力されてはいけませんが、ここではじつは空文字列が出力されます。ただ元の仕様は美しくないので、まあいいかということにしてしまいました。正しく修正するなら、メソッドの外ですることになります。

Enumerable#chunk_while は見たことがないという人もいるかもしれませんが、意外と有用なメソッドだと思います。
　

終りに

「国民の祝日.csv パースプログラム」と「値札分割問題」は問題の定義がわかりにくかったので解いていません。
全体的にそんなにむずかしくはないですね。すなおな回答を心がけました。

Gem 'Ruby2D' でテトリス

　
Ruby でゲーム制作を意識したグラフィック・ライブラリ 'Ruby2D' でテトリスを作ってみました。完全にオリジナルの実装です。ソースは以下。
Ruby2D を使ったテトリス · GitHub
　
'Ruby2D' については以下で紹介しています。
obelisk.hatenablog.com
ゲームはカーソルキーあるいはゲームパッドで遊べます。ゲームパッドでは、十字キーの左右で移動、下で落下、Aボタンで回転です。最小限度の機能しか実装していないので、あとは勝手に改変してみてください。

Linux Mint 19.2, Ruby 2.6.0 と Windows 8.1, Ruby 2.6.3 で動作確認しました。

ハッシュによる美しいメモ化（Ruby）

qiita.com元ネタはこれです。
　
Ruby のハッシュにはこのようなデフォルトの与え方があります。

h = Hash.new {|hash, key| hash[key] = default}

　
これを利用して、こんな風にフィボナッチ数列をメモ化で計算できます。

fib = Hash.new do |hash, n|
  hash[n] = if n == 0 or n == 1
    n
  else
    hash[n - 1] + hash[n - 2]
  end
end

fib[100]    #=>354224848179261915075

おお、すばらしい…。

ブログ「hp12c」の一問題（Ruby）

またまた Ruby ブログ「hp12c」からの問題（？）です。
melborne.github.io
さて、データ

data = <<EOS
player gameA gameB
Bob    20    56
Ross   68    33
Bob    78    55
Kent   90    15
Alice  84    79
Ross   10    15
Jimmy  80    31
Bob    12    36
Kent   88    43
Kent   12    33
Alice  90    32
Ross   67    77
Alice  56    92
Jimmy  33    88
Jimmy  11    87
EOS

から出力

player  gameA gameB total
Alice   230   203   433
Jimmy   124   206   330
Kent    190   91    281
Ross    145   125   270
Bob     110   147   257

を得よという問題です（totalで降順）。

元ブログでの回答はこちら。

require "csv"

class CSV
  def group_by(&blk)
    Hash[ super.map { |k, v| [k, CSV::Table.new(v)] } ]
  end
end

csv = CSV.new(data, col_sep:' ', headers:true, converters: :numeric, header_converters: :symbol)
scores_by_player = csv.group_by(&:first)
stat = scores_by_player.map do |(_, player), t|
  ab = [:gamea, :gameb].map { |e| t[e].inject(:+) }
  [player, *ab, ab.inject(:+)]
end
puts "%s\t%s\t%s\ttotal" % csv.headers
puts stat.sort_by{ |s| -s.last }.map { |line| "%s\t%d\t%d\t%d" % line }

標準添付ライブラリを使っているわけですね。しかし、メソッドのオーバーライドはさすがにちょっとという気がします。それに、コードが凝りすぎて自分には読みにくい感じ。

ライブラリを使わず、極ふつうに素直にやったらどうなるか、考えてみました。

header, *given = data.each_line.map(&:split)
ga, gb = Hash.new(0), Hash.new(0)
given.each do |name, a, b|
  ga[name] += a.to_i
  gb[name] += b.to_i
end

table = [header + ["total"]] +
        given.map(&:first).uniq.map {|n| [n, ga[n], gb[n], ga[n] + gb[n]]}
        .sort {|a, b| b[3] <=> a[3]}
puts table.map {|p, a, b, t| sprintf "%s\t%s\t%s\t%s", p, a, b, t}

結構めんどうですね。もっとうまくできますかね。

線分の交点（Ruby）

4点 があるとき、線分 と の交点を求めるメソッド。
　

require 'matrix'

def cross(x1, y1, x2, y2, x3, y3, x4, y4)
  a = Matrix[[x2 - x1, x3 - x4], [y2 - y1, y3 - y4]]
           .lup.solve([x3 - x1, y3 - y1]) rescue nil
  return nil unless a
  s, t = a[0], a[1]
  f = ((0 <= s and s <= 1) and (0 <= t and t <= 1))
  f ? Vector[x1 + s * (x2 - x1), y1 + s * (y2 - y1)] : nil
end

交点（端点でも OK）があれば Vector で返し、なければ nil を返します。

標準添付ライブラリを使わない場合。Vector の代わりに配列を返します。

def cross(x1, y1, x2, y2, x3, y3, x4, y4)
  l = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3)
  return nil if l.zero?
  vx, vy = x3 - x1, y3 - y1
  s = Rational((y4 - y3) * vx - (x4 - x3) * vy, l)
  t = Rational((y2 - y1) * vx - (x2 - x1) * vy, l)
  f = ((0 <= s and s <= 1) and (0 <= t and t <= 1))
  f ? [x1 + s * (x2 - x1), y1 + s * (y2 - y1)] : nil
end

　
線分でなくて直線の交点の場合は、メソッドでの s, t の範囲のチェックをおこなわなければよいです。

Ruby のローカル変数登録について

以下の Ruby コードを見てほしい。

if false
  a = 1
end
p a    #=>nil

if true
  nil
else
  b = 1
end
p b    #=>nil

c = 1 if false
p c    #=>nil

while false
  d = 1
end
p d    #=>nil

いずれも nil を出力し、「undefined local variable or method」の NameError は出ない。

覚えておくと役に立つかも知れない。

応用編。

$ pry
[1] pry(main)> i = 1 if i.nil?
=> 1
[2] pry(main)> i
=> 1
[3] pry(main)> j = 1 if j == 1
=> nil
[4] pry(main)> j
=> nil

これはたぶん何の役にも立たない。