160210

Ruby


Hop-over Puzzle(6)

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

他方が「とばさず進むだけ」できるとき、
左右を入れ替える手順を書き出してみる。

n = 1 のとき
[0, 2, 1]
[0, 1, 2] 1がとばさず進む
[2, 1, 0] 0が一つとばし
[1, 2, 0] 1がとばさず進む

n = 2 のとき
[0, 0, 2, 1, 1]
[0, 0, 1, 2, 1] 1がとばさず進む
[0, 0, 1, 1, 2] 1がとばさず進む
[0, 2, 1, 1, 0] 0が二つとばし
[0, 1, 2, 1, 0] 1がとばさず進む
[0, 1, 1, 2, 0] 1がとばさず進む
[2, 1, 1, 0, 0] 0が二つとばし
[1, 2, 1, 0, 0] 1がとばさず進む
[1, 1, 2, 0, 0] 1がとばさず進む

n = 3 のとき
[0, 0, 0, 2, 1, 1, 1]
[0, 0, 0, 1, 2, 1, 1] 1がとばさず進む
[0, 0, 0, 1, 1, 2, 1] 1がとばさず進む
[0, 0, 0, 1, 1, 1, 2] 1がとばさず進む
[0, 0, 2, 1, 1, 1, 0] 0が三つとばし
[0, 0, 1, 2, 1, 1, 0] 1がとばさず進む
[0, 0, 1, 1, 2, 1, 0] 1がとばさず進む
[0, 0, 1, 1, 1, 2, 0] 1がとばさず進む
[0, 2, 1, 1, 1, 0, 0] 0が三つとばし
[0, 1, 2, 1, 1, 0, 0] 1がとばさず進む
[0, 1, 1, 2, 1, 0, 0] 1がとばさず進む
[0, 1, 1, 1, 2, 0, 0] 1がとばさず進む
[2, 1, 1, 1, 0, 0, 0] 0が三つとばし
[1, 2, 1, 1, 0, 0, 0] 1がとばさず進む
[1, 1, 2, 1, 0, 0, 0] 1がとばさず進む
[1, 1, 1, 2, 0, 0, 0] 1がとばさず進む

すると、
片方が「n 個とばしだけ」でき、

他方が「とばさず進むだけ」できる
としてよさそうなことに気づく。

よって、
片方が「n 個とばしだけ」でき、
他方が「とばさず進むだけ」できるとき、
必要な手数を求めることにする。

(0..12).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)
      [-n - 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
      }
      [1].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]
[8, 1]
[15, 1]
[24, 1]
[35, 1]
[48, 1]
[63, 1]
[80, 1]
[99, 1]
[120, 1]
[143, 1]
[168, 1]

手順は
「「1がとばさず進む」がn 回、「0がn 個とばし」が1 回」がn 回の後、「1がとばさず進む」がn 回
となり、
計(n + 1)n + n = (n + 1)^2 - 1 回の移動で左右が入れ替わる。