#defining a class for the map
class groveMap():
    def __init__(self):
        self.grid = []
        self.checkOrder = [((-1, -1),(-1, 0),(-1, 1)),((1, -1),(1, 0),(1, 1)),((-1, -1),(0, -1),(1, -1)),((-1, 1),(0, 1),(1, 1))]
        self.round = 0
    
    def addLine(self, line):
        self.grid.append(list(line))

    def makeMove(self, elve, destination):
        global lastRound
        if destination not in self.doubles and elve != destination:
            self.grid[elve[0]][elve[1]] = '.'
            self.grid[destination[0]][destination[1]] = '#'
            lastRound = False

    def changeOrder(self):
        self.checkOrder.append(self.checkOrder[0])
        self.checkOrder.pop(0)

    def findElves(self):
        self.round += 1
        self.extendGrid()
        elves = {}
        self.destList = []
        for y in range(len(self.grid)):
            for x in range(len(self.grid[y])):
                if self.grid[y][x] == '#':
                    dest = self.goTo(y, x)
                    elves[(y, x)] = dest
                    self.destList.append(dest)
        self.findDoubles()
        self.changeOrder()
        return elves

    def findDoubles(self):
        self.doubles = []
        for dest in self.destList:
            if self.destList.count(dest) > 1 and dest not in self.doubles:
                self.doubles.append(dest)

    def extendGrid(self):
        self.grid.append(['.' for _ in range(len(self.grid[0]))])
        self.grid.insert(0, ['.' for _ in range(len(self.grid[-1]))])
        for i in range(len(self.grid)):
            self.grid[i].insert(0, '.')
            self.grid[i].append('.')

    def goTo(self, y, x):
        count = 0
        for directions in reversed(self.checkOrder):
            dir1, dir2, dir3 = directions
            if self.grid[y + dir1[0]][x + dir1[1]] == '.' and self.grid[y + dir2[0]][x + dir2[1]] == '.' and self.grid[y + dir3[0]][x + dir3[1]] == '.':
                count += 1
                destY = y + dir2[0]
                destX = x + dir2[1]
        if count in [0, 4]:
            destY = y
            destX = x
        return (destY, destX)

    def cleanup(self):
        while True:
            if '#' in self.grid[0]:
                break
            self.grid.pop(0)
        while True:
            if '#' in self.grid[-1]:
                break
            self.grid.pop(-1)
        done = False
        while not done:
            for y in range(len(self.grid)):
                if self.grid[y][0] == '#':
                    done = True
            if done:
                continue
            for y in range(len(self.grid)):
                self.grid[y].pop(0)
        done = False
        while not done:
            for y in range(len(self.grid)):
                if self.grid[y][-1] == '#':
                    done = True
            if done:
                continue
            for y in range(len(self.grid)):
                self.grid[y].pop(-1)

    def countSolution(self):
        count = 0
        for line in self.grid:
            count += line.count('.')
        return count
            
    def testPrint(self):
        for line in self.grid:
            for point in line:
                print(point, end=' ')
            print('\n')


grove = groveMap()

#read input
with open('input23.txt', 'r') as f:
    inp = f.read().splitlines(keepends=False)

for line in inp:
    grove.addLine(line)

lastRound = False

# solves part1, uncomment testprint to display state after 10 rounds
for _ in range(10):
    elves = grove.findElves()
    for elve in elves:
        grove.makeMove(elve, elves[elve])
#grove.testPrint()
grove.cleanup()
print('Empty tiles after round 10: ', grove.countSolution())

#solve part2
while not lastRound:
    lastRound = True
    elves = grove.findElves()
    for elve in elves:
        grove.makeMove(elve, elves[elve])
    if grove.round % 100 == 0:
        grove.cleanup()
    #print(grove.round)
print('final round: ',grove.round)