from typing import Tuple, List, Any
from marshmallow import Schema, fields, validates, ValidationError

MATRIX_ROW_LENGTH = 5
MATRIX_COL_LENGTH = 5
MATRIX_LENGTH = MATRIX_COL_LENGTH * MATRIX_ROW_LENGTH

MATRIX_MIN_VALUE = 11
MATRIX_MAX_VALUE = 55

MATRIX_START_CELL = (1, 1)


####################### Functionality implementation ##################

def validate_matrix_data(data: Tuple[int]) -> Tuple[int]:
    """Validate given data before create matrix."""
    if len(data) != MATRIX_LENGTH:
        raise Exception(f"Length of matrix must be equal to {MATRIX_LENGTH}")

    for value in data:
        if not isinstance(value, int):
            raise Exception(
                f"Values in given data must be of type Integer, not {type(value).__name__}")

        if value not in range(MATRIX_MIN_VALUE, MATRIX_MAX_VALUE + 1):
            raise Exception(
                f"Values in given data must be in range {MATRIX_MIN_VALUE} - {MATRIX_MAX_VALUE}")

    return data


def create_matrix(validated_data: Tuple[int]) -> List[List[int]]:
    """Create matrix from validated data."""
    matrix = []
    while validated_data:
        matrix.append(validated_data[:MATRIX_ROW_LENGTH])
        validated_data = validated_data[MATRIX_ROW_LENGTH:]

    return matrix


def do_next_step(matrix: List[List[int]],
                 row_index: int,
                 col_index: int,
                 steps_taken: Any = None
                 ) -> List[int]:
    """
    Take the next step to find the treasure.
    If the treasure was found - returns an array of steps taken.
    """
    found_value = matrix[row_index - 1][col_index - 1]

    if not steps_taken:
        steps_taken = []
    else:
        if found_value == steps_taken[-1]:
            return steps_taken

    steps_taken.append(found_value)
    next_row_index, next_col_index = int(str(found_value)[0]), int(str(found_value)[1])

    return do_next_step(matrix, next_row_index, next_col_index, steps_taken)


def search_treasure(*data: Tuple[int]) -> List[int]:
    """Preparing matrix and processing steps for find a treasure."""
    validated_data = validate_matrix_data(data)
    matrix = create_matrix(validated_data)
    steps_to_treasure = do_next_step(matrix, MATRIX_START_CELL[0], MATRIX_START_CELL[1])

    return steps_to_treasure


#################### OOP Implementation ##################

class TreasureMap:

    def __init__(self,
                 MATRIX_ROW_LENGTH: int, MATRIX_COL_LENGTH: int,
                 MATRIX_MIN_VALUE: int, MATRIX_MAX_VALUE: int,
                 MATRIX_LENGTH: int,
                 ValidateSchema: Schema,
                 data: List[int]
                 ) -> None:

        self.MATRIX_ROW_LENGTH = MATRIX_ROW_LENGTH
        self.MATRIX_COL_LENGTH = MATRIX_COL_LENGTH
        self.MATRIX_MIN_VALUE = MATRIX_MIN_VALUE
        self.MATRIX_MAX_VALUE = MATRIX_MAX_VALUE

        self.set_validator(ValidateSchema)
        self.create_matrix(data)

    def set_validator(self, ValidateSchema: Schema) -> None:
        if not issubclass(ValidateSchema, Schema):
            raise ValidationError("ValidateSchema must be type of marshmallow.Schema")
        self._validator = ValidateSchema

    def create_matrix(self, data: List[int]) -> None:
        validated_data = self._validator().load({"data": data})
        validated_data = validated_data["data"]

        matrix = []
        while validated_data:
            matrix.append(validated_data[:self.MATRIX_ROW_LENGTH])
            validated_data = validated_data[self.MATRIX_ROW_LENGTH:]

        self._matrix = matrix

    def get_matrix_number(self, row_index: int, col_index: int) -> int:
        return self._matrix[row_index - 1][col_index - 1]


class MatrixValidateSchema(Schema):
    data = fields.List(fields.Integer(), required=True)

    @validates("data")
    def validate_data(self, data: List[int]) -> List[int]:
        if len(data) != MATRIX_LENGTH:
            raise ValidationError(f"Length of matrix must be equal to {MATRIX_LENGTH}")

        for value in data:
            if value not in range(MATRIX_MIN_VALUE, MATRIX_MAX_VALUE + 1):
                raise Exception(
                    f"Values in given data must be in range {MATRIX_MIN_VALUE} - {MATRIX_MAX_VALUE}")

        return data


class TreasureSearcher:

    def __init__(self,
                 matrix: TreasureMap,
                 MATRIX_START_CELL: Tuple[int, int]
                 ) -> None:

        self.matrix = matrix
        self.row_index = MATRIX_START_CELL[0]
        self.col_index = MATRIX_START_CELL[1]
        self.steps_taken = []
        self.search_is_completed = False

    def __call__(self) -> None:
        self.search_treasure()

    def search_treasure(self) -> List[int]:
        while not self.search_is_completed:
            self.do_next_step()

        return self.steps_taken

    def do_next_step(self) -> None:
        next_matrix_number = self.matrix.get_matrix_number(self.row_index, self.col_index)

        if self.steps_taken and next_matrix_number == self.steps_taken[-1]:
            self.search_is_completed = True
        else:
            self.steps_taken.append(next_matrix_number)
            self.row_index = int(str(next_matrix_number)[0])
            self.col_index = int(str(next_matrix_number)[1])



if __name__ == '__main__':
    # In Functionality

    print(search_treasure(
        55, 14, 25, 52, 21,
        44, 31, 11, 53, 43,
        24, 13, 45, 12, 34,
        42, 22, 43, 32, 41,
        51, 23, 33, 54, 15)
    )

    # In OOP
    data = [55, 14, 25, 52, 21,
            44, 31, 11, 53, 43,
            24, 13, 45, 12, 34,
            42, 22, 43, 32, 41,
            51, 23, 33, 54, 15]

    matrix = TreasureMap(
        MATRIX_ROW_LENGTH=MATRIX_ROW_LENGTH, MATRIX_COL_LENGTH=MATRIX_COL_LENGTH,
        MATRIX_MIN_VALUE=MATRIX_MIN_VALUE, MATRIX_MAX_VALUE=MATRIX_MAX_VALUE,
        MATRIX_LENGTH=MATRIX_LENGTH,
        ValidateSchema=MatrixValidateSchema,
        data=data
    )

    treasure_searcher = TreasureSearcher(matrix, MATRIX_START_CELL)

    print(treasure_searcher.search_treasure())