お気楽 Ruby プログラミング入門

はじめに

Lisp ライクで immutable (書き換え不可) な連結リスト (imlist.rb) です。Ruby で immutable な連結リストを使う必要性はあまりないと思いますが、Ruby のお勉強ということで作ってみました。実用性はほとんどありませんが、興味のある方はいろいろ試してみてください。

●仕様

• クラス名 : ImList
• 特異メソッド
  • create(item, xs) => ImList
    要素 item をリスト xs の先頭に追加したリストを返す
  • list(*args) => ImList
    list() の引数を格納したリストを返す
  • fill(n, x) => ImList
    要素 x を n 個格納したリストを返す
  • iota(n, m) => ImList
    n 以上 m 以下の整数列を返す
  • iterate(n, a = 0, &func) => ImList
    初項を a とし、ブロック func で生成した項を n 個格納したリストを返す
  • tabulate(n, &func) => ImList
    数列 (0 ... n) の要素にブロック func を適用し、その結果を格納したリストを返す
  • null() => ImList
    空の連結リストを返す

irb> load "imlist.rb"
=> true
irb> a = ImList.create(1, ImList.null)
=> (1)
irb> b = ImList.create(2, a)
=> (2 1)
irb> c = ImList.create(3, b)
=> (3 2 1)
irb> ImList.list(1,2,3,4,5)
=> (1 2 3 4 5)
irb> ImList.list(*[1,2,3,4,5])
=> (1 2 3 4 5)
irb> ImList.fill(10, 0)
=> (0 0 0 0 0 0 0 0 0 0)
irb> ImList.iota(1, 10)
=> (1 2 3 4 5 6 7 8 9 10)
irb> ImList.iterate(10, 1){|x| x + 2}
=> (1 3 5 7 9 11 13 15 17 19)
irb> ImList.tabulate(10){|x| x * x}
=> (0 1 4 9 16 25 36 49 64 81)

• リスト操作
  • null?() => boolean
    リスト (self) が空リストであれば真を返す
  • cons(item) => ImList
    リスト (self) の先頭に要素 item を追加する
  • first() => item
    リスト (self) の先頭要素を返す
  • rest() => ImList
    リスト (self) 先頭要素を取り除いたリストを返す
  • get(n) => item
  • xs[n] => item
    リスト (self, xs) の n 番目の要素を返す
  • last() => item
    リスト (self) の最後の要素を返す
  • length() => n
    リスト (self) の長さを返す
  • reverse() => ImList
    リスト (self) を反転したリストを返す
  • append(xs) => ImList
    二つのリスト (self, xs) を連結する
  • xs + ys => ImList
    二つのリスト (xs, ys) を連結する
  • xs * n => ImList
    リスト xs を n 個連結したリストを返す
  • take(n) => ImList
    リスト (self) の先頭から n 個の要素を取り出したリストを返す
  • drop(n) => ImList
    リスト (self) の先頭から n 個の要素を取り除いたリストを返す
  • zip(xs) => ImList
    二つのリスト (self, xs) の要素を一つのリストにまとめ、それを格納したリストを返す

irb> a = ImList.null.cons(1).cons(2).cons(3)
=> (3 2 1)
irb> a.first
=> 3
irb> a.rest
=> (2 1)
irb> a.rest.rest.first
=> 1
irb> a.rest.rest.null?
=> false
irb> a.rest.rest.rest.null?
=> true
irb> b = ImList.iota(1, 10)
=> (1 2 3 4 5 6 7 8 9 10)
irb> b.get(0)
=> 1
irb> b.get(9)
=> 10
irb> b[1]
=> 2
irb> b[8]
=> 9
irb> b.last
=> 10
irb> a.length
=> 3
irb> b.length
=> 10
irb> a.reverse
=> (1 2 3)
irb> b.reverse
=> (10 9 8 7 6 5 4 3 2 1)
irb> a.append(b)
=> (3 2 1 1 2 3 4 5 6 7 8 9 10)
irb> a + b
=> (3 2 1 1 2 3 4 5 6 7 8 9 10)
irb> a * 10
=> (3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1)
irb> b.take(5)
=> (1 2 3 4 5)
irb> b.drop(5)
=> (6 7 8 9 10)
irb> c = ImList.iota(11, 20)
=> (11 12 13 14 15 16 17 18 19 20)
irb> b.zip(c)
=> ((1 11) (2 12) (3 13) (4 14) (5 15) (6 16) (7 17) (8 18) (9 19) (10 20))

• 高階関数
  • map(&func) => ImList
    リスト (self) の要素にブロックを適用し、その結果をリストに格納して返す (マッピング)
  • flat_map(&func) => ImList
    リスト (self) の要素にブロックを適用し、その結果 (リスト) を連結して返す
  • zip_with(xs, &func) => ImList
    リスト self と xs の要素をブロックに適用し、その結果をリストに格納して返す
  • filter(&pred) => ImList
    述語 pred が真を返す要素をリストに格納して返す
  • reduce(a, &func) => x
    リスト (self) の先頭から畳み込みを行う
  • reduce_right(a, &func) => x
    リスト (self) の末尾から畳み込みを行う
  • each(&func) => self
    リスト (self) の要素にブロックを適用する
  • each_with_index(&func) => self
    添字付きの each()、ブロックの第 1 引数が要素、第 2 引数が添字
  • all?(&pred) => boolean
    リスト (self) の要素に述語 pred を適用し、すべての結果が真であれば真を返す
  • any?(&pred) => boolean
    リスト (self) の要素に述語 pred を適用し、一つでも真を返す要素があれば真を返す
  • take_while(&func) => ImList
    述語 pred が真を返す間、先頭から要素を取り出す
  • drop_while(&func) => ImList
    述語 pred が真を返す間、先頭から要素を取り除く

irb> a = ImList.iota(1,8)
=> (1 2 3 4 5 6 7 8)
irb> a.map{|x| x * x}
=> (1 4 9 16 25 36 49 64)
irb> a.flat_map{|x| ImList.fill(x, x)}
=> (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8)
irb> b = ImList.iota(11, 18)
=> (11 12 13 14 15 16 17 18)
irb> a.zip_with(b){|x, y| x + y}
=> (12 14 16 18 20 22 24 26)
irb> a.zip_with(b){|x, y| x + y}
=> (12 14 16 18 20 22 24 26)
irb> a.filter{|x| x.even?}
=> (2 4 6 8)
irb> a.reduce(0){|x, y| x + y}
=> 36
irb> a.reduce_right(0){|x, y| x + y}
=> 36
irb> a.reduce(ImList.null){|x, y| x.cons(y)}
=> (8 7 6 5 4 3 2 1)
irb> a.reduce_right(ImList.null){|x, y| y.cons(x)}
=> (1 2 3 4 5 6 7 8)
irb> a.each{|x| puts x}
1
2
3
4
5
6
7
8
=> (1 2 3 4 5 6 7 8)
irb> a.each_with_index{|x, i| print x, " ", i, "\n"}
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
=> (1 2 3 4 5 6 7 8)
irb> ImList.list(2,4,6,8,10).all?(&:even?)
=> true
irb> ImList.list(2,4,6,8,11).all?(&:even?)
=> false
irb> ImList.list(2,4,6,8,10).any?(&:odd?)
=> false
irb> ImList.list(2,4,6,8,11).any?(&:odd?)
=> true
irb> a.take_while{|x| x < 6}
=> (1 2 3 4 5)
irb> a.drop_while{|x| x < 6}
=> (6 7 8)

• 線形探索
  • member?(x) => ImList
    リスト (self) から x と等しい要素を探索する。見つけた場合、それ以降のリストを返す。見つからない場合は空リストを返す
  • include?(x) => boolean
    リスト (self) から x と等しい要素を探索し、見つけたら true を返す
  • find(&pred) => item or false
    リスト (self) から述語 pred が真を返す要素を探索する
  • find_index(&pred) => index or false
    リスト (self) から述語 pred が真を返す要素を探索し、見つけた場合はその位置を返す
  • count(&pred) => n
    リスト (self) から述語 pred が真を返す要素の個数を求める

irb> a = ImList.iota(1, 8)
=> (1 2 3 4 5 6 7 8)
irb> a.member?(1)
=> (1 2 3 4 5 6 7 8)
irb> a.member?(5)
=> (5 6 7 8)
irb> a.member?(8)
=> (8)
irb> a.member?(9)
=> ()
irb> a.include?(1)
=> true
irb> a.include?(8)
=> true
irb> a.include?(9)
=> false
irb> a.find{|x| x > 5}
=> 6
irb> a.find{|x| x > 8}
=> false
irb> a.find_index{|x| x > 5}
=> 5
irb> a.find_index{|x| x > 8}
=> false
irb> b = ImList.list(1,1,2,1,2,3,1,2,3,4)
=> (1 1 2 1 2 3 1 2 3 4)
irb> b.count{|x| x == 1}
=> 4
irb> b.count{|x| x == 4}
=> 1
irb> b.count{|x| x == 5}
=> 0

●プログラムリスト

# coding: utf-8
#
# imlist.rb : immutable な連結リスト
#
#             Copyright (C) 2017-2023 Makoto Hiroi
#

# エラー
class ImListError < StandardError
end

# 連結リスト
class ImList
  def initialize(item, link)
    @item = item
    @link = link
  end

  def set_link(link)
    @link = link
  end
  protected :set_link

  # 終端
  Null = ImList.new(nil, nil)
  private_class_method :new

  def self.create(item, link)
    raise TypeError if !link.instance_of?(ImList)
    new(item, link)
  end
  
  def self.null
    Null
  end

  # 基本的な関数
  def cons(x)
    ImList.create(x, self)
  end
  
  def first
    raise ImListError, "Empty List" if null?
    @item
  end

  def rest
    raise ImListError, "Empty List" if null?
    @link
  end

  def null?
    self == Null
  end

  # 表示
  def to_s
    s = "("
    xs = self
    while !xs.null?
      s += xs.first.to_s
      s += " " if !xs.rest.null?
      xs = xs.rest
    end
    s += ")"
  end

  def inspect
    to_s
  end

  # 配列に変換
  def to_a
    xs = self
    ys = []
    while !xs.null?
      ys.push xs.first
      xs = xs.rest
    end
    ys
  end
  
  # 生成
  def self.list(*args)
    xs = Null
    args.reverse_each{|x| xs = xs.cons(x)}
    xs
  end

  def self.fill(n, x)
    xs = Null
    n.times { xs = xs.cons(x) }
    xs
  end

  def self.iota(n, m)
    list(*(n .. m).to_a)
  end
  
  def self.iterate(n, a, &func)
    xs = []
    n.times {
      xs.push(a)
      a = func.call(a)
    }
    list(*xs)
  end

  def self.tabulate(n, &func)
    xs = Null
    (n - 1).downto(0) {|x| xs = xs.cons(func.call(x)) }
    xs
  end

  #
  # リスト操作関数
  #
  def get(n)
    xs = self
    n.times {
      xs = xs.rest
    }
    xs.first
  end

  def [](n)
    get(n)
  end

  def last
    xs = self
    while !xs.rest.null?
      xs = xs.rest
    end
    xs.first
  end
  
  def length
    xs = self
    n = 0
    while !xs.null?
      n += 1
      xs = xs.rest
    end
    n
  end

  def reverse
    xs = self
    ys = Null
    while !xs.null?
      ys = ys.cons(xs.first)
      xs = xs.rest
    end
    ys
  end

  def reverse!
    xs = self
    ys = Null
    while !xs.null?
      zs = xs.rest()
      xs.set_link(ys)
      ys = xs
      xs = zs
    end
    ys
  end
  protected :reverse!

  def append(ys)
    return ys if null?
    xs = self
    zs = Null
    while !xs.null?
      zs = zs.cons(xs.first)
      xs = xs.rest
    end
    xs = zs.reverse!
    zs.set_link(ys)
    xs
  end

  def +(other)
    raise TypeError if !other.instance_of?(ImList)
    append(other)
  end

  def *(n)
    xs = Null
    n.times {
      xs = self.append(xs)
    }
    xs
  end

  def take(n)
    xs = self
    ys = Null
    while n > 0 && !xs.null?
      ys = ys.cons(xs.first)
      xs = xs.rest
      n -= 1
    end
    ys.reverse!
  end

  def drop(n)
    xs = self
    while n > 0 && !xs.null?
      xs = xs.rest
      n -= 1
    end
    xs
  end

  def zip(ys)
    xs = self
    zs = Null
    while !xs.null? && !ys.null?
      zs = zs.cons(ImList.list(xs.first, ys.first))
      xs = xs.rest
      ys = ys.rest
    end
    zs.reverse!
  end
  
  #
  # 高階関数
  #
  def map(&func)
    xs = self
    ys = Null
    while !xs.null?
      ys = ys.cons(func.call(xs.first))
      xs = xs.rest
    end
    ys.reverse!
  end

  def flat_map(&func)
    xs = self
    ys = Null
    zs = Null
    while !xs.null?
      ys = ys.cons(func.call(xs.first))
      xs = xs.rest
    end
    while !ys.null?
      zs = ys.first.append(zs)
      ys = ys.rest
    end
    zs
  end

  def zip_with(ys, &func)
    xs = self
    zs = Null
    while !xs.null? && !ys.null?
      zs = zs.cons(func.call(xs.first, ys.first))
      xs = xs.rest
      ys = ys.rest
    end
    zs.reverse!
  end
  
  def filter(&pred)
    xs = self
    ys = Null
    while !xs.null?
      ys = ys.cons(xs.first) if pred.call(xs.first)
      xs = xs.rest
    end
    ys.reverse!
  end

  def reduce(a, &func)
    xs = self
    while !xs.null?
      a = func.call(a, xs.first)
      xs = xs.rest
    end
    a
  end

  def reduce_right(a, &func)
    xs = reverse
    while !xs.null?
      a = func.call(xs.first, a)
      xs = xs.rest
    end
    a
  end

  def each(&func)
    xs = self
    while !xs.null?
      func.call(xs.first)
      xs = xs.rest
    end
    self
  end

  def each_with_index(&func)
    xs = self
    i = 0
    while !xs.null?
      func.call(xs.first, i)
      xs = xs.rest
      i += 1
    end
    self
  end

  def all?(&pred)
    each{|x| return false if !pred.call(x)}
    true
  end

  def any?(&pred)
    each{|x| return true if pred.call(x)}
    false
  end

  def take_while(&func)
    xs = self
    ys = Null
    while !xs.null? && func.call(xs.first)
      ys = ys.cons(xs.first)
      xs = xs.rest
    end
    ys.reverse!
  end

  def drop_while(&func)
    xs = self
    while !xs.null? && func.call(xs.first)
      xs = xs.rest
    end
    xs
  end

  #
  # 線形探索
  #
  def member?(x)
    xs = self
    while !xs.null?
      return xs if xs.first == x
      xs = xs.rest
    end
    Null
  end

  def include?(x)
    xs = self
    while !xs.null?
      return true if xs.first == x
      xs = xs.rest
    end
    false
  end

  def find(&pred)
    each{|x| return x if pred.call(x)}
    false
  end

  def find_index(&pred)
    each_with_index{|x, i| return i if pred.call(x) }
    false
  end

  def count(&pred)
    reduce(0){|c, x| pred.call(x) ? c + 1 : c}
  end

end

●リストで遊ぼう

immutable な連結リストを使った簡単な問題集です。

1. リスト xs の総和、最大値、最小値を求めるメソッド sum(xs), maximum(xs), minimum(xs) を定義してください。
2. リストを使って FizzBuzz 問題を解くプログラムを作ってください。
3. リスト xs の最後尾から n 個の要素を取り除くメソッド butlast(xs, n) を定義してください。
4. リスト xs を長さ n の部分リストに分割するメソッド group(xs, n) を定義してください。
5. リスト xs の n 番目から m - 1 番目までの要素を部分リストとして取り出すメソッド sublist(xs, n, m) を定義してください。
6. リスト xs の要素を述語 pred で二分割するメソッド partition(pred, xs) を定義してください。
7. リスト xs をクイックソートするメソッド quick_sort(xs) を定義してください。
8. 整列済みの 2 つのリスト xs, ys をマージするメソッド merge_list(xs, ys) を定義してください。
9. リスト xs をマージソートするメソッド merge_sort(xs) を定義してください。
10. リスト xs から n 個の要素を選ぶ順列を求めるメソッド permutation(n, xs) を定義してください。
11. リスト xs から n 個の要素を選ぶ組み合わせを求めるメソッド combination(n, xs) を定義してください。
12. リストを集合とみなして、重複要素を取り除くメソッド distinct(xs) を定義してください。
13. 和集合、積集合、差集合を求めるメソッド union(xs, ys), intersection(xs, ys), difference(xs, ys) を定義してください。
14. リストを集合とみなして、部分集合を判定する述語 subset?(xs, ys) を定義してください。
15. リスト xs のべき集合を求めるメソッド power_set(xs) を定義してください。
16. n 以下の素数を求めるメソッド sieve(n) を定義してください。
17. マスターマインドを解くプログラムを作ってください。

●解答

リスト : 「リストで遊ぼう」の解答

load "imlist.rb"

# Q01 総和, 最大値, 最小値
def sum(xs)
  xs.reduce(0){|m, x| m + x}
end

def maximum(xs)
  xs.rest.reduce(xs.first){|m, x| m < x ? x : m}
end

def minimum(xs)
  xs.rest.reduce(xs.first){|m, x| m > x ? x : m}
end

puts "----- Q01 -----"
a = ImList.list(5, 6, 4, 7, 3, 8, 2, 9, 1, 10)
puts a
puts sum(a)
puts maximum(a)
puts minimum(a)

# Q02 FizzBuzz
def change(x)
  return "FizzBuzz" if x % 15 == 0
  return "Fizz" if x % 3 == 0
  return "Buzz" if x % 5 == 0
  x.to_s
end

puts "----- Q02 -----"
puts ImList.iota(1, 100).map{|x| change(x)}

# Q03 
def butlast(xs, n)
  xs.reverse.drop(n).reverse
end

puts "----- Q03 -----"
q03 = ImList.iota(1, 8)
puts q03
puts butlast(q03, 1)
puts butlast(q03, 4)
puts butlast(q03, 8)

# Q04
def group(xs, n)
  if xs.null?
    ImList.null
  else
    group(xs.drop(n), n).cons(xs.take(n))
  end
end

puts "----- Q04 -----"
q04 = ImList.iota(1, 10)
puts q04
puts group(q04, 2)
puts group(q04, 3)
puts group(q04, 4)
puts group(q04, 5)

# Q05
def sublist(xs, n, m)
  xs.drop(n).take(m - n)
end

puts "----- Q05 -----"
q05 = ImList.iota(1, 10)
puts q05
puts sublist(q05, 0, 1)
puts sublist(q05, 2, 8)
puts sublist(q05, 3, 10)

# Q06 リストの分割
def partition(xs, &pred)
  if xs.null?
    return ImList.null, ImList.null
  else
    a, b = partition(xs.rest, &pred)
    if pred.call(xs.first)
      return a.cons(xs.first), b
    else
      return a, b.cons(xs.first)
    end
  end
end

puts "----- Q06 -----"
q06 = ImList.iota(1, 10)
puts partition(q06, &:even?)
puts partition(q06, &:odd?)

# Q07 クイックソート
def quick_sort(xs)
  if xs.null?
    ImList.null
  else
    a, b = partition(xs.rest){|x| x < xs.first}
    quick_sort(a).append(quick_sort(b).cons(xs.first))
  end
end

puts "----- Q07 -----"
puts quick_sort(ImList.list(5,6,4,7,3,8,2,9,1,0))
puts quick_sort(ImList.iota(0, 9))
puts quick_sort(ImList.iota(0, 9).reverse)

# Q08 マージ
def merge_list(xs, ys)
  if xs.null?
    ys
  elsif ys.null?
    xs
  else
    if xs.first <= ys.first
      merge_list(xs.rest, ys).cons(xs.first)
    else
      merge_list(xs, ys.rest).cons(ys.first)
    end
  end
end

puts "----- Q08 -----"
q081 = ImList.list(0,2,4,6,8,10)
q082 = ImList.list(1,3,5,7,9)
puts q081
puts q082
puts merge_list(q081, q082)
puts merge_list(q082, q081)

# Q09 マージソート
def merge_sort(xs, n)
  if n == 1
    ImList.list(xs.first)
  else
    m = n / 2
    merge_list(merge_sort(xs, m),
               merge_sort(xs.drop(m), n - m))
  end
end
      
puts "----- Q09 -----"
puts merge_sort(ImList.list(5,6,4,7,3,8,2,9,1,0), 10)
puts merge_sort(ImList.iota(0, 9), 10)
puts merge_sort(ImList.iota(0, 9).reverse, 10)

# Q10
def permutation(n, xs)
  if n == 0
    ImList.list(ImList.null)
  else
    xs.flat_map{|x| permutation(n - 1, xs.filter{|y| x != y}).map{|zs| zs.cons(x)}}
  end
end

puts "----- Q10 -----"
puts permutation(2, ImList.list(1,2,3,4))
puts permutation(4, ImList.list(1,2,3,4))

# Q11
def combination(n, xs)
  if n == 0
    ImList.list(ImList.null)
  elsif xs.null?
    ImList.null
  else
    combination(n - 1, xs.rest).map{|ys| ys.cons(xs.first)}.append(combination(n, xs.rest))
  end
end

puts "----- Q11 -----"
puts combination(2, ImList.iota(1, 5))
puts combination(3, ImList.iota(1, 5))
puts combination(4, ImList.iota(1, 5))

# Q12
def distinct(xs)
  xs.reduce_right(ImList.null) {|x, ys| ys.include?(x) ? ys : ys.cons(x)}
  #ys = ImList.null
  #xs.each{|x| ys = ys.cons(x) if !ys.include?(x)}
  #ys.reverse
end

puts "----- Q12 -----"
puts distinct(ImList.list(1,1,2,1,2,3,1,2,3,4,1,2,3,4,5))

# Q13
def union(xs, ys)
  if xs.null?
    ys
  elsif ys.include?(xs.first)
    union(xs.rest, ys)
  else
    union(xs.rest, ys).cons(xs.first)
  end
end

def intersection(xs, ys)
  if xs.null?
    ImList.null
  elsif ys.include?(xs.first)
    intersection(xs.rest, ys).cons(xs.first)
  else
    intersection(xs.rest, ys)
  end
end

def difference(xs, ys)
  if xs.null?
    ImList.null
  elsif ys.include?(xs.first)
    difference(xs.rest, ys)
  else
    difference(xs.rest, ys).cons(xs.first)
  end
end

puts "----- Q13 -----"
q13a = ImList.list(1,2,3,4,5,6)
q13b = ImList.list(1,3,5,7,9,11)
puts q13a
puts q13b
puts union(q13a, q13b)
puts intersection(q13a, q13b)
puts difference(q13a, q13b)

# Q14
def subset?(xs, ys)
  xs.all?{|x| ys.include?(x)}
end

puts "----- Q14 -----"
puts subset?(ImList.list(1,2,3,4), ImList.iota(1, 5))
puts subset?(ImList.list(1,2,3,4,5), ImList.iota(1, 5))
puts subset?(ImList.list(1,2,3,4,6), ImList.iota(1, 5))

# Q15
def power_set(xs)
  if xs.null?
    ImList.list(ImList.null)
  else
    ys = power_set(xs.rest)
    ys.append(ys.map{|zs| zs.cons(xs.first)})
  end
end

puts "----- Q15 -----"
puts power_set(ImList.iota(1, 3))
puts power_set(ImList.iota(1, 4))

# Q16
def rev_append(xs, ys)
  xs.reduce(ys){|zs, x| zs.cons(x)}
end

def sieve(n)
  xs = ImList.iota(2, n)
  ps = ImList.null
  while xs.first * xs.first <= n
    ps = ps.cons(xs.first)
    xs = xs.rest.filter{|x| x % xs.first != 0}
  end
  rev_append(ps, xs)
end

puts "----- Q16 -----"
puts sieve(100)
puts sieve(500)

# Q17 (mastermind)
def count_bulls(xs, ys)
  xs.zip_with(ys){|x, y| x == y}.count(&:itself)
end

def count_same_number(xs, ys)
  xs.reduce(0){|a, x| ys.include?(x) ? a + 1 : a}
end

class Query
  def initialize(code, bulls, cows)
    @code = code
    @bulls = bulls
    @cows = cows
  end
  attr_reader :code, :bulls, :cows
end

def check_query(qs, code)
  qs.each{|q|
    b = count_bulls(q.code, code)
    c = count_same_number(q.code, code) - b
    return false if b != q.bulls || c != q.cows
  }
  true
end

def mastermind(answer)
  perms = permutation(4, ImList.iota(0, 9))
  query = ImList.null
  perms.each{|code|
    if check_query(query, code)
      b = count_bulls(code, answer)
      c = count_same_number(code, answer) - b
      query = query.cons(Query.new(code, b, c))
      printf("%d: %s, bulls = %d, cows = %d\n", query.length, code, b, c)
      if b == 4
        puts "Good Job!!"
        return
      end
    end
  }
end

puts "----- Q17 -----"
mastermind(ImList.list(9,8,7,6))
mastermind(ImList.list(9,4,3,1))

●実行例

----- Q01 -----
(5 6 4 7 3 8 2 9 1 10)
55
10
1
----- Q02 -----
(1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 
23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 
43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 
Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 
83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz)
----- Q03 -----
(1 2 3 4 5 6 7 8)
(1 2 3 4 5 6 7)
(1 2 3 4)
()
----- Q04 -----
(1 2 3 4 5 6 7 8 9 10)
((1 2) (3 4) (5 6) (7 8) (9 10))
((1 2 3) (4 5 6) (7 8 9) (10))
((1 2 3 4) (5 6 7 8) (9 10))
((1 2 3 4 5) (6 7 8 9 10))
----- Q05 -----
(1 2 3 4 5 6 7 8 9 10)
(1)
(3 4 5 6 7 8)
(4 5 6 7 8 9 10)
----- Q06 -----
(2 4 6 8 10)
(1 3 5 7 9)
(1 3 5 7 9)
(2 4 6 8 10)
----- Q07 -----
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 3 4 5 6 7 8 9)
----- Q08 -----
(0 2 4 6 8 10)
(1 3 5 7 9)
(0 1 2 3 4 5 6 7 8 9 10)
(0 1 2 3 4 5 6 7 8 9 10)
----- Q09 -----
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 3 4 5 6 7 8 9)
(0 1 2 3 4 5 6 7 8 9)
----- Q10 -----
((1 2) (1 3) (1 4) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (4 1) (4 2) (4 3))
((1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) (1 4 3 2) (2 1 3 4) (2 1 4 3) 
(2 3 1 4) (2 3 4 1) (2 4 1 3) (2 4 3 1) (3 1 2 4) (3 1 4 2) (3 2 1 4) (3 2 4 1) 
(3 4 1 2) (3 4 2 1) (4 1 2 3) (4 1 3 2) (4 2 1 3) (4 2 3 1) (4 3 1 2) (4 3 2 1))
----- Q11 -----
((1 2) (1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 4) (3 5) (4 5))
((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
((1 2 3 4) (1 2 3 5) (1 2 4 5) (1 3 4 5) (2 3 4 5))
----- Q12 -----
(1 2 3 4 5)
----- Q13 -----
(1 2 3 4 5 6)
(1 3 5 7 9 11)
(2 4 6 1 3 5 7 9 11)
(1 3 5)
(2 4 6)
----- Q14 -----
true
true
false
----- Q15 -----
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4) (1 2 3) (1 2 3 4))
----- Q16 -----
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 
109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 
229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 
353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 
479 487 491 499)
----- Q17 -----
1: (0 1 2 3), bulls = 0, cows = 0
2: (4 5 6 7), bulls = 0, cows = 2
3: (5 4 8 9), bulls = 0, cows = 2
4: (6 7 9 8), bulls = 0, cows = 4
5: (8 9 7 6), bulls = 2, cows = 2
6: (9 8 7 6), bulls = 4, cows = 0
Good Job!!
1: (0 1 2 3), bulls = 0, cows = 2
2: (1 0 4 5), bulls = 0, cows = 2
3: (2 3 5 4), bulls = 0, cows = 2
4: (3 4 0 6), bulls = 1, cows = 1
5: (3 5 6 1), bulls = 1, cows = 1
6: (6 5 0 2), bulls = 0, cows = 0
7: (7 4 3 1), bulls = 3, cows = 0
8: (8 4 3 1), bulls = 3, cows = 0
9: (9 4 3 1), bulls = 4, cows = 0
Good Job!!

●マスターマインド

マスターマインドは、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。

     (6 2 8 1) : 正解
---------------------------------
1.   (0 1 2 3) : cows 2 : bulls 0
2.   (1 0 4 5) : cows 1 : bulls 0
3.   (2 3 5 6) : cows 2 : bulls 0
4.   (3 2 7 4) : cows 0 : bulls 1
5.   (3 6 0 8) : cows 2 : bulls 0
6.   (6 2 8 1) : cows 0 : bulls 4

  図 : マスターマインドの動作例

今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。このゲームでは、10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。コードを生成する処理は順列と同じですから、簡単にプログラムできます。

●推測アルゴリズム

次に、この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。

矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、下図の例を考えてみてください。

(0 1 2 3) で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、(0 X X X) というコードは (0 1 2 3) と比較すると bulls が 1 となるので、矛盾していることがわかります。

次に (1 0 3 4) というコードを考えてみます。(0 1 2 3) の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、(1 0 3 4) と (0 1 2 3) と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。

次に (1 0 4 5) というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は (0 1 2 3) と (1 0 4 5) に矛盾しないコードを選択すればいいわけです。

(6 2 8 1) が正解の場合

(0 1 2 3) => bulls = 0, cows = 2

           (0 1 2 3)  と比較する
     --------------------------------------------------------
           (0 X X X)  0 から始まるコードは bulls = 1
                      になるので矛盾する。
           ・・・・

           (1 0 3 4)  cows = 3, bulls = 0 になるので矛盾する

           ・・・・

           (1 0 4 5)  cows = 2, bulls = 0 で矛盾しない。
     --------------------------------------------------------

(1 0 4 5) => bulls = 0, cows = 1

次は、(0 1 2 3) と (1 0 4 5) に矛盾しない数字を選ぶ

        図 : マスターマインドの推測アルゴリズム