############################################################
# Section 3: Linear Disk Movement
############################################################


def solve_identical_disks(length, n):
    graph = [[],[]] #a list of tuple moves, and a list of result boards
    start_board=[]
    for i in range(length):
        if i<n:
            start_board.append(1)
        else:
            start_board.append(0)
    frontier = [[],start_board] # a list of tuple moves, and a list of result boards
    tuple_board = list2tuple(start_board)
    visited = set(tuple_board)
    while frontier:
        moves, current_board = frontier.pop()
        if current_board.is_solved():
            #also needs list of moves
            return moves
        else:
            move, board = generate_possible_moves(current_board)



            for move, new_p in current_board.successors():

                    #print(new_p.board_list)
                    new_p_tuple = list2tuple(new_p.board_list)
                    #print(new_p_tuple)
                    if new_p_tuple not in visited:
                        temp_moves=moves+[move]
                        #moves = moves + [move]
                        #print(moves)
                        frontier = [(temp_moves, new_p)] + frontier
                        visited.add(new_p_tuple)






    return start_board

def generate_possible_moves(board):
    x = copy.deepcopy(board)
    for i in range(len(board)):
        if x[i]:
            if not x[i+1]:
                yield (x[i],x[i+1]),move_piece(x,i,i+1)
            if x[i+1] and not x[i+2]:
                yield (x[i],x[i+2]),move_piece(x,i,i+2)



def move_piece(board, start, end):
    #make sure to check that a move is valid before sending it here
    board[start]=0
    board[end]=1
    return board



def solve_distinct_disks(length, n):
    pass