[Community puzzle] Ticket to Ride: Europe

Puzzles
#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 !

1 Like
#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
#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.

2 Likes
#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.

1 Like
#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 ?

1 Like
#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.

1 Like
#15

Completed this puzzle, but added a couple of my own test cases along the way to expose problems in earlier versions of my solver that didn’t get spotted in the test cases. I’ll share them here.
I don’t know if you need them to solve the confirmation puzzles (in my case, I just needed to be quicker, not better) but they provide some interesting extra cases.

// Check that we don’t kipper our colour allocation by using the
// important colour on the wrong route, so it’s not available later
6 1 2
4 2 0 0 0 0 0 0 0
3 Dieppe Brighton
2 0 Gray Dieppe London
4 0 Gray London Brighton
12

// Check that we still don’t kipper our colour allocation
// If a later route uses a colour we would otherwise have already used
// (so we must replan the whole of our layout, we can’t just go step by step)
4 2 3
2 1 0 0 0 0 0 0 1
15 Dieppe London
5 London Brighton
2 0 Gray Dieppe London
2 0 Red London Brighton
1 0 Yellow Nowhere DoesntMatter
24

// A long ticket that is a trap - if you take it you can’t get the more
// lucrative two shorter routes
// 2 points for long route, 5 for all the short ones.
4 4 3
3 0 0 0 0 0 0 0 0
3 Manchester London
2 Dieppe Paris
2 Lille Paris
1 Dieppe Lille
3 0 Red Manchester London
2 0 Red Dieppe Paris
1 0 Red Paris Lille
5

// A routes-only board where the long route is a trap
// which prevents you scoring two shorter routes
6 0 3
6 0 0 0 0 0 0 0 0
4 0 Red Manchester London
3 0 Red Dieppe Paris
3 0 Red Paris Luton
8

// A routes-only board where one of the middle value routes is a trap
// which prevents you scoring more on two shorter routes
12 0 4
6 6 0 0 0 0 0 0 0
6 0 Yellow Bodmin Wenford
4 0 Red Manchester London
3 0 Red Dieppe Paris
3 0 Red Paris Luton
23

#16

I’ll add them to the puzzle so they can help others too if you’re ok with that @codeingame

2 Likes
#17

No problem, as long as they don’t break other people’s existing solutions!

#18

My solution’s fine with them. The author’s solution is fine with them. So it would be allright if…

the author’s solution still passed its own tests.

It now times out on test/validator “Oh, the possibilities”. Most likely because of the hardware update some time ago.

If @player_one or anyone who feels like improving his C# could chime in, that would be appreciated.

#19

While we’re there, it would help if the ‘Oh, the possibilities’ validator was similar but slightly simpler than the ‘Oh, the possibilities’ test.
There’s nothing more frustrating than getting all the tests to green and then have the validator time out because it’s more complex than what you’ve been working on!

#20

I’ve updated the puzzle to include your tests, replacing the author’s solution with my own.
I also switched the last test and validator as you suggested.
But more importantly the puzzle now has an image :upside_down_face:

2 Likes
#21

Continuing the discussion from [Community puzzle] Ticket to Ride: Europe:

Hi,
This is a really nice puzzle! I thought I had solved it because I can play all test cases (and the last one only takes about 15 ms on my laptop), but then I submitted the solution and it turns out that I have case 16 and the last 2 cases wrong. Are the submit-solution cases different from the test cases? If so, would it be possible to add one to the test cases? That would be of great help. Thanks!
Nele