Offline real-time how to write E11 ruby and python implementation example

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

First, implement 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

To find the divisor, omit O (n).

The strategy. You can find the distance by comparing the list from the route to yourself.

I don't like the area around ʻeach_item, but it can't be helped. I'm not used to defining my own method of yield` or block arguments yet.

so. I ported this to python below:

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

I was confused about using python yield for the first time in my life, but it felt the same.

Recommended Posts

Offline real-time how to write E11 ruby and python implementation example
Offline real-time how to write Python implementation example of E14
Offline real-time how to write Python implementation example of E15 problem
How to write offline real-time Solving E05 problems with Python
Answer to "Offline Real-time How to Write E13 Problem"
20th Offline Real-time How to Write Problems in Python
How to write Ruby to_s in Python
The 15th offline real-time how to write reference problem in Python
How to write offline real time Solve E04 problems in Python
Difference in how to write if statement between ruby ​​and python
The 14th offline real-time how to write reference problem in python
The 18th offline real-time how to write reference problem in Python
Answer to "Offline real-time how to write F02 problem"
Answer to "Offline Real-time How to Write F01 Problem"
The 17th offline real-time how to write reference problem implemented in Python
How to write the correct shebang in Perl, Python and Ruby scripts
How to write offline real time I tried to solve E11 with python
The 16th offline real-time how to write reference problem to solve with Python
The 19th offline real-time how to write reference problem to solve with Python
The 15th offline real-time how to write problem was solved with python
How to write offline real time I tried to solve E12 with python
[Python] How to split and modularize files (simple, example)
The 15th offline real-time I tried to solve the problem of how to write with python
13th Offline Real-time How to Solve Writing Problems in Python
How to write a metaclass that supports both python2 and python3
How to call Python or Julia from Ruby (experimental implementation)
[Python / Ruby] Understanding with code How to get data from online and write it to CSV
The 17th Offline Real-time How to Solve Writing Problems in Python
The 10th offline real-time writing reference problem. Implementation example by Python.
The 11th offline real-time writing reference problem. Implementation example by python.
How to write offline real time Solve F01 problems with Python
How to package and distribute Python scripts
How to install and use pandas_datareader [Python]
How to write Python document comments (Docstrings)
Answer to "Offline Real-Time Writing E12 Problem"
python: How to use locals () and globals ()
[Python] How to calculate MAE and RMSE
How to use Python zip and enumerate
Compress python data and write to sqlite
How to use is and == in Python
How to write pydoc and multi-line comments
How to enjoy programming with Minecraft (Ruby, Python)
How to generate permutations in Python and C ++
[Python] How to read data from CIFAR-10 and CIFAR-100
How to convert SVG to PDF and PNG [Python]
[Python] How to use hash function and tuple.
How to write async and await in Vue.js
How to plot autocorrelation and partial autocorrelation in python
Part 1 I wrote an example of the answer to the reference problem of how to write offline in real time in Python
[Python] [Django] How to use ChoiceField and how to add options
How to install Python
[Python] How to write type annotations for Callable objects treated as variables and arguments
How to write string concatenation in multiple lines in Python
Ruby, Python and map
How to install python
How to write a list / dictionary type of Python3
Python and Ruby split
It's not easy to write Python, it's easy to write numpy and scipy
Write tests in Python to profile and check coverage
[Python] How to write a docstring that conforms to PEP8
[Note] How to write QR code and description in the same image with python