####
# Language: python
# This solution exploits the fact that the diagonals of the grid must themselves be sorted
# Also, the number of distinct values must be at least the number of diagonals (row_size + col_size - 1) or else we can not meet the no ties constraints
# The entire list of numbers is sorted in descending order
# Then we fill the grid diagonally, beginning in the upper left corner and filling down and left for each subsequent diagonal
# Each diagonal is compared to the last so we can short circuit if they do not follow the constraints
# When a solution can not be found, we return -1
# The solution is general enough to support other size grids (even non-square)
# For the inputs provided 55 have solutions
####

import ast
row_size = 6
col_size = 6

def main():
    lines = open("RandomNumbers.txt", "r").readlines()
    answers = []
    for l in lines:
        list_initial: list[int] = parse_line(l)
        assert len(list_initial) == row_size * col_size, "There should be {} numbers... seems to be {}".format(row_size * col_size, len(list_initial))
        answer = solve(list_initial)
        answers.append(answer)
    check(answers)
    return answers

def solve(numbers: list[int]):
    distinct_numbers = set(numbers)
    num_diagonals = col_size + row_size - 1
    if len(distinct_numbers) < num_diagonals:
        print("Not enough distinct numbers to fill the grid with decreasing rows and columns.")
        return -1 # impossible to fill grid
    result = [[0 for _ in range(col_size)] for _ in range(row_size)]
    r = 0
    c = 0
    sorted_numbers_desc = sorted(numbers, reverse=True)
    diagonals = []
    return addNextHighestToResult(result, sorted_numbers_desc, r, c, diagonals)

def addNextHighestToResult(result: list[list[int]], 
    sorted_numbers_desc: list[int], 
    r: int, 
    c: int, 
    diagonals: list[list[int]]):
    if len(sorted_numbers_desc) == 0:
        return result
    # from (r,c) what is the size of the diagnoal going down left?
    print("At row {}, col {}".format(r, c))
    
    diag_size = min(row_size - r, c + 1) # problem at r>0
    print(row_size-r, c+1,diag_size)
    # get the next diag_size highest numbers from desc list
    this_diagonal = sorted_numbers_desc[:diag_size]

    if len(diagonals) > 0 and not diagonals_are_compatible(diagonals[-1], this_diagonal):
        return -1 # impossible to fill grid
    diagonals.append(this_diagonal)

    apply_diagonal_to_result(result, this_diagonal, r, c)
    # traverse top row, then rightmost column
    next_diagonal_start_row = r if c < col_size - 1 else r + 1
    next_diagonal_start_col = c + 1 if c < col_size - 1 else c
    print(diagonals)
    remaining_numbers = sorted_numbers_desc[diag_size:]
    print(remaining_numbers)
    return addNextHighestToResult(result, remaining_numbers, next_diagonal_start_row, next_diagonal_start_col, diagonals)

def diagonals_are_compatible(diagonal1: list[int], diagonal2: list[int]) -> bool:
    if diagonal1[0] == diagonal2[0]:
        return False
    if diagonal1[-1] == diagonal2[-1]:
        return False
    if diagonal1[-1] == diagonal2[0]:
        if len(diagonal1) < len(diagonal2):
            for i in range(1, len(diagonal1)):
                if diagonal1[i] == diagonal2[i]:
                    return False
        else:
            for i in range(1, len(diagonal1)):
                if diagonal1[i] == diagonal2[i-1]:
                    return False

    return True

def apply_diagonal_to_result(result: list[list[int]], diagonal: list[int], r: int, c: int):
    for i in range(len(diagonal)):
        result[r + i][c - i] = diagonal[i]

def parse_line(line) -> list[int]:
    return ast.literal_eval(line.strip())

def check(answers: list[list[int]]):
    i=1
    impossible_count = 0
    for a in answers:
        print("Answer #{}".format(i))
        i+=1
        if a == -1:
            print("Impossible to fill grid")
            impossible_count += 1
            continue
        
        assert len(a) == row_size; 
        for row in a:
            print(row)
            assert len(row) == col_size; 
        for r in range(row_size):
            for c in range(col_size):
                if r > 0: assert a[r][c] < a[r-1][c], "Column not decreasing at row {}, col {}".format(r, c)
                if c > 0: assert a[r][c] < a[r][c-1], "Row not decreasing at row {}, col {}".format(r, c)
    print("Total impossible grids: {}".format(impossible_count))

main()

####
# Language: python
# This solution exploits the idea that any set with solutions has  at least one solution where the diagonals are also sorted
# Also, the number of distinct values must be at least the number of diagonals (row_size + col_size - 1) or else we can not meet the no ties constraints
# The entire list of numbers is sorted in descending order
# Then we fill the grid diagonally, beginning in the upper left corner and filling down and left for each subsequent diagonal
# Each diagonal is compared to the last so we can short circuit if they do not follow the constraints
# When a solution can not be found, we return -1
# The solution is general enough to support other size grids (even non-square)
# For the inputs provided 55 have solutions
####

import ast
row_size = 6
col_size = 6

def main():
    lines = open("RandomNumbers.txt", "r").readlines()
    answers = []
    for l in lines:
        list_initial: list[int] = parse_line(l)
        assert len(list_initial) == row_size * col_size, "There should be {} numbers... seems to be {}".format(row_size * col_size, len(list_initial))
        answer = solve(list_initial)
        answers.append(answer)
    check(answers)
    return answers

def solve(numbers: list[int]):
    distinct_numbers = set(numbers)
    num_diagonals = col_size + row_size - 1
    if len(distinct_numbers) < num_diagonals:
        print("Not enough distinct numbers to fill the grid with decreasing rows and columns.")
        return -1 # impossible to fill grid
    result = [[0 for _ in range(col_size)] for _ in range(row_size)]
    r = 0
    c = 0
    sorted_numbers_desc = sorted(numbers, reverse=True)
    diagonals = []
    return addNextHighestToResult(result, sorted_numbers_desc, r, c, diagonals)

def addNextHighestToResult(result: list[list[int]], 
    sorted_numbers_desc: list[int], 
    r: int, 
    c: int, 
    diagonals: list[list[int]]):
    if len(sorted_numbers_desc) == 0:
        return result
    # from (r,c) what is the size of the diagnoal going down left?
    print("At row {}, col {}".format(r, c))
    
    diag_size = min(row_size - r, c + 1) # problem at r>0
    print(row_size-r, c+1,diag_size)
    # get the next diag_size highest numbers from desc list
    this_diagonal = sorted_numbers_desc[:diag_size]

    if len(diagonals) > 0 and not diagonals_are_compatible(diagonals[-1], this_diagonal):
        return -1 # impossible to fill grid
    diagonals.append(this_diagonal)

    apply_diagonal_to_result(result, this_diagonal, r, c)
    # traverse top row, then rightmost column
    next_diagonal_start_row = r if c < col_size - 1 else r + 1
    next_diagonal_start_col = c + 1 if c < col_size - 1 else c
    print(diagonals)
    remaining_numbers = sorted_numbers_desc[diag_size:]
    print(remaining_numbers)
    return addNextHighestToResult(result, remaining_numbers, next_diagonal_start_row, next_diagonal_start_col, diagonals)

def diagonals_are_compatible(diagonal1: list[int], diagonal2: list[int]) -> bool:
    if diagonal1[0] == diagonal2[0]:
        return False
    if diagonal1[-1] == diagonal2[-1]:
        return False
    if diagonal1[-1] == diagonal2[0]:
        if len(diagonal1) < len(diagonal2):
            for i in range(1, len(diagonal1)):
                if diagonal1[i] == diagonal2[i]:
                    return False
        else:
            for i in range(1, len(diagonal1)):
                if diagonal1[i] == diagonal2[i-1]:
                    return False

    return True

def apply_diagonal_to_result(result: list[list[int]], diagonal: list[int], r: int, c: int):
    for i in range(len(diagonal)):
        result[r + i][c - i] = diagonal[i]

def parse_line(line) -> list[int]:
    return ast.literal_eval(line.strip())

def check(answers: list[list[int]]):
    i=1
    impossible_count = 0
    for a in answers:
        print("Answer #{}".format(i))
        i+=1
        if a == -1:
            print("Impossible to fill grid")
            impossible_count += 1
            continue
        
        assert len(a) == row_size; 
        for row in a:
            print(row)
            assert len(row) == col_size; 
        for r in range(row_size):
            for c in range(col_size):
                if r > 0: assert a[r][c] < a[r-1][c], "Column not decreasing at row {}, col {}".format(r, c)
                if c > 0: assert a[r][c] < a[r][c-1], "Row not decreasing at row {}, col {}".format(r, c)
    print("Total impossible grids: {}".format(impossible_count))

main()