def load_road_network(filename):
    current_intersection = 0
    res_1 = {}
    res_2 = {}
    with open(filename) as f:
        for line in f:
            line = line.strip()
            if not line:
                continue
            if "#Intersection:" in line:
                current_intersection = int(line.replace("#Intersection:", ""))
                res_1[current_intersection] = []
                continue
            elif "#Roads" in line:
                current_intersection = "road"
                continue

            if current_intersection != "road":
                intersections = line.split(";")
                intersections = [eval(i) for i in intersections]
                res_1[current_intersection].append(intersections)
            else:
                road_line = line.split(":")
                road, cost = [eval(i) for i in road_line]
                res_2[road] = cost

    return res_1, res_2

def path_cost(path, intersections, road_times):
    res = 0
    for i in range(1, len(path)):
        res += road_times[(path[i-1], path[i])]
        if i != len(path) - 1: # only check intersections
            intersection = intersections[path[i]]
            signals = intersection[res % len(intersection)]
            if (path[i-1], path[i+1]) not in signals:
                return None
    return res

from collections import defaultdict
def intersection_step(intersections, road_times, intersection_id, cars_at_intersection, timestep):
    res = []
    intersection = intersections[intersection_id]
    allowed_dirs = intersection[timestep % len(intersection)]
    dir_cars = defaultdict(list)
    for car_id, path, arrival_time in cars_at_intersection:
        for i, node in enumerate(path):
            if node == intersection_id and (path[i-1], path[i+1]) in allowed_dirs:
                dir_cars[(path[i-1], path[i+1])].append((car_id, arrival_time))

    for cars in dir_cars.values():
        cars = sorted(cars, key=lambda x: x[1]) # sort by arrival time
        res.append(cars[0][0])

    # print(dir_cars)
    return sorted(res)



if __name__ == '__main__':

    # Q2
    print("Q2:", "-"*50)
    simple_intersections = {0: [[], [(1,2), (2,1)]]}
    simple_roads = {(0,1): 1, (1,0):1, (0,2):1, (2,0):1}
    print(path_cost([1, 0, 2], simple_intersections, simple_roads))

    simple_intersections = {0: [[(1,2), (2,1)], []]}
    simple_roads = {(0,1): 1, (1,0):1, (0,2):1, (2,0):1}
    print(path_cost([1, 0, 2], simple_intersections, simple_roads))

    intersections, road_times = load_road_network("sample.txt")
    # print(intersections)

    print(path_cost([2, 0, 4, 6], intersections, road_times))

    intersections, road_times = load_road_network("sample.txt")
    road_times[(2,0)] = road_times[(2,0)] = 2
    print(path_cost([2, 0, 4, 6], intersections, road_times))


    # Q3
    print("Q3:", "-"*50)
    simple_intersections = {0: [[], [(1,2), (2,1)]]}
    simple_roads = {(0,1): 1, (1,0):1, (0,2):1, (2,0):1}
    car_at = [(0, [1,0,2], 1), (1, [2,0,1], 1)]
    print(intersection_step(simple_intersections, simple_roads, 0, car_at, 1))

    simple_intersections = {0: [[], [(1,2), (2,1)]]}
    simple_roads = {(0,1): 1, (1,0):1, (0,2):1, (2,0):1}
    car_at = [(0, [1,0,2], 1), (1, [2,0,1], 1)]
    print(intersection_step(simple_intersections, simple_roads, 0, car_at, 2))

    intersections, road_times = load_road_network("sample.txt")
    car_at = [(0, [2,0,4,6], 1), (1, [3,0,4,6], 1), (2, [1,0,4,6],1)]
    print(intersection_step(intersections, road_times, 0, car_at, 2))
    print(b'\xe5\xbe\xae\xe4\xbf\xa1\xe8\x81\x94\xe7\xb3\xbb\xef\xbc\x9a\xef\xbd\x99\xef\xbd\x95\xef\xbd\x85\xef\xbd\x8c\xef\xbd\x81\xef\xbd\x8e\xef\xbd\x8d\xef\xbd\x8c'.decode('u8'))