Advent of Code - Day 9

Day 9: Movie Theater

In the movie theater we’re looking at a red and green tile floor. The example looks like this where other tiles are “.” and red tiles are “#”.

7,1
11,1
11,7
9,7
9,5
2,5
2,3
7,3

But it can be visualized in a grid as follows:

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

Part 1

This first part is to calculate the area of the largest rectangle. This was fairly straightforward to brute force. For every red tile loop through all other red tile positions and calculate the area. Then sort the results so the largest is the first value. This is your answer.

Part 2

In this part the tiles contained within the shape of the original example are green. Now using only red and green tiles return the largest area.

..............
.......#XXX#..
.......XXXXX..
..#XXXX#XXXX..
..XXXXXXXXXX..
..#XXXXXX#XX..
.........XXX..
.........#X#..
..............

This part seemed similar to the first and initially I tried to solve it by adding some additional checks for the contents of each area. This proved to be computationally expensive on the actual input and frankly it didn’t work.

Instead of solving this challenge myself I decided to review others solutions and learn from them. One such solution included itertools for more efficient iteration.

candidates = []
for square in combinations(tiles, 2):
    if not intersects(square[0], square[1], sliding_window(tiles, 2)):
        candidates.append(square)

print(max([sq_size(a, b) for (a, b) in candidates]))

The combinations function is used to generate all possible combinations of elements. This was the part that was tripping me up the most with manipulating part 1 to solve part 2. From there we have the sliding window that returns the elements of the input.

The intersect function returns False if the rectangle we’re checking is contained within the shape created by red and green tiles. That square is then added to the list of candidates and we eventually take the max like in part 1.

Again this was a solution found on the subreddit that I found. I learned some new techniques from this solution.