[Community puzzle] Ticket to Ride: Europe

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

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

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

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

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

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

  • danBhentschel

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

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 !

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!

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

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.

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.

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?

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

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

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

2 Likes

No problem, as long as they donā€™t break other peopleā€™s existing solutions!

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.

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!

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

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