[Community Puzzle] Sokoban

https://www.codingame.com/training/hard/sokoban

Send your feedback or ask for help here!

Created by @eulerscheZahl,validated by @Westicles,@Nazdhun and @Kr4unos.
If you have any issues, feel free to ping them.

I’ve struggled with solving this puzzle in 1s. I have few small tips for anyone who would like to try:

  • deadlocks detection is probably not required.
  • you might want to use a faster language (I couldn’t find a way to solve it in python with simple solution).
  • if you’re able to solve all puzzles but you’re a bit too slow you can use additional turns for computing the answer.

Thank you very much for this puzzle! I’ve had a blast solving it and mostly failing :smiley:

2 Likes

I agree with @Gabbek.

Even with Swift, which I don’t think is in the “slow languages” category, I had to significantly uglify the code to pass in 1s.

Also, I’m not sure it doesn’t belong in the “Very Hard” section, as is often the case when you need to find heuristics to tackle a NP-hard problem with inputs that are only small (and not very small).

I don’t see it as very hard. My code isn’t more than a BFS, admittedly in one of the faster languages (C#).
As a compromise I increased the time for the first turn from 1 to 10 seconds (and had to reduce the maximum number of turns from 600 to 400 which is still more than twice of what you need).
cc @Nazdhun as I see a 76% solved state here.

I think hard is a very good place for this puzzle. Test cases could be much harder and it would force you to implement a lot more to manage it - as I’ve mentioned in my first post not being required to implement deadlocks solution and still passing all of them in 1s means it’s in good place, I think.

:sweat_smile: 10 seconds pushed me to 96% ^^.
But my code is still way unoptimized, i am new to Rust and as far as i read other forum posts, Rust is only compiled in Release mode fur multiplayer submits…

But as I said: Still optimizing, my code does produce a solution fpr Scoria 3 - Level 4 in 2,6 seconds with 87 pushes, but then i need > 400 steps and it fails.
So definitely my faulty code…