[Community Puzzle] 5D Chests

https://www.codingame.com/training/medium/5d-chests

Send your feedback or ask for help here!

Created by @Westicles,validated by @fpringle,@chouch and @_bruh.
If you have any issues, feel free to ping them.

Interesting one !

A bit unbalanced depending on the language, in C++ a bruteforce algorithm that fills the whole 5D space works while in Python I had to figure out symetries or the last testcases would fail.

But in the end it’s more interesting that way, I could compute the last testcase by launching only 2054 explorations instead of the 143339 required explorations with the bruteforce.

2 Likes

A very simple floodfill was fast enough in php (with memoization for the isPrime() function results).

3 Likes

Sadly the time is basically the same if you memoize isPrime, precalculate all primes in a lookup table (cause 10000 is nothing so why not), or save no results at all.
All those approaches gave me the same ~10 sec in Python.

I think the only significant optimisation comes from symetries.

I agree : the difficulty is largely dependent on the language.

I could just make it in Ruby (without using symmetries), but it needed significantly uglifying things (and using a profiler).

Simple flood-filling in Java can pass it too. No need to dreadfully tweak the usual design pattern.

I used python and could barely make it to third validator until I decided to use scipy.ndimage.label which broke the game.

1 Like

Can you publish your code? I’m curious to see what you’ve done.

I published it :slight_smile:

1 Like

Hey! I want to know if my solution timed out in the 4th validator( in C# all testcases pass with brute-force, but not in Python, I wonder why! ).
I don’t know if you can access my solution, if you can, can you please suggest a way to optimize solution. Thank you.

As said above, bruteforce doesn’t work with Python cause it’s too slow.
You can significantly speed things up by using symetries (cause all “orthants” will behave the same).

3 Likes

is 1 prime…

update: no

don’t try a brute force flood, but with disjoint set it works for lua :wink:

3 Likes