solver.py

import os
import sys
import os.path

sys.path.append('..')
sys.path.append('../..')
import argparse
import utils
import complete_home_graph_generator as chgg
import output_validator as ov
from student_utils import *
import google_solver as gs
import walking as walk

"""
# Run in terminal with "python solver.py --all "path to inputs" "path to outputs folder"
# Run in terminal with "python solver.py "path to a single input" "path to outputs folder"
# Takes less than an hour to solve and generate .out outputs for all 949 .in inputs in inputs folder
# Count number of files in a directory with :  ls -F |grep -v / | wc -l
# To create "outputs.json" file : python3 compress_output.py <path to outputs directory>

Solve is feed in a newly created complete_home_graph, not the original graph generated by input_generator.py
Step 1 : Apply the best-tsp from google on the newly created complete_home_graph(=chg), get "a list of locations
         representing the car path" using shortest_paths_between_homes
Step 2 : Optimize "the shortest possible route that visits each city and returns to the origin city" for walking
  Step 2-1 : A naive list of locations representing the car path (= the result of TSP !)
  Step 2-2 : A naive dictionary mapping drop-off location to a list of homes of TAs that got off at that particular
             location
  Step 2-3 : Whenever the path is optimized for walking, fix the naive list and the naive dictionary
"""


def finishDrop(walkDrops, homes_to_index_list, opt_path):
    for index, val in enumerate(homes_to_index_list):
        if val in opt_path:
            walkDrops[val].append(val)
    list_no_drops = []
    for i, val in enumerate(walkDrops.keys()):
        if walkDrops[val] == []:
            list_no_drops.append(val)
    for i, val in enumerate(list_no_drops):
        del walkDrops[val]
    return walkDrops


def initialRoute(not_full_route, shortest_paths_between_homes):
    not_optimized_full_route = []
    # print(" not_full_route length = " + str(len(not_full_route)))
    for i in range(len(not_full_route) - 1):
        left = not_full_route[i]
        right = not_full_route[i + 1]
        not_optimized_full_route.extend(shortest_paths_between_homes[(left, right)][:-1])
    not_optimized_full_route.append(not_optimized_full_route[0])
    # print(" * not_optimized_full: " + str(not_optimized_full_route))
    return not_optimized_full_route


def solve(original_locations, list_of_locations, list_of_homes, starting_car_location, adjacency_matrix,
          shortest_paths_between_homes, old_graph, new_starting_point_index):
    """
    Input:
        list_of_locations: A list of locations such that node i of the graph corresponds to name at index i of the list
        list_of_homes: A list of homes
        starting_car_location: The name of the starting location for the car
        shortest_paths_between_homes :
    Output:
        A list of locations representing the car path (= the result of tsp)
        A dictionary mapping drop-off location to a list of homes of TAs that got off at that particular location
            dropped off loc: TA_1 Home, TA_2 Home
            Soda : Cory
            Dwinelle : Wheeler RSF
            Campanile : Campanile
        NOTE: both outputs should be in terms of indices not the names of the locations themselves
    """
    old_name_to_index = {}
    old_index_to_name = {}

    new_index_to_name = {}
    new_name_to_index = {}

    homes_to_index_list = []

    for i in range(len(list_of_locations)):
        new_name_to_index[list_of_locations[i]] = i
        new_index_to_name[i] = list_of_locations[i]
    for i in range(len(original_locations)):
        old_name_to_index[original_locations[i]] = i
        old_index_to_name[i] = original_locations[i]

    for i in list_of_homes:
        homes_to_index_list.append(old_name_to_index[i])

    # not_full_routes, we can even get costs of Complete Graph that are calcualted by google solver
    google_routes, google_costs, google_best_index = gs.main(adjacency_matrix,
                                                             new_starting_point_index)  # EX: 0 -> 1 -> 2 -> 3 -> 0
    names_first_strats = ["AUTOMATIC", "PATH_CHEAPEST_ARC", "PATH_MOST_CONSTRAINED_ARC", "EVALUATOR_STRATEGY",
                          "SAVINGS", "SWEEP", "CHRISTOFIDES", "ALL_UNPERFORMED", "BEST_INSERTION",
                          "PARALLEL_CHEAPEST_INSERTION", "LOCAL_CHEAPEST_INSERTION", "GLOBAL_CHEAPEST_ARC",
                          "LOCAL_CHEAPEST_ARC", "FIRST_UNBOUND_MIN_VALUE"]
    names_local_strats = ["AUTOMATIC", "GREEDY_DESCENT", "GUIDED_LOCAL_SEARCH", "SIMULATED_ANNEALING", "TABU_SEARCH"]

    not_optimized_but_full_routes = {}
    # initialRoute = not_optimized_but_full_route
    for i in range(14):
        for j in range(5):
            not_optimized_but_full_routes[(i, j)] = initialRoute(google_routes[(i, j)], shortest_paths_between_homes)
    print("\n *** Full, Not-Walking-Optimized Routes in index")
    for i in range(14):
        for j in range(5):
            print(" * " + str((i, j)) + " (nodes in index): " + str(not_optimized_but_full_routes[(i, j)]))

    print("\n *** Full, Walking-Optimized Routes in index ")
    full_optimized_routes = {}
    drops = {}
    final_costs = {}
    final_messages = {}
    for i in range(14):
        for j in range(5):
            full_optimized_routes[(i, j)], drops[(i, j)] = walk.main(not_optimized_but_full_routes[(i, j)],
                                                                     homes_to_index_list)
            print(" * " + str((i, j)) + " :  (nodes in index): " + str(full_optimized_routes[(i, j)]))
            drops[(i, j)] = finishDrop(drops[(i, j)], homes_to_index_list, full_optimized_routes[(i, j)])
            final_costs[(i, j)], final_messages[(i, j)] = cost_of_solution(old_graph, full_optimized_routes[(i, j)],
                                                                           drops[(i, j)], mapping=None)

    print("\n *** Walking-Optimized Costs for the Original Graph")
    for i in range(14):
        for j in range(5):
            print(" * " + str((i, j)) + "          cost = " + str(final_costs[(i, j)]))

    # pick the best strategy result
    best_cost = final_costs[(0, 0)]
    best_index = (0, 0)
    for i in range(14):
        for j in range(5):
            if best_cost > final_costs[(i, j)]:
                best_cost = final_costs[(i, j)]
                best_index = (i, j)

    print(" ****** " + str(best_index) + " is the best after Walking Optimization\n")
    # print(drop_list[bestIndex])
    return full_optimized_routes[best_index], drops[best_index]


"""
======================================================================
   No need to change any code below this line
======================================================================
"""
"""
Convert solution with path and dropoff_mapping in terms of indices
and write solution output in terms of names to path_to_file + file_number + '.out'
"""
"""
1. The first line should be a space-separated list of location names which represents the route taken by the car in your solution
These locations should be in the order in which they are visited and the list must start and end with the starting location
defined in the corresponding input file. Locations may be repeated.
2. The second line should contain the number of drop-off locations.
3. Each line in the rest of the output file should be a list of locations,
4. the first of which corresponds to the drop-off location and
5. the rest of which correspond to the homes of the TAs who were dropped off at that location.
"""


def convertToFile(path, dropoff_mapping, path_to_file, list_locs):
    string = ''
    for node in path:
        string += list_locs[node] + ' '
    string = string.strip()
    string += '\n'

    dropoffNumber = len(dropoff_mapping.keys())
    string += str(dropoffNumber) + '\n'
    for dropoff in dropoff_mapping.keys():
        strDrop = list_locs[dropoff] + ' '
        for node in dropoff_mapping[dropoff]:
            strDrop += list_locs[node] + ' '
        strDrop = strDrop.strip()
        strDrop += '\n'
        string += strDrop
    utils.write_to_file(path_to_file, string)


def solve_from_file(input_file, output_directory, params=[]):
    print(
        "===============================================================================================================================================")
    print(' In "solve_from_file, Processing...making new complete_home_graph and feeding it to "solve"\n', input_file)
    message, error, num_of_locations, num_houses, old_list_locations, new_list_locations, list_houses, starting_car_location, \
    adjacency_matrix, shortest_paths_between_homes, complete_home_graph, old_graph, new_starting_point_index = chgg.complete_home_graph_generator_from_file(
        input_file, params=[])
    print(message)

    car_path, drop_offs = solve(old_list_locations, new_list_locations, list_houses, starting_car_location,
                                adjacency_matrix,
                                shortest_paths_between_homes, old_graph, new_starting_point_index)

    basename, filename = os.path.split(input_file)
    if not os.path.exists(output_directory):
        os.makedirs(output_directory)
    output_file = utils.input_to_output(input_file, output_directory)

    # save result as .out file
    convertToFile(car_path, drop_offs, output_file, old_list_locations)
    # outputs message if .out is not valid
    result = ov.validate_output(input_file, output_file)
    print (" *** Validate_output Message :\n " + result[3])


def solve_all(input_directory, output_directory, params=[]):
    input_files = utils.get_files_with_extension(input_directory, 'in')

    for input_file in input_files:
        solve_from_file(input_file, output_directory, params=params)


"""
# Run in terminal with "python solver.py --all "path to inputs" "path to outputs folder"
# Run in terminal with "python solver.py "path to a single input" "path to outputs folder"
# Takes less than an hour to solve and generate .out outputs for all 949 .in inputs in inputs folder
# Count number of files in a directory with :  ls -F |grep -v / | wc -l
"""
if __name__ == "__main__":
    parser = argparse.ArgumentParser(description='Parsing arguments')
    parser.add_argument('--all', action='store_true',
                        help='If specified, the solver is run on all files in the input directory. Else, it is run on just the given input file')
    parser.add_argument('input', type=str, help='The path to the input file or directory')
    parser.add_argument('output_directory', type=str, nargs='?', default='.',
                        help='The path to the directory where the output should be written')
    parser.add_argument('params', nargs=argparse.REMAINDER, help='Extra arguments passed in')
    args = parser.parse_args()
    output_directory = args.output_directory
    if args.all:
        input_directory = args.input
        solve_all(input_directory, output_directory, params=args.params)
    else:
        input_file = args.input
        solve_from_file(input_file, output_directory, params=args.params)