class ProposalParser:
    """A class to parse IKE and ESP proposal strings into human-readable formats.

    This class supports parsing of IKE and ESP proposals, extracting encryption, hash, PRF (for IKE),
    and Diffie-Hellman (DH) group information. It also handles the concatenation of these components
    into a structured format, indicating whether Perfect Forward Secrecy (PFS) is enabled for ESP proposals.
    The parser uses predefined mappings for DH groups, encryption algorithms, hash functions, and Pseudo-Random Functions (PRFs).
    It can process a list of proposals and return a formatted string summarizing the cryptographic parameters.

    Attributes:
        dh_mapping (dict): A mapping of Diffie-Hellman groups to their corresponding identifiers
        enc_mapping (dict): A mapping of encryption algorithms to their corresponding identifiers
        hash_mapping (dict): A mapping of hash functions to their corresponding identifiers
        prf_mapping (dict): A mapping of Pseudo-Random Functions to their corresponding identifiers
    """

    def __init__(self):
        """Initialize the parser with mappings for DH groups, encryption, hash, and PRF."""
        self.dh_mapping = {
            'MODP_768': '1',  # RFC 2409: 768-bit MODP group (Group 1), considered weak by modern standards
            'MODP_1024': '2',  # RFC 2409: 1024-bit MODP group (Group 2), considered weak today
            'MODP_1536': '5',  # RFC 3526: 1536-bit MODP group (Group 5), stronger than Groups 1 and 2
            'MODP_2048': '14',  # RFC 3526: 2048-bit MODP group (Group 14), commonly used for modern IKE
            'MODP_3072': '15',  # RFC 3526: 3072-bit MODP group (Group 15), high security
            'MODP_4096': '16',  # RFC 3526: 4096-bit MODP group (Group 16), suitable for high-security applications
            'MODP_6144': '17',  # RFC 3526: 6144-bit MODP group (Group 17), very high security, less common
            'MODP_8192': '18',  # RFC 3526: 8192-bit MODP group (Group 18), highest MODP group, rarely used
            'ECP_256': '19',  # RFC 5903: 256-bit ECP group (NIST P-256, Group 19), efficient elliptic curve
            'ECP_384': '20',  # RFC 5903: 384-bit ECP group (NIST P-384, Group 20), stronger elliptic curve
            'ECP_521': '21',  # RFC 5903: 521-bit ECP group (NIST P-521, Group 21), high-security elliptic curve
            'ECP_192': '25',  # RFC 5903: 192-bit ECP group (NIST P-192, Group 25), weaker elliptic curve
            'ECP_224': '26',  # RFC 5903: 224-bit ECP group (NIST P-224, Group 26), intermediate security
            'MODP_1024_160': '22',  # RFC 5114: 1024-bit MODP with 160-bit subgroup (Group 22), less common
            'MODP_2048_224': '23',  # RFC 5114: 2048-bit MODP with 224-bit subgroup (Group 23), enhanced security
            'MODP_2048_256': '24',  # RFC 5114: 2048-bit MODP with 256-bit subgroup (Group 24), enhanced security
            'FFDHE_2048': '256',  # RFC 7919: 2048-bit FFDHE group, secure Diffie-Hellman parameters
            'FFDHE_3072': '257',  # RFC 7919: 3072-bit FFDHE group, secure Diffie-Hellman parameters
            'FFDHE_4096': '258',  # RFC 7919: 4096-bit FFDHE group, secure Diffie-Hellman parameters
            'FFDHE_6144': '259',  # RFC 7919: 6144-bit FFDHE group, secure Diffie-Hellman parameters
            'FFDHE_8192': '260',  # RFC 7919: 8192-bit FFDHE group, secure Diffie-Hellman parameters
            'ECP_224_BP': '27',  # RFC 6460: 224-bit Brainpool ECP group, alternative elliptic curve
            'ECP_256_BP': '28',  # RFC 6460: 256-bit Brainpool ECP group, alternative elliptic curve
            'ECP_384_BP': '29',  # RFC 6460: 384-bit Brainpool ECP group, alternative elliptic curve
            'ECP_512_BP': '30',  # RFC 6460: 512-bit Brainpool ECP group, alternative elliptic curve
            'CURVE_25519': '31',  # RFC 8031: Curve25519, modern elliptic curve for high-speed cryptography
            'CURVE_448': '32',  # RFC 8031: Curve448, modern elliptic curve for high-security cryptography
        }

        self.enc_mapping = {
            'AES_CBC_128': 'AES128',  # RFC 3602: AES-CBC with 128-bit key, standard encryption for IPsec
            'AES_CBC_192': 'AES192',  # RFC 3602: AES-CBC with 192-bit key, less common but supported
            'AES_CBC_256': 'AES256',  # RFC 3602: AES-CBC with 256-bit key, widely used for high security
            'AES_GCM_16_128': 'AES128-GCM-16',  # RFC 4106: AES-GCM with 128-bit key, 16-byte ICV
            'AES_GCM_16_192': 'AES192-GCM-16',  # RFC 4106: AES-GCM with 192-bit key, 16-byte ICV
            'AES_GCM_16_256': 'AES256-GCM-16',  # RFC 4106: AES-GCM with 256-bit key, 16-byte ICV
            'AES_GCM_8_128': 'AES128-GCM-8',  # RFC 4106: AES-GCM with 128-bit key, 8-byte ICV
            'AES_GCM_8_256': 'AES256-GCM-8',  # RFC 4106: AES-GCM with 256-bit key, 8-byte ICV
            'AES_GCM_12_128': 'AES128-GCM-12',  # RFC 4106: AES-GCM with 128-bit key, 12-byte ICV
            'AES_GCM_12_256': 'AES256-GCM-12',  # RFC 4106: AES-GCM with 256-bit key, 12-byte ICV
            'AES_CCM_16_128': 'AES128-CCM-16',  # RFC 4309: AES-CCM with 128-bit key, 16-byte ICV
            'AES_CCM_16_256': 'AES256-CCM-16',  # RFC 4309: AES-CCM with 256-bit key, 16-byte ICV
            'AES_CTR_128': 'AES128-CTR',  # RFC 3686: AES-CTR with 128-bit key, stream cipher mode
            'AES_CTR_192': 'AES192-CTR',  # RFC 3686: AES-CTR with 192-bit key, stream cipher mode
            'AES_CTR_256': 'AES256-CTR',  # RFC 3686: AES-CTR with 256-bit key, stream cipher mode
            '3DES_CBC': '3DES',  # RFC 2451: Triple DES in CBC mode, legacy encryption
            'DES_CBC': 'DES',  # RFC 2405: DES in CBC mode, considered insecure today
            'CAMELLIA_CBC_128': 'CAMELLIA128',  # RFC 5529: Camellia-CBC with 128-bit key
            'CAMELLIA_CBC_256': 'CAMELLIA256',  # RFC 5529: Camellia-CBC with 256-bit key
            'CHACHA20_POLY1305': 'CHACHA20-POLY1305',  # RFC 7634: ChaCha20 with Poly1305, modern AEAD cipher
            'BLOWFISH_CBC': 'BLOWFISH',  # RFC 2451: Blowfish in CBC mode, legacy and less secure
            'CAST5_CBC': 'CAST5',  # RFC 2144: CAST-128 in CBC mode, legacy encryption
        }

        self.hash_mapping = {
            'HMAC_MD5': 'MD5',  # RFC 2403: HMAC-MD5, considered weak by modern standards
            'HMAC_MD5_96': 'MD5',  # RFC 2403: HMAC-MD5 with 96-bit truncation, weak
            'HMAC_SHA1': 'SHA1',  # RFC 2404: HMAC-SHA1, widely used but aging
            'HMAC_SHA1_96': 'SHA1',  # RFC 2404: HMAC-SHA1 with 96-bit truncation
            'HMAC_SHA2_256': 'SHA2-256',  # RFC 4868: HMAC-SHA256, strong hash function
            'HMAC_SHA2_256_128': 'SHA2-256',  # RFC 4868: HMAC-SHA256 with 128-bit truncation
            'HMAC_SHA2_384': 'SHA2-384',  # RFC 4868: HMAC-SHA384, stronger hash function
            'HMAC_SHA2_384_192': 'SHA2-384',  # RFC 4868: HMAC-SHA384 with 192-bit truncation
            'HMAC_SHA2_512': 'SHA2-512',  # RFC 4868: HMAC-SHA512, very strong hash function
            'HMAC_SHA2_512_256': 'SHA2-512',  # RFC 4868: HMAC-SHA512 with 256-bit truncation
            'HMAC_SHA3_224': 'SHA3-224',  # RFC 8446 (TLS context): SHA3-224, modern hash function, experimental for the most part
            'HMAC_SHA3_256': 'SHA3-256',  # RFC 8446 (TLS context): SHA3-256, modern hash function, experimental for the most part
            'HMAC_SHA3_384': 'SHA3-384',  # RFC 8446 (TLS context): SHA3-384, modern hash function, experimental for the most part
            'HMAC_SHA3_512': 'SHA3-512',  # RFC 8446 (TLS context): SHA3-512, modern hash function, experimental for the most part
            'AES_GMAC_128': 'GMAC-128',  # RFC 4543: AES-GMAC with 128-bit key, for authentication
            'AES_GMAC_192': 'GMAC-192',  # RFC 4543: AES-GMAC with 192-bit key, for authentication
            'AES_GMAC_256': 'GMAC-256',  # RFC 4543: AES-GMAC with 256-bit key, for authentication
            'POLY1305': 'POLY1305',  # RFC 7539: Poly1305, used with ChaCha20 for authentication
        }

        self.prf_mapping = {
            'PRF_HMAC_MD5': 'MD5',  # RFC 2403 (via IKEv1): HMAC-MD5 PRF, weak by modern standards
            'PRF_HMAC_SHA1': 'SHA1',  # RFC 2404 (via IKEv1): HMAC-SHA1 PRF, widely used but aging
            'PRF_HMAC_SHA2_256': 'SHA2-256',  # RFC 4868: HMAC-SHA256 PRF, strong and common
            'PRF_HMAC_SHA2_384': 'SHA2-384',  # RFC 4868: HMAC-SHA384 PRF, stronger PRF
            'PRF_HMAC_SHA2_512': 'SHA2-512',  # RFC 4868: HMAC-SHA512 PRF, very strong PRF
            'PRF_AES128_CMAC': 'AES128-CMAC',  # RFC 4494: AES-CMAC with 128-bit key, secure PRF
            'PRF_AES128_XCBC': 'AES128-XCBC',  # RFC 4434: AES-XCBC PRF, alternative to CMAC
            'PRF_HMAC_SHA3_224': 'SHA3-224',  # RFC 8446 (TLS context): SHA3-224 PRF, modern algorithm, experimental for the most part
            'PRF_HMAC_SHA3_256': 'SHA3-256',  # RFC 8446 (TLS context): SHA3-256 PRF, modern algorithm, experimental for the most part
            'PRF_HMAC_SHA3_384': 'SHA3-384',  # RFC 8446 (TLS context): SHA3-384 PRF, modern algorithm, experimental for the most part
            'PRF_HMAC_SHA3_512': 'SHA3-512',  # RFC 8446 (TLS context): SHA3-512 PRF, modern algorithm, experimental for the most part
        }

    def _categorize_component(self, component, is_ike):
        """Categorize a proposal component into encryption, hash, PRF, or DH group."""
        enc_keywords = ['AES_CBC', 'AES_GCM', 'AES_CTR', 'CHACHA20', 'BLOWFISH', 'CAST5', 'DES', '3DES', 'CAMELLIA']
        hash_keywords = ['HMAC_SHA', 'HMAC_MD5', 'POLY1305', 'AES_GMAC']
        dh_keywords = ['MODP_', 'ECP_', 'FFDHE_', 'CURVE_']

        if (component in self.enc_mapping or any(s in component for s in enc_keywords)):
            return 'encryption', component
        elif is_ike and 'PRF_' in component:
            return 'prf', component
        elif (component in self.hash_mapping or any(s in component for s in hash_keywords)) and not component.startswith("PRF_"):
            return 'hash', component
        elif (component in self.dh_mapping or any(s in component for s in dh_keywords)):
            return 'dh_group', component
        elif component == 'NO_EXT_SEQ':
            return 'skip', component
        else:
            return 'unknown', component

    def _map_encryption(self, enc_components, result):
        """Map encryption components to their corresponding identifiers."""
        for enc in enc_components:
            mapped_enc = self.enc_mapping.get(enc, 'Unknown')
            if mapped_enc != 'Unknown' and mapped_enc not in result['encryption']:
                result['encryption'].append(mapped_enc)

    def _map_hash_and_prf(self, enc_components, hash_components, prf_components, result):
        """Map hash and PRF components, handling AEAD ciphers."""
        # Map hash components (skip for AEAD ciphers like AES-GCM, AES-CCM, CHACHA20-POLY1305)
        if not any(enc.startswith('AES_GCM') or enc.startswith('AES_CCM') or enc == 'CHACHA20_POLY1305' for enc in enc_components):
            for hash_val in hash_components:
                mapped_hash = self.hash_mapping.get(hash_val, 'Unknown')
                if mapped_hash not in result['hash']:
                    result['hash'].append(mapped_hash)
        else:
            result['hash'].append('None')

        # Map PRF components
        for prf in prf_components:
            mapped_prf = self.prf_mapping.get(prf, 'Unknown')
            if mapped_prf not in result['prf']:
                result['prf'].append(mapped_prf)

    def _map_dh_group(self, dh_components, result):
        """Map Diffie-Hellman group components to their corresponding identifiers."""
        for dh in dh_components:
            mapped_dh = self.dh_mapping.get(dh)
            if mapped_dh != 'None' and mapped_dh not in result['dh_group']:
                result['dh_group'].append(mapped_dh)

    def parse_ike_proposal(self, proposal):
        """
        Parse an IKE or ESP proposal string into a structured format.

        Args:
            proposal (str): The proposal string, e.g., "IKE:AES_CBC_256/HMAC_SHA2_256/PRF_HMAC_SHA2_256/MODP_2048"

        Returns:
            dict: A dictionary with keys 'encryption', 'hash', 'prf', and 'dh_group'
        """
        # Split the proposal into components based on '/'
        components = proposal.split('/')

        result = {
            'encryption': [],
            'hash': [],
            'prf': [],
            'dh_group': []
        }

        is_ike = proposal.startswith('IKE:')
        is_esp = proposal.startswith('ESP:')

        # Remove IKE or ESP prefix if present for easier parsing
        if is_ike or is_esp:
            components[0] = components[0].replace('IKE:', '').replace('ESP:', '')

        enc_components = []
        hash_components = []
        prf_components = []
        dh_components = []
        unknown_components = []

        # Categorize components
        for component in components:
            category, value = self._categorize_component(component, is_ike)
            if category == 'encryption':
                enc_components.append(value)
            elif category == 'hash':
                hash_components.append(value)
            elif category == 'prf':
                prf_components.append(value)
            elif category == 'dh_group':
                dh_components.append(value)
            elif category == 'unknown':
                unknown_components.append(value)

        # Map components to their identifiers
        self._map_encryption(enc_components, result)
        self._map_hash_and_prf(enc_components, hash_components, prf_components, result)
        self._map_dh_group(dh_components, result)

        # Handle ESP case (no PRF for ESP proposals)
        if is_esp:
            result['prf'] = ['None']

        # Set defaults if no valid components found
        if not result['encryption']:
            result['encryption'] = ['Unknown']
        if not result['hash']:
            result['hash'] = ['None']
        if not result['prf']:
            result['prf'] = ['None']
        if not result['dh_group']:
            result['dh_group'] = ['None']

        return result

    def collect_components(self, proposals):
        """Collect unique encryption, hash, PRF, and DH group components from a list of proposals."""
        enc_set = set()
        hash_set = set()
        prf_set = set()
        dh_set = set()
        all_aead = True

        for proposal in proposals:
            parsed = self.parse_ike_proposal(proposal.strip())
            enc_set.update(parsed['encryption'])
            
            # Check if the proposal uses a non-AEAD cipher
            if not any('GCM' in enc or 'CCM' in enc or 'CHACHA20' in enc for enc in parsed['encryption']):
                hash_set.update(parsed['hash'])
                all_aead = False
            prf_set.update(parsed['prf'])
            if parsed['dh_group'] != ['None']:
                dh_set.update(parsed['dh_group'])

        # If all proposals are AEAD, set hash to "None"
        if all_aead and not hash_set:
            hash_set.add('None')

        return enc_set, hash_set, prf_set, dh_set

    def format_output(self, enc_set, hash_set, prf_set, dh_set, is_ike):
        """Format the collected components into a human-readable string."""
        # Convert sets to sorted lists
        enc_list = sorted(list(enc_set))
        hash_list = sorted(list(hash_set))
        prf_list = sorted(list(prf_set))
        dh_list = sorted(list(dh_set), key=lambda x: int(x))

        # Determine PFS status for ESP proposals only
        pfs_status = "PFS: Enabled" if dh_set and not is_ike else "PFS: None"

        # Format output as a single concatenated string
        enc_part = f"Encryption: {', '.join(enc_list)}" if enc_list else "Encryption: None"
        hash_part = f"Hash: {', '.join(hash_list)}" if hash_list else "Hash: None"
        dh_part = f"DH Group(s): {', '.join(dh_list)}" if dh_list else "DH Group(s): None"
        prf_part = f"PRF: {', '.join(prf_list)}" if prf_list else "PRF: None"

        # Return formatted string based on whether it's an IKE or ESP proposal
        if is_ike:
            return f"{enc_part} {hash_part} {prf_part} {dh_part}"
        else:
            return f"{enc_part} {hash_part} {dh_part} {pfs_status}"

    def process_proposals(self, proposal_list):
        """
        Process a list of IKE or ESP proposals, concatenating encryption, hash, PRF (for IKE only),
        and DH group values, and indicate whether PFS is enabled for ESP proposals only.

        Args:
            proposal_list (str): Comma-separated string of IKE or ESP proposals

        Returns:
            str: Formatted string with concatenated encryption, hash, PRF (for IKE), DH groups, and PFS status (for ESP)
        """
        if proposal_list is None:
            return "No proposals provided"

        if not proposal_list:
            return "No proposals provided"

        if not (proposal_list.startswith('IKE:') or proposal_list.startswith('ESP:')):
            return "Invalid proposal format. Proposals must be of type 'IKE' for Phase 1 or 'ESP' for Phase 2"

        proposal_list = proposal_list.replace(',', ', ')
        proposals = proposal_list.strip().split(', ')
        is_ike = any(proposal.startswith('IKE:') for proposal in proposals)

        enc_set, hash_set, prf_set, dh_set = self.collect_components(proposals)
        return self.format_output(enc_set, hash_set, prf_set, dh_set, is_ike)
# Example usage
if __name__ == "__main__":
    parser = ProposalParser()

    # unknown_hash = "IKE:AES_CBC_256/HMAC_SHA22222/PRF_HMAC_SHA2_256/MODP_2048"
    # none_hash = "IKE:AES_CBC_256/PRF_HMAC_SHA2_256/MODP_2048"

    # # Outputs: Encryption: AES256 Hash: None PRF: SHA2-256 DH Group(s): 14
    # print(parser.process_proposals(unknown_hash))

    # # Outputs: Encryption: AES256 Hash: None PRF: SHA2-256 DH Group(s): 14
    # print(parser.process_proposals(none_hash))

    proposal = "IKE:AES_GCM_16_256/MODP_2048/NO_EXT_SEQ"

    print(parser.process_proposals(proposal))

"""
Assignment 6

The goal is to make a graph of
who bit who and who was bitten.
There should be 10 nodes and 15 edges.
3 arrows of biting each other and
3 arrows of someone biting themselves.
Networkx can not do self biting
arrows, but it is in the code.
"""

from graphviz import Digraph as DDotGraph
from graphviz import Graph as UDotGraph
import networkx as nx
from networkx.algorithms.dag import transitive_closure
import graphviz as gv
import matplotlib.pyplot as plt
import numpy as np
from numpy.linalg import matrix_power

"""
class DGraph:
    def __init__(self):
        self.d = dict()

    def clear(self):
        self.d = dict()

    def add_node(self,n):
        if not self.d.get(n):
            self.d[n] = set()

    def add_edge(self,e):
        f,t=e
        self.add_node(f)
        self.add_node(t)
        vs=self.d.get(f)
        if not vs:
            self.d[f] = {t}
        else:
            vs.add(t)

    def add_edges_from(self,es):
        for e in es:
            self.add_edge(e)

    def edges(self):
        for f in self.d:
            for t in self.d[f]:
                yield (f,t)

    def number_of_nodes(self):
        return len(self.d)

    def __repr__(self):
        return self.d.__repr__()

    def show(self):
        dot = gv.Digraph()
        for e in self.edges():
            #print(e)
            f, t = e
            dot.edge(str(f), str(t), label='')
        #print(dot.source)
        show(dot)

# displays graph with graphviz
def show(dot, show=True, file_name='graph.gv'):
    dot.render(file_name, view=show)


def showGraph(g,label="",directed=True):
    if directed:
        dot = gv.Digraph()
    else:
        dot = gv.Graph()

    for e in g.edges():
        print(e)
        f, t = e
        dot.edge(str(f), str(t), label=label)
    print(dot.source)
    show(dot)


def bit():
    G = DGraph()
    G.add_edge(("Blade","Samara"))
    G.add_edge(("Shadow","Wolfe"))
    G.add_edge(("Raven", "Austin"))
    G.add_edge(("Blade", "Alice"))
    G.add_edge(("Alice","Brandon"))
    G.add_edge(("Blade", "Wolfe"))
    G.add_edge(("Samara", "Robin"))
    G.add_edge(("Samara", "Raven"))
    G.add_edge(("Samara", "Hamed"))
    G.add_edge(("Wolfe", "Blade"))
    G.add_edge(("Hamed", "Samara"))
    G.add_edge(("Wolfe", "Shadow"))
    G.add_edge(("Brandon", "Brandon"))
    G.add_edge(("Hamed", "Hamed"))
    G.add_edge(("Austin", "Austin"))
    showGraph(G, label="bit")

bit()

def bitten():
    G=DGraph()
    G.add_edge(("Samara","Blade"))
    G.add_edge(("Wolfe","Shadow"))
    G.add_edge(("Austin", "Raven"))
    G.add_edge(("Alice","Blade"))
    G.add_edge(("Brandon", "Alice"))
    G.add_edge(("Wolfe", "Blade" ))
    G.add_edge(("Robin", "Samara"))
    G.add_edge(("Raven", "Samara"))
    G.add_edge(("Hamed", "Samara"))
    G.add_edge(("Blade", "Wolfe"))
    G.add_edge(("Samara", "Hamed"))
    G.add_edge(("Shadow", "Wolfe"))
    G.add_edge(("Brandon", "Brandon"))
    G.add_edge(("Hamed", "Hamed"))
    G.add_edge(("Austin", "Austin"))
    showGraph(G, label="bitten by")

#bitten()

family = ["Blade", "Samara", "Shadow", "Wolfe", "Raven", "Alice"]
"""

#Do transitive closure call out and the
#matrix power operation should be the same
D = nx.DiGraph()
#D.add_nodes_from("SamaraBladeWolfeShadowAliceRavenBrandonRobinHamedAustin")
D.add_edge("Blade","Samara")
D.add_edge("Shadow","Wolfe")
D.add_edge("Raven", "Austin")
D.add_edge("Blade", "Alice")
D.add_edge("Alice","Brandon")
D.add_edge("Blade", "Wolfe")
D.add_edge("Samara", "Robin")
D.add_edge("Samara", "Raven")
D.add_edge("Samara", "Hamed")
D.add_edge("Wolfe", "Blade")
D.add_edge("Hamed", "Samara")
D.add_edge("Wolfe", "Shadow")
D.add_edge("Brandon", "Brandon")
D.add_edge("Hamed", "Hamed")
D.add_edge("Austin", "Austin")

T = transitive_closure(D)

for e in D.edges(): print(e)
for n in D.nodes(): print(n)

def show(H):
    nx.draw(H, with_labels=True, font_weight='bold')
    plt.show()
#Use nx.to_numpy_matrix instead of nx.adjacency_matrix

# M = nx.adjacency_matrix(D)
# MT = nx.adjacency_matrix(T)
M = nx.to_numpy_matrix(D)
MT = nx.to_numpy_matrix(T)
M2 = M@M

def mPower(M, k): #M is numpy matrix
    assert k >= 1
    P = M
    for _ in range(k):
       P = P @ M
    return P

def tc(M):
    #compute transitive closure
    pass

D1 = nx.DiGraph(M)
D2 = nx.DiGraph(M2)

print('Matrix for Original\n', M)
N = nx.to_numpy_array(D,dtype=int)
print('np_array for Original\n', N)
print('\nMatrix for Transitive Closure\n', MT)
N2 = nx.to_numpy_array(T,dtype=int)
print('np_array for Transitive Closure\n', N2)

show(D) #can use D, T, and numpy matrix power operation
show(T)
show(T)

prime_lists=[] # a list to store the prime numbers

def prime(n): # define prime numbers
    if n <= 1:
        return False
    # divide n by 2... up to n-1
    for i in range(2, n):
        if n % i == 0:  # the remainder should'nt be a 0
            return False
    else:
        prime_lists.append(n)
        return True



for n in range(30,1000):  # calling function and passing starting point =30 coz we need primes >30
    prime(n)

check=0 # a var to limit the output  to 10 only
for n in prime_lists:
    for x in prime_lists:
        val=  n *x
        if (val > 1000 ):
            check=check +1
        if (check <10) :
            print("the num is:", val , "=",n , "* ", x )
        break

print(“Hello World”)

#Sets
U = {0,1,2,3,4,5,6,7,8,9}
P = {1,2,3,4}
Q = {4,5,6}
R = {3,4,6,8,9}

def set2bits(xs,us) :
    bs=[]
    for x in us :
        if x in xs :
            bs.append(1)
        else:
            bs.append(0)
    assert len(us) == len(bs)
    return bs

def union(set1,set2) :
    finalSet = set()
    bitList1 = set2bits(set1, U)
    bitList2 = set2bits(set2, U)

    for i in range(len(U)) :
        if(bitList1[i] or bitList2[i]) :
            finalSet.add(i)

    return finalSet

def intersection(set1,set2) :
    finalSet = set()
    bitList1 = set2bits(set1, U)
    bitList2 = set2bits(set2, U)

    for i in range(len(U)) :
        if(bitList1[i] and bitList2[i]) :
            finalSet.add(i)

    return finalSet

def compliment(set1) :
    finalSet = set()
    bitList = set2bits(set1, U)

    for i in range(len(U)) :
        if(not bitList[i]) :
            finalSet.add(i)

    return finalSet

def implication(a,b):
    return union(compliment(a), b)

###########################################################################################
######################         Problems 1-6         #######################################
###########################################################################################

#p \/ (q /\ r) = (p \/ q) /\ (p \/ r)
def prob1():
    return union(P, intersection(Q,R)) == intersection(union(P,Q), union(P,R))

#p /\ (q \/ r) = (p /\ q) \/ (p /\ r)
def prob2():
    return intersection(P, union(Q,R)) == union(intersection(P,Q), intersection(P,R))

#~(p /\ q) = ~p \/ ~q
def prob3():
    return compliment(intersection(P,R)) == union(compliment(P), compliment(R))

#~(p \/ q) = ~p /\ ~q
def prob4():
    return compliment(union(P,Q)) == intersection(compliment(P), compliment(Q))

#(p=>q) = (~q => ~p)
def prob5():
    return implication(P,Q) == implication(compliment(Q), compliment(P))

#(p => q) /\ (q => r)  =>  (p => r)
def prob6():
    return implication(intersection(implication(P,Q), implication(Q,R)), implication(P,R))


print("Problem 1: ", prob1())
print("Problem 2: ", prob2())
print("Problem 3: ", prob3())
print("Problem 4: ", prob4())
print("Problem 5: ", prob5())
print("Problem 6: ", prob6())

'''
Problem 1:  True
Problem 2:  True
Problem 3:  True
Problem 4:  True
Problem 5:  True
Problem 6:  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
'''

# @return a list of strings, [s1, s2]
def letterCombinations(self, digits):
    if '' == digits: return []
    kvmaps = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }
    return reduce(lambda acc, digit: [x + y for x in acc for y in kvmaps[digit]], digits, [''])