[Community puzzle] Ticket to Ride: Europe


#1

This topic is about the puzzle Ticket to Ride: Europe.

Feel free to send your feedback or ask some help here!


#2

Hi ! I enjoyed very much working on ‘Ticket to Ride : Europe’!!!

My program passed every test except the last one. Probably too slow…
I worked with Python. Is this the reason why ? Are the time-limits the same with Python ?
Or is this because my program is too slow by itself ?
Did anyone manage the puzzle with Python ?

Thank you, player_one for this wonderfull puzzle !


#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

#4

I solved it originally in go without many speed issues (~300msec for the final validator), but tried porting that solution to python. It takes around 30 seconds. I’ve optimised it enough that I can pass all the visible test cases (with about 2 seconds to spare), but a submit fails on the last validator (so I only get 94%).

It may well be that there is an efficient algorithm for solving this that I am not using, but it’s significantly easier to solve this puzzle in a faster language.

edit: I’ve managed to make mine pass all the time, but I think there could be some other test cases that may cause problems (I sort my routes based on the route score and then only calculate ticket score for about 50% of the generated routes before running out of time and just print my current best).

edit2: @player_one if you disable garbage collection (gc.disable()) your solution works every time in under 3 seconds (on the last test case) with a very consistent time. Not sure why it’s so variable with garbage collection enabled.


#5

So it does! Good to know. Thanks for pointing it out.

  • danBhentschel

#6

Great puzzle!
Made it in C++. My code solves the last testcase in 400-600ms without compiler optimisation options, and in 50-80ms with agressive optimisation.


#7

I finally understood what the problem was (nothing to do with execution time):
In some validators, there are several different routes to join the same city-pair.
I ignored that it was possible, so, my script just kept the last of these multiple city-pairs encountered. And the result was false.
Thank you again for this nice puzzle !


#8

Very nice puzzle!
I tried several different algorithms without and with optimizations.
It was spent a lot of time for me, but I don’t regret this.
Thanks to creator!


#9

Hi @player_one,

Thanks for this puzzle, it is a good challenge :slight_smile:

I am a bit stuck, my algorithm make all tests OK before submit, but after submit the test 18 become always KO.
As all is OK before submit, i really cant guess what is wrong with this test after submit, so cannot debug it.
I am so close of the goal, it is frustrating :stuck_out_tongue:

Is it possible that you tell me what are the inputs of test 18 after submit please ?


#11

Anyone passing the last test without timeout in JavaScript? Actually I have passed it, but I realized that I used an optimization that could fail in some circumstances. So I continued looking for the clean and proud solution, but after many serious optimization rounds it still timeouts.


#12

Hello,
I am not very familiar with the game itself. Is it possible to use the same routes to complete multiple tickets?
For example in the last test case I can connect Madrid and Zurich (the third ticket) if I have the routes 3 0 Black Madrid Pamplona, 4 0 Blue Pamplona Paris and 3 0 Gray Zurich Paris, where the first two of them are also part of the routes connecting Cadiz and Stockholm (3 0 Orange Cadiz Madrid, 3 0 Black Madrid Pamplona, 4 0 Blue Pamplona Paris, 3 0 White Paris Frankfurt, 2 0 Green Essen Frankfurt, 3 1 Gray Essen Kobenhavn, 3 0 White Kobenhavn Stockholm).
Following this logic I am able to complete more tickets and get more points than the suggested answer 56.

Thanks.


#13

not too familiar with the puzzle but I know the game well. Did you ensure that you complete the gray routes with cards of the same color?


#14

Hi, thanks for the reply.
These are the routes I have collected:

3 0 Orange Cadiz Madrid
3 0 Black Madrid Pamplona
4 0 Blue Pamplona Paris
3 0 White Paris Frankfurt
2 0 Green Essen Frankfurt
3 1 Gray Essen Kobenhavn
3 0 White Kobenhavn Stockholm
3 0 Gray Zurich Paris
1 0 Pink Paris Dieppe

And these are the cards I had at each step:

2 5 5 4 5 3 5 7 3
2 5 5 4 5 3 2 7 3
2 5 5 4 5 0 2 7 3
2 5 5 0 5 0 2 7 3
2 5 5 0 2 0 2 7 3
2 5 3 0 2 0 2 7 3
2 5 3 0 2 0 0 7 2
2 5 3 0 0 0 0 7 1
2 2 3 0 0 0 0 7 1
2 2 3 0 0 0 0 6 1

As far as I can see it checks out.

PS: I figured it out. I have forgotten to observe the rule of subtracting the points of tickets that were not completed.
Thanks.