# The Fall - Episode 3 - Puzzle discussion

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

2 Likes

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.

4 Likes

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

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

1 Like

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

1 Like

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()``````
1 Like

ΠΏΠ°ΡΡ ΠΊΠ΅Π½ΡΡ ΠΏΠΎΠΌΠΎΠ³ΠΈΡΠ΅ Ρ Π·Π°Π΄ΡΠ΅ΠΉ ΠΏΠΆ ΠΌΠ΅Π½Ρ Ρ Π½Π°Π·ΡΠ²Π°Π΅ΡΡΡ The Fall - Episode 3 ΠΏΠΆΠΏΠΆΠΏΠΆΠΏΠΆΠΏΠΏΠΆΠΏΠΆΠΏΠΆΠΏΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΆΠΏΠΏΠΆΠΏΠΆΠΏΠΆΠΏΠΆΠΏΠΆ

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!

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

1 Like