Offline in Echtzeit, wie man ein Implementierungsbeispiel für E11 Ruby und Python schreibt

Problem: http://nabetani.sakura.ne.jp/hena/orde11tredis/ Implementierungslinks: http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6

Implementieren Sie zuerst 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

Lassen Sie O (n) weg, um die Zahl zu finden.

• Notieren Sie den Pfad vom Knoten, den Sie interessieren, zur Wurzel, während Sie dem Baum folgen.
• Sie können die Entfernung sehen, indem Sie die aufgezeichneten Pfade vergleichen

Die Strategie. Sie können die Entfernung ermitteln, indem Sie die Liste von der Route mit sich selbst vergleichen.

Ich mag den Bereich um "each_item" nicht, aber ich kann nichts dagegen tun. Ich bin es nicht gewohnt, meine eigene Methode für "Yield" oder Blockargumente zu definieren.

damit. Ich habe dies unten auf Python portiert:

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" )

Ich war verwirrt über die Verwendung von Python Yield zum ersten Mal in meinem Leben, aber es fühlte sich genauso an.