© Ivana Martic, MATH+
Authors: Ravi Snellenberg, Martin Skrodzki (TU Delft)
Project: Holonomy, Computer Graphics and Visualization
Challenge
The elves of the esoteric research department have found a way to increase the amount of storage in the current storage warehouse. This was badly needed due to the ever-increasing amount of presents that need to be stored each year. The way the elves accomplished this is by connecting the rooms in the current warehouse in a clever way using portals. Usually, one could place 4 square rooms around a corner, but with the way rooms are connected now, an elf would need to walk through 5 square rooms in order to walk around the corner point where the rooms meet instead of the usual 4, see Figure 1. However, due to the difficulty of creating these space-warping portals, the elves are only able to create them in a limited, separate area that is surrounded by walls. This area is called the control room. So to traverse the warehouse, the elves enter the control room instead of the physical warehouse. And when an elf crosses into another square in the control room they are walking into a new warehouse room. Which room is decided by the new way of connecting the rooms. This control room is given as a grid of 3\times 3 rooms with portals on every wall that seperates two square rooms within the control room, see Figure 1. Corners do not have portals on them, so that it is not possible to walk diagonally inside the control room but only orthogonally. Even with this limitation, it is still possible to reach any of the possibly in finite rooms in the warehouse by using the layout of the rooms in a clever way.
Figure 1: The warehouse room layout. The left figure is a map of the new warehouse layout. Each quadrilateral is actually a square room but they are distorted on the map due to the way we need to represent the extra fifth room at each corner. It uses the Poincaré disk model to display this special layout. The right figure is the control room.
Since the elves at the esoteric research department realised that this entire situation is really confusing, they created an infographic to hang on the front door of the control room, see figure 2.
Figure 2: The infograpic. The lighter the floor gets, the further away is a room.
The infographic displays a hypothetical situation where an elf needs to reach a present that is not directly reachable within the starting control room layout. The top part of the infographic shows the control room the elf is confi ned to as they walk through the warehouse. The bottom part of the infographic shows a top view of the warehouse layout, which is linked to the control room view that is above it. The rooms that are colored in the infographic are the rooms that are reachable by walking a direct path (a shortest path) to a tile in the control room from the current position of the elf. Walking di fferent shortest paths to the same tile in the control room does not always lead to the same room in the warehouse. For example, in the control room that is displayed in the fi rst step of the infographic, the elf can reach each corner tile in two di fferent ways. In the warehouse layout it can, for example, be seen that both ways of reaching the upper right corner tile in the control room ( first up then right or first right then up) reach two di fferent rooms in the warehouse, see figure 3.
Figure 3: left: two paths to the upper right corner in the control room, right: the corresponding paths in the actual warehouse.
The infographic demonstrates that by walking in the control room in a certain way, it is possible to reach the present, although it was not directly reachable from the starting position. It also demonstrates how the directly accessible area shifts as the elf walks through the warehouse.
Now, the developmental elves of the esoteric research department wonder: What is the minimum amount of portals that need to be crossed to reach the present in the situation of figure 4 that could, without the control room size restriction, be reached by walking 3 steps forward? Assume that the elf starts in the center tile of the control room in this scenario.
Figure 4: The question scenario.
Possible Answers
- 3
- 5
- 6
- 7
- 8
- 9
- 10
- 12
- 14
- 42
Project Context:
The scenario this problem describes is the environment of a Virtual Reality application called Holonomy (named after the mathematical property that makes this traversal possible). Holonomy is being developed to answer several di fferent questions. For example, questions such as “Could such a demonstration help people understand the underlying mathematical properties more intuitively?”, “How quickly do people adapt to navigation in a hyperbolic world?”, “How could we help the player navigate such an environment?” And if we can fi gure out how to make navigation of these hyperbolic spaces easy, it could be used to create consistent worlds of any size that can be traversed while con fined to a limited space. And calculating the shortest paths between two locations is an example of one of the challenges that we stumbled upon while creating Holonomy.