day 20

yesterday's one straight-up murdered me because my brain was so foggy and i have zero experience in formal languages - i've put up my working solutions but there's no chance i'm going to explain it lmao

for today's one, i'm going to just nyoom through 20b.py (it solves 20a first to get the positions and orientations of tiles). i imported numpy for the first time (and then had to roll back because it failed a sanity check...)

import numpy
# input
with open('20.txt', 'r') as file:    input = file.read()
# turn the input into a list
input_list = list(input.split('\n'))

i put together a dict of tiles by getting the tile number on the first line, removing that line, then removing lines below it and adding these to tile_val (a list of lists). if it hits a line break (a line of length 0), then we have the entire tile, so it turns tile_val into a numpy array, removes the line break from the empty list, and then restarts this process if there are still lines remaining

# go through the lines
while len(input_list) > 0:
    # grab the tile ID
    tile_str = input_list.pop(0)
    tile_key = int(tile_str.replace('Tile ','').replace(':',''))
    tile_val = []
    # add in rows until we hit a line break
    while len(input_list[0]) > 0:
        row = input_list.pop(0)
        tile_val.append(list(row))
    # we hit a line break
    tile = numpy.array(tile_val)
    tiles[tile_key] = tile
    # skip over this line break
    input_list.pop(0)

i then defined a couple of functions. the first one gets all possible orientations of the image (being an algebra man at heart, this is the image of the tile under D4 [dihedral group of a square]) - we can get eight of these just using 90 degree rotations and reflections (four by just rotation, four by a single reflection composed with these rotations). numpy has flips and a 90-degree rotation built-in (main reason i finally used it):

def d4(tile_key):
    tile = tiles[tile_key]
    # start from the base: the tile, and the tile flipped horizontally
    ttiles = [tile, numpy.fliplr(tile)]
    all_d4 = []
    # add all rotations
    for i in range(0,4):
        for ttile in ttiles:
            all_d4.append(numpy.rot90(ttile,i))
    return all_d4 # list of arrays

the second function gets the borders of a tile, and then returns these borders in a dict - this is just an exercise in slicing. the input is (tile_key, variation) where you want to get the borders of d4(tile_key)[variation]:

def borders(tile_key,variation):
    ttile = d4(tile_key)[variation]
    (rows,cols) = ttile.shape
    top = ttile[0,:]
    bottom = ttile[rows-1,:]
    left = ttile[:,0]
    right = ttile[:,cols-1]
    return {'top': top, 'bottom': bottom, 'left': left, 'right': right}

i get a list of keys of unplaced tiles, make an empty list for the puzzle - which will store a tile ID and its coordinates in the completed puzzle - and then add the first tile to this puzzle.

# get tile keys
unplaced_tiles = [tile_key for tile_key in tiles.keys()]
# puzzle is a list [n,x,y] where n is a tile key and x,y are the coordinates of it
puzzle = []
# start off with one tile
tile_key = unplaced_tiles.pop(0)
puzzle.append([tile_key, 0, 0])

one more function to get all possible places to put the next tile, given that it has to be adjacent to a tile already in the puzzle and it cannot be in the same position as a placed tile:

def next_tile_pos(puzzle):
    positions_done = [(tile[1],tile[2]) for tile in puzzle]
    adj_positions = []
    offsets = [(1,0),(-1,0),(0,1),(0,-1)]
    for pos in positions_done:
        for offset in offsets:
            adj_pos = (pos[0] + offset[0], pos[1] + offset[1])
            if not adj_pos in positions_done + adj_positions:
                adj_positions.append(adj_pos)
    return adj_positions

now we get a big while loop that just continues so long as you have at least one unplaced tile. for each instance of the loop, it gets all possible positions for a new tile. for each tile_key, it gets the list ttiles containing the eight possible orientations of the corresponding tile. for each position, it gets the surrounding tiles (to_left, ..., to_bottom) and the border_rules for the border of the piece that goes in that position - if there is a tile to one side, then the borders on that side must match (so if there's a tile to the left, the right border of that tile must match the left border of the tile you want to place).

once it has these border rules, it goes through each orientation ttile of the current tile, and checks if the borders match those of the adjacent tiles. if it doesn't match one of these, we hit a break and go to the next possible position; otherwise, we place this tile. this consists of replacing the tile in the tiles dict by ttile (simplest way to keep the right orientation for checking border rules and constructing the map in part b), adding the tile_key and its position to the puzzle list, and removing this tile_key from unplaced_tiles.

# while there are still unplaced tiles
while unplaced_tiles:
    adj_positions = next_tile_pos(puzzle)
    # go through each tile
    for tile_key in unplaced_tiles:
        # get all versions of this tile (with rotation + reflection)
        ttiles = d4(tile_key)
        # go through each possible position
        for pos in adj_positions:
            # get any puzzle pieces around it
            to_left = [tile[0] for tile in puzzle if (tile[1], tile[2]) == (pos[0] - 1, pos[1])]
            to_right = [tile[0] for tile in puzzle if (tile[1], tile[2]) == (pos[0] + 1, pos[1])]
            to_top = [tile[0] for tile in puzzle if (tile[1], tile[2]) == (pos[0], pos[1] - 1)]
            to_bottom = [tile[0] for tile in puzzle if (tile[1], tile[2]) == (pos[0], pos[1] + 1)]
            # get rules needed for a tile going in pos
            border_rules = {}
            if to_left:
                adj_tile_key = to_left[0]
                adj_tile_val = tiles[adj_tile_key]
                border_rules['left'] = borders(adj_tile_key,0)['right']
            if to_right:
                adj_tile_key = to_right[0]
                adj_tile_val = tiles[adj_tile_key]
                border_rules['right'] = borders(adj_tile_key,0)['left']
            if to_top:
                adj_tile_key = to_top[0]
                adj_tile_val = tiles[adj_tile_key]
                border_rules['top'] = borders(adj_tile_key,0)['bottom']
            if to_bottom:
                adj_tile_key = to_bottom[0]
                adj_tile_val = tiles[adj_tile_key]
                border_rules['bottom'] = borders(adj_tile_key,0)['top']
            # go through each possible version of the tile
            for i in range(0,8):
                ttile = ttiles[i]
                ttile_borders = borders(tile_key,i)
                # see if all of the border rules are satisfied
                for direction in border_rules.keys():
                    if not numpy.array_equal(ttile_borders[direction], border_rules[direction]):
                        # does not satify the rule!
                        break # next ttile
                else:
                    # satisfies all rules
                    # we want to replace tile by ttile
                    tiles[tile_key] = ttile
                    # we also want to place this tile_key in the position
                    puzzle.append([tile_key, pos[0], pos[1]])
                    # and we want to remove this tile_key from unplaced_tiles
                    unplaced_tiles.remove(tile_key)
                    break # next pos
    print('tiles placed:', len(tiles.keys()) - len(unplaced_tiles), '     ', end='\r', flush=True)

now we get all x and y values (where (x,y) are the coordinates of a tile in the puzzle) and the minimum and maximum:

# get range of x and y coordinates
x_vals = [puzzle_tile[1] for puzzle_tile in puzzle]
y_vals = [puzzle_tile[2] for puzzle_tile in puzzle]
# get max and min coordinates
max_x = max(x_vals)
max_y = max(y_vals)
min_x = min(x_vals)
min_y = min(y_vals)

we can then use every combination of {min_x, max_x} * {min_y, max_y} to get the tile IDs of the four corners of the puzzle (itch.io's gonna wrap this, rip) and then get the product of these for the answer to part a:

# get IDs at coordinates
tl = [puzzle_tile[0] for puzzle_tile in puzzle if (puzzle_tile[1],puzzle_tile[2]) == (min_x, min_y)][0]
tr = [puzzle_tile[0] for puzzle_tile in puzzle if (puzzle_tile[1],puzzle_tile[2]) == (max_x, min_y)][0]
bl = [puzzle_tile[0] for puzzle_tile in puzzle if (puzzle_tile[1],puzzle_tile[2]) == (min_x, max_y)][0]
br = [puzzle_tile[0] for puzzle_tile in puzzle if (puzzle_tile[1],puzzle_tile[2]) == (max_x, max_y)][0]
# get product
print('')
print('product of corner tile IDs (part a answer):',tl*tr*bl*br)

now we move onto part b. i'm not sure if i needed to clear unused stuff or if python does it automatically, but i just did it anyway for the sake of memory

first task is constructing the map. we correct the coordinates in puzzle to get puzzle_cc, which has min_x = min_y = 0:

puzzle_cc = [] # corrected coordinates
# also put the actual tiles in this list, not the IDs
for puzzle_tile in puzzle:
    tile_id = puzzle_tile[0]
    x = puzzle_tile[1]
    y = puzzle_tile[2]
    puzzle_cc.append([tiles[tile_id], x - min_x, y - min_y])
# set new max values
max_x -= min_x
max_y -= min_y
puzzle = [] # can just clear this
tiles = {} # and also this

next, we remove the borders from each piece - numpy.delete(tile,n,1) deletes the nth (rk. zero-indexed) column, which is what you'll see in 20b.py, but while writing this i realised i can just slice the columns as i did with the rows:

# remove borders from each piece
puzzle_nb = [] # no borders
for puzzle_tile in puzzle_cc:
    tile = puzzle_tile[0]
    x = puzzle_tile[1]
    y = puzzle_tile[2]
    # remove border
    tile = tile[1:-1,1:-1]
    puzzle_nb.append([tile, x, y])
puzzle_cc = [] # can just clear this

we now put together rows of tiles by appending the tile with coordinates (i,1) to the right (axis = 1) of the tile with coordinates (i,0), then appending (i,2) to the right of this, etc., to get a list puzzle_rows of all rows of tiles:

puzzle_rows = [] # row of tiles
for j in range(0,max_y+1):
    row = [tile[0] for tile in puzzle_nb if (tile[1],tile[2]) == (0,j)][0]
    for i in range(1,max_x+1):
        row = numpy.append(row,[tile[0] for tile in puzzle_nb if (tile[1],tile[2]) == (i,j)][0], axis = 1)
    puzzle_rows.append(row)
puzzle_nb = [] # can just clear this

and then we finish constructing the map by appending these rows to each other, but with axis = 0 so that they're added underneath:

map = puzzle_rows.pop(0)
while len(puzzle_rows) > 0:
    row = puzzle_rows.pop(0)
    map = numpy.append(map, row, axis = 0)

map now has an array of all of the tiles, without their borders, stuck together.

we now find the number of sea monsters in this map. a sea monster is given by a 3x20 array:

sm_str = '                  # \n#    ##    ##    ###\n #  #  #  #  #  #   '
sm = numpy.array([list(line) for line in sm_str.split('\n')])

it can be in any orientation, so we proceed similarly to the d4() function earlier, by getting the original sea monster, this one flipped horizontally, and then applying all four rotations to each of these. the difference here is that we have two separate lists: sea_monsters_h for horizontal (3 rows, 20 columns) sea monsters, and sea_monsters_v for vertical ones (20 rows, 3 columns). a sea monster ends up being horizontal if and only if it's rotated 90 degrees an even number of times:

sm_flip = [sm, numpy.fliplr(sm)]
sea_monsters_h = [] # ones where the sea monster is lomg
sea_monsters_v = [] # ones where the sea monster is tol
# add all rotations
for i in range(0,4):
    for smf in sm_flip:
        if i % 2 == 0:
            sea_monsters_h.append(numpy.rot90(smf,i))
        else:
            sea_monsters_v.append(numpy.rot90(smf, i))

i made an assumption for the next section in that the sea monsters didn't overlap, so i could get the answer (number of #s not in a sea monster) by getting the total number of #s and subtracting the number of #s in all the sea monsters combined. luckily this gave the right answer, so i didn't need to go back and rewrite for overlaps!

the next function takes an orientation of the sea monster as an array, the shape of this array (put this as an argument since we only have two possible shapes, so it's more efficient to calculate this separately), and the coordinate (i,j) where we want to look for this sea monster, and then returns whether the sea monster is at this coordinate. we then get the subarray of the map with the shape of the sea monster and top-left-most coordinate at (i,j). then, we iterate over every (x,y) coordinate in this subarray. if we hit a point where there is a # at that coordinate in the sea monster, but there is not a # in the subarray, then we know the sea monster isn't there, so we return false. if we get through the for loops without ever ending up in this if statement, then the sea monster is there, so we return true.

# return whether the sea monster with that orientation exists here
def find_sea_monster(sea_monster,sm_shape,i,j):
    # get subarray
    sub_map = map[i:i+sm_shape[0], j:j+sm_shape[1]]
    # pattern match
    for x in range(0,sm_shape[0]):
        for y in range(0,sm_shape[1]):
            if sea_monster[x,y] == '#' and not sub_map[x,y] == '#':
                # sea monster is not here
                return False
    # if we get here, then all of these checks passed
    return True

now we count the number of sea monsters found:

sm_found = 0

first, we find all the horizontal sea monsters, by going through every subarray of the map with the shape (3,20) - technically, by going through every coordinate that could be the top-left-most of such a subarray:

# try to find horizontal sea monsters
sm_shape = sea_monsters_h[0].shape
for sea_monster in sea_monsters_h:
    for i in range(0,map.shape[0] - sm_shape[0] + 1):
        for j in range(0,map.shape[1] - sm_shape[1] + 1):
            if find_sea_monster(sea_monster,sm_shape,i,j):
                sm_found += 1

we do the same for vertical sea monsters:

# try to find vertical sea monsters
sm_shape = sea_monsters_v[0].shape
for sea_monster in sea_monsters_v:
    for i in range(0,map.shape[0] - sm_shape[0] + 1):
        for j in range(0,map.shape[1] - sm_shape[1] + 1):
            if find_sea_monster(sea_monster,sm_shape,i,j):
                sm_found += 1

and now we print the findings and calculate the answer - num_hashes gets the number of #s in the sea monster, num_hashes_map gets the number of #s in the entire map, and then the answer we want is num_hashes_map - (sm_found * num_hashes):

print('sea monsters found:',sm_found)
num_hashes = len([char for char in sm_str if char == '#']) # number of hashes in sea monster
print('sea monsters take up',sm_found*num_hashes,'#s')
map_row_list = map.tolist()
map_elt_list = [elt for row in map_row_list for elt in row]
num_hashes_map = len([char for char in map_elt_list if char == '#'])
print('total number of hashes in map:',num_hashes_map)
print('answer to part b, if no sea monsters overlap:',num_hashes_map - (sm_found*num_hashes))

i liked this one! it forced me to actually learn some new stuff - i'm not sure if numpy will ever come up while i'm modding but actually having an array structure instead of nested lists feels v nice