Jurassic Jigsaw

Published: 2020-12-29 Original Prompt

Part 1

For part one, we’re identifying corner tiles. How do we tell a corner from any other type of piece?

The prompt tells us that each interior edge has a twin. So if we count the occurrences for each edge, we’ll know which ones only show up once. Those must be our exterior edges! And any tiles that have two such edges? Corners.

Let’s parse some input.

Given that we’ll be working closely with these tiles, I thought it worthwhile to put them into a class. It’ll take a list of strings (each newline-separated block describing a tile) and will store both the unique id and the actual points:

class Tile:
    def __init__(self, data: List[str]) -> None:
        lines = data.split("\n")

        self.num = int(lines[0].split(" ")[1][:-1])
        self.points = [tuple(line) for line in lines[1:]]

In our quests to get all sides of a tile, we’ll need to both rotate and flip the tiles:

class Tile:
    ...

    def rotate(self) -> None:
        """
        Rotates the grid 90deg clockwise. Modifies the tile.

        https://stackoverflow.com/a/8421412/1825390
        """
        self.points = list(zip(*self.points[::-1]))

    def flip(self) -> None:
        """
        Flips a tile horizontally
        """
        for i in range(len(self.points)):
            self.points[i] = tuple(reversed(self.points[i]))

Nothing much to call out here. I did pull the 2D List rotation from StackOverlfow because I couldn’t be bothered to walk through how to do something I figured existed already.

Next, we need a function to get all 8 versions of the edges of a tile. Why 8? Because the tiles can flip, so read left-to-right, there’s 2 versions of each of the 4 sides of a tile. Using the above, we’ll need to flip and rotate our way around a tile and get its top row as a string:

class Tile:
    ...

    @property
    def top_row(self) -> str:
        return "".join(self.points[0])

    def all_tops(self, skip_flip=False) -> List[str]:
        """
        Rotates and flips the tile to return each of the 8 versions of the top row.
        Modifies the tile when it runs, but has a net-zero effect on position.

        By default, does all 8 sides. Can optionally only get the non-flipped sides.
        """
        res = []
        for _ in range(4):
            res.append(self.top_row)
            self.rotate()
        if skip_flip:
            return res

        self.flip()
        for _ in range(4):
            res.append(self.top_row)
            self.rotate()
        self.flip()
        return res

Now for our solution. We’ll use a Counter, which will quickly count all unique edges it sees.

tiles = [Tile(x) for x in self.input.split("\n\n")]

c = Counter()
for tile in tiles:
    c.update(tile.all_tops())

Printing that Counter to check our work and we see that most edges were counted twice and exactly 24 (of the prompt’s example) were counted once (3 segments on 4 sides, plus the flipped ones).

Now we need to step through the tiles and count how many edges on that tile were only seen once. We don’t need to flip anymore, so I added a kwarg, skip_flip (that you may have been wondering about above), to help. Our final answer is the product of the corner ids, so we’ll compute that as we go:

result = 1
for tile in tiles:
    # find the tiles who have 2 sides that only show up once
    if len([s for s in tile.all_tops(skip_flip=True) if c[s] == 1]) == 2:
        result *= tile.num

return result

It’s a bit of a dense line, but we look at the 4 sides of an un-flipped tile and count up those whose value in the counter is 1. If that total is 2, we know we’ve got our 2 unmatched sides and we multiply the running result with the num of that tile. Tada!

Part 2

This part seems intimidating, and it requires a lot of code, but algorithmically, it’s straightforward. I’ve tweaked some part 1 code that I’ll reference below, but you should recognize it.

We’ll eventually need to look through a completed puzzle for monsters, so we must solve the puzzle. We know that given a tile, we’ll always be able to find an adjacent tile. So if we start with a corner (just like we would with any puzzle), then we can keep finding adjacent tiles until we’re done.

To start, we need to identify a corner. During part 1, we were already finding corners, so let’s stash an ID while we’re at it.

# part 1
corner_num_product = 1
corner_num = None
for tile in self.tiles:
    # find the tiles who have 2 sides that only show up once
    num_outside_edges = len(
        [s for s in tile.all_tops(skip_flip=True) if self.edge_counts[s] == 1]
    )
    if num_outside_edges == 2:
        corner_num_product *= tile.num
        if corner_num is None:
            corner_num = tile.num

So now we’ve got a corner. We need to make sure it’s facing the right way, so we need to be able to read any side of a tile. Let’s add some methods to match our top_row:

class Tile:
    ...

    # renamed to match others
    @property
    def top_side(self) -> str:
        """
        read left to right
        """
        return "".join(self.points[0])

    @property
    def bottom_side(self) -> str:
        """
        read left to right
        """
        return "".join(self.points[-1])

    @property
    def left_side(self) -> str:
        """
        read top to bottom
        """
        return "".join(x[0] for x in self.points)

    @property
    def right_side(self) -> str:
        """
        read top to bottom
        """
        return "".join(x[-1] for x in self.points)

    def get_side(self, side) -> str:
        return getattr(self, f"{side}_side")

Now we can grab any side both programmatically and by name. This lets us write a function to specify where a corner’s exterior sides should be:

class Solution():
    ...

    def align_corner(self, tile: Tile, side_a: str, side_b: str) -> None:
        """
        Modifies the `tile` so each of the passed sides are edges
        """
        while not (
            self.edge_counts[tile.get_side(side_a)] == 1
            and self.edge_counts[tile.get_side(side_b)] == 1
        ):
            tile.rotate()

# in Solution.solve()
next_tile = next(t for t in self.tiles if t.num == corner_num)
self.align_corner(next_tile, "left", "top")

Now, with our top-left corner, we can begin. We know the grid is always a square (the example is 9 tiles, the puzzle input is 144), so the height and width are both int(sqrt(len(self.tiles))). To solve the whole puzzle, we need to actually build that grid structure. If we’re at the very start of our 2d grid, we’ll grab and orient our corner:

solved: List[List[Tile]] = []
for row in range(grid_size):
    next_row: List[Tile] = []
    for column in range(grid_size):
        if column == 0 and row == 0:
            # start with any corner
            next_tile = next(t for t in self.tiles if t.num == corner_num)
            self.align_corner(next_tile, "left", "top")

It doesn’t matter which corner we start with because the puzzle can only be solved one way (and in any orientation). We’ll worry about that later.

Once we’ve got the first tile, we find whatever tiles pairs with its right side. We need a method to iterate over all tiles to find the matching one and another to orient it:

class Tile:
    ...

    def match_side(self, side: str, target: str) -> None:
        """
        Flips and rotates the tile until it's in the correct orientation for
        its `side` side to match the given one
        """
        for _ in range(4):
            if self.get_side(side) == target:
                return
            self.rotate()

        self.flip()
        for _ in range(4):
            if self.get_side(side) == target:
                return
            self.rotate()

        raise ValueError("Non-matching tile")

class Solution:
    ...

    def find_and_rotate_tile(self, side: str, target: str) -> Tile:
        for tile in self.tiles:
            if target in tile.all_tops():
                tile.match_side(side, target)
                return tile

        raise ValueError("Unable to find tile", side, target)

Back in our main loop:

    ...

    if column == 0 and row == 0:
        ...
    else:
        next_tile = self.find_and_rotate_tile(
            "left", next_row[-1].right_side
        )

    self.tiles.remove(next_tile)
    next_row.append(next_tile)

The first time through row, column we grab and store a corner. On subsequent loops, we find a tile whose left side matches the .right_side of the last tile we found. We can keep that up through the end of the row… until we get to the next row. Now next_row is empty and there’s no previous tile. Instead, we need to match off the bottom of the first tile in the row above:

    ...
    if column == 0 and row == 0:
        ...
    elif column == 0:
        next_tile = self.find_and_rotate_tile(
            "top", solved[-1][column].bottom_side
        )
    else:
        ...

solved.append(next_row)

Now we can match every tile for each row and column in the grid. No matter which one we find, we remove it from self.tiles so we don’t check it in future loops. Once it completes (and our search functions error if they fail to find, so you’ll know), we have a 2D array with our tiles connected correctly.

Now let’s start part 2.

We need to build the actual grid contents by dropping the borders of our tile:

class Tile():
    ...

    def drop_border(self) -> List[str]:
        return ["".join(row[1:-1]) for row in self.points[1:-1]]

Each row of our actual image is all of the tiles in that row (each one is 9 lines tall). So we need to zoom out a bit and build strings that are the top row of points for each tile in the solved row. If our first row is 3 tiles:

ABC DEF GHI
DEF GHI ABC
GHI ABC DEF

then our result should be:

[
    'ABCDEFGHI',
    'DEFGHIABC',
    'GHIABCDEF',
]

We can leverage the zip function, which is perfect for this. If we feed it 3 iterables (remember, tile.drop_border() gives a list of strings), it’ll give us the first item from each, the second from each, etc:

tiles = [['ABC', 'DEF', 'GHI'], ['DEF', 'GHI', 'ABC'], ['GHI', 'ABC', 'DEF']]
list(zip(*tiles))

# gives
[('ABC', 'DEF', 'GHI'), ('DEF', 'GHI', 'ABC'), ('GHI', 'ABC', 'DEF')]

Which is exactly what we want:

actual_image_strs = []
for row in solved:
    for subrow in zip(*[t.drop_border() for t in row]):
        actual_image_strs.append("".join(subrow))

So now we’ve got a list of strings that we need to flip, rotate, and search through. As luck would have it, we’ve got just the class for that! We’re going to add some new functions that will only work on a big completed image though, so let’s create a subclass:

class Image(Tile):
    def __init__(self, data: List[str]) -> None:
        # create a fake header so it looks like a huge tile
        super().__init__("\n".join(["tile 0000:", *data]))
        self.stringify_points()

    def stringify_points(self) -> None:
        self.points = ["".join(line) for line in self.points]

    def rotate(self) -> None:
        super().rotate()
        self.stringify_points()

    def flip(self) -> None:
        super().flip()
        self.stringify_points()

While Tile stores its points as a List[Tuple[str]], we’re going to be searching through our Image as strings. So every time we modify the internal representation, we should re-stringify the data. It saves us having to do so in our actual algorithm code. In any case, we now have a working image:

actual_image = Image(actual_image_strs)

The last big piece is finding monsters. Monsters follow a nice regular pattern, so they’re pretty easy to spot. They exist on 3 lines:

the middle line is #....##....##....###
the bottom line is #..#..#..#..#..# (but it starts 1 spot after the middle)
the top is a single # exactly 18 characters after the start of the middle line

In each case, the # need to be exactly that while the . can be either an actual period or a hash mark. Sounds like a job for some carefully applied regular expressions. I say carefully applied because we unfortunately can’t just count all the matches. Python doesn’t allow overlapping matches when matching regex. For example, if we’re looking for ABBA in the string ABBABBA, a human might see ABBA twice. Python only sees a single match though (even in “multi” mode), because once the middle A is matched with the first instance, only BBA is left and it fails to match. In our case, each valid regex match might not be a valid monster. It could be missing either the head or tail, so we can’t discount the whole string until we know we’ve found one.

To verify a sighting is actually pretty easy. Given a row and a column where the middle of a monster has been found, we can check the surrounding rows to ensure they match:

MONSTER_BOTTOM = r"#..#..#..#..#..#"

class Image:
    ...

    def is_monster(self, row_num: int, tail_start: int) -> bool:
        found_head = self.points[row_num - 1][tail_start + 18] == "#"
        found_bottom = bool(
            re.match(MONSTER_BOTTOM, self.points[row_num + 1][tail_start + 1 :])
        )
        return found_head and found_bottom

Note the use of re.match instead of the more versatile re.search. Since the bottom needs to start exactly 1 element after the start of the middle, we use .match to ensure the found match is at the start of the supplied string. We could also use the regex ^ character, but not building a regex string if we could avoid it is a little cleaner.

Next, actually walking the image. While we hunt for MONSTER_MIDDLEs, we don’t need to consider the first or last lines (since the head or bottom would be cut off). But, if we enumerate(self.points[1:-1]), then our index variable will be off-by-one; the index will be 0, but the row will actually be 1 (this was a nasty bug). So, we have a sort of dumb block (that totally works, which makes it not-dumb):

MONSTER_MIDDLE = r"#....##....##....###"

class Image:
    ...

    def count_monsters(self) -> int:
        # the middle of the monster can't be in the first or last line
        total = 0
        for row_num, line in enumerate(self.points[:-1]):
            # so our indexing isn't off-by-1
            if row_num == 0:
                continue

Next, we walk over each line with an int. Using an int directly instead of for x in line lets us jump manually, which will become very important. If the character we’re looking at isn’t #, we can skip it (can’t be the start of a tail). Then we re.match for the MONSTER_MIDDLE. If that’s found, we call is_monster for that row_num and index (named i). If that’s true, then we increment i by 20, the total width of a monster. Sound reasonable?

def count_monsters(self):
    ...

    for row_num, line in enumerate(self.points[:-1]):
        ...

        i = 0
        while i < len(line):
            if line[i] != "#":
                i += 1
                continue
            match = re.match(MONSTER_MIDDLE, line[i:])
            if match:
                if self.is_monster(row_num, i):
                    total += 1
                    i += 20  # total length of sea monster

            i += 1

    return total

Finally, if our image is oriented the right way, we can find and count monsters correctly. Home stretch.

The prompt makes it sound like there’s only one orientation of the image that will show monsters, so we can rotate and flip until we find any. We can use a generator function to do this. We don’t have to yield anything in particular - they’re great for “do a thing and then stop and then later, pick up where you left off”:

class Image(Tile):
    ...

    def each_orientation(self):
        for _ in range(4):
            self.rotate()
            yield None

        self.flip()
        for _ in range(4):
            self.rotate()
            yield None

    def find_monsters(self) -> int:
        for _ in self.each_orientation():
            res = self.count_monsters()
            if res:
                return res
        raise ValueError("Unable to find monster")

We search for monsters in each orientation and return if we get a non-zero answer.

Lastly, we need to count the number of # that aren’t part of the monsters. Each monster is comprised of exactly 15 #, so we can count them all and subtract 15 * num_mosters:

class Image(Tile):
    ...

    def count_waves(self, num_monsters):
        return sum([line.count("#") for line in self.points]) - (num_monsters * 15)

At long last, we can return to our actual solution, which is sort of underwhelming after all of that:

actual_image = Image(actual_image_strs)
num_monsters = actual_image.find_monsters()
num_waves = actual_image.count_waves(num_monsters)

Thanks for hanging in there!