Untitled

from itertools import product
import numpy as np
from functools import partial
from multiprocessing import Pool, cpu_count


# Helper functions
def rotate_bits(binary_str):
    """Generate all rotated versions of a binary string."""
    n = len(binary_str)
    return [binary_str[i:] + binary_str[:i] for i in range(n)]


def hamming_distance(bin1, bin2):
    """Calculate the Hamming distance between two binary strings."""
    return sum(bit1 != bit2 for bit1, bit2 in zip(bin1, bin2))


def is_valid_sequence(sequence):
    """Check if a sequence satisfies the one-bit change property."""
    return all(hamming_distance(sequence[i], sequence[i + 1]) == 1 for i in range(len(sequence) - 1))


def evaluate_pattern(ep):
    """Evaluate the pattern of the EP based on groups of 1."""
    groups = [len(group) for group in ep.split('0') if group]
    groups.sort()
    return groups


def compare_patterns(new_pattern, best_pattern):
    """Compare two patterns to determine the most optimal based on LLOSG1 and LNOTSG1."""
    for i in range(min(len(new_pattern), len(best_pattern))):
        if new_pattern[i] > best_pattern[i]:
            return True
        elif new_pattern[i] < best_pattern[i]:
            return False
    return len(new_pattern) < len(best_pattern)


def generate_EP(n_bit_binaries):
    """Generate the EP by transposing the binary matrix of the given sequence."""
    matrix = np.array([list(binary) for binary in n_bit_binaries])
    transposed_matrix = matrix.T
    ep = "".join(transposed_matrix.flatten())
    return ep, matrix, transposed_matrix


def recursive_search(path, used, depth, binary_numbers, all_rotations):
    """Recursive search for optimal sequence."""
    best_pattern = None
    best_sequence = None
    best_ep = None
    best_original_matrix = None
    best_transposed_matrix = None

    # Base case: if the path forms a complete sequence
    if depth == len(binary_numbers):
        ep, original_matrix, transposed_matrix = generate_EP(path)
        pattern = evaluate_pattern(ep)

        return pattern, path[:], ep, original_matrix, transposed_matrix

    # Recursive step: add unused rotations to the path
    for i in range(len(binary_numbers)):
        if not used[i]:
            for rotation in all_rotations[i]:
                if not path or hamming_distance(path[-1], rotation) == 1:
                    path.append(rotation)
                    used[i] = True

                    # Recursive call
                    result = recursive_search(path, used, depth + 1, binary_numbers, all_rotations)
                    if result:
                        pattern, sequence, ep, original_matrix, transposed_matrix = result
                        if best_pattern is None or compare_patterns(pattern, best_pattern):
                            best_pattern = pattern
                            best_sequence = sequence
                            best_ep = ep
                            best_original_matrix = original_matrix
                            best_transposed_matrix = transposed_matrix

                    # Backtrack
                    used[i] = False
                    path.pop()

    # Return best results for this branch
    if best_pattern is not None:
        return best_pattern, best_sequence, best_ep, best_original_matrix, best_transposed_matrix
    return None


# Parallelized function wrapper
def parallel_worker(task_data):
    binary_numbers, all_rotations, start_index = task_data
    path = [all_rotations[start_index][0]]
    used = [False] * len(binary_numbers)
    used[start_index] = True
    return recursive_search(path, used, 1, binary_numbers, all_rotations)


def find_most_optimal_pattern(binary_numbers):
    """Find the Gray code combination producing the most optimal EP."""
    all_rotations = [rotate_bits(binary) for binary in binary_numbers]

    # Parallelization setup
    tasks = [(binary_numbers, all_rotations, i) for i in range(len(binary_numbers))]
    best_pattern = None
    best_sequence = None
    best_ep = None
    best_original_matrix = None
    best_transposed_matrix = None

    with Pool(cpu_count()) as pool:
        results = pool.map(parallel_worker, tasks)

    # Determine the best result from all parallel tasks
    for result in results:
        if result is not None:
            pattern, sequence, ep, original_matrix, transposed_matrix = result
            if best_pattern is None or compare_patterns(pattern, best_pattern):
                best_pattern = pattern
                best_sequence = sequence
                best_ep = ep
                best_original_matrix = original_matrix
                best_transposed_matrix = transposed_matrix

    return best_sequence, best_ep, best_original_matrix, best_transposed_matrix


# TNC generation
def is_tnc(binary_number):
    """
    Check if a binary number is a TNC (unique binary sequence under rotation).
    """
    rotations = set()
    n = len(binary_number)
    for i in range(n):
        rotated = binary_number[i:] + binary_number[:i]
        rotations.add(rotated)
    return len(rotations) == n and binary_number == min(rotations)


def generate_tnc(n):
    """Generate all TNC for n-bit binary numbers."""
    tnc_list = []
    for binary_number in product("01", repeat=n):
        binary_str = "".join(binary_number)
        if is_tnc(binary_str):
            tnc_list.append(binary_str)
    return tnc_list


# Main execution flow
if __name__ == "__main__":
    n = int(input("Enter the number of bits: "))
    tnc_list = generate_tnc(n)
    print(f"TNCs for {n} bits: {tnc_list}")
    print(f"Number of TNCs: {len(tnc_list)}\n")

    best_sequence, best_ep, best_original_matrix, best_transposed_matrix = find_most_optimal_pattern(tnc_list)

    if best_sequence:
        print("Optimal Gray Code Sequence:", best_sequence)
        print("\nOriginal Matrix:")
        print(best_original_matrix)
        print("\nTransposed Matrix:")
        print(best_transposed_matrix)
        print("\nEP:", best_ep)
    else:
        print("No valid Gray Code sequence found.")