The Fall - Episode 3 - Puzzle discussion

Puzzles
#1

Feel free to send your feedback or ask some help here!

2 Likes
#3

This was a HUGE task. For me the second hardest in CodinGame so far, after the Mars Lander puzzle. It really tweaked my imagination and got me thinking. I tried several solutions but non of them came close to 100% result, especially with the “You may have to anticipate the arrival of some rocks if you want Indy to survive…” idea in the problem statement. In the end I decided to implement DFS as much optimized as possible, run it every turn when I see a collision danger for Indy and it worked quite well. Definitely one of my favorite puzzles.

5 Likes
#4

Oh man… I was going here to see if anyone has the idea of solving this… Such empty man…

#5

How far have you come with solving the task?
Or you have a specific problem/question?

2 Likes
#7

Sorry for not replying you man… I thought no one answered so I had to figure out the solution by myself ~.~

1 Like
#8

This was funny one… It’s not that hard to solve, but it’s definitely hard to properly represent all the data and transformations. My solution is about 250 lines of code and in theory works as follows:

  1. Get all the paths from actual indi position to end including counter for rotations (0 = no rotation, +1 = left rotation, +2 = 2xleft rotation, -1 = right rotation) (very similar to image in Rotations section of this blogpost)
  2. For each Rock compute all “Hit Paths” - paths, that rock has to follow in order to hit end of the board or wall of other piece. Also skip computation if rock at any point hits the position indi was already in (rock is behind indi)
  3. I’ve implemented funny middle step - mapping obtained paths to paths with boolean metadata for each position where hitting “true” on some cell means, yo have to act on actual path in order to complete it - false true false means you can wait one turn, but you have to act on next one
  4. Term you are looking for to make all possible combinations of indi/rock paths is called cartesian product
  5. Finding solution: for each item of cartesian product:
    – Shorten rock paths if they colide with each other
    – If any rock path intercepts indi path (same x,y value at the same time) - NOT A SOLUTION
    – If paths create paradox (tiles at any x,y for any pair path are not matching) - NOT A SOLUTION
    – If can’t rotate cells fast enough - NOT A SOLUTION
    – otherwise - SOLUTION
  6. Pick any item of cartesian product marked as SOLUTION and do a move on path that requires interaction in nearest future

Worst part for me was data representation so I’ll post some snippets (Kotlin lang). Hopefully it isn’t too much to share and will help you:

  1. To define moves in a Piece I’ve used custom Move objects, for example: object TT : Move(Direction.TOP, Direction.TOP)
  2. This is how my Piece9 looked like: object Piece9 : Piece(9, { Piece8 }, { Piece6 }, listOf(TT, LT))
  3. Tile was composed of Piece and canRotate flag
  4. Board was composed as 2D Array of Tiles
  5. Paths from step 1. and 2. were just list of - x, y, enterDirection, requiredPiece, requiredRotations
  6. Path from step 3. is list of - x, y, requiredPiece, haveToActFlag, requiredRotations

Cartesian Product in Kotlin:

fun <T> cartesianProduct(a: List<T>, vararg sets: List<T>): List<List<T>> =
    (setOf(a) + sets)
        .fold(listOf(listOf<T>())) { acc, set ->
            acc.flatMap { list -> set.map { element -> list + element } }
        }.toList()
3 Likes
#10

I just passed the last two test cases “Multiple choice and rocks” + “Only one way” with my uncompleted solution, without considering the presence of the rocks at all. That’s odd! I currently have in place a DFS search to find all possible paths for the player. After this my intention was to find the hitpaths for the rocks and compare these paths to find the solution. Kind of disappointing!

#11

Just to be clear, it does not pass the first two!

1 Like
#12

Amazing puzzle! Took me 3 days to solve it. Originally I tried solving episode 2, but last two tests there with rocks just killed me, trying to take into account them bloated my code so much and it still didn’t work, so I gave up on that.
That’s when I noticed that episode 3 has the same rules, just all tests are with rocks and I decided to rewrite everything from scratch, so that my backtracking algorithm takes rocks into account too when building path for Indy. This is such a nice feeling when I submitted code for episode 3 and got 100%, immediately copy pasted it into episode 2 and got 100% there too. So, I solved two puzzles with the same code simultaneously :smiley:

1 Like