Don't Panic - Episode 2 - Puzzle discussion

Puzzles
#46

This was nightmare to debug, with the possibility for clones to overlap after elevators . I used 2D grid to represent the area. First I rate each cell of the grid if it is good for building an elevator or place a blocking clone. Then with DFS tried sequences of commands for the leading clone. Where the depth of the search is the turns count, I tried to somehow ignore the WAIT command in the search, but unsuccessfully. If the leading clone is transformed I return it back 3 moves where the next leading clone should be. I managed to solve the task in the first turn.

The main observations I had:

  1. No more than 1 blocked clone should be used on one floor
  2. Maximum 8 BLOCK or ELEVATOR commands are needed
  3. Maximum 9 clones are needed
#47

It took me 5 days and half my sanity but i finally made it. If any other brave soul decided to try this here are some tips.

  • Contrary to some tips BLOCK and ELEVATOR takse 4 turns (maybe depends on the code)
  • I use BFS without the Graph class, just the node class and a method.
  • You gonna need some memoization (look for [CyberLemonade] for clues)
  • Dont panic, for real just keep trying, you can do it.
3 Likes
#48

Wow this puzzle was tough… But I learned a lot from it, thanks !

I started with A* but realised that it was difficult to estimate the cost h to the remaining path to the goal. So I went back to Dijkstra’s algorithm with a weighted Graph class and a priority queue but realised it was difficult to estimate if the cost of a node was less than another without knowing the full path. So I finally went back to a simple BFS search like @CyberLemonade with a Node class with parent, position, direction, nb_turns, nb_clones and nb_elevators. That way every node is unique and we are sure to test all possibles paths.

But my advice to make your algorithm fast is too really think and optimize your graph. You need to make it with the fewest nodes as possible. You should also remove dead ends and not useful elevators.

If this can help :slightly_smiling_face:

4 Likes
#49

I need some help with “Few Clones” validation case.

I am using A* algorithm with a 5 dimensional node array and so far it passed all cases except “Few Clones” for a 90% solve.

For the “Few Clones” validation case, currently, this is the list of elevators I am using/constructing on each floor:

{11: 39, 10: 39, 9: 24, 8: 23, 7: 17, 6: 13, 5: 17, 4: 17, 3: 17, 2: 24, 1: 34, 0: 33}

It is one move short away from the desired number of moves. I could actually get shorter moves elsewhere but it costs me an additional BLOCK, which means that it is infeasible as the number of clones are limited.

Can someone share the solution for the validation case, so I may go about debugging. Just looking at the map I am unable to think of a faster way to reach the goal.

Thanks!

#50

Hi, I would recommend you to choose another elevator on 1st floor

#51

I keep getting

ERROR: ld.so: object ‘libstdbuf.so’ from LD_PRELOAD cannot be preloaded: ignored.

This is without any of my code even in the program. Simply the base example

2 Likes
#52

Same issue here. This prevents the editor from jumping to error locations…

1 Like
#53

I have the same issue. How do I solve it ?

#54

We’ll look into it. Thank you for reporting it. It should not block the running of your code though.

#55

Same issue in Coders of the Caribbean. My code modifications are not taken into account and the simulation runs with my old code.
ERROR: ld.so: object ‘libstdbuf.so’ from LD_PRELOAD cannot be preloaded: ignored.

1 Like
#56

Hm, this is interesting, how did you get to the number of 4? If you consider that the next clone is always 3 steps (turns) behind the leading clone, then when the leading clone makes an action like BLOCK or ELEVATOR, the next clone makes a step within that action. So there should be just 2 remaining steps to the originally leading clone position. So I also get 1 + 2 = 3 turns as the others…

#57

OK, never mind my question, I got the resulting … +1 = 4 as well once I really started to think of the algorithm, so you are definitely right! :slight_smile:

#58

The last tip saved my day, thank you! Without this, I couldn’t pass the last test #10 “Giant map” because of timeout. This tip decreased the number of generated states about 3 times in this level for me. And the other tips are also pretty useful.

BTW I used just “the good old plain” BFS (i. e. no A* or pre-optimizing the map), with I hope pretty much optimized states-generating algorithm (generating only valid and “promising” states and throwing away / marking the “beaten” ones). I had some hard time with correctly keeping the current elevators data though - moving the additionally built ones “back and forth” while going through every previously generated state…

Finally, this was my 1st hard puzzle I tried here, spent several days / evenings on it. I really wonder if the other hard puzzles will be as hard as this one as well… :sweat_smile:

2 Likes
#59

Great puzzle! I was finally able to solve it. Here are my tips that I found along the way

  • A simple BFS worked for me. I couldn’t find a good heuristics for a faster A*. Traps or elevators around the exit will make any heuristics work against you
  • I used a simple integer vector as a state. I didn’t need to keep track of a list of elevators
  • You need to heavily prune the game tree, aside the obvious, 2 criteria helped the most (and took me the longest to get right):
  • These are : the positions where you can Block and the one where you can Create an elevator. Restricting them to just a few places will have the most impact on the tree size

It also happened that I overpruned the tree (and could’nt find a solution), so I had to tinker with the pruning criteria. What helped me, is to let my search take as long as it can to find the solution, and then study it. You’ll find that the best series of actions will always have a certain pattern.

Good luck for anyone trying this challenge! :slight_smile:

1 Like
#60

This was really hard to debug, but solution isn’t that complicated

Not sure why everybody recommends BFS. This is more of DFS problem, since I’m looking for fisrt viable path. Anyway some maybe-not-so-obvious hints to reduce search space:

  1. You can cut quite a few position if you cut elevators that will make you loose (look from exit down)
  2. BLOCK should be the first operation on given line (0-1 x BLOCK + 0-n x WAIT + 0-1 ELEVATOR)
  3. you can break path when manhattan distance from exit is larger then remaining turns
  4. when creating new nodes, make sure WAIT will be expanded last! so you won’t search paths with too long WAIT sequence

Hints 2 and 4 helped most

1 Like
#61

Pretty challenging puzzle, this one. I didn’t get as deep into the weeds as I did going for the Skynet 1 bonus achievement, but this was a workout.

I got stuck trying to solve the last 3 big puzzles with a DFS in Java - my solution kept timing out. When I switched to BFS, it sailed right through with no problem. More magical, I guess.

Some things I discovered that might be helpful:

  • You should only build elevators underneath preexisting elevators or underneath the exit. Not necessarily immediately below, but at the same X position on any of the floors below.
  • The only place you should ever block is immediately after exiting an elevator (or the starting gate).
  • Like @VizGhar pointed out, the best pruning to start with is comparing Manhattan distance from your lead clone to the exit against remaining turns.

Good luck and have fun!

2 Likes
#62

Hi ! Very fun game, thank you.

I’m not a professional, so please be kind with my code, it could be the worst you’ve seen.

But I progress step by step, and i’m happy with that.

I just have a question that fooled me : in the joint code, why i can get values of GenF and GenP, but not of var0, var1, var2, etc… and why the var ‘test’ is not updated ?

Thank you.

I put my code below :

/**

 * Auto-generated code below aims at helping you parse

 * the standard input according to the problem statement.

 **/

var GenF = []; // list of elevators floors

var GenP = []; // list of elevators positions

var inputs = readline().split(' ');

const nbFloors = parseInt(inputs[0]); // number of floors

const width = parseInt(inputs[1]); // width of the area

const nbRounds = parseInt(inputs[2]); // maximum number of rounds

const exitFloor = parseInt(inputs[3]); // floor on which the exit is found

const exitPos = parseInt(inputs[4]); // position of the exit on its floor

const nbTotalClones = parseInt(inputs[5]); // number of generated clones

const nbAdditionalElevators = parseInt(inputs[6]); // number of additional elevators that you can build

const nbElevators = parseInt(inputs[7]); // number of elevators

for (let i = 0; i < nbElevators; i++) {

    var inputs = readline().split(' ');

    const elevatorFloor = parseInt(inputs[0]); // floor on which this elevator is found

    const elevatorPos = parseInt(inputs[1]); // position of the elevator on its floor

    GenF[i] = elevatorFloor;

    GenP[i] = elevatorPos;

    

}

var noPos = 0;

var ext = 'WAIT';

var elPos = 0;

var ctrlFloor = 0;

var addel = nbAdditionalElevators;

var j = 0;

var k = 0;

var elFloor = 0;

var var0 = [];

var var1 = [];

var var2 = [];

var var3 = [];

var var4 = [];

var vard = [];

var test = 0;

var variable = [];

const variables = [];  // data matrix of variables used in test 08 by floor, floor[0] is the last used, the one under the exit floor, floor[10] is the first floor

variables[0] = '17 12 0 0 12'; // 1st number is the position the first clone enter the floor

variables[1] = '23 17 1 24 0'; // 2nd number is the position the first clone exit the floor

variables[2] = '17 23 0 0 0';  // 3rd number is the block index : 0 not block, 1 block

variables[3] = '13 17 0 0 0'; // 4th number is the block position

variables[4] = '13 13 0 0 0'; // 5th number is the position of the elevator to build

variables[5] = '9 13 0 0 13';

variables[6] = '3 9 1 2 0';

variables[7] = '3 3 0 0 3';

variables[8] = '4 3 0 0 0';

variables[9] = '4 4 0 0 0';

variables[10] = '6 4 1 7 4';

for (k = 0; k == exitFloor - 1; k++) {  //try to build the matrix with this algorythm

    j = 0;

    test = 1;

    var0 = exitPos ;

    var4[k] = 0;

    for (let i = 0; i < nbElevators; i++) {

        

        if (GenF[i] == k - 1) {

            

            if (j == 0){

            

                elPos = GenP[i];

                j++;

                                

            }

            if (j > 0 && Math.abs(elPos - var0[k]) > Math.abs(var0[k] - GenP[i])) {

            

                elPos = GenP[i];

            }

            

            var1[k] = elPos;

            if ( elPos == var0[k]) {

                var4[k] = var0[k];

            }

                         

        }

        

    }

    if ( var0[k] - var1[k] < 0 ) {

        vard[k] = 'RIGHT';

    }

    if ( var0[k] - var1[k] > 0 ) {

        vard[k] = 'LEFT'

        

    }

    if ( var0[k] - var1[k] == 0 ) {

        vard[k] = 'X'

        

    }

}

for (let k = exitFloor - 1; k == 0; k--) {  // second part of the algorythm for building data matrix

    var2[k] = 0;

    var3[k] = 0;

        

    if (vard[k] != vard[k-1] && vard[k] != 'X') {

        var2[k] = 1;

        if (vard[k] == 'RIGHT') {

            var3[k] = var0[k] + 1;

        }

        if (vard[k] == 'LEFT') {

            var3[k] = var0[k] - 1;

        }

        

    }

    variable[k] = var0[k] + var1[k] + var2[k] + var3[k] + var4[k] ;

   

}

// game loop

while (true) {

    var inputs = readline().split(' ');

    const cloneFloor = parseInt(inputs[0]); // floor of the leading clone

    const clonePos = parseInt(inputs[1]); // position of the leading clone on its floor

    const direction = inputs[2]; // direction of the leading clone: LEFT or RIGHT

    // Write an action using console.log()

    // To debug: console.error('Debug messages...');

    j = 0;

    ext = 'WAIT';

    elPos = 0;

       

    var inPos = 0;

    var outPos = 0;

    var blockPos = 0;

    var blockIdx = 0;

    var liftPos = 0;

    console.error(test);

    console.error(var1);

    

    // algorythm for running program, it works when the data matrix is correct

    if (cloneFloor > elFloor) {

        ctrlFloor = cloneFloor;

    }

        

    if (cloneFloor == ctrlFloor && cloneFloor != exitFloor) {

        var data = Array.from(variables[10-cloneFloor].split(' '));

                        

        inPos = data[0];

        outPos = data[1];

        blockPos = data[3];

        blockIdx = data[2];

        liftPos = data[4];

                        

        if (clonePos == blockPos && blockIdx == 1) {

            ext = 'BLOCK';

            blockIdx = 0;

        }

        if (clonePos == outPos && clonePos == liftPos && liftPos != 0) {

            ext = 'ELEVATOR';

            ctrlFloor = ctrlFloor + 1;

        }

        if (clonePos == 0 || clonePos == width - 1) {

            ext = 'BLOCK';

            blockIdx = 0;

            

        }

    }

    if (cloneFloor == -1 || clonePos == -1 || direction == 'NONE') {

        ext = 'WAIT';

        

    }

    elFloor = ctrlFloor ; 

    

    console.log(ext);     // action: WAIT or BLOCK

}
#63

I’m having troubles to handle BFS in case where 2 paths p1 and p2 lead to an elevator with distance(p1) < distance (p2) but after the elevator , distance (p2) < distance (p1) (caused by BLOCK above elevator for p1).
Does someone has a tip for this ? I fill my priority queue of neighbor only if node is not visited or its new distance is < to the old one. So p2 is forgotten with this rule…

#64

Looking to your question and to your code, I really have the feeling you’ve not understand how CodinGame works.
There’s no “magical interaction” between the system and your code. The system launch your code and send the inputs to it, then do nothing until you output something. So it’s not because you create a variable ‘test’ that the system will read your code, understand that this variable represent the currently runned test, and kindly put the test number in it. (I’m not mocking, I’m just presenting it in the absurd way to be impactful ^^)
Furthermore, the goal in every CG puzzle is to code an algorithm able to solve any situation described by the statement. The tests are just there to allow you to… test your solution, but they’re not the goal. The test used for the validation are different anyway.
I hope it’s clearer.

#65

Many thanks for your answer.

I dont know if i understand what you mean with the variable test, but it seems you think it is to know the number of the running test example.

Its not for that, and for the example 1 to 7(the one before the trap), i made something working well.

But as I said, I forward step by step, cause i dont know everything I should now.

To go further and try to solve the example 8, I have to follow a different way than my old code, because it was made just to react with the clone position, and it didnt made the better way to exit.

So my solution was to read the entries, to calculate a list of variables to apply in the game loop, then run the algorithm in the game loop, set up with the variables read from the declaration block, for doing the correct actions to solve the game.

When the variables are entered manually, the algorithm in the game loop is working, for example 8. My follow step is to calculate the variables with an algorithm.

I though the variable test helps me to know if something is working or not in my code before the game loop, like a console(error) can do in the game loop. I assumed test will return 1 in the game loop, only if the part of the code above the game loop was run, but obviously im wrong.

So yes the code is working for example8, but its because they are the hard coded variables read. I have a flag to know the state of the variable test and the list of variable that should be calculate, they both show, as I can know, like they never been calculated, but i dont know why.

Many thanks again to take time to read my poor english.