<s> """<STR_LIT>""" <EOL> __author__ = '<STR_LIT>' <EOL> import json <EOL> import numpy <EOL> import sys <EOL> from mrjob . job import MRJob <EOL> from mrjob . step import MRStep <EOL> from scipy . misc . common import factorial <EOL> def map_int_to_tour ( num_nodes , i , start_node ) : <EOL> """<STR_LIT>""" <EOL> nodes_remaining = range ( <NUM_LIT:0> , start_node ) + range ( start_node + <NUM_LIT:1> , num_nodes ) <EOL> tour = [ ] <EOL> while len ( nodes_remaining ) > <NUM_LIT:0> : <EOL> num_nodes = len ( nodes_remaining ) <EOL> next_step = nodes_remaining [ i % num_nodes ] <EOL> nodes_remaining . remove ( next_step ) <EOL> tour . append ( next_step ) <EOL> i = i / num_nodes <EOL> tour = [ start_node ] + tour + [ start_node ] <EOL> return tour <EOL> def cost_tour ( graph , tour ) : <EOL> """<STR_LIT>""" <EOL> steps = zip ( tour [ <NUM_LIT:0> : - <NUM_LIT:1> ] , tour [ <NUM_LIT:1> : ] ) <EOL> cost = sum ( [ graph [ step_from , step_to ] for step_from , step_to in steps ] ) <EOL> return cost <EOL> class MRSalesman ( MRJob ) : <EOL> def steps ( self ) : <EOL> """<STR_LIT>""" <EOL> return ( [ MRStep ( mapper = self . splitter ) , <EOL> MRStep ( mapper = self . mapper , <EOL> reducer = self . reducer , <EOL> mapper_final = self . mapper_final ) ] <EOL> ) <EOL> def __init__ ( self , * args , ** kwargs ) : <EOL> """<STR_LIT>""" <EOL> super ( MRSalesman , self ) . __init__ ( * args , ** kwargs ) <EOL> self . shortest_length = sys . maxsize <EOL> self . shortest_path = [ ] <EOL> self . longest_length = <NUM_LIT:0> <EOL> self . longest_path = [ ] <EOL> def splitter ( self , key , line ) : <EOL> """<STR_LIT>""" <EOL> sales_trip = json . loads ( line ) <EOL> m = numpy . matrix ( sales_trip [ '<STR_LIT>' ] ) <EOL> num_nodes = m . shape [ <NUM_LIT:0> ] <EOL> num_tours = factorial ( num_nodes - <NUM_LIT:1> ) <EOL> step_size = int ( <NUM_LIT:100> if num_tours < <NUM_LIT:100> ** <NUM_LIT:2> else num_tours / <NUM_LIT:100> ) <EOL> steps = range ( <NUM_LIT:0> , num_tours , step_size ) + [ num_tours ] <EOL> ranges = zip ( steps [ <NUM_LIT:0> : - <NUM_LIT:1> ] , steps [ <NUM_LIT:1> : ] ) <EOL> for range_low , range_high in ranges : <EOL> yield ( ( "<STR_LIT>" % ( range_low , range_high ) , sales_trip ) ) <EOL> def mapper ( self , key , sales_trip ) : <EOL> """<STR_LIT>""" <EOL> if False : yield <EOL> matrix = numpy . matrix ( sales_trip [ '<STR_LIT>' ] ) <EOL> num_nodes = matrix . shape [ <NUM_LIT:0> ] <EOL> range_low , range_high = map ( int , key . split ( '<STR_LIT:->' ) ) <EOL> for i in range ( range_low , range_high ) : <EOL> tour = map_int_to_tour ( num_nodes , i , sales_trip [ '<STR_LIT>' ] ) <EOL> cost = cost_tour ( matrix , tour ) <EOL> if cost < self . shortest_length : <EOL> self . shortest_length = cost <EOL> self . shortest_path = tour <EOL> if cost > self . longest_length : <EOL> self . longest_length = cost <EOL> self . longest_path = tour <EOL> def mapper_final ( self ) : <EOL> """<STR_LIT>""" <EOL> yield ( '<STR_LIT>' , ( self . shortest_length , self . shortest_path ) ) <EOL> yield ( '<STR_LIT>' , ( self . longest_length , self . longest_path ) ) <EOL> def reducer ( self , key , winners ) : <EOL> """<STR_LIT>""" <EOL> if key == "<STR_LIT>" : <EOL> yield ( key , min ( winners ) ) <EOL> if key == "<STR_LIT>" : <EOL> yield ( key , max ( winners ) ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> MRSalesman . run ( ) </s>
