import re

def find_indices_of_words(text, words_to_find):
    word_indices = {}

    for word in words_to_find:
        indices = [match.start() for match in re.finditer(r'\b' + re.escape(word) + r'\b', text)]
        if indices:
            word_indices[indices[0]] = word

    return word_indices

def validate_credit_card(card_number: str) -> bool:
    # 1. Change datatype to list[int]
    card_number = [int(num) for num in card_number]

    # 2. Remove the last digit:
    checkDigit = card_number.pop(-1)

    # 3. Reverse the remaining digits:
    card_number.reverse()

    # 4. Double digits at even indices
    card_number = [num * 2 if idx % 2 == 0
                   else num for idx, num in enumerate(card_number)]

    # 5. Subtract 9 at even indices if digit is over 9
    # (or you can add the digits)
    card_number = [num - 9 if idx % 2 == 0 and num > 9
                   else num for idx, num in enumerate(card_number)]

    # 6. Add the checkDigit back to the list:
    card_number.append(checkDigit)

    # 7. Sum all digits:
    checkSum = sum(card_number)

    # 8. If checkSum is divisible by 10, it is valid.
    return checkSum % 10 == 0

def extract_sensitive_data(text):
    ssns = re.findall(r'\b(\d{3}-\d{2}-\d{4})\b', text)
    phone_number_pattern = re.compile(r'\(\d{3}\) \d{3}-\d{4}')
    phone_numbers = phone_number_pattern.findall(text)
    credit_card_numbers = re.findall(r'\b(\d{16})\b', text)
    email_addresses = re.findall(r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b', text)
    

    return ssns, credit_card_numbers, email_addresses, phone_numbers

def extract_last_characters(data):
    return [entry[-1] for entry in data]

def main():
    with open('file.txt', 'r') as file:
        file_contents = file.read()

    ssns, credit_card_numbers, email_addresses, phone_numbers = extract_sensitive_data(file_contents)
    
    valid_credit_card_number = []
    for cc in credit_card_numbers:
    	if validate_credit_card(cc) == True:
    		valid_credit_card_number.append(cc)
    ssns_index_dict = find_indices_of_words(file_contents,ssns)
    cc_index_dict = find_indices_of_words(file_contents,valid_credit_card_number)
    email_index_dict = find_indices_of_words(file_contents,email_addresses)    
    pn_index_dict = {}
    for phone in phone_numbers:
    	pn_index_dict[file_contents.index(phone)] = phone
    
    final_dict = ssns_index_dict | cc_index_dict | email_index_dict | pn_index_dict
    
    
    final_dict = dict(sorted(final_dict.items()))
    last = extract_last_characters(final_dict.values())

    flag = f'HQ8{{{"".join(last)}}}'
    
    
    print("\nFlag:", flag)

if __name__ == "__main__":
    main()