"""
This code is written by CS 340 course staff in an effort to be easy to read.
This often means picking slower, longer, more C-like approaches to tasks
instead of briefer, faster, more Pythonic approaches.
"""

from collections import Counter

# a definition of the 8 neighbors of a cell
deltas = ((-1,-1), (0,-1), (1,-1),
          (-1, 0),         (1, 0),
          (-1, 1), (0, 1), (1, 1))

def starter_code(current):
    """This is the two-line GoL set-based solution from the "getting started" page"""
    counts = Counter((x+i,y+j) for (x,y) in current 
                               for (i,j) in deltas)
    return {c for c,n in counts.items() 
              if n==3 or (n==2 and c in current)}



def life_alphabet(board):
    # 1. get dimensions
    board = board[:-1].split('\n') # [:-1] removes the trailing \n
    height, width = len(board), len(board[0])
    
    # 2. get current live cells and their letters
    current = set()
    current_letters = {}
    for y in range(height):
        for x in range(width):
            if board[y][x] != ' ':
                current.add((x,y))
                current_letters[(x,y)] = board[y][x]
    
    # 3. update one time step, then update the letters too
    next = starter_code(current)
    next_letters = {}
    for (x,y) in next:
        if (x,y) in current:
            next_letters[(x,y)] = current_letters[(x,y)]
        else:
            best = 'Z' # the largest allowed value
            for old_x in (x-1,x,x+1):
                for old_y in (y-1,y,y+1):
                    if (old_x, old_y) in current_letters and current_letters[(old_x, old_y)] < best:
                        best = current_letters[(old_x, old_y)]
            next_letters[(x,y)] = best

    # 4. put it back in the desired format for return
    next_board = ''
    for y in range(height):
        for x in range(width):
            if (x,y) in next:
                next_board += next_letters[(x,y)]
            else:
                next_board += ' '
        next_board += '\n'
    return next_board


def life_ring(w, h, ticks, border):
    # 1. unwrap the border into coordinates
    border_cells = {}
    x,y = -1,-1 # start in the top-left corner
    index = 0 # and the first character in the border
    while x < w:
        border_cells[(x,y)] = border[index]
        x += 1 # move to the right along the top border
        index += 1
    while y < h:
        border_cells[(x,y)] = border[index]
        y += 1 # move down along the right border
        index += 1
    while x > -1:
        border_cells[(x,y)] = border[index]
        x -= 1 # move to the left along the bottom border
        index += 1
    while y > -1:
        border_cells[(x,y)] = border[index]
        y -= 1 # move up along the left border
        index += 1

    # 2. set up the initial board (empty)
    board = set()
    
    # repeat ticks times
    for tick in range(ticks):
        # 3. set the border cells
        for cell, character in border_cells.items():
            if character == ' ':
                if cell in board: board.remove(cell)
            elif character == '#':
                board.add(cell)
            elif character == '"':
                pass
            else:
                raise ValueError('invalid border character '+repr(character))
        
        # 4. run one tick
        board = starter_code(board)
                
    # 5. put it back in the desired format for return
    next_board = ''
    for y in range(h):
        for x in range(w):
            if (x,y) in board:
                next_board += '#'
            else:
                next_board += ' '
        next_board += '\n'
    return next_board