Step 0: discard unnecessary information and recode the problem to make plain what is actually being asked for.
A string that contains each three-tuple in order but not necessarily contiguous, and is the shortest possible string that meets this criteria.
The second clause of the problem rules out simply concatinating the fifty succesful login attempts. But that does give us an upper limit on the length of the string.
N[max] = 3 * 50 = 150
Next consider the simple brute-force solution: Iterate through the integers from n (to be determined later, for now set it to zero or one) to 10^150 - 1 and check each one. Halt when the solution is found.
Depending on the urgency of the situation this is as much thinking as you might need to do. There are several fairly obvious ways to trim the amount of integers you would need to check.
But of course, the generate-and-test strategy is overkill for this problem, and relatively uninteresting compared to the possibility of devising a clever mathematical or logical solution.
One angle would be to explore generation functions that might produce minimal strings directly from the set of three-tuples.
Another angle would be to set up the problem for a contraint-solver. I'm a little rusty these days but I think you could convert the problem to a SAT instance and use an off-the shelf SAT solver.
(As an aside, watch out for unfounded assumptions, e.g. maybe all ten digits don't appear in the logins. Do digits appear more than once in a given keylog entry?)
It took me about ten minutes to write the brute force python code, and about half an hour to get it to work. (The biggest problem I had was debuggin a stupid Python 2/3 error: map() returns an iterator now not a list. FML. Also, getting conda to work in windows with vscode was a lil hassle (use cmd.exe not PowerShell.) FML.)
For the curious:
keylog = list(map(list, '''\
319
680
180
690
129
620
762
689
762
318
368
710
720
710
629
168
160
689
716
731
736
729
316
729
729
710
769
290
719
680
318
389
162
289
162
718
729
319
790
680
890
362
319
760
316
729
380
319
728
716'''.splitlines()))
def predicate(N):
f = N.find
# This works because there are no repeated digits (like 112).
for a, b, c in keylog:
i = f(a)
if -1 == i:
return False
j = f(b, i)
if -1 == j:
return False
if -1 == f(c, j):
return False
return True
def do():
n = 9999
while True:
N = str(n)
if predicate(N):
print(N)
break
n += 1
do()
A string that contains each three-tuple in order but not necessarily contiguous, and is the shortest possible string that meets this criteria.
The second clause of the problem rules out simply concatinating the fifty succesful login attempts. But that does give us an upper limit on the length of the string.
N[max] = 3 * 50 = 150
Next consider the simple brute-force solution: Iterate through the integers from n (to be determined later, for now set it to zero or one) to 10^150 - 1 and check each one. Halt when the solution is found.
Depending on the urgency of the situation this is as much thinking as you might need to do. There are several fairly obvious ways to trim the amount of integers you would need to check.
But of course, the generate-and-test strategy is overkill for this problem, and relatively uninteresting compared to the possibility of devising a clever mathematical or logical solution.
One angle would be to explore generation functions that might produce minimal strings directly from the set of three-tuples.
Another angle would be to set up the problem for a contraint-solver. I'm a little rusty these days but I think you could convert the problem to a SAT instance and use an off-the shelf SAT solver.
(As an aside, watch out for unfounded assumptions, e.g. maybe all ten digits don't appear in the logins. Do digits appear more than once in a given keylog entry?)
It took me about ten minutes to write the brute force python code, and about half an hour to get it to work. (The biggest problem I had was debuggin a stupid Python 2/3 error: map() returns an iterator now not a list. FML. Also, getting conda to work in windows with vscode was a lil hassle (use cmd.exe not PowerShell.) FML.)
For the curious: