Friday, December 26, 2014

adctf2014 - Reversing - Day 6 paths

There are many paths, and search for shortest path from start to goal.

(to, cost)

http://adctf2014.katsudon.org/dat/UEwowIeASXiLxJEN/paths.py




paths.sys contains the following source:


import sys

E = [[(96, 65)], [(64, 99), (82, 120), (3, 100), (19, 87), (51, 85), (96, 112), (85, 108), (87, 98), (16, 57), (80, 98), (55, 115), (9, 68), (46, 87), (90, 57), (56, 57), (0, 118), (57, 66), (7, 70), (27, 120), (18, 110), (75, 110), (20, 114), (72, 104), (30, 109), (58, 111), (4, 65), (37, 79), (45, 112)], [(24, 88), (91, 67), (58, 112), (13, 52), (72, 70), (15, 97), (36, 75), (52, 71), (31, 78), (76, 109), (26, 78), (29, 101), (32, 109), (65, 117), (22, 53), (96, 119), (30, 77), (2, 77), (6, 115), (71, 122)], [(75, 48), (21, 80), (32, 119), (61, 48), (13, 57), (82, 97), (55, 88), (50, 121), (77, 83), (70, 114), (96, 83), (38, 72), (74, 51), (34, 80), (28, 102), (78, 116), (66, 53), (89, 107), (11, 54), (54, 100), (48, 72), (64, 112), (76, 104)], [(63, 66), (49, 55), (80, 79), (31, 122), (1, 67), (6, 89), (86, 100), (57, 49), (29, 67), (20, 81), (97, 48), (44, 70), (8, 73), (85, 100)], [(38, 55), (5, 119), (97, 68), (10, 72), (11, 106), (35, 106), (73, 83), (17, 115), (7, 106), (60, 52)], [(98, 113), (82, 52), (38, 118), (15, 48), (63, 97), (47, 120), (73, 89), (58, 67), (67, 78), (9, 75), (70, 78), (7, 83)], [(99, 104), (22, 77), (79, 51)], [(46, 72), (42, 79), (57, 51), (59, 89), (41, 90), (19, 75), (14, 88), (33, 86), (13, 107), (20, 121), (48, 115), (45, 99), (25, 54)], [(22, 108), (58, 83), (67, 50), (17, 105), (5, 112), (84, 88), (1, 120), (20, 119), (50, 106), (87, 51), (25, 118), (40, 54), (16, 120), (75, 122)], [(28, 65), (83, 119), (84, 48), (6, 84), (68, 87), (87, 72), (12, 88), (30, 72), (34, 68), (16, 103), (5, 68), (89, 116), (95, 82), (44, 88), (77, 114), (41, 49), (55, 79), (14, 87), (23, 90), (81, 76), (27, 106), (60, 76)], [(36, 74), (15, 69), (16, 49), (85, 83), (53, 118), (91, 52), (31, 76), (28, 82), (3, 55), (89, 86), (47, 68)], [(87, 110), (62, 89), (27, 114), (5, 51), (37, 120), (91, 65), (74, 72), (42, 75), (29, 112), (52, 69)], [(64, 72), (58, 73), (37, 116), (2, 66), (30, 48), (17, 69), (73, 67), (97, 82), (93, 48), (24, 71), (26, 51)], [(98, 52), (43, 100), (71, 98), (51, 56), (66, 95), (52, 75), (29, 65)], [(29, 100), (60, 71), (12, 115), (86, 66), (43, 73), (22, 84), (55, 50), (70, 109), (8, 101), (49, 89), (54, 108), (17, 100), (96, 52), (88, 66), (87, 111), (14, 95), (72, 68), (36, 66), (65, 107), (23, 55), (79, 106), (62, 68), (25, 100), (10, 122), (33, 56), (97, 82), (51, 67), (68, 68)], [(17, 66), (56, 51), (76, 73), (18, 100), (26, 65), (9, 95), (77, 76), (5, 118), (72, 102), (53, 105), (44, 105), (38, 108), (80, 101), (83, 115), (59, 80), (58, 107), (27, 103)], [(89, 85), (81, 49), (41, 85), (52, 121), (59, 87), (96, 117), (10, 70), (2, 101), (68, 99)], [(46, 48), (18, 110), (72, 79)], [(85, 98), (84, 65), (27, 56), (82, 54), (90, 112), (91, 85), (46, 65), (44, 87), (32, 82), (50, 115)], [(29, 102), (72, 97), (82, 80), (4, 83), (41, 68), (5, 73), (71, 104), (2, 78), (70, 68), (88, 121), (26, 56), (56, 117), (25, 82), (15, 85), (67, 106), (8, 108), (38, 80), (10, 73), (77, 111), (28, 72), (66, 71), (24, 73), (30, 85), (42, 57), (61, 102), (60, 110), (31, 51), (96, 82)], [(44, 66), (56, 75), (9, 89), (30, 69), (35, 78), (10, 65), (28, 79), (68, 51), (37, 111), (72, 88), (81, 102), (11, 111)], [(22, 105), (89, 105), (96, 104), (92, 103)], [(83, 97), (16, 86), (37, 67), (70, 117), (56, 83), (2, 65), (68, 85), (88, 70), (50, 54), (31, 68), (18, 115), (42, 79), (90, 48), (92, 88), (86, 86), (6, 68), (55, 119), (3, 111), (64, 56), (72, 101), (24, 52), (22, 72), (0, 106), (53, 50), (34, 106)], [(19, 108), (9, 87), (25, 112), (37, 48), (54, 82), (87, 118), (15, 101), (56, 75), (46, 102), (61, 54), (92, 115), (78, 97), (85, 106), (65, 49), (30, 68), (96, 65), (58, 65), (47, 117), (88, 74), (1, 73), (64, 86), (74, 115), (81, 79), (83, 103), (89, 113), (82, 66), (21, 104), (24, 55)], [(40, 80), (85, 55), (97, 77), (30, 89), (72, 71), (58, 68), (22, 56)], [(48, 74), (77, 49), (18, 119), (41, 78), (90, 112)], [(53, 107), (58, 82), (83, 71), (4, 82), (3, 115), (56, 122), (40, 68), (54, 108), (78, 81), (24, 53), (0, 72), (82, 118), (59, 54), (62, 89), (48, 79), (73, 120), (92, 110), (36, 55), (44, 81), (45, 98), (30, 51), (10, 50)], [(9, 120), (92, 49), (82, 68), (76, 86), (11, 80), (60, 78), (29, 120), (0, 102)], [(59, 67), (80, 113), (52, 110), (68, 75), (32, 106), (86, 98), (39, 55), (89, 103), (29, 111), (50, 68), (76, 102), (63, 80), (43, 90), (37, 83), (5, 48), (51, 79), (7, 118), (46, 49), (73, 67), (78, 89), (49, 67), (90, 51)], [(79, 95), (58, 115), (30, 115), (87, 55)], [(91, 122), (18, 113), (2, 105), (89, 110), (10, 111), (15, 117), (24, 119), (53, 114), (59, 87), (51, 115), (78, 70), (46, 70), (82, 95), (1, 102), (31, 87), (81, 57), (61, 75), (66, 77), (52, 121), (95, 79), (22, 100), (42, 83), (25, 52), (16, 67)], [(73, 107)], [(75, 84), (71, 78), (15, 99), (33, 99), (45, 113), (89, 65), (53, 101), (70, 85), (64, 100), (81, 73), (62, 72), (12, 101)], [(3, 119), (43, 86), (41, 90), (30, 76), (24, 67), (9, 80), (68, 111), (10, 121), (79, 117), (83, 108), (45, 83), (94, 67), (26, 102), (62, 79)], [(94, 51), (85, 69), (96, 74)], [(19, 97), (60, 48), (6, 100)], [(77, 117), (66, 119), (91, 112), (93, 72), (98, 89), (33, 69), (86, 110), (40, 54), (54, 100), (10, 77), (48, 99), (16, 109), (76, 72), (65, 74), (41, 90), (90, 82), (18, 69), (61, 114), (59, 56), (85, 101), (46, 81), (83, 69), (53, 50), (56, 101), (49, 79), (2, 54)], [(85, 52), (48, 95), (55, 118)], [(24, 72), (6, 72), (77, 97), (36, 82), (26, 65), (37, 90), (54, 118), (41, 51), (8, 121), (85, 105), (38, 72), (46, 80), (15, 105), (80, 111), (65, 122), (86, 73), (1, 75), (97, 89), (53, 82), (64, 53), (35, 95), (30, 104)], [(30, 121), (92, 73), (22, 69), (18, 69), (41, 97)], [(35, 67), (70, 86), (97, 69), (7, 84)], [(21, 110), (26, 107), (73, 115), (93, 71), (67, 104), (80, 110), (35, 68), (41, 87), (7, 108), (90, 53), (76, 114), (69, 65), (86, 101), (70, 87), (94, 53), (42, 70)], [(29, 75), (55, 102), (2, 82), (82, 105), (92, 56), (26, 122), (27, 105), (7, 66), (58, 108)], [(35, 53), (28, 69), (91, 102), (21, 83), (89, 71), (41, 108), (69, 100), (94, 77), (25, 70), (93, 53), (50, 85), (6, 87), (34, 86), (85, 84), (38, 79), (12, 82), (57, 53), (72, 66), (11, 115), (79, 112), (83, 108)], [(1, 57), (7, 87), (49, 67), (77, 104), (73, 87), (14, 99), (41, 79), (63, 109), (64, 55)], [(72, 101), (18, 109), (22, 95)], [(44, 68), (26, 98), (71, 100), (10, 84), (2, 75), (39, 107), (76, 103), (77, 65), (14, 101), (19, 69), (62, 120), (86, 101), (34, 57), (18, 74), (90, 121), (7, 56), (83, 105), (56, 109), (69, 51), (60, 104), (96, 100)], [(44, 72), (37, 89), (95, 77), (66, 72), (52, 65), (27, 118), (14, 120), (82, 57), (67, 118), (55, 88), (49, 82), (48, 65), (59, 117), (30, 84), (7, 104), (92, 102), (26, 115), (16, 121), (3, 87), (34, 81), (77, 53)], [(80, 86), (77, 75), (28, 122), (0, 121)], [(28, 84), (44, 74), (86, 108), (54, 97), (7, 51), (52, 98), (79, 49), (55, 109), (98, 72), (32, 52), (12, 115), (23, 112), (29, 106), (42, 86), (92, 112), (84, 90), (78, 120), (0, 110), (59, 118), (90, 83), (34, 78)], [(96, 55), (6, 86), (1, 99), (60, 82), (90, 69), (24, 51), (27, 48), (17, 102), (15, 75), (71, 114), (0, 74)], [(65, 89), (74, 102)], [(90, 49), (89, 100), (86, 88), (79, 50), (0, 90), (71, 82), (75, 69), (85, 101), (88, 88), (53, 108), (81, 70), (67, 111), (56, 109), (40, 55), (55, 56), (14, 68), (2, 97), (35, 54), (48, 105), (11, 122), (43, 103), (23, 57), (61, 49), (95, 53), (68, 52), (7, 111), (62, 116), (59, 52), (46, 52)], [(47, 84)], [(31, 119), (80, 53), (13, 57), (33, 83), (63, 68), (85, 116), (35, 103), (87, 82), (32, 54), (92, 89), (56, 115)], [(88, 66), (79, 100), (25, 69)], [(61, 110), (73, 103), (17, 77), (14, 66), (88, 103), (45, 82), (32, 56), (79, 50), (92, 106), (60, 87), (3, 73), (87, 81), (44, 79)], [(82, 114)], [(74, 53)], [(34, 89), (64, 114), (80, 71), (83, 53), (68, 98), (60, 115), (82, 70), (88, 119), (28, 52), (62, 74), (11, 100), (25, 87), (59, 52), (95, 79)], [(6, 80)], [(0, 122), (95, 51), (48, 53), (59, 108)], [(41, 77), (58, 55), (57, 50), (59, 121), (68, 77), (93, 48), (80, 113), (9, 76), (21, 66), (96, 66), (79, 89), (32, 86), (55, 78), (31, 116), (47, 97), (15, 90), (82, 80)], [(55, 76), (95, 75), (15, 86), (17, 83), (53, 55), (2, 81)], [(55, 118), (71, 87), (20, 79), (69, 99), (97, 56), (12, 79), (56, 87)], [(18, 89), (86, 117), (66, 77), (4, 85), (7, 66), (47, 114), (88, 71), (16, 86), (77, 75), (95, 112), (19, 104), (48, 65), (96, 78), (51, 54), (81, 81), (41, 66), (11, 116), (33, 115), (13, 54), (87, 57), (10, 89), (68, 104), (53, 78), (12, 51), (8, 115), (59, 56), (5, 113), (57, 108), (14, 107), (82, 70)], [(63, 67), (59, 81), (58, 85)], [(66, 110), (25, 85), (85, 69), (40, 80), (94, 90), (10, 113), (68, 70), (47, 53), (87, 68), (52, 78), (80, 107), (55, 70), (30, 108), (58, 73)], [(96, 116), (89, 95)], [(69, 70)], [(57, 107), (58, 82), (77, 86), (36, 107), (11, 111), (84, 108), (29, 75), (5, 100), (43, 119), (13, 104), (69, 121), (25, 85), (68, 51), (93, 89), (76, 98), (49, 69), (23, 90), (90, 99), (78, 79), (3, 87), (87, 122), (15, 121), (18, 71)], [(70, 84)], [(58, 48), (36, 83), (0, 97), (65, 74), (90, 111)], [(69, 112), (79, 108), (97, 104)], [(12, 102), (88, 102), (62, 49), (5, 105), (36, 67), (38, 72), (44, 115), (47, 79), (86, 69), (30, 88), (20, 83), (89, 95), (25, 119), (65, 55), (75, 110), (93, 72), (21, 98), (54, 80), (90, 52), (69, 72), (15, 70), (40, 71), (32, 86), (14, 113), (71, 117)], [(17, 73), (31, 104)], [(51, 117), (5, 52), (11, 100), (16, 117), (80, 70), (85, 67)], [(94, 95), (14, 55), (59, 76)], [(70, 107), (79, 48), (59, 95)], [(50, 76), (72, 50), (64, 72), (7, 85), (77, 112), (3, 106), (91, 115), (55, 55), (57, 55), (49, 54)], [(76, 82), (83, 107), (4, 122), (79, 68), (59, 81), (34, 73), (14, 69), (30, 81), (10, 103), (67, 54), (50, 52), (54, 122), (7, 90), (97, 110), (2, 67)], [(58, 77), (94, 55), (35, 55)], [(23, 65), (41, 52), (48, 76), (83, 99), (26, 116), (16, 76), (57, 121), (2, 100), (18, 53), (87, 53), (21, 66), (66, 108), (72, 88), (91, 103), (63, 105), (9, 89), (11, 102), (67, 72), (96, 101), (1, 55), (39, 108), (28, 108), (12, 72), (54, 55), (89, 105)], [(85, 108), (88, 54), (22, 68), (59, 49)], [(30, 53), (35, 99), (79, 107), (46, 109)], [(61, 121), (22, 121), (91, 119), (2, 77), (71, 78), (66, 48), (14, 116), (79, 82)], [(69, 103), (87, 113), (82, 105), (25, 95), (18, 116), (70, 118)], [(79, 86), (32, 115), (51, 66), (96, 112), (52, 114)], [(72, 122), (18, 71), (96, 106)], [(46, 79), (76, 82), (61, 57), (69, 107), (18, 110), (96, 114), (82, 110)], [(66, 105), (41, 114), (62, 77), (59, 68), (50, 81), (92, 77), (19, 106), (43, 97), (20, 67), (40, 56), (55, 102), (76, 103), (47, 74), (37, 100), (88, 65), (39, 71), (16, 83), (35, 110), (14, 115), (94, 80), (22, 49), (81, 103), (0, 83), (65, 73), (70, 112), (17, 116), (77, 57), (7, 67)], [(79, 111)], [(75, 70), (33, 120), (24, 87), (93, 54), (83, 106), (1, 68), (49, 100), (30, 51), (90, 55), (12, 50), (29, 118), (80, 121), (21, 86), (66, 115), (45, 85), (56, 83), (91, 65), (67, 105), (78, 105), (88, 122), (87, 99), (0, 108), (94, 95), (79, 67), (76, 69), (46, 82), (84, 97), (3, 79), (5, 108)], [(72, 67)], [(41, 65), (42, 98), (36, 108), (82, 113), (37, 101), (18, 115), (9, 105), (77, 102), (34, 111), (83, 86), (70, 73)], [(94, 68)], [(58, 79), (79, 57)], [(67, 50), (19, 107), (93, 51), (69, 74), (60, 118), (46, 77), (2, 90), (86, 66), (84, 51), (30, 118), (32, 56), (63, 86), (51, 97), (98, 103)], []]

start = 0
goal = 99
shortest = 2014

past = []
from_ = start
for to in map(int, sys.argv[1:]):
    for e in E[from_]:
        if e[0] == to:
            past.append(e[1])
            break
    else:
        sys.exit(1)
    from_ = to
    if to == goal:
        if sum(past) == shortest:
            print 'the flag is: ' + ''.join(chr(c) for c in past)


I'm not sure why this was categorized as a reversing challenge, as the codes there in easy to read python. Seems more like a PPC challenge to me. 

There's an array of arrays. The inner arrays contain destination-cost pairs. The destination is both the decimal equivalent of a character of the flag and the next inner array to work with. The cost is amount that "moving" to that destination array is valued. The goal is to get to the final inner array (#99) with the total cost equaling 2014 (apparently the shortest route happens to be 2014 cost).

I guess we could do some college CompSci stuff here, but I'm lazy. Lets just build a recursive function that tries the first possible path, if the cost hits 2014 before reaching the goal, it rewinds up a level and tries the next option, until all options have been exhausted. Basically its a depth-first search algo...dang it, they tricked me into doing CompSci stuff :(

import sys

E = [[(96, 65)], [(64, 99), (82, 120), (3, 100), (19, 87), (51, 85), (96, 112), (85, 108), (87, 98), (16, 57), (80, 98), (55, 115), (9, 68), (46, 87), (90, 57), (56, 57), (0, 118), (57, 66), (7, 70), (27, 120), (18, 110), (75, 110), (20, 114), (72, 104), (30, 109), (58, 111), (4, 65), (37, 79), (45, 112)], [(24, 88), (91, 67), (58, 112), (13, 52), (72, 70), (15, 97), (36, 75), (52, 71), (31, 78), (76, 109), (26, 78), (29, 101), (32, 109), (65, 117), (22, 53), (96, 119), (30, 77), (2, 77), (6, 115), (71, 122)], [(75, 48), (21, 80), (32, 119), (61, 48), (13, 57), (82, 97), (55, 88), (50, 121), (77, 83), (70, 114), (96, 83), (38, 72), (74, 51), (34, 80), (28, 102), (78, 116), (66, 53), (89, 107), (11, 54), (54, 100), (48, 72), (64, 112), (76, 104)], [(63, 66), (49, 55), (80, 79), (31, 122), (1, 67), (6, 89), (86, 100), (57, 49), (29, 67), (20, 81), (97, 48), (44, 70), (8, 73), (85, 100)], [(38, 55), (5, 119), (97, 68), (10, 72), (11, 106), (35, 106), (73, 83), (17, 115), (7, 106), (60, 52)], [(98, 113), (82, 52), (38, 118), (15, 48), (63, 97), (47, 120), (73, 89), (58, 67), (67, 78), (9, 75), (70, 78), (7, 83)], [(99, 104), (22, 77), (79, 51)], [(46, 72), (42, 79), (57, 51), (59, 89), (41, 90), (19, 75), (14, 88), (33, 86), (13, 107), (20, 121), (48, 115), (45, 99), (25, 54)], [(22, 108), (58, 83), (67, 50), (17, 105), (5, 112), (84, 88), (1, 120), (20, 119), (50, 106), (87, 51), (25, 118), (40, 54), (16, 120), (75, 122)], [(28, 65), (83, 119), (84, 48), (6, 84), (68, 87), (87, 72), (12, 88), (30, 72), (34, 68), (16, 103), (5, 68), (89, 116), (95, 82), (44, 88), (77, 114), (41, 49), (55, 79), (14, 87), (23, 90), (81, 76), (27, 106), (60, 76)], [(36, 74), (15, 69), (16, 49), (85, 83), (53, 118), (91, 52), (31, 76), (28, 82), (3, 55), (89, 86), (47, 68)], [(87, 110), (62, 89), (27, 114), (5, 51), (37, 120), (91, 65), (74, 72), (42, 75), (29, 112), (52, 69)], [(64, 72), (58, 73), (37, 116), (2, 66), (30, 48), (17, 69), (73, 67), (97, 82), (93, 48), (24, 71), (26, 51)], [(98, 52), (43, 100), (71, 98), (51, 56), (66, 95), (52, 75), (29, 65)], [(29, 100), (60, 71), (12, 115), (86, 66), (43, 73), (22, 84), (55, 50), (70, 109), (8, 101), (49, 89), (54, 108), (17, 100), (96, 52), (88, 66), (87, 111), (14, 95), (72, 68), (36, 66), (65, 107), (23, 55), (79, 106), (62, 68), (25, 100), (10, 122), (33, 56), (97, 82), (51, 67), (68, 68)], [(17, 66), (56, 51), (76, 73), (18, 100), (26, 65), (9, 95), (77, 76), (5, 118), (72, 102), (53, 105), (44, 105), (38, 108), (80, 101), (83, 115), (59, 80), (58, 107), (27, 103)], [(89, 85), (81, 49), (41, 85), (52, 121), (59, 87), (96, 117), (10, 70), (2, 101), (68, 99)], [(46, 48), (18, 110), (72, 79)], [(85, 98), (84, 65), (27, 56), (82, 54), (90, 112), (91, 85), (46, 65), (44, 87), (32, 82), (50, 115)], [(29, 102), (72, 97), (82, 80), (4, 83), (41, 68), (5, 73), (71, 104), (2, 78), (70, 68), (88, 121), (26, 56), (56, 117), (25, 82), (15, 85), (67, 106), (8, 108), (38, 80), (10, 73), (77, 111), (28, 72), (66, 71), (24, 73), (30, 85), (42, 57), (61, 102), (60, 110), (31, 51), (96, 82)], [(44, 66), (56, 75), (9, 89), (30, 69), (35, 78), (10, 65), (28, 79), (68, 51), (37, 111), (72, 88), (81, 102), (11, 111)], [(22, 105), (89, 105), (96, 104), (92, 103)], [(83, 97), (16, 86), (37, 67), (70, 117), (56, 83), (2, 65), (68, 85), (88, 70), (50, 54), (31, 68), (18, 115), (42, 79), (90, 48), (92, 88), (86, 86), (6, 68), (55, 119), (3, 111), (64, 56), (72, 101), (24, 52), (22, 72), (0, 106), (53, 50), (34, 106)], [(19, 108), (9, 87), (25, 112), (37, 48), (54, 82), (87, 118), (15, 101), (56, 75), (46, 102), (61, 54), (92, 115), (78, 97), (85, 106), (65, 49), (30, 68), (96, 65), (58, 65), (47, 117), (88, 74), (1, 73), (64, 86), (74, 115), (81, 79), (83, 103), (89, 113), (82, 66), (21, 104), (24, 55)], [(40, 80), (85, 55), (97, 77), (30, 89), (72, 71), (58, 68), (22, 56)], [(48, 74), (77, 49), (18, 119), (41, 78), (90, 112)], [(53, 107), (58, 82), (83, 71), (4, 82), (3, 115), (56, 122), (40, 68), (54, 108), (78, 81), (24, 53), (0, 72), (82, 118), (59, 54), (62, 89), (48, 79), (73, 120), (92, 110), (36, 55), (44, 81), (45, 98), (30, 51), (10, 50)], [(9, 120), (92, 49), (82, 68), (76, 86), (11, 80), (60, 78), (29, 120), (0, 102)], [(59, 67), (80, 113), (52, 110), (68, 75), (32, 106), (86, 98), (39, 55), (89, 103), (29, 111), (50, 68), (76, 102), (63, 80), (43, 90), (37, 83), (5, 48), (51, 79), (7, 118), (46, 49), (73, 67), (78, 89), (49, 67), (90, 51)], [(79, 95), (58, 115), (30, 115), (87, 55)], [(91, 122), (18, 113), (2, 105), (89, 110), (10, 111), (15, 117), (24, 119), (53, 114), (59, 87), (51, 115), (78, 70), (46, 70), (82, 95), (1, 102), (31, 87), (81, 57), (61, 75), (66, 77), (52, 121), (95, 79), (22, 100), (42, 83), (25, 52), (16, 67)], [(73, 107)], [(75, 84), (71, 78), (15, 99), (33, 99), (45, 113), (89, 65), (53, 101), (70, 85), (64, 100), (81, 73), (62, 72), (12, 101)], [(3, 119), (43, 86), (41, 90), (30, 76), (24, 67), (9, 80), (68, 111), (10, 121), (79, 117), (83, 108), (45, 83), (94, 67), (26, 102), (62, 79)], [(94, 51), (85, 69), (96, 74)], [(19, 97), (60, 48), (6, 100)], [(77, 117), (66, 119), (91, 112), (93, 72), (98, 89), (33, 69), (86, 110), (40, 54), (54, 100), (10, 77), (48, 99), (16, 109), (76, 72), (65, 74), (41, 90), (90, 82), (18, 69), (61, 114), (59, 56), (85, 101), (46, 81), (83, 69), (53, 50), (56, 101), (49, 79), (2, 54)], [(85, 52), (48, 95), (55, 118)], [(24, 72), (6, 72), (77, 97), (36, 82), (26, 65), (37, 90), (54, 118), (41, 51), (8, 121), (85, 105), (38, 72), (46, 80), (15, 105), (80, 111), (65, 122), (86, 73), (1, 75), (97, 89), (53, 82), (64, 53), (35, 95), (30, 104)], [(30, 121), (92, 73), (22, 69), (18, 69), (41, 97)], [(35, 67), (70, 86), (97, 69), (7, 84)], [(21, 110), (26, 107), (73, 115), (93, 71), (67, 104), (80, 110), (35, 68), (41, 87), (7, 108), (90, 53), (76, 114), (69, 65), (86, 101), (70, 87), (94, 53), (42, 70)], [(29, 75), (55, 102), (2, 82), (82, 105), (92, 56), (26, 122), (27, 105), (7, 66), (58, 108)], [(35, 53), (28, 69), (91, 102), (21, 83), (89, 71), (41, 108), (69, 100), (94, 77), (25, 70), (93, 53), (50, 85), (6, 87), (34, 86), (85, 84), (38, 79), (12, 82), (57, 53), (72, 66), (11, 115), (79, 112), (83, 108)], [(1, 57), (7, 87), (49, 67), (77, 104), (73, 87), (14, 99), (41, 79), (63, 109), (64, 55)], [(72, 101), (18, 109), (22, 95)], [(44, 68), (26, 98), (71, 100), (10, 84), (2, 75), (39, 107), (76, 103), (77, 65), (14, 101), (19, 69), (62, 120), (86, 101), (34, 57), (18, 74), (90, 121), (7, 56), (83, 105), (56, 109), (69, 51), (60, 104), (96, 100)], [(44, 72), (37, 89), (95, 77), (66, 72), (52, 65), (27, 118), (14, 120), (82, 57), (67, 118), (55, 88), (49, 82), (48, 65), (59, 117), (30, 84), (7, 104), (92, 102), (26, 115), (16, 121), (3, 87), (34, 81), (77, 53)], [(80, 86), (77, 75), (28, 122), (0, 121)], [(28, 84), (44, 74), (86, 108), (54, 97), (7, 51), (52, 98), (79, 49), (55, 109), (98, 72), (32, 52), (12, 115), (23, 112), (29, 106), (42, 86), (92, 112), (84, 90), (78, 120), (0, 110), (59, 118), (90, 83), (34, 78)], [(96, 55), (6, 86), (1, 99), (60, 82), (90, 69), (24, 51), (27, 48), (17, 102), (15, 75), (71, 114), (0, 74)], [(65, 89), (74, 102)], [(90, 49), (89, 100), (86, 88), (79, 50), (0, 90), (71, 82), (75, 69), (85, 101), (88, 88), (53, 108), (81, 70), (67, 111), (56, 109), (40, 55), (55, 56), (14, 68), (2, 97), (35, 54), (48, 105), (11, 122), (43, 103), (23, 57), (61, 49), (95, 53), (68, 52), (7, 111), (62, 116), (59, 52), (46, 52)], [(47, 84)], [(31, 119), (80, 53), (13, 57), (33, 83), (63, 68), (85, 116), (35, 103), (87, 82), (32, 54), (92, 89), (56, 115)], [(88, 66), (79, 100), (25, 69)], [(61, 110), (73, 103), (17, 77), (14, 66), (88, 103), (45, 82), (32, 56), (79, 50), (92, 106), (60, 87), (3, 73), (87, 81), (44, 79)], [(82, 114)], [(74, 53)], [(34, 89), (64, 114), (80, 71), (83, 53), (68, 98), (60, 115), (82, 70), (88, 119), (28, 52), (62, 74), (11, 100), (25, 87), (59, 52), (95, 79)], [(6, 80)], [(0, 122), (95, 51), (48, 53), (59, 108)], [(41, 77), (58, 55), (57, 50), (59, 121), (68, 77), (93, 48), (80, 113), (9, 76), (21, 66), (96, 66), (79, 89), (32, 86), (55, 78), (31, 116), (47, 97), (15, 90), (82, 80)], [(55, 76), (95, 75), (15, 86), (17, 83), (53, 55), (2, 81)], [(55, 118), (71, 87), (20, 79), (69, 99), (97, 56), (12, 79), (56, 87)], [(18, 89), (86, 117), (66, 77), (4, 85), (7, 66), (47, 114), (88, 71), (16, 86), (77, 75), (95, 112), (19, 104), (48, 65), (96, 78), (51, 54), (81, 81), (41, 66), (11, 116), (33, 115), (13, 54), (87, 57), (10, 89), (68, 104), (53, 78), (12, 51), (8, 115), (59, 56), (5, 113), (57, 108), (14, 107), (82, 70)], [(63, 67), (59, 81), (58, 85)], [(66, 110), (25, 85), (85, 69), (40, 80), (94, 90), (10, 113), (68, 70), (47, 53), (87, 68), (52, 78), (80, 107), (55, 70), (30, 108), (58, 73)], [(96, 116), (89, 95)], [(69, 70)], [(57, 107), (58, 82), (77, 86), (36, 107), (11, 111), (84, 108), (29, 75), (5, 100), (43, 119), (13, 104), (69, 121), (25, 85), (68, 51), (93, 89), (76, 98), (49, 69), (23, 90), (90, 99), (78, 79), (3, 87), (87, 122), (15, 121), (18, 71)], [(70, 84)], [(58, 48), (36, 83), (0, 97), (65, 74), (90, 111)], [(69, 112), (79, 108), (97, 104)], [(12, 102), (88, 102), (62, 49), (5, 105), (36, 67), (38, 72), (44, 115), (47, 79), (86, 69), (30, 88), (20, 83), (89, 95), (25, 119), (65, 55), (75, 110), (93, 72), (21, 98), (54, 80), (90, 52), (69, 72), (15, 70), (40, 71), (32, 86), (14, 113), (71, 117)], [(17, 73), (31, 104)], [(51, 117), (5, 52), (11, 100), (16, 117), (80, 70), (85, 67)], [(94, 95), (14, 55), (59, 76)], [(70, 107), (79, 48), (59, 95)], [(50, 76), (72, 50), (64, 72), (7, 85), (77, 112), (3, 106), (91, 115), (55, 55), (57, 55), (49, 54)], [(76, 82), (83, 107), (4, 122), (79, 68), (59, 81), (34, 73), (14, 69), (30, 81), (10, 103), (67, 54), (50, 52), (54, 122), (7, 90), (97, 110), (2, 67)], [(58, 77), (94, 55), (35, 55)], [(23, 65), (41, 52), (48, 76), (83, 99), (26, 116), (16, 76), (57, 121), (2, 100), (18, 53), (87, 53), (21, 66), (66, 108), (72, 88), (91, 103), (63, 105), (9, 89), (11, 102), (67, 72), (96, 101), (1, 55), (39, 108), (28, 108), (12, 72), (54, 55), (89, 105)], [(85, 108), (88, 54), (22, 68), (59, 49)], [(30, 53), (35, 99), (79, 107), (46, 109)], [(61, 121), (22, 121), (91, 119), (2, 77), (71, 78), (66, 48), (14, 116), (79, 82)], [(69, 103), (87, 113), (82, 105), (25, 95), (18, 116), (70, 118)], [(79, 86), (32, 115), (51, 66), (96, 112), (52, 114)], [(72, 122), (18, 71), (96, 106)], [(46, 79), (76, 82), (61, 57), (69, 107), (18, 110), (96, 114), (82, 110)], [(66, 105), (41, 114), (62, 77), (59, 68), (50, 81), (92, 77), (19, 106), (43, 97), (20, 67), (40, 56), (55, 102), (76, 103), (47, 74), (37, 100), (88, 65), (39, 71), (16, 83), (35, 110), (14, 115), (94, 80), (22, 49), (81, 103), (0, 83), (65, 73), (70, 112), (17, 116), (77, 57), (7, 67)], [(79, 111)], [(75, 70), (33, 120), (24, 87), (93, 54), (83, 106), (1, 68), (49, 100), (30, 51), (90, 55), (12, 50), (29, 118), (80, 121), (21, 86), (66, 115), (45, 85), (56, 83), (91, 65), (67, 105), (78, 105), (88, 122), (87, 99), (0, 108), (94, 95), (79, 67), (76, 69), (46, 82), (84, 97), (3, 79), (5, 108)], [(72, 67)], [(41, 65), (42, 98), (36, 108), (82, 113), (37, 101), (18, 115), (9, 105), (77, 102), (34, 111), (83, 86), (70, 73)], [(94, 68)], [(58, 79), (79, 57)], [(67, 50), (19, 107), (93, 51), (69, 74), (60, 118), (46, 77), (2, 90), (86, 66), (84, 51), (30, 118), (32, 56), (63, 86), (51, 97), (98, 103)], []]

start = 0
goal = 99
shortest = 2014

def explore(i, cost, key):
  for e in E[i]:
    if (e[1]+cost <= 2014):
      if e[0] == goal:
        key=key+chr(e[1])
        print key
        sys.exit(0)
      else:
        explore(e[0], cost+e[1], key+chr(e[1]))

  return

explore(0, 0, '')

gomi@(none):~/advctf$ python paths.py
ADCTF_G0_go_5hOr7E57_PaTh


No comments:

Post a Comment