Part 1

In Day 3, we are now proposed a problem which will have us navigate through a two-dimensional array which contains either open squares (.) or trees (#). We are also told that we will always be following a defined set of rules when going through this array: three steps to the right followed by one step down. The objective of Part 1 is to count the number of trees on our path from the top-left corner to the bottom right-corner of the 2D array.

An obvious difficulty here is thus to be able to navigate through a two-dimensional array. But the difficult does not stop here: the input data is seemingly incomplete. Indeed, this is the input data that we are given:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

If I’m following the rules, here is my path (positions are marked with X, without paying attention to trees for the moment):

X.##.......
#..X#...#..
.#....X..#.
..#.#...#X# <-- Moving three steps to the right is making us go
.#...##..#.     outside of the array!!!
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

The problem tells us that this case is actually managed by copying the exact same array to its right, until we can reach the bottom-right corner. And so, we have something like the following. For better readability, I’m separating each identical array with a whitespace. And we now have our complete path.

X.##....... ..##....... ..##.......
#..X#...#.. #...#...#.. #...#...#..
.#....X..#. .#....#..#. .#....#..#.
..#.#...#X# ..#.#...#.# ..#.#...#.#
.#...##..#. .X...##..#. .#...##..#.
..#.##..... ..#.X#..... ..#.##.....
.#.#.#....# .#.#.#.X..# .#.#.#....#
.#........# .#........X .#........#
#.##...#... #.##...#... #.X#...#...
#...##....# #...##....# #...#X....#
.#..#...#.# .#..#...#.# .#..#...X.#

How can we solve this problem?

The naive approach would be to generate a larger 2D array. But that will but a lot more difficult with the actual input data which is, for me, 323 lines long. Instead, and because the same pattern is always repeating itself, we can recognize that the modulo operator might be useful here.

   0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 <-- modulo 11 values
0  X . # # . . . . . . .  . . # # . . . . . . .  . . # # . . . . . . .
1  # . . X # . . . # . .  # . . . # . . . # . .  # . . . # . . . # . .
2  . # . . . . X . . # .  . # . . . . # . . # .  . # . . . . # . . # .
3  . . # . # . . . # X #  . . # . # . . . # . #  . . # . # . . . # . #
4  . # . . . # # . . # .  . X . . . # # . . # .  . # . . . # # . . # .
5  . . # . # # . . . . .  . . # . X # . . . . .  . . # . # # . . . . .
6  . # . # . # . . . . #  . # . # . # . X . . #  . # . # . # . . . . #
7  . # . . . . . . . . #  . # . . . . . . . . X  . # . . . . . . . . #
8  # . # # . . . # . . .  # . # # . . . # . . .  # . X # . . . # . . .
9  # . . . # # . . . . #  # . . . # # . . . . #  # . . . # X . . . . #
10 . # . . # . . . # . #  . # . . # . . . # . #  . # . . # . . . X . #

Once we have realized that, we can also realize that the coordinates of each X position is actually of the form (x, 3x). We can thus propose the following solution:

# lines <- a list where each element is a line
count = 0
length = len(lines[0])  # The length of each line
for i in range(len(lines)):
    if lines[3*i % length] == "#":
        count += 1

Part 2

In Part 2, the problem is quite the same but we are asked to generalize our answer so that we can find and multiply the numbers of encountered trees when:

1. We are moving one step to the right and one step down;
2. We are moving three steps to the right and one step down;
3. We are moving five steps to the right and one step down;
4. We are moving seven steps to the right and one step down;
5. We are moving one step to the right and two steps down.

Rules 1 to 4 are quite similar to what we have done in Part 1. We simply have to modify the factor (was before 3) by the appropriate value. Rule 5 can require a little bit more thoughts. So let’s take a look at what happens when we are going down two steps.

   0 1 2 3 4 5 6 7 8 9 10  <-- modulo 11 values
0  X . # # . . . . . . .   X = (0, 0)
1  # . . . # . . . # . .
2  . X . . . . # . . # .   X = (2, 1)
3  . . # . # . . . # . #
4  . # X . . # # . . # .   X = (4, 2)
5  . . # . # # . . . . .
6  . # . X . # . . . . #   X = (6, 3)
7  . # . . . . . . . . #
8  # . # # X . . # . . .   X = (8, 4)
9  # . . . # # . . . . #
10 . # . . # X . . # . #   X = (10, 5)

We thus realize that the X positions can be generalized with a single formulae that is valid for rules 1 to 5: X = (i, R*i//D), where R is the number of steps to the right, D the number of steps down, and // symbolizes the floor division. This formulae might be a little tricky to identify, but that’s also a good exercise to practice what we might call pattern seeking.

In the end, we can define a function that would do this work for us and multiply the results of each different call to get our result.

def encounter_tree(lines, right_step, down_step):
    count = 0
    length = len(lines[0])
    for i in range(len(lines)):
        if i % down_step == 0:
            line = lines[i]
            if line[(right_step*i)//down_step % length] == "#":
                count += 1
    return count

Concepts and difficulties

In today’s challenge, there are basically two difficulties. The first one is to work with a 2D array. This means being able to work with indices for rows and columns. And to this end, it’s important to actually understand how these 2D arrays are created:

# a is a matrix, or also a "list of list"
a = [[1, 2, 3],
     [2, 3, 4],
     [3, 4, 5]]

# The first index can be used to get "rows"
a[0] == [1, 2, 3]   # True. This means that a[0] is actually a list!
a[1] == [2, 3, 4]   # Same here
a[2] == [3, 4, 5]   # and here

# Because a[0], a[1], and a[2] are lists, we can also use indices to get
# elements in these lists
a[0][2] == 3    # True
a[1][0] == 2    # True
a[2][1] == 4    # True

The second difficulty is to recognize patterns and understand that we have to use the modulo operator. This might not be obvious for programming beginners, but this operator is used pretty commonly in lots of different scenarios.