immutable な連結リスト
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
空の連結リストを返す
- create(item, xs) => 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) の要素を一つのリストにまとめ、それを格納したリストを返す
- null?() => boolean
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 が真を返す間、先頭から要素を取り除く
- map(&func) => ImList
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 が真を返す要素の個数を求める
- member?(x) => ImList
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 な連結リストを使った簡単な問題集です。
- リスト xs の総和、最大値、最小値を求めるメソッド sum(xs), maximum(xs), minimum(xs) を定義してください。
- リストを使って FizzBuzz 問題を解くプログラムを作ってください。
- リスト xs の最後尾から n 個の要素を取り除くメソッド butlast(xs, n) を定義してください。
- リスト xs を長さ n の部分リストに分割するメソッド group(xs, n) を定義してください。
- リスト xs の n 番目から m - 1 番目までの要素を部分リストとして取り出すメソッド sublist(xs, n, m) を定義してください。
- リスト xs の要素を述語 pred で二分割するメソッド partition(pred, xs) を定義してください。
- リスト xs をクイックソートするメソッド quick_sort(xs) を定義してください。
- 整列済みの 2 つのリスト xs, ys をマージするメソッド merge_list(xs, ys) を定義してください。
- リスト xs をマージソートするメソッド merge_sort(xs) を定義してください。
- リスト xs から n 個の要素を選ぶ順列を求めるメソッド permutation(n, xs) を定義してください。
- リスト xs から n 個の要素を選ぶ組み合わせを求めるメソッド combination(n, xs) を定義してください。
- リストを集合とみなして、重複要素を取り除くメソッド distinct(xs) を定義してください。
- 和集合、積集合、差集合を求めるメソッド union(xs, ys), intersection(xs, ys), difference(xs, ys) を定義してください。
- リストを集合とみなして、部分集合を判定する述語 subset?(xs, ys) を定義してください。
- リスト xs のべき集合を求めるメソッド power_set(xs) を定義してください。
- n 以下の素数を求めるメソッド sieve(n) を定義してください。
- マスターマインド を解くプログラムを作ってください。
●解答
リスト : 「リストで遊ぼう」の解答
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) に矛盾しないコードを選択すればいいわけです。
初版 2017 年 1 月 29 日
改訂 2023 年 1 月 22 日
改訂 2023 年 1 月 22 日