160208(3)

Ruby


Hop-over Puzzle(3)

片方が「とばさず進むと二つとばし」ができ、

他方が「一つとばしだけ」できるとき、
必要な手数で最小なものを求めてみたら、

面白い結果になった。

n ≧ 3 のとき、

a(n + 6) = a(n + 4) + a(n + 2) - a(n) + 16

が成り立つようだ。

(0..20).each{|n|
  n2 = 2 * n
  ary = [0] * n + [2] + [1] * n
  # 最終の並び
  ary0 = [1] * n + [2] + [0] * n
  s = 0
  f_ary = [ary]
  while !f_ary.include?(ary0)
    b_ary = []
    f_ary.each{|a|
      # カエルのいない場所
      i = a.index(2)
      [-3, -1].each{|j|
        b = a.clone
        k = i + j
        if k >= 0 && b[k] == 0
          # カエルのいない場所に0のカエルがとんでくる
          b[i], b[k] = b[k], b[i]
          b_ary << b
        end
      }
      [2].each{|j|
        b = a.clone
        k = i + j
        if k <= n2 && b[k] == 1
          # カエルのいない場所に1のカエルがとんでくる
          b[i], b[k] = b[k], b[i]
          b_ary << b
        end
      }
    }
    f_ary = b_ary.uniq
    s += 1
  end
  p [s, f_ary.size]
}

出力結果
[0, 1]
[3, 1]
[5, 3]
[12, 1]
[22, 1]
[31, 1]
[45, 1]
[56, 1]
[76, 1]
[91, 1]
[115, 1]
[132, 1]
[162, 1]
[183, 1]
[217, 1]
[240, 1]
[280, 1]
[307, 1]
[351, 1]
[380, 1]
[430, 1]