Comment écrire un exemple d'implémentation E11 Ruby et Python en temps réel hors ligne

Problème: http://nabetani.sakura.ne.jp/hena/orde11tredis/ Liens d'implémentation: http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6

Tout d'abord, implémentez 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

Pour trouver le nombre, omettez O (n).

• Enregistrez le chemin du nœud qui vous intéresse à la racine tout en suivant l'arborescence.
• Vous pouvez voir la distance en comparant les chemins enregistrés

Stratégie. Vous pouvez trouver la distance en comparant la liste de l'itinéraire à vous-même.

Je n'aime pas la zone autour de ʻeach_item, mais ça ne peut pas être aidé. Je ne suis pas habitué à définir ma propre méthode d'argument yield` ou block.

alors. J'ai porté ceci en python ci-dessous:

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

J'étais confus à propos de l'utilisation de python yield pour la première fois de ma vie, mais c'était la même chose.