The problem in matter can be found here: Problem #79

"A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length."

So far I've been able to find the number of digits making up the passcode, but I can't order them. I'm working on defining a simple function that will return the position of each digit in regard with the others and finally figure out the final position and the Passcode.

If anyone can help, here is my work so far:

# Open the file and create a list from a set in order to remove duplicates.
with open('D:\\Development\\keylog.txt', 'r') as file:
    logins = list(set(file.read().split()))

# Create three separate sets with the positions of the digits.
first_digits = set()
second_digits = set()
third_digits = set()

for login in logins:
    first_digits.add(login[0])
    second_digits.add(login[1])
    third_digits.add(login[2])

newSet = (first_digits | second_digits | third_digits)

# After the three sets are combined it will return another set of 8 digits.
# From this we can deduce that the shortest passcode is made from the 8 different digits.
# The set looks like this: {'3', '7', '2', '6', '1', '0', '9', '8'}

# def A function that gives the order of the digits in the passcode.

I've tried a few variations of functions like "is_before(x)" or "is_after(x)" but it gets way to complicated for me and also not working or returning the final answer.

CodePudding user response：

Do you believe that the answer is ten digits or less with no digit repeated? (A much harder problem would have strings like both 762 and 726, and you would have to figure out which gives you the shorter solution.)

In that case just repeat the following:

1. Find a digit that only appears as the first digit of your remaining strings.
2. Add that digit to the key code
3. Remove that digit from front of every string that it appears in. If the string is now empty, remove it.
4. If you've removed all the strings, you're done. Otherwise, go back to step 1.

In essence, this is a simplified topological sort.

CodePudding user response：

Found the answer and checked it with Project Euler as it is correct. Thanks to those who tried to help and here is my version.

with open('D:\\Development\\keylog.txt', 'r') as file:
logins = list(set(file.read().split()))

first_digits = set()
second_digits = set()
third_digits = set()
for login in logins:
    first_digits.add(login[0])
    second_digits.add(login[1])
    third_digits.add(login[2])
newSet = (first_digits | second_digits | third_digits)


def digits_before(x, attempts):
    before_digit_x = set()
    for attempt in attempts:
        if x in attempt:
            for digit in attempt:
                if digit == x:
                    break
                else:
                    before_digit_x.add(digit)
    return before_digit_x


def get_passcode(digits, attempts):
    passcode1 = []
    for digit in digits:
        before_digit = digits_before(digit, attempts)
        if not before_digit:
            passcode1.append(digit)
        else:
            for d in passcode1:
                if d in before_digit:
                    passcode1.insert(passcode1.index(d), digit)
                    break
            else:
                passcode1.append(digit)
    return "".join(reversed(passcode1))

passcode = get_passcode(newSet, logins)
print(passcode)