Hacker News Reader

Comment by bntyhntr | Hacker News Reader

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.

View on HN

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

And in other fun knowledge, the f150 2016 has no way to disable that keypad. Short of taking apart the door and disconnecting it.

Is this a mean trick to snipe HN users into thinking about algorithms for hours? I have a friend who wants to know.

python assures me this is a valid solution:

>111211131114111511221123112411251132113311341135114211431144114511521153115411551212131214121512221223122412251232123312341235124212431244124512521253125412551313141315132213231324132513321333133413351342134313441345135213531354135514141514221423142414251432143314341435144214431444144514521453145414551515221523152415251532153315341535154215431544154515521553155415552222322242225223322342235224322442245225322542255232324232523332334233523432344234523532354235524242524332434243524432444244524532454245525253325342535254325442545255325542555333343335334433453354335534343534443445345434553535443545355435554444544554545555

625(?) presses, i was way off. :-( It's still a lot fewer than trying all 10,000 individual 4 digit possibilities that the keypad implies are there.

Also this is possibly not the shortest, according to some sibling comments to mine, above. This could be the upper bound?

3+5432=123, so 4 digit code would require at least 134 key presses.
Even 3 digit code would require over 60 keypresses.
We're there other constraints on valid codes?

Did the door unlock in a valid non-consecutive* subsequence like 3,4,5,0,6?

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.

If the code is allowed repeats then the problem is much easier: https://en.wikipedia.org/wiki/De_Bruijn_sequence.

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.

The point is that if you input, say, 00001, then you will have tested both 0000 and 0001.

If the code is either 0000 or 0001, then entering 00001 will open the door, as you just need the four digits in order.

That shows how you can do a shorter sequence by using overlaps.

> 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.

From https://en.wikipedia.org/wiki/Superpermutation

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.

If you're not making some joke that I'm missing it's just 10^4 = 10000, which is a just a fancier way of saying 0000-9999.

10^4 permutations. Which you then permute again except the second time you're overlapping them to search for the shortest possible sequence.

Or it's 10000?

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.

Reply on news.ycombinator.com