# Solution to Infinite Corridor Back to Round

#### by Josh Alman and Jon Schneider

The Infinite Corridor consists of an infinite chain of rooms numbered 1, 2, and so on. An NPC placed at the start of the corridor will tell you which room to visit in order to unlock the subsequent puzzle in the Infinite Corridor (there are five such puzzles total). Unfortunately, the room numbers are greater than 10000, making it infeasible to travel there on foot.

However, each classroom has two portals in it that allow warping. The left portal is always grey and warps the solver back to room 1. The right portal has various functions, which differs for each of the five target rooms. The color of the portal changes accordingly to reflect which sub-puzzle is active:

- For the first function, the portals are red.
- For the second function, the portals are yellow.
- For the third function, the portals are green.
- For the fourth function, the portals are cyan.
- For the fifth function, the portals are dark blue.

For each sub-puzzle, solvers need to first figure out how the function behaves, and then find a path to the target room that will not take too many steps. Moreover, none of the portals can take us to a room greater than one million, and the projection quality degrades with very high room numbers so that it is very difficult to move in the corridor past room 100000, so our path needs to avoid using numbers greater than 100000.

Once all five navigation puzzles are completed (i.e. when all five types of Infinite Corridor puzzle are revealed), a final white portal appears which unlocks the meta-puzzle. When talking to the original NPC at the start of the hallway, the portals will revert back to the simplest red portals. (The portals are also red to begin with, before the first sub-puzzle.)

### Navigation sub-puzzle 1 (red portals)

The red portals are simple: they double the room number. For example, the red portal in room 37 will lead to room 74.

One strategy for efficiently navigating to the target room is to convert the number to its binary representation. This binary representation can then be read as a list of instructions: a ‘0’ corresponds to going from room x to 2x (via the portal), and a ‘1’ corresponds to going from x to 2x+1 (first via the portal, then by walking one room forward). For example, if we want to navigate to room 74, we can write 74 in binary as 1001010, which can then be parsed into a list of instructions as follows:

- 1: Start at room 1.
- 0: Take the portal, going to room 2.
- 0: Take the portal, going to room 4.
- 1: Take the portal, going to room 8. Then go one room further, to room 9.
- 0: Take the portal, going to room 18.
- 1: Take the portal, going to room 36. Then go one room further, to room 37.
- 0: Take the portal, going to room 74.

The target number for this room is 13536. The strategy above leads to the following path to the target room (here, taking portals is indicated by ‘>’, and walking is indicated by ‘-’):

### Navigation sub-puzzle 2 (yellow portals)

The yellow portals are similar to the red portals, except they only work if the number of ones in the binary representation of the current room number is odd. (Otherwise, the portal sends us back to room 1.)

As with the previous sub-puzzle, we can still read off a path from the binary representation, but this requires fudging the addition a little bit in order to ensure the portal continues to work. Instead, it is a little easier to work in reverse -- walk from the target number until we find a room which we can get to via a portal (this is any even number with an odd number of ones in its binary representation), and then go back through the portal to half of that number. For example, if we want to get to room 74, running this procedure backwards we do the following:

- 74 is 1001010 in binary. This has an odd number of 1s, so we can get to it by taking a portal from 37.
- 37 is 100101 in binary. Walking backwards 1 gets us to 100100, which has an even number of ones (so we can’t get there directly from a portal). But walking forwards 1 gets us to 38 = 100110 in binary, which has an odd number of 1s, so we can get to it by taking a portal from 19.
- 19 is 10011 in binary. Going backwards 3 we reach 16, which has an odd number of 1s, so we can get to it by taking a portal from 8.
- From 8, we can repeatedly take a portal until we start at 1.

The target number for this room is 68091. The strategy above leads to the following path:

### Navigation sub-puzzle 3 (green portals)

The green portals cycle the digits so that the unit digit is moved to the front; for example, the green portal in room 1234 leads to room 4123.

The first difficulty is getting the room number to grow quickly: for example, a two-digit room will never lead to a room exceeding 100. The idea is to make the units digit equal to 9 to progress. For example, an opening route might look like:

- Walk from 1 to 12, warp to room 21.
- Walk backwards to room 19, then warp to room 91.
- Walk backwards to room 89, warp to room 98.
- Walk forwards to room 109, warp to room 910.
- Walk backwards to room 909, warp to room 990.
- Walk forwards to room 1009, warp to room 9100.
- Walk backwards to room 9099, warp to room 9909 then 9990.
- Walk forwards to rooms 10000+.

Once in this area, one takes the target room number reads the digits from right to left. Setting these as the units digit and repeatedly warping will lead to the desired room. We should also take care not to enter the portal when the room number ends in a zero, since leading zeros are removed after cycling.

The target number for this room is 33136. The strategy above leads to the following path:

### Navigation sub-puzzle 4 (cyan portals)

The cyan portal adds the *square of the product of the digits* of the current room number.
For example, the portal in room 1234 leads to room 1234 + (1 * 2 * 3 * 4)^{2} = 1810.

As with several other of the sub-puzzles, one good way to solve this by hand is to try working from the target room backwards. In particular, it is useful to try to find a nearby square number less than the target with small factors (that can appear as digits). For example, the target for this puzzle is 85567. The square root of 85567 is approximately 293; the first number smaller than this with a lot of small factors is 288 = 2^{5} * 3^{2}, so we’ll try to find a number whose digits have product 288 which is close to 85567 - 2882 = 2623. One such number is 2638. We can now repeat this process and try to find a good path to reach 2638.

Alternatively, it is also possible to find an efficient solution via computer search (in fact, this is true for all of the sub-puzzles -- see the note at the end).

The target number for this room is 85567. One possible path to get to this room is:

### Navigation sub-puzzle 5 (blue portals)

The blue portal adds *2 to the power of the number of ones in the binary representation* to the current room number.
For example, the portal in room 21 leads to 21 + 2^{3} = 29.

One useful observation is that by repeatedly using the portal, we go from 1 to 3, to 7, to 15, to 31, and so on. In particular, we can get to numbers which are one less than a power of 2 (and thus powers of 2) fairly quickly. This allows us to reach the highest-order bit of the target room number.

Once we’ve reached this power of 2, we can repeat this process with slight modifications. For example, since we have one bit set already, we now can easily reach 2, 6, 14, 30, 62, etc., more than the current room number. This allows us to set one additional bit. In general, we can iterate this process to set a prefix of the bits correctly, and then walk to deal with the remainder of the bits (once 2^{number of set bits} gets too large).

The target number for this room is 57138. One path to reach this room is:

### Computer search

It is also possible to find near-optimal paths for all of these puzzles via computer search. The Python snippet below runs a breadth-first search
to find the shortest path from room 1 to a target room *n* (under the assumption that taking a portal and going forward/backward one room take the same time) for any portal function *f*.

MAX_ROOM = 10**5 from collections import deque def solve_infinite_nav_puzzle(target, portal_function): bfs = deque([1]) seen = set([1]) parent = dict() while bfs: cur = bfs.popleft() nbrs = [cur - 1, cur + 1, portal_function(cur)] for nbr in nbrs: if nbr not in seen and nbr > 0 and nbr < MAX_ROOM: bfs.append(nbr) seen.add(nbr) parent[nbr] = cur path = [target] while path[-1] != 1: path.append(parent[path[-1]]) return list(reversed(path))