AoC Day 20

day20.py

from copy import deepcopy

import math
from typing import List, Set


def join(itr):
    return "".join(itr)


def denullify(t):
    if t is None:
        return '____'
    else:
        return str(t.ticket_num)


class Transformable:
    def __init__(self):
        self._perm_cnt = 0
        self._mat = []

    def flip_x(self):
        self._mat = [list(reversed(line)) for line in self._mat]
        self._post_transform()

    def flip_y(self):
        self._mat = list(reversed(self._mat))
        self._post_transform()

    def rotate(self):
        self._mat = list(reversed(list(zip(*self._mat))))
        self._post_transform()

    def transform(self):
        self._perm_cnt += 1
        if 1 <= self._perm_cnt <= 4:
            self.rotate()
        elif 5 <= self._perm_cnt <= 6:
            self.flip_x()
        elif 7 <= self._perm_cnt <= 8:
            self.flip_y()
        elif 9 == self._perm_cnt:
            self.flip_y()
        elif 10 <= self._perm_cnt <= 14:
            self.rotate()
        elif self._perm_cnt == 15:
            self.flip_y()
        else:
            self._perm_cnt = 0
            return True
        return False

    def _post_transform(self):
        pass

    def get_dimensions(self):
        return len(self._mat), len(self._mat[0])

    def count(self, invoke):
        return sum([1 for line in self._mat for obj in line if invoke(obj)])


class Monster(Transformable):
    def __init__(self):
        self._mat = [
            list("                  # "),
            list("#    ##    ##    ###"),
            list(" #  #  #  #  #  #   ")
        ]

    def water_chunk_contains_monster(self, chunk):
        for mon_line, chunk_line in zip(self._mat, chunk):
            for mon, c in zip(mon_line, chunk_line):
                # print(f'mon: {mon} c: {c}')
                if mon == "#" and c != "#":
                    return False
        return True


class Tile(Transformable):
    def __init__(self, lines: List[str]):
        super().__init__()
        lines_split = lines.split('\n')
        self.ticket_num = int(lines_split[0][len('Tile '):-1])
        lines_split.pop(0)
        self._mat = [list(line.strip()) for line in lines_split if line != '']
        self.connections = 0
        self.possible_connecting_tiles: Set[Tile] = set()
        self.top = None
        self.left = None
        self.right = None
        self.bottom = None
        self._populate_borders()
        self._perm_cnt = 0

    def _post_transform(self):
        self._populate_borders()

    def _populate_borders(self):
        (top, bottom, left, right) = self._borders_strings()
        self.top = self._get_bin(top)
        self.bottom = self._get_bin(bottom)
        self.left = self._get_bin(left)
        self.right = self._get_bin(right)

    def _borders_strings(self):
        return join(self._mat[0]), \
               join(self._mat[-1]), \
               join([self._mat[idx][0] for idx in range(0, len(self._mat))]), \
               join([self._mat[idx][-1] for idx in range(0, len(self._mat))])

    def get_borders(self):
        return {self.top, self.bottom, self.left, self.right}

    def get_possible_borders(self):
        tile_clone = deepcopy(self)
        borders = set()
        borders = set.union(borders, tile_clone.get_borders())

        while not tile_clone.transform():
            borders = set.union(borders, tile_clone.get_borders())
        return borders

    def _get_bin(self, s: str):
        if s is None:
            return -1
        return int(s.replace("#", '1').replace(".", '0'), 2)

    def __repr__(self):
        return f'{self.ticket_num}\n' + \
               f'\ttop: {self.top}\n\t ' + \
               f'\n left:{self.left} \t\t right:{self.right} ' + \
               f'\n\t bottom:{self.bottom} \n\t' + \
               f'\n\t'.join([''.join(line) for line in self._mat]) + \
               f'\n----------------------------------------------------------'

    def get_tile_no_borders(self):
        return [[self._mat[y][x] for x in range(1, len(self._mat) - 1)] for y in range(1, len(self._mat) - 1)]


class GridImage(Transformable):
    def __init__(self, mat):
        super().__init__()
        self._mat = mat

    def get_matrix(self):
        return self._mat

    def monster_check(self, m: Monster):
        full_img = self._mat
        (m_height, m_width) = m.get_dimensions()
        cnt = 0
        for y_offset in range(0, len(full_img) - m_height):
            for x_offset in range(0, len(full_img[0]) - m_width):
                chunk = [[full_img[y_offset + y][x_offset + x] for x in range(0, m_width)] for y in range(0, m_height)]
                # print(chunk)
                if m.water_chunk_contains_monster(chunk):
                    cnt += 1
        print(f"monster_check cnt: {cnt}")
        return cnt

    def __repr__(self):
        return f'\n'.join([''.join(line) for line in self._mat])

class Grid:
    def __init__(self, tiles: List[Tile]):
        super().__init__()
        self._tiles = tiles
        print('finding possible connections')
        for t1 in tiles:
            for t2 in tiles:
                if t1 != t2:
                    inter = set.intersection(t1.get_possible_borders(), t2.get_possible_borders())
                    if len(inter) > 0:
                        t1.connections += len(inter)
                        t1.possible_connecting_tiles.add(t2)
                        t2.possible_connecting_tiles.add(t1)
        tiles.sort(key=lambda x: x.connections)
        print('done finding possible connections')
        init_tile: Tile = tiles[0]
        self._mat: List[List[Tile]] = [[None for x in range(int(math.sqrt(len(self._tiles))))] for y in
                                       range(int(math.sqrt(len(self._tiles))))]
        self._step = self._tile_step()
        (y, x) = next(self._step)
        self._mat[y][x] = init_tile
        self._orient_tile(y, x)

        for (y, x) in self._step:
            do_not_fit = set()
            while True:
                self._place_tile(y, x, do_not_fit)
                try:
                    self._orient_tile(y, x)
                    break
                except:
                    do_not_fit.add(self._mat[y][x].ticket_num)
                    self._mat[y][x] = None

    def _already_placed_tiles(self):
        return set(tile.ticket_num for line in self._mat for tile in line if tile is not None)

    def _place_tile(self, y, x, do_not_fit=set()):
        if x > 0:
            adj_tile = self._mat[y][x - 1]
        else:
            adj_tile = self._mat[y - 1][x]
        for tile in adj_tile.possible_connecting_tiles:
            if tile.ticket_num not in self._already_placed_tiles() and tile.ticket_num not in do_not_fit:
                inter = set.intersection(adj_tile.get_borders(), tile.get_possible_borders())
                if len(inter) > 0:
                    self._mat[y][x] = tile
                    return tile

    def _orient_tile(self, y, x):
        print(f'orient y:{y} x:{x}')
        t = self._mat[y][x]
        while not self._tile_fits_position(y, x):
            reached_end = t.transform()
            if reached_end and not self._tile_fits_position(y, x):
                raise Exception('fuck')

    def _tile_fits_position(self, y, x):
        t = self._mat[y][x]
        print(f'num: {t.ticket_num} top: {t.top}')
        all_pos_conn_borders = set()
        pos_tiles = set()
        for tile in t.possible_connecting_tiles:
            pos_tiles.add(tile)
            all_pos_conn_borders = set.union(all_pos_conn_borders, tile.get_possible_borders())
        if y == 0:
            if t.top in all_pos_conn_borders:
                return False
        else:
            if t.top != self._mat[y - 1][x].bottom:
                return False
        if x == 0:
            if t.left in all_pos_conn_borders:
                return False
        else:
            if t.left != self._mat[y][x - 1].right:
                return False
        if x == len(self._mat) - 1 and t.right in all_pos_conn_borders:
            return False
        elif y == len(self._mat) - 1 and t.bottom in all_pos_conn_borders:
            return False
        elif x > 0 and t.left != self._mat[y][x - 1].right:
            return False
        elif y > 0 and t.top != self._mat[y - 1][x].bottom:
            return False
        elif x != len(self._mat) - 1 and t.right not in all_pos_conn_borders:
            return False
        elif y != len(self._mat) - 1 and t.bottom not in all_pos_conn_borders:
            return False

        print(f'found orientation for ticket_num {t.ticket_num}')
        print(t)
        return True

    def __repr__(self):
        return "\n".join([" ".join([str(t.ticket_num) for t in line]) for line in self._mat])

    def _tile_step(self):
        for y in range(0, len(self._mat)):
            for x in range(0, len(self._mat)):
                yield y, x

    def get_image_no_borders(self):
        full_img = []
        for line in self._mat:
            line_chunk = []
            for tile in line:
                if len(line_chunk) == 0:
                    line_chunk = tile.get_tile_no_borders()
                else:
                    for idx, chunk_line in enumerate(tile.get_tile_no_borders()):
                        line_chunk[idx].extend(chunk_line)
            full_img.extend(line_chunk)
        img = GridImage(full_img)
        return img


def day20():
    with open('day20input.txt', 'r') as f:
        tile_txts = f.read().split("\n\n")
        tiles = [Tile(tile_txt) for tile_txt in tile_txts]
        g = Grid(tiles=tiles)
        print(g)

        monster = Monster()
        img = g.get_image_no_borders()

        print(f'len1 {len(img.get_matrix())}')
        print(f'len2 {len(img.get_matrix()[0])}')

        cnt = img.monster_check(monster)
        while cnt == 0 and not img.transform():
            cnt = img.monster_check(monster)
        print('--')
        print(img)
        print('--')
        print(f'found monster count: {cnt}')
        all_hash = img.count(lambda x: x == "#")
        mon_hash = monster.count(lambda x: x == "#")
        print(f'all_hash count: {all_hash}')
        print(f'mon_hash count: {mon_hash}')
        print(all_hash - (mon_hash * cnt))
        print()
        # for tile in tiles:
        #     tile.print_links()
        # print(reduce(lambda x, y: x * y, [t.ticket_num for t in tiles][0:4]))


if __name__ == '__main__':
    day20()