### -> -> -> USER: P0

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = []
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if not 'N' in seq:
            result.append(seq)
        else:
            index = len(seq)

            if seq[index] == 'N':
                for ch in dna_chars:
                    q.append(seq[:-1] + ch)
            else:
                indx = seq.index("N")
                for ch in dna_chars:
                    q.append(seq[:indx] +ch+ seq[indx+1:])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P1

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) <= len(pattern)
            result.append(seq)
        else:
            index = len(seq)
            current_character = pattern[index]
            if current_character == 'N':
                for ch in dna_chars:
                    q.append(seq + ch) # adding all the possible combinations
            else:
                q.append(seq + current_character)
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P2

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in pattern:
            result.append(pattern)
        else:
            index = len(seq)

            if index > 0:
                for ch in dna_chars:
                    # TODO: fill this part
                    result.append(seq + ch)
            else:
                # TODO: fill this part
                pass
    return result

print(dna_sequences("N"))
assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P3

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(q) == len(n): #m
            result.append(seq)
        else:
            index = len(seq)

            if 
                for ch in dna_chars:
                    # TODO: fill this part
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P4

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)
        
        if len(q) > 0:
            result.append(seq)
        else:
            index = len(seq)
            if pattern[index] == "N":
                for ch in dna_chars:
                    q.append(seq + ch)
                    
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P5

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if index < len(pattern):
                if pattern[index] == 'N':
                    for ch in dna_chars:
                        q.append(seq + ch)
                else:
                    q.append(seq + pattern[index])
                
    return result

assert dna_sequences('N') == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']



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

### -> -> -> USER: P6

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(pattern) == len(seq):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == "N":
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P7

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq
            result.append(seq)
        else:
            index = len(seq)

            if # TODO: fill this part:
                for ch in dna_chars:
                    result.append(ch+"")
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P8

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)
        
        if seq != '':
            result.append(seq)
        else:
            index = len(seq)
			
            if index != 1:
                for ch in dna_chars:
                    result.append(ch + seq)
            else:
                result.append(seq)

    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P9

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']


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

### -> -> -> USER: P10

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)
        
        if seq in dna_chars:
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(ch)
            else:
                result.append(pattern[index])
       
    return result

    
assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P11

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if :
                for ch in dna_chars:
                    # TODO: fill this part
                    seq += ch
                    q.append(seq)
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P12

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if "N" not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if seq.count("N") == 1:
                for ch in dna_chars:
                    index = seq.index("N")
                    partition = seq[:index + 1]
                    partition.replace("N", ch)
                    seq = partition + seq[index + 1:]

            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P13

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq.__contains__('N') is False:# TODO: fill this part
            result.append(seq)
        else:
            index = len(seq)

            if seq.__contains__('N'):# TODO: fill this part:
                for ch in dna_chars:
                    index_of_N = seq.index('N'):# TODO: fill this part
                    new_seq = seq[:index_of_N]+ch+seq[index_of_N+1:]
                    q.append(new_seq)
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P14

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if "N" not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if 0 <= index and seq[index] == 'N':
                for ch in dna_chars:
                    q.append(seq[:index] + ch + seq[index + 1:])
            else:
                
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P15

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' in patterns: 
            result.append(seq)
        else:
            index = len(seq)

            if patterns != []:
                for ch in dna_chars:
                    if 'N' in patterns:
                        result.append(seq)
            else:
                continue
                
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P16

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if : # TODO: fill this part
            result.append(seq)
        else:
            index = len(seq)

            if :# TODO: fill this part:
                for ch in dna_chars:
                    q.append(ch)
                    # TODO: fill this part
            else:
                for i in dna_chars:
                    for n in dna_chars:
                        new = i + n
                        if if not new in result:
                            result.
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P17

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []
    while len(q) > 0:
        
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P18

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if pattern[0] != "n":
            result.append(seq)
        else:
            index = len(seq)

            if pattern[0] in dna:
                for ch in dna_chars:
                   result.append(str(pattern[0]) + str(ch))
            else:
                for elem in pattern:
                    result.append(elem)
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P19

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq != '':
            result.append(seq)
        else:
            index = len(seq)

            if 
                for ch in dna_chars:
                    q.append(ch)
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P20

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if seq[index] == 'N':
                for ch in dna_chars:
                    q.append(seq[:index] + ch)
                    
            else:
                q.append(seq)
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P21

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if seq[index - 1] == 'N':
                for ch in dna_chars:
                    q.append(seq[:index - 1] + ch + seq[index - 1:])
            else:
                index -= 1
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P22

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern): 
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N': # TODO: fill this part:
                for ch in dna_chars:
                    q.append(seq + ch) # TODO: fill this part
            else:
                q.append(seq + pattern[index])# TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P23

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if "N" in seq:
            result.append(seq)
        else:
            index = len(seq)

            if seq == "N":
                for ch in dna_chars:
                    # add the letters before N and then after N, but we would need an index tracker...
                    # not sure how to do it this way
            else:
                result.append(seq)
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P24

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if "N" not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if #TODO: fill this part
                for ch in dna_chars:
                    q.append(seq[:index]+ch + seq[index + 1:])
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P25

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) < 1
            result.append(seq)
        else:
            index = len(seq)

            if seq[index] == "N"
                for ch in dna_chars:
                    result.append(ch+seq)
            else:
                result.append()
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P26

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if index > 0:
                for ch in dna_chars:
                    q.append(seq.replace('N', ch))
            else:
                return ''
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P27

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq != '':
            result.append(seq)
        else:
            index = len(seq)

            if index > 0:
                for ch in dna_chars:
                    seq[index] = ch
                    q.append(seq)
            else:
                idx = pattern.index('N')
                q.append(pattern[:idx + 1])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P28

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P29

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq and seq not in dna_chars:
            result.append(seq)
        else:
            index = len(seq)

            if seq == 'N':
                for ch in dna_chars:
                    seq.append(ch)
            else:
                result.append(seq)
                
    return result

# assert dna_sequences("N") == ['A', 'C', 'G', 'T']
# assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
# assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
# assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P30

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):# TODO: fill this part
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':# TODO: fill this part:
                for ch in dna_chars:
                    # TODO: fill this part
                    q.append(seq + ch)
            else:
                # TODO: fill this part
                q.append(seq + pattern[index])

                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P31

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P32

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) < pattern:
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index]=='N':
                for ch in dna_chars:
                    q.append(seq+ch)
            else:
                q.append(seq+pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P33

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P34

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if seq != "N"
            result.append(seq)
        else:
            index = len(seq)

            if index > 1:
                for ch in dna_chars:
                    q.append(ch)
            else:
                
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P35

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern) and 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P36

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if "N" not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if 'N' in pattern[index]:
                for ch in dna_chars:
                    replaced = pattern[index].replace('N', ch)
                    result.append(replaced)
            else:
                result.append(pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P37

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in seq:
            result.append(seq)
        else:
            index = len(seq)

            if # TODO: fill this part:
                for ch in dna_chars:
                    # TODO: fill this part
            else:
                # TODO: fill this part
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P38

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern): # TODO: fill this part
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == "N": # TODO: fill this part:
                for ch in dna_chars:
                    # TODO: fill this part
                    q.append(ch)
                    seq += ch
                    
            else:
                # TODO: fill this part
                seq += pattern[index]
                q.append(pattern[index])
    return result

print(dna_sequences("N"))
print(dna_sequences("AN"))
print(dna_sequences("NN"))
print(dna_sequences("AAN"))

# assert dna_sequences("N") == ['A', 'C', 'G', 'T']
# assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
# assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
# assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P39

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == "N":
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P40

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if 'N' not in pattern:
            result.append(seq)
        else:
            index = len(seq)

            if index < len(pattern) - 1:
                for ch in dna_chars:
                    new_seq = seq[:index] + ch + seq[index + 1:]
                    q.append(new_seq)
            else:
                raise IndexError
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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

### -> -> -> USER: P41

def dna_sequences(pattern: str) -> list[str]:
    
    dna_chars = ['A', 'C', 'G', 'T']
    q = ['']
    result = []

    while len(q) > 0:
        seq = q.pop(0)

        if len(seq) == len(pattern):
            result.append(seq)
        else:
            index = len(seq)

            if pattern[index] == 'N':
                for ch in dna_chars:
                    q.append(seq + ch)
            else:
                q.append(seq + pattern[index])
                
    return result

assert dna_sequences("N") == ['A', 'C', 'G', 'T']
assert dna_sequences("AN") == ['AA', 'AC', 'AG', 'AT']
assert dna_sequences("NN") == ['AA', 'AC', 'AG', 'AT', 'CA', 'CC', 'CG', 'CT', 'GA', 'GC', 'GG', 'GT', 'TA', 'TC', 'TG', 'TT']
assert dna_sequences("AAN") == ['AAA', 'AAC', 'AAG', 'AAT']

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