hello, eulerscheZahl
I really like this topic, I tried to solve the problem in C++, but I don’t know why my code can display the results locally (for the first example), there is nothing in the platform’s Standard Output Stream, I try to use Printf, found that nothing is output, I think it might be to use cout, but change to cout or nothing
I cout << ans << endl; Is it not right, must cout << RRLL…<<endl; This way, but the string will not know in advance, can only be stored in the array, please advise
Annex 1:
This is my code: https://paste.ubuntu.com/p/32PMt3sdhV/
Annex 2:
Why is the data of test1 is this：https://github.com/eulerscheZahl/Bender4/blob/master/config/test1.json, shouldn’t it be
8 8
…#…
##.##.#.
.#…###.
.##.#…
…#.###.
.##…#.
…###.#.
…
1 1 8 8 0
Well? This is what I wrote myself based on the first data.
Don’t print to the out stream, but the error stream: example code.
The test input is almost the same as on github. The only difference is, that there are | characters instead of linebreaks (back then there was a bug in the framework, which crashed on linebreaks).
When you tried to extract the map by hand, you forgot the surrounding wall.
thanks,I know
Wonderful puzzle, eulerscheZahl! 2 days and 4 evenings of fun coding 
Thank you very much!
I’m glad you like it
And congrats on getting first.
Hi,
This was a tough one. I first started to think about it a year ago and finally managed to finish it. Thanks @eulerscheZahl, yet another great puzzle from you! I really liked how there were multiple problems packed together. It gave a bit the same feeling as the leagues in multiplayer: solve introduction cases (Wood 1), avoid magnetic fields (Bronze), find a good compression algorithm (Silver), solve big maps (Gold), make good use of the Garbage balls (Legend).
Here below are the detailed steps it took me to solve the problem (spoiler alert).
Click to expand
Data structure
First an important thing for every problem is to define properly the data stracture, notably what is static and what is part of a game state. One has to find the good balance with a minimalist game state (which will perform faster with search algorithms that make many copies) and readability/easiness to use. The following was what worked best for me.
Global static data
- Map layout: for each cell, it gives the information of whether it’s a wall or not (Can be stored in a 2D array CELLS[x][y] or 1D array CELLS[position] where position = x + y * width)
- Neighbours: for each cells, precompute the neighbours (many structures are possible, I tend to go for a 1D array NEIGHBOURS[position*NB_DIRECTIONS + direction] where NB_DIRECTIONS=4 and direction is a char between 0 and 3 mapped to UP, DOWN, LEFT, RIGHT)
- Fry’s position
- Fields: for each field, store its position and associated switch
- Switches: for each switch, store its position and associated field
Game state data:
- Bender’s position
- state of the fields (on/off)
- position of the balls
- path: list of directions that Bender took to get to the state (Alternatively, we could just store the last move and the pointer to the parent and deduce the path from backtracking. But I didn’t want to manage pointers and the performances were already good enough)
Step 1 - Basic maze resolution
I started to work on the problem as if it was a standard maze puzzle, ignoring all fields and considering balls as walls. I just used a simple BFS disallowing Bender to go back to an already visited cell. This was easy to test thanks to the introduction levels.
See code here
State initialState;
list<State> queue;
queue.push(initialState);
array<bool, NB_CELLS> visitedCells;
visitedCells.fill(false);
visitedCells[initialState.position] = true;
while (queue.size() > 0) {
State& currentState = queue.front();
for (char direction = 0; direction < NB_DIRECTIONS; direction++) {
int nextPosition = NEIGHBOURS[position * NB_DIRECTIONS + direction];
// if the next position was already visited we skip it
if (visitedCells[nextPosition]) continue;
// playDirection returns whether the move was successful
bool hasMoved = currentState.playDirection(direction);
if (hasMoved) {
if (currentState.position == targetPosition) {
// if Bender is on Fry's position, we found our solution
return currentState;
}
// Mark the cell as visited so we don't process it again
visitedCells[currentState.position] = true;
queue.push_back(tempState);
// reset currentState for the next moves
currentState.revertLastMove();
}
}
queue.pop_front();
}
Step 2 - Solve the maze with magnetic fields
As expected, when we start to test the previous code on maps containing fields, Bender will rush to Fry and get nuked by the first field he encounters.
So, in a second step, in State::playDirection we need to take fields into account:
- When Bender walks on a switch, toggle the associated field
- When Bender tries to go on an active field, consider it as an invalid move
With this, we pass all the introduction levels, and the basic setup is done. But we quickly notice that for complex maps, the BFS fails to find a solution. Indeed, sometimes when a Bender reaches a switch, he needs to go back on his steps to go to his next target, but he can’t because of the visited cells logic.
I tried a few approaches that didn’t work that well:
- Remove visited cells logic: it’s the issue, so why not just removing it? Well allowing Bender to go back on his steps without any conditions makes the search space explode with duplicated non relevant states:
- depth 0: (0,0)
- depth 1: (0,1), (1,0)
- depth 2: (0, 0), (0,2), (1,1), (0,0), (1,1), (2,0) => at depth 2 only, we already have a duplicated (1,1) position and even a (0,0) duplicated position that is equivalent to depth 0
- Reset visited cells when walking on a switch: This one is better and actually on some maps where the switch is not far from its associated field AND Fry, it would pass the validators. But the search space still explodes when Bender has to walk on multiple switches:
- depth X: (posSwitch0), etc
- depth Y: (posSwitch1), etc (=> walking on posSwitch1 reset the visited cells so Bender can go back to posSwitch0)
- depth Z: (posSwitch0), etc (=> a few turns later, Bender is again on posSwitch0, which reset the visited cells and he can go back to posSwitch1 in a few turns, etc…)
What we notice is that with poor reset conditions, the search space is unbounded (due to the infinite loops between states) and the bfs will never terminate in time.
After thinking about the problem, I realized that a BFS can be bounded by the number of different possible states of a problem. The basic maze problem mislead me because Bender’s position/cell was actually equivalent to the state. But actually, all we need to do is to prevent Bender from going back to a visited state rather than a visited cell.
Our game state structure consists of the position, the state of the fields, the position of the balls and the path. The position of the balls can be ignored for now and the path is there merely to easily print the result of the search. So in the end, our state is Bender’s position and the state of the magnetic fields (if you are good at visualizing, the problem is similar to a 3D maze where switches are portals that link 2D maps), with a search space limited to:
NB_STATES = WIDTH * HEIGHT * pow(2, NB_SWITCHES) = 21 * 21 * pow(2, 11) = 903168
Wow it’s almost a million! But it’s still good news:
- A boundary of 1 million is better than an unbounded problem
- States can be defined by a 32-bits int
- Our NB_STATES is very pessimistic. There is sometimes less than 11 switches per map, not all state combinations will be explored before finding a solution. And we are lucky enough to be in a maze, so a lot of the cells are walls.
After replacing the visitedCells by the visitedStates logic in the BFS, all tests were now passing in under 10ms (in C++)!
Step 3 - Allow moves on Garbage Balls
We now need to include garbage balls handling in State::playDirection:
- Bender can walk on a ball if the next cell behind it is not a wall or another ball
- Update the position of the ball
My first approach was to run a BFS once with balls as walls and once considering that balls can be moved for the rest of the time. It actually gives pretty decent results with a score around 3800. But because the BFS is still relying on states that aren’t considering the balls, it behaves a bit randomly depending on the map.
I tried to include the balls in the state “hash” but it was making the search space too big. In the end my best score without compression was 3744.
Step 4 - Compression
Nothing fancy here, I check all the substrings of the result and find the one that will reduce the most the size of the result. I repeat the process until I reach 9 functions or I can’t improve the size of the result. (Pro tip: ignore substrings containing the “;” function separator)
Misc
Pruning
In a maze, most dead ends are useless. Replacing them by walls can reduce the search space by a lot. But removing all of them can have bad consequences as well so choose carefully 
Direction order
If like me, you use a search with fixed direction order, changing the order might affect the result of your searches. While it won’t change the size of the path, it can change the path itself and as such how good it is for compression. Tweaking the direction order made me gain a few more points.
Thanks for your writeup, it was a good read.
There’s just 1 thing I’d like to correct:
You calculated 21*21*2^21. Actually there are only 903168 states.
I think the compression can do a lot more: intentionally bumping into walls (see the first testcase) is one thing.
Naab even shared a replay where he didn’t return from the function calls and reached Fry with some instructions and maybe 4 functions on the callstack left.
Oups, good catch. I updated it.
I didn’t think at all about strategies like bumping into walls or finishing the game without consuming the whole call stack. It’s quite interesting and clever. Now I understand better how the top 4 can have such a big lead.
I finaly did it !! Awesome puzzle 
I learned so much during this week of coding, trying to gain execution time. Thank you very much eulerscheZahl 
(It’s realy sad so few coders joined this challenge, it deserve beter)
I began with PHP, the execution time was more than some minutes.
I switched with Java, and it was beter, but still too much… Until I find some tricks to gain seconds.
I also want to thanks k4ng0u, your explanations helped me and inspired me a lot 
In fact, I haven’t finished yet. Now comes the funny part to shrink the output. But the hardest part of the challenge is done, so I wanted to give my feedback right now 
This might be a completely hypothetical question, but I was wondering, how the following case is handled or whether that will never happen
Assuming:
- a corresponding switch and block are next to each other
- a garbage ball is on the block’s cell
- Bender pushes the garbage ball onto the switch, toggling the block.
Of course if the block was switched off, it will now be on and Bender’s circuit fries.
But what happens if the block was switched on? The garbage ball would switch it off, so Bender could technically enter the block’s cell - or would he die in that case as well?
Asking the real questions here 
Looking at the code, the magnetic field only kills you at the beginning of the next turn, while the field is turned off in the current turn already. Thus you would survive such an action.
Thanks for looking into this! I’m slowly getting to the point where it might become relevant. Just validator 26 is failing now for some mysterious reason. Will look at your github repository and debug locally. I really like this puzzle - made me try some low-level C programming, which I haven’t done in 20 years. When is Julia finally coming to CodinGame?
Updated
You must have passed a lot of time one the game design and graphics.
The game is really interesting and fun.
But there is some issues with the tests:
- Specific title for each test would help a lot.
- In code testing I get 25/30 test ok but after submission only 9/30, I know tests should be differents after submission to avoid hardcoding, but without titles on tests I cannot understand what is going on.
Anyway thx for this great puzzle.
I can’t thank Zerplin enough for all the graphics he made for this game.
Regarding the test cases: except for the 5 introduction cases, they are all generated by the same script. I just generated random mazes and then tried to solve them.
I was about to link the contribution page, but for some reason the validators aren’t even shown there anymore. You can find them as test31 - test60 if you are willing to run the game offline.
Unfortunately it’s not possible for me to update the contribution anymore (not even a typo in the statement), as there is a limit of 50 testcases+validators now. But passing 19/30 visible testcases sounds like you can still find a bug with what you have.
Hello, @eulerscheZahl
Thank you for this great puzzle, I am very interesting to solve it, I can pass 80% of validator cases now, but I can’t improve it anymore, can anyone recommend topics to study it to improve my skills in this type of puzzles!
Why i have Invalid path, I haven’t finish to search the good path? It’s meant TLE or not???
In Test cases, there should be some intermediate tests.
The jump between Introduction and Testcases is too big.
The introduction cases are deceptively easy, but the truth is that the puzzle itself is. Having more intermediate cases would just led you into creating solutions that won’t scale for the large levels.
As k4ng0u pointed out, at first it looks like a basic maze resolution, but once you take magnets and switches into account, it’s not enough to simply keep track of visited cells, you need to track every visited state. Once you take balls into account, the search space explodes and you need to find ways to optimize it.