オフラインリアルタイムどう書く E11 の ruby と python による実装例

問題 : http://nabetani.sakura.ne.jp/hena/orde11tredis/
実装リンク集 : http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6

まずはrubyの実装。

def each_item(n, list)
  yield( list )
  (2..(n/2)).each do |x|
    next unless n % x==0
    each_item( x+1, list+[x+1] ){ |y| yield(y) }
  end
end

def dist(a,b)
  a.size+b.size - 2*(0..Float::INFINITY).find{ |x| a[x] != b[x] }
end

def impl( root, a, b )
  as=[]
  bs=[]
  each_item(root,[root]){ |x|
    as<<x if x.last==a
    bs<<x if x.last==b
  }
  as.inject(Float::INFINITY) do |d0, ai|
    bs.inject(d0) do |d1, bi|
      d1=[d1, dist(ai,bi)].min
    end
  end
end

def solve( src )
  impl( *src.split(/\D+/).map(&:to_i) ).to_s
end

DATA.map{ |line|
  num, src, expected = line.split( /\s+/ )
  actual = solve( src )
  ok = actual==expected
  puts [ num, ( ok ? "ok" : "**NG**" ), src, actual, expected ].join( " " )
  ok
}.all?.tap{ |x| p( x ? "all okay!" : "something wrong!!" ) }

__END__
0 50:6,3  1
1 98:5,11 4
2 1000:33,20  7

約数の求め方は、手抜きで O(n)。

• ツリーを辿りながら、気になるノードからルートまでのパスを記録する。
• 記録したパスを比較すると距離がわかる

という作戦。距離は、ルートから自分までのリストを比較するとわかる。

each_item の周辺がなんとなく気に入らないんだけど、まあ仕方ない。
まだ yield というかブロック引数のメソッドを自分で定義することに慣れていない。

で。
これを python に移植したのが下記：

import re

def each_item(n,list) :
  yield( list )
  for x in range( 2, n//2+1 ) :
    if n % x == 0 :
      for item in each_item( x+1, list + [x+1] ):
        yield(item)

def dist(a,b):
  n=0
  while n<len(a) and n<len(b) and a[n]==b[n]:
    n+=1
  return len(a) + len(b) - 2*n


def impl( root, a, b ) :
  a_s=[]
  b_s=[]
  for item in each_item(root, [root]) :
    if item[-1]==a:
      a_s.append( item )
    if item[-1]==b:
      b_s.append( item )
  d=1e100
  for a in a_s:
    for b in b_s:
      d = min( d, dist(a,b) )
  return d

def solve( src ):
  root, a, b = [ int(x) for x in re.split( "\\D", src ) ]
  return "%d" % ( impl( root, a, b ) )

def test( src, expected ):
  actual = solve( src )
  ok= ( actual==expected )
  print( "%s : %s -> %s ( %s )" % ( ("ok" if ok else "**NG**"), src, actual, expected ) )

test( "50:6,3", "1" )
test( "98:5,11", "4" )
test( "1000:33,20", "7" )

生まれて初めて python の yield を使っていろいろ戸惑ったんだけど、同じ感じになった。