推理判断のプレゼント交換の問題

rsc.hatenablog.comrsc さんのブログから問題を拝借しました。

問題:
A~Eの5人がプレゼント交換をした。5人とも自分以外の人から1つずつプレゼントを受け取ったが、プレゼントを渡した相手からプレゼントを受け取った人はいなかったという。さらに次のア~エのことがわかっているとき、確実にいえるのはどれか。
 ア.AはBからもDからもプレゼントを受け取らなかった。 
 イ.BはCかDからプレゼントを受け取った。 
 ウ.DはEからプレゼントを受け取らなかった。
 エ.EはBからもCからもプレゼントを受け取らなかった。
1.AはEにプレゼントを渡した。
2.BはCにプレゼントを渡した。
3.CはAにプレゼントを渡した。
4.DはBにプレゼントを渡した。
5.EはAにプレゼントを渡した。

http://rsc.hatenablog.com/entry/2019/04/07/235903

 
コードは以下です。Ruby で解いてみました。
solve.rb

Name = "ABCDE"
N = Name.size

def try(given)
  person = given.size
  if person == N
    #プレゼントを渡した相手からプレゼントを受け取った人はいないかチェック
    N.times {|i| return if i == given[given[i]]}
    
    #どの条件が当て嵌まるかチェック
    [[0, 4], [1, 2], [2, 0], [3, 1], [4, 0]].each_with_index do |c, i|
      if given[c.last] == c.first
        str = given.map.with_index {|p, i| "#{Name[p]}=>#{Name[i]}"}.join(", ")
        puts "[#{str}]"
        puts "正解: #{i + 1}"
      end
    end
  else
    left = [*0...N] - given
    left.each do |gift|
      next if gift == person
      
      case person
      when 0
        next if gift == 1 || gift == 3
      when 1
        next unless gift == 2 || gift == 3
      when 3
        next if gift == 4
      when 4
        next if gift == 1 || gift == 2
      end
      
      try(given + [gift])
    end
  end
end

try([])

Array#permutaion を使ってもよいのですが、敢て再帰を使って解いてみました。配列 given は、位置 i (0~4) の人物が given[i] の人物からプレゼントをもらったことを表わしています。
 
結果。

$ time ruby solve.rb
[E=>A, C=>B, A=>C, B=>D, D=>E]
正解: 5

real	0m0.115s
user	0m0.076s
sys	0m0.008s

これだったら Ruby も関数型言語?

anopara.net
わたしは初級者プログラマですが、ここでの話は納得、というか、Ruby プログラマなら常識みたいな話でもあると思います。Ruby はふつうに書いて関数型プログラミングのエッセンスを抽出しているといわれることもありますが、Ruby関数型プログラミングと相性がよいことはあまり知られていないのではないでしょうか。って初級者がいうことですけれどね。いや、map とか select とか inject を使えって、ただそれだけのことで、Rubyist なら常識だと思います。

上のブログの C# コードを再掲しておきます。

var maleEmps = new List<Employee>();
for(var e in employeeList){
    if(e.gender == "M")
        maleEmps.Add(e);
}

「従業員リストの中から男性のみを抽出したい」というようなコードだそうです。
 

var maleEmps = new List<Employee>();
for(var e in employeeList){
    if(e.gender == "M" && e.salary > 4000000)
        maleEmps.Add(e);
}

男性社員で年収400万以上の人を抽出したい。
 

var names = new List<String>();
for(var e in employeeList)
    names.Add(e.name);

社員の名前のリストを抽出したい。
 

var sum = 0;
for(var e in employeeList){
    if(e.gender == "M")
        sum += e.salary;
}

男性社員の年俸の合計を計算しています。
 

Ruby で「関数型プログラミング」っぽく

では、男性のみを抽出してみましょう。Scala だと

val maleEmps = employeeList.filter(e => e.gender == "M")

となるのだそうです。ワンライナーですね。じゃあ Ruby だと、select を使って

male_emps = employee_list.select {|e| e.gender == "M")}

という感じですか(変数名は Ruby 文化のスネークケースで書いています)。Ruby だとふつうですね。

どんどんいきましょう。
男性社員で年収400万以上の人を抽出したい。

male_400over_emps = employee_list.select {|e| e.gender == "M" && e.salary > 400_0000}

 
社員の名前のリストを抽出したい。

emp_names = employee_list.map(&:name)

map を使用。ここではブロック変数が省略可能なので、さらにシンプルになっています。

男性社員の年俸の合計を計算。

sum = employee_list.select {|e| e.gender == "M"}.inject(0) {|acc, e| acc + e.salary}

inject(畳み込み)を使用。あるいは Ruby 2.4 以降だと、Array#sum を使って

sum = employee_list.select {|e| e.gender == "M"}.map(&:salary).sum

でも OK です。
以上、上サイトの Scala の場合とほぼ同じように書けているのがわかります。


つまり、ここで「関数型プログラミング」っぽいといっているのは、Ruby ではふつうの文化だということがわかります。Ruby のブロックは、高階関数を可読性の高い形で書くのにぴったりなのです。というのは、もちろん Rubyist には当り前の話なのですが。

Ruby でマンデルブロ集合を描画

qiita.comQiita 記事を見てやってみたくなりました。ほとんどパクリです。Numo::NArray を使っています。


実行結果。
20190608211301
 
コード。
mandelbrot_narray.rb

require 'numo/narray'
require 'gdk_pixbuf2'
include Numo

MaxCalc = 5000      #最大計算回数(数字が大きいと細部がくっきりします)
W, H = 1000, 800    #画像サイズ

#計算(size_w: 横幅の長さ, x: 画像中心のx座標, y: 画像中心のy座標)
def mandel(size_w, x, y)
  size_h = size_w * H / W
  c = (DComplex.new(1, W).seq / W * size_w - size_w / 2 + x) +
      (DComplex.new(H, 1).seq / H * size_h - size_h / 2 - y) * Complex(0, 1)

  z = DComplex.new(H, W).fill(0)
  count = Int32.zeros(W, H)
  idx = Int32.new(W, H).seq

  (1..MaxCalc).each do |i|
    z = z ** 2 + c
    idx_t = (z.abs >  2).where
    idx_f = (z.abs <= 2).where
    count[idx[idx_t]] = i
    break if idx_f.empty?

    idx = idx[idx_f]
    z = z[idx_f]
    c = c[idx_f]
  end
  count
end

#データ生成
data0 = mandel(0.004, 0.3801718623708117, 0.19031789808145916)

#画像化
data = UInt8.zeros(W, H, 3)
data[true, true, 1] = (data0 % 255 - 127).abs * 2    #着色

pixbuf = GdkPixbuf::Pixbuf.new(data: data.to_string, width: W, height: H)

pixbuf.save('mandel.png')

 
いちばん基本的なマンデルブロ集合は mandel(4.0, 0.0, 0.0) という感じで生成します。
20190608121156
色の付け方をあれこれ工夫したいところですね。

こんなのも。mandel(0.004, 0.30145277714203783, 0.024192503140736933) でやってみた。
20190608212923

 
※参考
Numo::NArray概要 · ruby-numo/numo-narray Wiki · GitHub
NArrayの簡単なつかい方 - Qiita
マンデルブロ集合の不思議な世界
 
※追記
よく考えたらこれでは上下が逆転するので、コードを修正しました。上の画像はすべて上下が反転しています。


追加。mandel(0.004, 0.282, -0.01)
20190608221942

チャーチ数の簡単な計算(Ruby)

WikipediaOCaml の項目を読んでいたら、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' でテトリス

20190428021409
 
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

おお、すばらしい…。