Roller Coaster puzzle discussion

Puzzles
#103

Using Python3:
Solved test #9 by using dtype=float on my sums. Apparently one of my computed numbers is higher than 2**32. I guess I’m not summing efficiently. So i’m finally at 100% after a few hours of headache.

Also if it’s the only one you’re failing, it’s most likely because of the remaining values that are calculated wrong after you’ve multiplied your cycles. (The wrong formula can work for the other tests even #10)

#106

Hey peeps ! Trying to implement Tortoise and Hare Algorithm but get incorrect result for large datasets. Here’s my code:

[Mod edit: Please avoid posting codes on the forum.]

I did test it with all kinds of input data and it works but does one tests huge datasets anyways…

#108

Not all kinds of input data apparently. Please read the previous discussion, and you’ll find these cases for checking the correctness of your code.

Also, please try to describe what your code does instead of posting codes on the forum in the future.

#109

Thanks for the link @5DN1L. I have however did all kinds of testing with normal data and it works, as I have indicated in my previous post. Only when it starts to get to 10^9 problems arise.
I wanted to show my code in order for someone who has already solved the puzzle perhaps quickly pinpoint the problem. TBH I find it extremely inappropriate to not be able to post code at the coding forum. But it’s ok, I’ll post it on stackoverflow.

#110

Your code doen’t always give the correct answers for the cases with small values in the link. You should try debugging from there.

#111

@5DN1L, yes you were right I did have some errors with these specific tests. However after fixing them I still have wrong answer for the big data cases.

#112

If you want, you may send me your code in private message and I’ll take a look.

#113

This custom case may prove useful for debugging if you fail the last visible test (i.e. Test 6 “Works with a large dataset”) and the reason isn’t a timeout:

Input:

100 9 10
3
8
2
19
33
29
22
19
2
15

The output should be 724.

#114

My code works. I have even tested the “large dataset” locally. It takes between 3 to 4 sec… how fast it is supposed to be ? I read about memoization, but I’m seriously unable to get where I can apply in my code.

#115

In my first version I used shift and push with the arrays.
I already changed that and now a have a circular for.

#116

in Codingame, for a little bit more than 7000000 rides it takes more than 5s…

#117

Search memoization in this topic, and you’ll see what other players have talked about it.

#118

I did twice.

In fact. I just realized that my new code pass the large dataset of the validator but not yet the very large dataset.

And it doesn’t pass the large dataset test case

#119

So, have you done any memoization in your code?

If you do, there’s also a possibility that your calculation based on the memoization is wrong, instead of a timeout.

Try this case if you have not: https://forum.codingame.com/t/roller-coaster-puzzle-discussion/21/113

#120

apparently I don’t know how to do efficient memoization… it goes from 3s to 450s :sweat_smile:

#121

Maybe you use a human brain?

#122

:joy: I finally got it. Memoization, yes, but good method decomposing first.

#123

Juste merci !
je devenais fou :slight_smile:

#124

Je deviens fou !

J’ai appliqué l’algo de Floyd (lièvre et la tortue), puisque comme beaucoup le dernier test tombait en Time Out :slight_smile:

Du coup, tous les tests passent maintenant… Je trouve bien les cycles et calculent le résultat en conséquence et juste… Sauf pour le dernier, j’obtiens bien un résultat mais faux (89750396502599 au lieu de 89744892565569)
Et vu la tête du jeu de tests, je ne m’en sors pas pour identifier ce qui n’irait pas !

J’ai créé plusieurs cas de tests localement, il fonctionne tous…

J’aurais besoin d’aide… Y a quoi sur ce dernier test bien qu’ils soient méga volumineux ?
On est bien d’accord, la detection de cycle se fait sur la référence des wagons qui contient les groupes et non la queue des groupes ?

(J’suis en LUA)

Thx

#125

Ouf c’est bon, j’ai fini par l’avoir, mais j’avoue qu’il m’a fait saigner ! J’avais une coquille dans mon code…

Je suis juste scotché de voir les solutions des autres joueurs qui traitent le problème en 30 lignes… Chapeau !