[Community puzzle] Ticket to Ride: Europe

Puzzles
3

I’m glad you enjoyed it.

I will answer this with a qualified “yes”. I directly translated my C# solution to python3 this morning, and it timed out on the last test, just as you mention. After fiddling with it a bit, I was able to make it pass SOMETIMES. It seems that the execution time for my solution is all over the place. Here is the last several lines of my solution:

def calculate_max_score():
    st = time.perf_counter()
    max_route_list = calc_max_route_list()
    print("t1: {0}".format(time.perf_counter() - st), file=sys.stderr)
    sys.stderr.flush()
    return max( score(route) for route in max_route_list )
        
print(calculate_max_score())

the calc_max_route_list() function is definitely the most expensive part of my algorithm, but I need right around a couple seconds to calculate all the scores. My route list for the last test is just shy of 90,000 permutations

I get widely varying execution times for calc_max_route_list() when I run the test repeatedly. The puzzle times out if it the solution requires more than 6 seconds to calculate. Calls to calc_max_route_list() vary between ~ 3.5 seconds to > 6 seconds (times out before the stderr prints). When it’s closer to 3.5 seconds, my solution passes. When it takes longer, my solution times out.

I was able to get my python3 solution to pass all validators by repeatedly submitting (it only took 2 tries) so I would say that it is possible to make a python3 solution that passes this puzzle, but it’s tricky and unreliable. I haven’t nailed down why the execution times vary so much. Perhaps which physical device I happen to run on might make a difference?

All that being said, I’m sure it’s possible to optimize my solution more to make it more likely to succeed. I don’t know if I could get it fast enough to pass 100% of the time, given the current execution behavior.

  • danBhentschel
1 Like