print("""
Jane St Puzzle
Oct 2024 - Knight Moves 6
141 Million Valid, Optimal Solutions
By Kauri Beckmann and Dominik Tatakis
kauri.b@outlook.co.nz
### Dom do you want me to publish your email?
12/10/2024
""")

"""
We use a recursive depth-first search approach to solving Knight Moves 6.

    Search depth    Program runtime     Valid, optimal solutions found
    13              15 sec              0
    15              60 sec              581,790
    17              15 min              11,143,958
    19              100 min             141,617,662
    21              I'm running this on a 2016 Surface Pro that lags if you try to load YouTube or something, so...
"""

# STAGE 1

# Use a recursive DFS to find all possible paths from one corner to the other, up to a certain path length (ie search depth)
    # Store these possible paths as lists of coordinates

grid_size = 6
global i
i = 0
max_path_length = 17  # Defines search depth. Our realistic computational limit maxed at 19.

print("Stage 1 paths")
print("Checking pathways of up to " + str(max_path_length) + "moves")
print("Grid size = " + str(grid_size))

# Define how the knight moves
knight_moves = [
    (2, 1),  (2, -1),  (-2, 1),  (-2, -1),  # 2 squares horizontal, 1 square vertical
    (1, 2),  (1, -2),  (-1, 2),  (-1, -2)  # 2 squares vertical, 1 square horizontal
]

# Function to check if a position is valid (within bounds and not visited)
def is_valid_position(row, col, visited):
    return 0 <= row < grid_size and 0 <= col < grid_size and (row, col) not in visited

# DFS function to explore all paths from start to end
def dfs(current_position, visited, path, all_paths_set):
    global i

    # Base case: If we reach f6 (position (5, 5)) and path length <= max_path_length, add the current path to all_paths_set
    if current_position == (grid_size - 1, grid_size - 1) and len(path) <= max_path_length:
        # Convert path list to a tuple of tuples and add to list of valid paths
        all_paths_set.add(tuple(path))

    # Stop exploring further if the current path exceeds the maximum allowed length
    if len(path) > max_path_length:
        return False

    # Explore all possible knight move directions
    for direction in knight_moves:
        new_row, new_col = current_position[0] + direction[0], current_position[1] + direction[1]
        i += 1

        # Check if our move has placed us in a valid position
        if is_valid_position(new_row, new_col, visited):
            # Mark the new position as visited and add it to the current path
            visited.add((new_row, new_col))
            path.append((new_row, new_col))
            
            # Recursively explore from the new position
            if dfs((new_row, new_col), visited, path, all_paths_set):
                return True  # Stop further recursion if the limit is reached
            
            # Backtrack: remove the position from the path and visited set
            path.pop()
            visited.remove((new_row, new_col))

    return False  # Continue recursion if the limit isn't reached yet

# Initialize DFS from a1 (position (0, 0)) to f6 (position (5, 5))
start = (0, 0)  # Starting position a1
visited = set([start])  # Keep track of visited cells
all_paths_set = set()  # Store all unique valid paths (as tuples)

# Start the DFS search
dfs(start, visited, [start], all_paths_set)

# Convert set of paths back to list (optional, for ease of use)
all_paths = list(all_paths_set)

# Print the number of paths found
print(f"Total number of iterations: {i}")
print(f"Total number of unique valid paths from a6 to f1 using knight moves: {len(all_paths)}")

# Stage 2: 
# Find all possible paths for the a1 knight

# Create a grid defining positions of A, B, C
# For each path found in Stage 1,, iterate through values for A B and C

# Define the maximum sum for A, B, and C
# Since we are seeking to minimise A+B+C, set max_sum A+B+C to minimum possible, ie 6.

import pandas as pd

max_sum = 6
search_number = 2024
#print(f"Searching for total of {search_number}")

# List to store results for each set of coordinates
s2_results = []
s2_count = 0

# Iterate through each line of coordinates
for index, coordinates in enumerate(all_paths):
    results = []

    # Iterate over all possible values of A, B, and C
    for A in range(1, max_sum + 1):
        for B in range(1, max_sum + 1):
            if B == A:
                continue
            for C in range(1, max_sum + 1):
                if C in (A, B) or A + B + C > max_sum:
                    continue

                # Create the 6x6 grid
                grid = [
                    [A, B, B, C, C, C],
                    [A, B, B, C, C, C],
                    [A, A, B, B, C, C],
                    [A, A, B, B, C, C],
                    [A, A, A, B, B, C],
                    [A, A, A, B, B, C],
                ]

                # Initialize x and u for the current A, B, C
                # x is the starting score
                x = A
                # u is the current position
                u = A
                
                # Logic to calculate the move score, depending whether the move lands on the same or different square.

                # Loop through the coordinates
                for i, (row, col) in enumerate(coordinates):
                    if i == 0:  # Skip the first coordinate
                        continue
                    # v is the position we are moving to
                    # Get the grid value at (row, col)
                    v = grid[row][col]  

                    # Apply the formula based on u and v
                    if u == v:
                        x += v  # If u equals v, add v to x
                    else:
                        x *= v  # If u does not equal v, multiply x by v

                    # Update u to the current v for the next movement
                    u = v

                # Store results if x equals search_number
                if x == search_number:
                    results = [A, B, C]
                    # print(results)
                    # print(coordinates)
                    # print("Grid:")
                    # for row in grid:
                    #     print(" | ".join(f"{value:2}" for value in row))
                    # print("\n")  # Add an extra newline for spacing

                    s2_count = s2_count + 1

                    s2_results.append({
                        'number' : s2_count,
                        'coordinates': coordinates,
                        'results': results
                    })

print("Stage 2")
print(f"Number of possible paths for one the a6 knight: ", str(s2_count))

df2 = pd.DataFrame(s2_results)
print("For possible ABC values, Number of optimal pathways a6 to f1")
print("a6 knight")
print(df2['results'].value_counts())

# Stage 3

# Almost the same as stage 2...
# But consider our pathways are valid from a6 to f1.
# So, we'll simply rotate our search grid 90 degrees, and we can apply the same pathways as before.

# List to store results for each set of coordinates
s3_results = []
s3_count = 0

# Iterate through each line of coordinates
for index, coordinates in enumerate(all_paths):
    results = []

    # Iterate over all possible values of A, B, and C
    for A in range(1, max_sum + 1):
        for B in range(1, max_sum + 1):
            if B == A:
                continue
            for C in range(1, max_sum + 1):
                if C in (A, B) or A + B + C > max_sum:
                    continue

                # Create the 6x6 grid
                grid2 = [
                    [A, A, A, A, A, A],
                    [A, A, A, A, B, B],
                    [A, A, B, B, B, B],
                    [B, B, B, B, C, C],
                    [B, B, C, C, C, C],
                    [C, C, C, C, C, C],
                ]

                # Initialize x and u for the current A, B, C
                # x is the starting score
                x = A
                # u is the current position
                u = A
                

                # Loop through the coordinates
                for i, (row, col) in enumerate(coordinates):
                    if i == 0:  # Skip the first coordinate
                        continue
                    # v is the position we are moving to
                    # Get the grid value at (row, col)
                    v = grid2[row][col]  

                    # Apply the formula based on u and v
                    if u == v:
                        x += v  # If u equals v, add v to x
                    else:
                        x *= v  # If u does not equal v, multiply x by v

                    # Update u to the current v for the next movement
                    u = v

                # Store results if x equals search_number
                if x == search_number:
                    results = [A, B, C]
                    # print(results)
                    # print(coordinates)
                    # print("Grid:")
                    # for row in grid:
                    #     print(" | ".join(f"{value:2}" for value in row))
                    # print("\n")  # Add an extra newline for spacing

                    s3_count = s3_count + 1

                    s3_results.append({
                        'number' : s3_count,
                        'coordinates': coordinates,
                        'results': results
                    })

print("Stage 3")
print(f"Total number of possible paths for one the a1 knight: ", str(s3_count))
df3 = pd.DataFrame(s3_results)
print("For possible ABC values, Number of optimal pathways a1 to f6")
print(df3['results'].value_counts())

# Stage 4

# Calculate our total number of solutions

# Any [1,3,2] a6 can match any other [1,3,2] a1 pathway.
# Therefore just multiple these values together to get the total number of solutions found.

df2['results'] = df2['results'].apply(tuple)
value_counts = df2['results'].value_counts()
df3['results'] = df3['results'].apply(tuple)

# Yes, this is stupid and dumb and manual. I should have used a loop. It works, alright!?
ABC132 = df2['results'].value_counts().get((1, 3, 2), 0) * df3['results'].value_counts().get((1, 3, 2), 0)
ABC231 = df2['results'].value_counts().get((2, 3, 1), 0) * df3['results'].value_counts().get((2, 3, 1), 0)
ABC312 = df2['results'].value_counts().get((3, 1, 2), 0) * df3['results'].value_counts().get((3, 1, 2), 0)
ABC321 = df2['results'].value_counts().get((3, 2, 1), 0) * df3['results'].value_counts().get((3, 2, 1), 0)
ABC123 = df2['results'].value_counts().get((1, 2, 3), 0) * df3['results'].value_counts().get((1, 2, 3), 0)
ABC213 = df2['results'].value_counts().get((2, 1, 3), 0) * df3['results'].value_counts().get((2, 1, 3), 0)
total_solutions = ABC132 + ABC231 + ABC312 + ABC321 + ABC123 + ABC213

print("Stage 4")
print("")
print("[A B C] number of solutions")
print(f"[1 3 2]", ABC132)
print(f"[2 3 1]", ABC231)
print(f"[3 1 2]", ABC312)
print(f"[3 2 1]", ABC321)
print(f"[1 2 3]", ABC123)
print(f"[2 1 3]", ABC213)
print(f"[A B C]", total_solutions, "total solutions")

# Stage 5
# Pull up some valid solution to be submitted.

print("Stage 5")
print("Example pathway for a6 knight:")

a6_sol = 150 # Picks which solution

coordinates_2 = s2_results[a6_sol]['coordinates']

grid_labels_2 = [
    ['a6', 'b6', 'c6', 'd6', 'e6', 'f6'],
    ['a5', 'b5', 'c5', 'd5', 'e5', 'f5'],
    ['a4', 'b4', 'c4', 'd4', 'e4', 'f4'],
    ['a3', 'b3', 'c3', 'd3', 'e3', 'f3'],
    ['a2', 'b2', 'c2', 'd2', 'e2', 'f2'],
    ['a1', 'b1', 'c1', 'd1', 'e1', 'f1']
]

# s2_results[0]['coordinates'] = ((0, 0),

# Create a string that combines the grid labels
combined_labels_2 = ','.join(grid_labels_2[x][y] for x, y in coordinates_2)
print(coordinates_2)
# Print the result
ABC_a6 = s2_results[a6_sol]['results']
print(ABC_a6)
print(combined_labels_2)

print("Example pathway for a1 knight:")
a1_sol = 1122 # Picks which solution

coordinates_3 = s3_results[a1_sol]['coordinates']

#As before, a1 knight works on a rotated grid
grid_labels_3 =[
    ['a1', 'a2', 'a3', 'a4', 'a5', 'a6'],
    ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'],
    ['c1', 'c2', 'c3', 'c4', 'c5', 'c6'],
    ['d1', 'd2', 'd3', 'd4', 'd5', 'd6'],
    ['e1', 'e2', 'e3', 'e4', 'e5', 'e6'],
    ['f1', 'f2', 'f3', 'f4', 'f5', 'f6']
]

# Create a string that combines the grid labels
combined_labels_3 = ','.join(grid_labels_3[x][y] for x, y in coordinates_3)
print(coordinates)
# Print the result
ABC_a1 = s3_results[a1_sol]['results']
print(ABC_a1)
print(combined_labels_3)

if ABC_a6 == ABC_a1:
    print("Example valid answer:")
    ABC_string = ','.join(map(str, ABC_a1))
    print(ABC_string + "," + combined_labels_3 + "," + combined_labels_2)
else:
    print("Error: ABC values are different for a6 and a1")