CodeIQ に出した「ハノイの塔ではありません」の解説解題のようなもの

このブログは久々の更新になってしまった。すいません。

問題は、下記のような感じだった。

【概要】
「鷲」「鮫」「豹」と名付けられた三本の棒と、中心に穴が空いた円盤が何枚かあります。
最初は「鷲」の棒に、全ての円盤が刺さっています。
円盤を一回に一枚ずつどれかの棒に移動させることができますが、以下の条件を常に満たさなくてはいけません：

どの円盤も、自分よりも上には、自分よりも大きな円盤は1枚入以下しかない。
【入出力】
入力は
1234
のようになっています。
これは「鷲」に刺さっている円盤の大きさ(1〜9 の整数)を上から順に書いたものです。区切り文字はありません。

出力は、
6
のような感じです。
最小の手数を普通に10進数で出力して下さい。
【補足】
不正な入力に対処する必要はありません。
円盤の枚数は 1枚 以上、 7枚 以下です。
ゴールの状態としては「鮫」に全て刺さっていればOKです。元の順序を維持している必要はありません。

今回も数学的背景とかアルゴリズム的背景はいつもどおり特になくて、ふと思いついたから出したという感じ。

有名なハノイの塔をちょっと複雑にして、構造を汚くしてみた。

実装戦略としては、メモ化つきの幅優先探索が自然だと思う。

私の実装はあまりきれいに書けていないけどこんな感じ：

class Solver
  def initialize
    @k={}
  end

  def move( cur, from, to )
    m=cur[from][0]
    return nil unless m && okay( cur[to], m )
    o=3-from-to
    r=[]
    r[to]=m+cur[to]
    r[from]=cur[from][1..-1]
    r[o]=cur[o]
    r
  end

  def okay( c, m )
    k= @k[c] ||= (0...c.size).select{ |me|
      (0...me).any?{ |o| c[me]<c[o] }
    }.map{ |ix| c[ix] }.min
    !k || m<=k
  end

  def makekey(s)
    ((s[1]<=>s[2]) < 0 ? s : [s[0],s[2],s[1]] ).join("|")
  end

  def  solved?( s )
    s[0].empty? && (s[1].empty? || s[2].empty?)
  end

  def solve( state )
    q=[[ state, 0 ]]
    dones = { makekey(state)=>1 }
    moves = [0,1,2].permutation(2).to_a
    loop do
      cur, h = q.shift
      moves.each do |from,to|
        newstate = move( cur, from, to )
        next unless newstate
        return h+1 if solved?( newstate )
        key = makekey(newstate)
        next if dones[ key ]
        q.push([newstate, h+1 ])
        dones[ key ] = 1
      end
    end
  end
end

def solve( src )
  Solver.new.solve( [src, "", "" ] ).to_s
end

puts( solve( gets.strip ) )

50行以上あってちょっと残念な感じだけど、私の実装はこんな感じ。

普通に、メモ化つき幅優先探索。

permutation が地味に便利。move の実装がダラダラしているのが不満なんだけど、これよりいい方法が思いつかない。

探索済みのチェックのときに「鮫」と「豹」を区別しないようにしてちょっと枝刈りしている。

一番複雑なケースで、手元のPCで0.1秒前後。CodeIQ の( ideone の？ )サーバーはもう少し速いので、たぶん 0.0秒になると思う。

計算量のオーダーを劇的に減らす計算方法があるかもしれないけど、検討していない。

そんなところかな。

挑戦者数は 70名。初回正答率は 37%。

条件がちょっとごちゃごちゃしていてい難しく感じられたかもしれない。どうだろう。