[Community Puzzle] Thomas and the Freight Cars

This approach will work well until it’s possible to allocate new calls on the stack. And as the number of calls grows exponentially that’s pretty easy to end up with a StackOverflow error. But for these tests, it’s quite enough.
The best in recursion + memorization solution that it’s very intuitive and performs great (when input is limited…))

1 Like

So it’s one of those time where I KNOW there is a factorial number of cases, that test case goes up to 100, and yet I still code a greedy algorithm. Like, yeah maybe 100! isn’t as much as last time I checked … :smiley:

1 Like

I do agree. A relatively simple recursion can do the trick. The problem is the execution time. I have a simple code that finds pretty well the right answer, but that cannot resolve the problem in time when it comes to the last test and I’m a stuck finding an efficient algorithm.

That’s where the dynamic programming comes.

Consider reading this section of the wikipedia article : Dynamic programming - Wikipedia

This really helped me to identify and solve the exercise :slight_smile:

Same for me, the problem is the execution time. I know that I have too much possibilities (and no recursion by the way) :frowning: It succeed till 40 cars, then it fails.

I didn’t success 100% yet. only the last test fail with my code so I’m probably not the best to reply but here is my advice:
become familiar with recursive function
then think of a code that can check every possible cases
then optimise your code with condition to skip useless cases.

Also, when the optimisation is needed, I guess the language choosen is important. I code with Js but it’s not the fastest one…