Maze of Twisty Trampolines

Positive jumps ("forward") move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found: (0) 3 0 1 -3 - before we have taken any steps. (1) 3 0 1 -3 - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1. 2 (3) 0 1 -3 - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2. 2 4 0 1 (-3) - jump all the way to the end; leave a 4 behind. 2 (4) 0 1 -2 - go back to where we just were; increment -3 to -2. 2 5 0 1 -2 - jump 4 steps forward, escaping the maze. In this example, the exit is reached in 5 steps. How many steps does it take to reach the exit?

Part 1

Input



In [18]:

    
import csv
import numpy as np

with open('input.txt', 'rt') as f_input:
    csv_reader = csv.reader(f_input)
    l = np.array([int(a[0]) for a in csv_reader])

Class Maze



In [20]:

    
class Maze(object):
    
    def __init__(self, curr_pos, state):
        self.curr_pos = curr_pos
        self.state = state.copy()
        self.length = len(self.state)
    
    def evolve(self):
        self.state[self.curr_pos] += 1
        self.curr_pos += self.state[self.curr_pos] - 1
        
    def outside(self):
        return (self.curr_pos >= self.length) or (self.curr_pos < 0)

Main



In [21]:

    
def steps_maze(l):
    maze = Maze(0, l)
    count = 0
    while not maze.outside():
        maze.evolve()
        count += 1
    return count, maze.state

Test



In [22]:

    
t = np.array([0, 3, 0, 1, -3])
steps_maze(t)









    Out[22]:





(5, array([ 2,  5,  0,  1, -2]))

Solution



In [23]:

    
steps_maze(l)









    Out[23]:





(387096, array([   2,    8,   15, ..., -697,  -80, -681]))

Part 2

Now, the jumps are even stranger: after each jump, if the offset was three or more, instead decrease it by 1. Otherwise, increase it by 1 as before.

Class Maze with new dynamics



In [78]:

    
class NewMaze(Maze):
    
    def evolve(self):
        if self.state[self.curr_pos] >= 3:
            self.state[self.curr_pos] -= 1
            self.curr_pos += self.state[self.curr_pos] + 1
        else:
            self.state[self.curr_pos] += 1
            self.curr_pos += self.state[self.curr_pos] - 1



In [79]:

    
def steps_new_maze(l):
    new_maze = NewMaze(0, l)
    count = 0
    while not new_maze.outside():
        new_maze.evolve()
        count += 1
    return count, new_maze.curr_pos, new_maze.state

Test



In [92]:

    
t = np.array([0, 3, 0, 1, -3])
steps_new_maze(t)









    Out[92]:





(10, 5, array([ 2,  3,  2,  3, -1]))

Solution



In [93]:

    
steps_new_maze(l)









    Out[93]:





(28040648, 1097, array([   2,    2,    3, ...,  -76,    3, -681]))



In [ ]: