## What will I learn?

In this puzzle, you have to use an associative array that maps arbitrary types to directions.

You compute the list of all possible actions from a complex environment (lots of different variables).

You go through the nodes of a tree using a depth first search algorithm.

You handle complex data structure, like trees, to store the list of possibilities over the time.

You have to optimize your algorithm to reduce the number of combinations in order to decrease the overall computation time. You have to prune a decision tree based on heuristics.

You can perform advanced backtracking operations.

## LEARN ALGORITHMS ASSOCIATED WITH THIS PUZZLE

Shortest paths with Dijkstra’s Algorithm by RacsoFocus on a Puzzle: The Last Crusade by fafl

#### External resources

Breadth First SearchPruningDijkstra## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

The goal of the puzzle is to select rooms to pivot from a 2 dimensional grid to help Indiana Jones find his way to the exit. This puzzle requires to build the tree of all the possible rotations that can be performed over time, and use some heuristics to perform some predictive optimisations to avoid unnecessary computation.

These expert test cases (compared to episode 1) will need extra care in finding a solution through a huge decision tree.

A higher resolution is required to access the IDE

## Story

*"Woops, forgot my hat."*

Indy is back with a brand new and novel series of evil labyrinths, just to check that you have what it takes to be a great archeologist! (Doctorate in archeology : optional. Being able to program while being chased by a 1.5 ton rock : strongly recommended)

*This expert sized puzzle is the last out of a series of 3 exercises, proposed for the challenge « The Last Crusade ». Before you try to solve it, we recommend you solve the two previous levels that will provide you with a useful base code before you start this puzzle.*