At one of my old jobs, the bathroom was locked with a 4 digit code followed by the key symbol.
We jokingly made up "Bathroom Code" as an interview question/to nerd snipe each other instead of working, which was "assuming you don't have to press key, and that the bathroom door will unlock if the correct 4 digits are entered in order at any time, write the code to print the shortest possible test sequence to guarantee you entry". Obviously we didn't give this to any candidates but it's amusing to think that the problem is a lot more interesting than we gave it credit for.
You know Ford/Lincoln had those buttons / touch strip in the door with the buttons labelled like [1|2] [3|4], and so on to [9|0]?
There's a permutation list claimed to be the shortest that I used to carry in my PDA to impress friends that had one of those sorts of cars. If I recall, it was guaranteed to open the door in something like 32 button presses, but it may have been less.
It was because there was no "start" or stop to the sequence, the computer would unlock if the sequence appeared intact anywhere. So a code 3,4,5,6 would trigger with 8,2,7,3,4,5,6,0,2
No, but it would unlock with 3355 or 3455 or 3365 or 4466 or
there's 5 buttons, and the code is four of those 5 in an arbitrary order. at least to my memory. it could have been 5 buttons in an arbitrary order. It's been 20 years!
5 pick 4 = 120, so that's an upper bound for my recollection. I remember it being fewer than that, but the original "paper" was a sheet of graph paper that had been scanned, i just transcribed it to my palm pilot.
oh. It isn't 120 * 4 keypresses. Because the thing that decided if the code was valid didn't have start/stop/reset states, so 1234523413452 would trigger 1234, 2345, 3452, 4523, 5234, 2341, 3413, 4134, 1345, and 3452. that would take "40 keypresses" in the OP "game", whereas it only takes 13 keypresses on these code pads.
so the paper was "an" shortest permutation that covered every possible combination.
edit: python gave a 625 keypress answer, i replied to a sibling with the full list of numbers.
Superpermutation must repeat all possible combination in the shortest number possible. De Bruijn sequence places a lower bound on the length of superpermutations but shorter sequences are possible. De bruijn is also cyclical, which superpermutations in the literature are not.
I'm no mathematician or leetcode expert and probably don't understand "shortest possible test sequence", but it sounds like this is just bruteforcing 0000-9999. You can't guess what would be closer to the correct solution, so at best I'd propose making a list of choices and randomizing the tries in case you get lucky.
It's different if the keypad gives an indication that one number is correct though, then it'll be 40 tries at most.
Have you read the article we're commenting on? Obviously mathematicians know that n! * k, with k the length of the code, would work. The idea is to superpose the end of a code with the start of the next, so you don't have to test nearly as many combinations.
> creat[e] a graph where each permutation is a vertex and every permutation is connected by an edge. Each edge has a weight associated with it; the weight is calculated by seeing how many characters can be added to the end of one permutation (dropping the same number of characters from the start) to result in the other permutation. [...] Any Hamiltonian path through the created graph is a superpermutation, and the problem of finding the path with the smallest weight becomes a form of the traveling salesman problem.
Given that you just care about 4 digit codes (so you don't actually care about a generic algorithm that's not super slow in asymptotic time), can't you just solve it with an easy to code bruteforce algorithm? Or is the combinatorial explosion so big that it's actually intractable that way?
Think about this. You need to calculate the number of permutation for 4 digit codes. Then you need to arrange them in every order possible to brute force. So that’s 4!!. That’s a lot: roughly 620000000000000000000000 combos.
That's the number of possible codes. Not the number of possible ways you could arrange all 10000 codes to see which ordering contains the most shortcuts.
i have a python script running through that right now to find "the shortest" and it's been burning a single core for at least 6 hours. So it looks like you are right and i am wrong ;-)
i assume my pc on a single core can do ~1billion permutations per second, this will take 19,647 millennia. AFK.
what do you think the chances are, if i let this run, that it would find a shorter solution than 625 keypresses? the naive De Bruijn algorithm popped that out in like 2 seconds.
