Keypad locks
-
For those who enjoy playing with algoritms ... A two-step problem: The simple part, make something that works. The difficult part: Provomg that your solution is the optimal one. Disclaimer: I have no clue about the second part. Problem: We have a keypad lock at our work facilities. You present your card, and then if the last four digits typed are a valid entry code, the door opens. So if a valid code is 2345, and you type 1234, the door doesn't open. If you then add a 5, the door opens. An algoritm for trying all possible keys is like the first homework assignment in 101 Elementary Programming. If you have no knowledge of any entry code, but you know that if the last four digits are correct, the door will open, what will be your dialing strategy for making the minimal nunber of keys dialled to get in? What will be the worst case number of digits dialled? Can you prove that this it the theoretically best, that no other algorithm will provide a lower worst case? What will be the average across all possible entry codes? Can you prove that your algorithm provides the minimal number of total keypresses in the average case? I do not have any ready-made "right answer" to this problem, just a bunch of implementations of how to make sure I get it if I have forgotten the code :-) with no complexity analysis. I do know the code, so I do get in - don't worry about that! The problem here is not to get in, but the complexity of getting in if you do NOT know the code!