Hi guys,
I have problems limiting the search space for this puzzle: https://www.codingame.com/training/expert/cubax-folding
My code runs forever for the 4x4x4 testcase. How can optimize this?
Best,
fafl
Hello
Was wondering if you made any progress since then and possibly could share some insights?
My naive brute force recursion approach is suffering from the same exponential slowness and I’d like to make it less dumb. However, I don’t know what concepts I should be studying more closely.
The search tree is huge, but it can be pruned a lot.
List all the prunes you can think of. In plain English: if you’ve got a partial folding, how can you know in advance that it’s never going to end up in a solution, without completing it to the end?
Sort them by ease of implementation. Implement them one by one, until performance is enough.
For an example prune that doesn’t spoil the problem, this one’s not in my final code so it’s obviously not needed (though it could help if you’ve got a different set) but could give you an idea of what to try. It’s common sense, but to succeed a complete fold you need to have long enough of Cubax to reach the end. At any point in the search, if the distance from where you are to the goal exceeds the remaining length, there’s no point in even branching to find a clear path: there won’t be one and you’d better backtrack immediately.
1 Like
Just the kind of pointers I was hoping for to get some new ideas off the ground.
Thank you very much JBM! 
Happy to help. 
I don’t get Cubax Folding. None of the examples explain the 3D aspect of the puzzle. Besides, the example 3332 doesn’t add up to a cubic number. Can we get some better examples, maybe one in 3D.