[Community Puzzle] Thomas and the Freight Cars

Puzzles
#1

https://www.codingame.com/training/hard/thomas-and-the-freight-cars

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @Djoums,@TeddyS and @icecuber.
If you have any issues, feel free to ping them.

#2

loved it. very satisfying organizational problem. @java_coffee_cup

#3

Hi, is there a way to get the solution if I’m stuck? Thanks!

#4

I can not think of an algorithm to do this. Does anyone have any help? Can I search the internet for something? I love codingame, but sometimes it’s so out there, that I feel like I can’t learn. I don’t want the solution, but ways of thinking.

I’ve tried a few ways, like “if this is bigger or smaller” add it here and so on.
But it seems that my ideas get broken if say 2 in a row don’t make sense.
Or i end up over deleting “good ones” cause something too high or low get’s added. So i’m guessing i need recursion of some sort, to dig deeper, but i don’t know any algorithms or way of thinking to solve this at all.

If the problem had better tags, I would know what to look up to figure out.

3 Likes
#5

This puzzle is hard so it is classified as “Hard”.
Hard puzzles are intended for challenging people more than educating. Hard puzzles are like hot spicy food that people like it just because it burns their tongues heavily.

So, if you really want a hint to spoil the fun of engaging in a critical challenge, go on to click below…

spoiler

It is somehow related to the idea of Longest increasing subsequence

But this puzzle is trickier than that. Direct implementation of the algorithm cannot solve it. You need to thoroughly understand the standard algorithm and modify it to fit for a specific applications.

2 Likes
#6

Since all the cars are given in sequential order, a simple approach is to go car by car and compute what you get if you take the car, and if you don’t. With recursion and a good memoization structure it is enough to solve this problem.

1 Like
#7

I have solved a few hard puzzles. To me this entire site is about learning, practicing etc… recursion is something i’m not very good at so this helps a ton. It may feel cheaty to you, and direct answers are. But understanding where to locate and get the math behind things, and then implementing it isn’t cheaty.

1 Like
#8

This puzzle is driving me insane. I can not figure it out. I have found a good formula to find all the decreasing objects, and all the increasing objects. But the problem is they may include eachother in my calculation. So they need to exclude eachother.

#9

My approach is using lis and lds. It is harder to explain and understand but can be more efficient and can handle much longer inputs. If you like this approach you have to explore it further by yourself.

@Djoums approach, I have not tried it, should be more intutitive.

When each car comes, you have two choices only: take it, or drop it.
So it is like a binary tree which has 2 branches under each node.

By brute force to try out each branch, by memorization to retain the intermediate results, by early pruning to cut off unnecessary deeper search, it could be good enough to handle input length of 100, I guess.

1 Like
#10

I was really close, and figured it out, instead of climbing up in my numbers, i needed to climb down.
my loops were backwards basically. But reversing them, it allowed for me to find the best from the end, instead of the beginning. Thank you for ALL YOUR HELP! I really appreciate it!

#11

I don’t know how far this simple method can go, but the last test (100 cars) is practically instantaneous.
I can send you the code by PM if you want to test it.

#12

Sounds like the dp approach is promising. I wish to try it out as an exercise later. Too little opportunities to apply these skills in real jobs.

#13

I tried to solve it using creating a tree. I removed all that was not needed with the goal to keep the tree as small as possible. But it failes in IDE at 100 and in the validators at 40 and 100.

Could someone give me a hint where I could optimize the tree creation more. (commenting out the calculation of the longest will still result in a timeout. so I think my tree is too big)

Or is my whole idea with a tree the wrong approach?

Spoiler: My attempt in JavaScript 
class Node {
    constructor(wagons, length, first, last) {
        this.wagons = wagons // string with the numbers eg: 15;3;2
        this.first = first // 15
        this.last = last   // 2
        this.children = [] // will hold further Nodes
        this.length = length
    }

    addWagon(wagon) {
        this.children.forEach(e => e.addWagon(wagon)) // every child should add it's nodes
        if (this.length) {    // used for first child node and for the chain as long as the inputs were skipped
            if (wagon > this.first) {
                // add before
                this.children.push(new Node(`${wagon};${this.wagons}`, this.length + 1, wagon, this.last))
            } else if (wagon < this.last) {
                // or add after
                this.children.push(new Node(`${this.wagons};${wagon}`, this.length + 1, this.first, wagon))
            }
        } else {
            // first run. inplace
            this.children.push(new Node(wagon.toString(), 1, wagon, wagon))
        }
    }

    getLongest() {
        //console.error(this.wagons)
        return this.children
            .map(e => e.getLongest())
            .reduce((a, b) => Math.max(a, b), this.length)
    }
}


const N = parseInt(readline());
var inputs = readline().split(' ');
const root = new Node("", 0)
for (let i = 0; i < N; i++) {
    root.addWagon(inputs[i] * 1)
}

console.log(root.getLongest())
#14

By creating a tree like that, you are effectively generating the entire set of possibilities in memory.
Performance wise this is the worst case scenario. You need a way to dynamically cull your tree, and/or avoid repetitions by generating unique subtrees that can potentially be held by multiple parents.

1 Like
#15

There seems to be some discrepancy between the test cases and the validators. I appear to have solved it in tests and just looking at it from a logic standpoint, but it gets a 40% in the validation.

#16

What’s your overall approach ?
And what language ?

From what you say it sounds like you use a greedy algorithm but I don’t think there’s a greedy method that works consistently here.

I didn’t do this one but it looks like a typical problem you solve with ascending dynamic programming or recursively with memoization.

1 Like
#17

I did use recursion, but looking back I somehow did a greedy algorithm in front of it. Definitely worked for the test cases, but I think I see where it goes wrong now.

#18

In this case Greedy does not find the optimal solution. It finds an approximate good solution only, not the global best solution.
A common working approach is DP. You may like to look into algorithms like LIS or LDS because the nature of this puzzle is allowing you to skip some items. It needs customizing the standard algorithms to fit into the puzzle requirements so it will not be a simple copy and paste exercise.

1 Like
#19

I know how to solve it, just the easy approach I first took passes all of the test cases even though it is wrong. I am not asking for help on how to solve it, I am saying that the test cases need to be beefed up.

#20

While the expectation is reasonable, it is generally impossible to have a set of test cases that will assure all incorrect programs to fail.

Just as an example, “greedy algorithm” is a concept or an approach which can mean many different designs and implementations (some are badly done but still run). I cannot test these endless possibilities to come up with an absolute foolproof test set.

Remedy to some extend can be done. I could add an extra test case to lower the chance of an incorrect program luckily passing all test cases.

1 Like