from os.path import dirname,realpath,join

from collections.abc import Callable
def profiler(method) -> Callable[..., any]:
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret
    return wrapper_method

@profiler
def solver(locks_and_keys_str: str) -> int:
    locks_list = []
    keys_list  = []

    for schematic in locks_and_keys_str.split('\n\n'):
        if schematic[0] == '#':
            locks_list.append(tuple([column.index('.') for column in zip(*schematic.split())]))
        else:
            keys_list.append(tuple([column.index('#') for column in zip(*schematic.split())]))
    
    count = 0
    for lock_configuration in locks_list:
        for key_configuration in keys_list:
            for i,l in enumerate(lock_configuration):
                if l>key_configuration[i]:
                    # break on the first configuration that is invalid
                    break
            else:
                # skipped when loop is broken
                count += 1
    
    return count

if __name__ == "__main__":
    BASE_DIR = dirname(realpath(__file__))
    with open(join(BASE_DIR, r'input'), 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = solver(input_data)
    print("Day 25 final solve:", result)

#
    # we step through a proper Ripple Carry adder and check if the gate is correct for the given input.
    # first level is will start with all the initial input gates.
    # these must have XOR and AND as gates.
    marked_problem_gates = defaultdict(lambda: defaultdict(list))
    # dict of the full adder as the index and the value of what the next wires lead to.
    full_adder_dict = defaultdict(lambda: defaultdict(lambda: defaultdict(list)))
    for i in range(len(wire_states)//2):
        for (a_key,gate,b_key),output_wire in connections['x'+str(i).rjust(len(next(iter(wire_states)))-1, '0')]:
            if i == 0:
                matching_z_wire = 'z' + str(i).rjust(len(next(iter(wire_states)))-1, '0')
                # we check the first adder as it should have the correct output wire connections for a half adder type.
                if gate == 'XOR' and output_wire != matching_z_wire:
                    # for the half adder the final sum output bit should be a matching z wire.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                elif gate == 'AND' and (output_wire.startswith('z') and (output_wire[1:].isdigit())):
                    # for the half adder the carry over bit should not be a z wire.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                if output_wire in connections:
                    full_adder_dict[i][gate][output_wire].extend(connections[output_wire])
            else:
                # since the first adder is a half-adder, we only need to check the other adders to verify that their output wire is not to a z wire.
                if (output_wire.startswith('z') and (output_wire[1:].isdigit())):
                    # if the output wire is a z wire, we mark the gate as a problem.
                    marked_problem_gates[i][gate].append(((a_key,gate,b_key),output_wire))
                else:
                    # we get what the output wires to the next step in the adder would be.
                    full_adder_dict[i][gate][output_wire].extend(connections[output_wire])
    
    # for the next step in the full adders, we expect the carry over bit from the previous step in the adder should be have.
    # 
    
    print(marked_problem_gates)
    print(full_adder_dict)

from os.path import dirname,realpath,join
from itertools import combinations as itertools_combinations
from collections import defaultdict

from collections.abc import Callable
def profiler(method) -> Callable[..., any]:
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret
    return wrapper_method

@profiler
def build_graph(connections: list[str]) -> defaultdict[set[str]]:
    """
    Builds an adjacency list from the list of connections.
    """
    adj = defaultdict(set)
    for conn in connections:
        nodes = conn.strip().split('-')
        nodes.sort()
        node1, node2 = nodes
        adj[node1].add(node2)
        adj[node2].add(node1)
    
    return adj

@profiler
def count_unique_triads(adj: defaultdict[set[str]]) -> int:
    """
    Counts the number of unique triads where a 't_node' is connected to two other nodes
    that are also directly connected to each other. Ensures that each triad is counted only once.
    """
    unique_triads = set()
    
    # Identify all nodes starting with 't' (case-insensitive)
    t_nodes = [node for node in adj if node.lower().startswith('t')]
    
    for t_node in t_nodes:
        neighbors = adj[t_node]
        if len(neighbors) < 2:
            continue  # Need at least two neighbors to form a triad
        
        # Generate all unique unordered pairs of neighbors
        for node1, node2 in itertools_combinations(neighbors, 2):
            if node2 in adj[node1]:
                # Create a sorted tuple to represent the triad uniquely
                triad = tuple(sorted([t_node, node1, node2]))
                unique_triads.add(triad)
    
    return len(unique_triads)

def all_connected(nodes: tuple, adj: defaultdict[set[str]]) -> bool:
    """
    Determines if all nodes are connected to each other by checking if every node is reachable from any other node.
    Effectively determines if a clique exists.
    """
    for i,node in enumerate(nodes):
        for j in range(i + 1, len(nodes)):
            if nodes[j] not in adj[node]:
                return False
    return True

@profiler
def find_largest_clique(adj: defaultdict[set[str]]) -> list[str]:
    """
    Iterates over each vertex and its neighbors to find the largest clique. A clique is a subset of nodes where every pair of nodes is connected by an edge.
    The function returns the vertices of the largest clique found. If no clique is found, it returns an empty list.
    """
    # Keep track of the largest connected set found so far
    best_connected_set = tuple(['',''])
    # Iterate over each vertex in the graph with the neighbors
    for vertex, neighbors in adj.items():
        # Since the clique must have all nodes share similar neighbors then we can start with the size of the neighbors and iterate down to a clique size of 2
        for i in range(len(neighbors), len(best_connected_set)-1, -1):
            # we don't check smaller cliques because they will be smaller than the current best connected set
            if i < len(best_connected_set):
                break
            for comb in itertools_combinations(neighbors, r=i):
                if all_connected(comb, adj):
                    best_connected_set = max(
                        (*comb, vertex), best_connected_set, key=len
                    )
                    break
    return sorted(best_connected_set)

# Solve Part 1 and Part 2 of the challenge at the same time
@profiler
def solver(connections: str) -> tuple[int, str]:
    # Build the graph
    adj = build_graph(connections.splitlines())
    # return the count of unique triads and the largest clique found
    return count_unique_triads(adj),','.join(find_largest_clique(adj))

if __name__ == "__main__":
    BASE_DIR = dirname(realpath(__file__))
    with open(join(BASE_DIR, r'input'), 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = solver(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])

from tqdm import tqdm
from os.path import dirname,isfile,realpath,join

from collections.abc import Callable
def profiler(method) -> Callable[..., any]:
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret
    return wrapper_method

# Process a secret to a new secret number
# @param n: The secret number to be processed
# @return: The new secret number after processing
def process_secret(n: int) -> int:
    """ 
    Process a secret number by XORing it with the result of shifting left and right operations on itself. 
    The process involves several bitwise operations to ensure that the resulting number is different from the original one.
    
    First, multiply the original secret number by 64 with a left bit shift, then XOR the original secret number with the new number and prune to get a new secret number
    Second, divide the previous secret number by 32 with a right bit shift, then XOR the previous secret number with the new number and prune to get another new secret number
    Third, multiply the previous secret number by 2048 with a left bit shift, then XOR the previous secret number with the new number and prune to get the final secret number
    Finally, return the new secret number after these operations.

    """
    n ^= (n << 6) 
    n &= 0xFFFFFF
    n ^= (n >> 5)
    n &= 0xFFFFFF
    n ^= (n << 11)
    return n & 0xFFFFFF

# Solve Part 1 and Part 2 of the challenge at the same time
@profiler
def solve(secrets: list[int]) -> tuple[int, int]:
    # Build a dictionary for each buyer with the tuple of changes being the key and the sum of prices of the earliest occurrence for each buyer as the value
    # At the same time we solve Part 1 of the challenge by adding the last price for each secret
    last_price_sum = 0
    changes_map = {}
    for start_secret in (secrets):
        # Keep track of seen patterns for current secret
        changes_seen = set()
        # tuple of last 4 changes
        # first change is 0 because it is ignored
        last_four_changes = tuple([
                                    (cur_secret:=process_secret(start_secret)), 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) , 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) , 
                                   -(cur_secret%10) + ((cur_secret:=process_secret(cur_secret)) % 10) 
                                   ]
                                   )
        current_price = sum(last_four_changes)
        # Map 4-tuple of changes -> sum of prices index of earliest occurrence for all secrets
        for i in range(3, 1999):
            # sliding window of last four changes
            last_four_changes = (*last_four_changes[1:], -(cur_secret%10) + (current_price := (cur_secret:=process_secret(cur_secret)) % 10) )
            # if we have seen this pattern before, then we continue to next four changes
            # otherwise, we add the price to the mapped value
            # this ensures we only add the first occurence of a patten for each list of prices each secret produces
            if last_four_changes not in changes_seen:
                # add to the set of seen patterns for this buyer
                changes_seen.add(last_four_changes)
                # If not recorded yet, store the price
                # i+4 is the index of the price where we sell
                changes_map[last_four_changes] = changes_map.get(last_four_changes, 0) + current_price

        # Sum the 2000th price to the total sum for all secrets
        last_price_sum += cur_secret
    # Return the sum of all prices at the 2000th iteration and the maximum amount of bananas that one pattern can obtain
    return last_price_sum,max(changes_map.values())

if __name__ == "__main__":
    # Read buyers' initial secrets from file or define them here
    BASE_DIR = dirname(realpath(__file__))
    with open(join(BASE_DIR, r'input'), "r") as f:
        secrets = [int(x) for x in f.read().split()]
    last_price_sum,best_score = solve(secrets)
    print("Part 1:")
    print(f"sum of each of the 2000th secret number:", last_price_sum)
    print("Part 2:")
    print("Max bananas for one of patterns:", best_score)

from collections import deque

def profiler(method):
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret

    return wrapper_method

def build_aho_corasick(towels):
    # Each node: edges dict, failure link, output (which towels end here)
    trie = [{'fail': 0, 'out': []}]
    
    # Build trie of towels
    for index, word in enumerate(towels):
        node = 0
        for char in word:
            if char not in trie[node]:
                trie[node][char] = len(trie)
                trie.append({'fail': 0, 'out': []})
            node = trie[node][char]
        trie[node]['out'].append(len(word))  # store length of matched towel

    # Build fail links (BFS)
    queue = deque()
    # Initialize depth-1 fail links
    for c in trie[0]:
        if c not in ('fail', 'out'):
            nxt = trie[0][c]
            trie[nxt]['fail'] = 0
            queue.append(nxt)

    # BFS build deeper fail links
    while queue:
        r = queue.popleft()
        for c in trie[r]:
            if c in ('fail', 'out'):
                continue
            nxt = trie[r][c]
            queue.append(nxt)
            f = trie[r]['fail']
            while f and c not in trie[f]:
                f = trie[f]['fail']
            trie[nxt]['fail'] = trie[f][c] if c in trie[f] else 0
            trie[nxt]['out'] += trie[trie[nxt]['fail']]['out']
    return trie

def count_possible_designs_aho(trie, design):
    n = len(design)
    dp = [0] * (n + 1)
    dp[0] = 1

    # State in the trie automaton
    state = 0

    for i, char in enumerate(design, 1):
        # Advance in trie
        while state and char not in trie[state]:
            state = trie[state]['fail']
        if char in trie[state]:
            state = trie[state][char]
        else:
            state = 0
        
        # For every towel match that ends here:
        for length_matched in trie[state]['out']:
            dp[i] += dp[i - length_matched]
    
    return dp[n]

@profiler
def main(input_data):
    towels,desired_patterns = ( sorted(x.split(), key=len, reverse=True) for x in input_data.replace(',', ' ').split('\n\n') )
    part1 = 0
    part2 = 0
    
    # Build Aho-Corasick structure
    trie = build_aho_corasick(towels)
    
    for pattern in desired_patterns:
        count = count_possible_designs_aho(trie, pattern)
        if count:
            part1 += 1
            part2 += count
    
    return part1,part2

if __name__ == "__main__":
    with open('input', 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = main(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])