import sys
import copy
import os
import math
import scipy
import scipy.sparse as sp
import numpy as np
import gmpy2
gmpy2.get_context().precision = 1000

# Works best on python 3.8, at least for me.
# Exact 3 Cover
S = [5,33,24,45,46,47,564,12,234]
S_dict = {element: True for element in S}
C = {5,33,24},{24,5,33},{45,46,47},{24,46,33}
#########################################################################
# Making sure subsets follow the rules of combinations

# Rules for input that does not violate the correctness for general Exact 3 Cover
# Only one permutation of a subset is needed to form a solution (eg. {1,2,3} and {3,2,1})
# Only subsets that have elements in S are allowed
# subsets are only of size 3
# Subsets must contain no duplicates
# Only one occurrence of a subset

valid_subsets_dict = {}
valid_subsets = []
for SL in C:
    # Make sure that subsets have 3 elements
    if len(SL) == 3:
        # Make sure only subsets with elements in S are considered
        if all(element in S_dict for element in SL):
            # Remove multiple permutations of subsets and only
            # allows one occurrence of a subset
            # Does not affect the correctness of deciding if a solution exists
            # because you only need one permutation to form a solution.
            if tuple(sorted(SL)) not in valid_subsets_dict:
                valid_subsets_dict[tuple(sorted(SL))] = True
                # Since sets aren't subscribtable I have to convert them to a list.
                # I have to touch the subsets to perform the reduction.
                valid_subsets.append(list(SL))

C = valid_subsets
# Creating a copy of C to make sure that I can reverse the reduction to show
# the original solution
C_copy = copy.deepcopy(C)

#########################################################################
def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True
# Get the first N odd primes
def get_primes_up_to_N(N):
    primes = []
    num = k[len(k)-1] + 1
    while len(primes) < N:
        if is_prime(num):
            primes.append(num)
        num += 1
    return primes

#########################################################################
# Generate primes following the pattern
# [3,5,7]  Size 3
# [11,13,17,19,23,29]  Size 6
# [31, 37, 41, 43, 47, 53, 59, 61, 67]   Size 9
# Go to last iteration, such as [3,5,7] Notice i[len(i)-1] is 7
# Find prime larger than i[len(i)-1] which is 11
# Generate N odd primes start at 11, which is 11,13,17,19,23,29. Where N is six.
# Raise each odd prime to the powers of 5,6,7 in sequential order (eg. a^5, b^6, c^7, d^5, e^6, f^7, g^5...)
# This ensures list of different sizes always has a unique list of odd primes. And that it uses primes larger than the last one


k = [2]
N = 0
new_S = []
while len(new_S) != len(S):
    N = N + 3
    B = [i for i in range(1, N + 1)]
    primes = get_primes_up_to_N(len(B))
    k = primes
    Y = [5,6,7]
    new_S = []
    i = 0
    x = 0
    while len(new_S) != len(B):
        new_S.append(primes[x]**Y[i])
        i = i + 1
        x = x + 1
        if i == 3:
            i = 0
#########################################################################

# Create a dictionary to map elements in S to their indices in new_S
index_mapping = {element: new_S[index] for index, element in enumerate(S)}

# Define N for Subset Sum dynamic solution
N = sum(new_S)
# sums from the collection of transformed subsets
sums = []
# Mapping new C
for SL in C:
    for j in range(len(SL)):
        # Use the dictionary to map the elem to its corresponding value in new_S
        SL[j] = index_mapping[SL[j]]
    sums.append(sum(SL))

#########################################################################

# Function to write a list to a file on the flash drive
def write_list_to_file(filename, data):
    with open(filename, 'wb') as f:  # Open the file in binary mode
        for row in data:
            # Convert boolean values to bytes before writing to file
            row_bytes = bytearray([1 if cell else 0 for cell in row])
            f.write(row_bytes)
            f.write(b'\n')  # Add newline separator

#############################################################################################

# Function to read a list from a file on the flash drive
def read_list_from_file(filename):
    with open(filename, 'rb') as f:  # Open the file in binary mode
        return [[byte != 0 for byte in line.strip()] for line in f]

#########################################################################

def isSubsetSumSolidStateDrive(arr, n, target, filename):
    # Initialize a set to store the indices of subset sums that are possible
    subset_indices = set()
    subset_indices.add(0)  # 0 is always possible

    # Perform dynamic programming and write intermediate results to the flash drive
    with open(filename, 'wb') as f:  # Open the file in binary write mode
        for i in range(1, n + 1):
            new_indices = set()
            for j in subset_indices:
                new_indices.add(j + arr[i - 1])

            subset_indices.update(new_indices)

            # Convert boolean values to bytes and write them to the file
            for j in range(target + 1):
                f.write(np.uint8(int(j in subset_indices)).tobytes())

    # Backtrack to find the solution
    # backtracking does not explore all possible subsets exhaustively.
    # Instead, it prunes the search space
    # This pruning is based on the information stored in the subset table.
    solution = []
    j = target
    for i in range(n, 0, -1):
        if j - arr[i - 1] in subset_indices:
            solution.append(arr[i - 1])
            j -= arr[i - 1]

    return target in subset_indices, solution[::-1]  # Return whether solution exists and the solution itself

#########################################################################

# You must put the path here for the SSD. SSD should be dedicated to this algorithm.
# Otherwise, the algorithm will throw a hissy fit
# You have to physically write out the file name on the 1 Terabyte SSD, case sensitive

subset_table_file = 'C:\\Users\\....\\....\\...\\subset_table.txt'
# Function to reset the subset table file before using the code.
def reset_subset_table(filename):
    with open(filename, 'w') as f:
        pass  # Simply open the file in write mode, which clears its contents
reset_subset_table(subset_table_file)

#########################################################################

n = len(sums)
# Call isSubsetSumSolidStateDrive function with SSD file path
solution = isSubsetSumSolidStateDrive(sums, n, N, subset_table_file)
cover = []
# Reverse the reduction in order verify if the algorithm
# was able to find a solution.
if solution[0] == True:
    get_i = solution[1]
    for i in get_i:
        get_index = sums.index(i)
        reverse_map = C_copy[get_index]
        cover.append(reverse_map)


if len(cover) == len(S)//3:
    # flatten the list and check for duplicates
    F = [item for sublist in cover for item in sublist]
    if len(F) == len(set(F)):
        print('Solution Exists')
else:
    print('no solution found')