7セグメントコードの反転（Ruby）

デジタル表示で 0~9 の数字を表示させることを考えます。数字はディスプレイの 7つの場所の on, off で表示することになります。このとき、二つの数字を連続して表示するとして、7つの場所の on, off の切り替わりが出来るだけ少なくなるような順番を考えます。つまりその場所で、できるだけ on なら on、off なら off のままになるようにするということです。

0~9 の数字を適当な順番ですべて一度ずつ表示させるとき、on, off の切り替え数の和の最小値を求めよという問題です。

q38.rb

pattern = [0b1111110, 0b0110000, 0b1101101, 0b1111001, 0b0110011,
           0b1011011, 0b1011111, 0b1110000, 0b1111111, 0b1111011]
@table = {}
[*0..9].combination(2) do |i, j|
  @table[[i, j]] = ("%07b" % (pattern[i] ^ pattern[j])).count("1")
end

@min = Float::INFINITY

def count(not_used, co, order)
  i = order[-1]
  not_used -= [i]
  if not_used.empty?
    @min = co
    p [order, co]
  end
  not_used.each do |j|
    pair = (i < j) ? [i, j] : [j, i]
    sum = co + @table[pair]
    next if sum >= @min
    count(not_used, sum, order + [j])
  end
end

count([*0..9], 0, [0])
puts @min

結果。

$ time ruby q38.rb
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 28]
[[0, 1, 2, 3, 4, 5, 6, 7, 9, 8], 27]
[[0, 1, 2, 3, 4, 5, 6, 8, 7, 9], 26]
[[0, 1, 2, 3, 4, 5, 6, 8, 9, 7], 23]
[[0, 1, 2, 3, 5, 6, 8, 9, 4, 7], 21]
[[0, 1, 2, 8, 6, 5, 9, 3, 7, 4], 20]
[[0, 1, 3, 2, 8, 6, 5, 9, 4, 7], 19]
[[0, 1, 4, 7, 3, 2, 8, 6, 5, 9], 18]
[[0, 1, 4, 7, 3, 9, 5, 6, 8, 2], 17]
[[0, 1, 7, 3, 2, 8, 6, 5, 9, 4], 16]
[[0, 2, 3, 5, 6, 8, 9, 4, 1, 7], 15]
[[0, 2, 8, 6, 5, 9, 3, 7, 1, 4], 14]
[[0, 8, 6, 5, 9, 4, 1, 7, 3, 2], 13]
13

real	0m0.611s
user	0m0.608s
sys	0m0.000s

最小値は 13 になります。まず、すべての組の数字の on, off の切り替え数を先に計算しておいて、@table に格納します。あとはすべての順列の場合を再帰で求めています。その際、途中で和が暫定的な最小値 @min の値に等しくなるかそれを超えた場合、それ以上の探索は無用なので打ち切って高速化します。自分の環境では 0.6秒くらいで求まりました。
　