5
$\begingroup$

This is related to Hacking an electronic keypad.

You are a spy trying to break into an enemy facility. The back door is protected by an electronic keypad lock. You know that this particular lock is opened by a three-digit code only and you also notice that luckily the keypad only consists of 4 keys ($1$, $2$, $3$ and a $cancel$ button). It sounds pretty easy right? Only $3^3=27$ combinations.

Moreover, this electronic keypad is very special - it also counts the key entrances in the reverse, cyclic and circular orders:

  • Reverse Acceptance: Let's say the actual code is $321$. If you enter $123$, the keypad considers you have entered $321$ too.
  • Circular Acceptance: Let's say the actual password is $212$. After you press $1$, it will try to read the code until it reaches 3 digits in total and it will consider you have entered $111$ because of circular reading until 3 digit read so it will not open yet, then pressing $2$ will cover $121$, $212$ as well, so the lock will open. If we had added $3$ at the end, the reading principle would become like this:
  1
 / \
2 - 3

and the machine will try to start reading straight/reverse and circular from every digit, so the possible combinations will become then: $123$,$132$,$321$,$312$... etc.

  • Cancel Key: If you press the cancel key, it will reset all previous key presses.

Note that, for counting 3 digit codes, the machine counts starting at every digit entered while using reverse or circular reading the codes.

So:

At least how many times you need to press the keys (including $cancel$) on the keypad to guarantee to open the door?

$\endgroup$
  • $\begingroup$ Just one press on 1 try the "111" password? $\endgroup$ – Saeïdryl Mar 23 '18 at 8:16
  • $\begingroup$ @Saeïdryl yes as it is said in the text. $\endgroup$ – Oray Mar 23 '18 at 8:20
  • 1
    $\begingroup$ @Oray From the comment on Kepotx's answer, you say that pressing $123$ also works if the password is $132$, because $123$ can be rotated to $231$, which in turn is the reverse of $132$. This is not at all clear from the question statement. In there it looks like only the rotations and the reverse of the password will work, not rotations of the reverse of the password. Also, your explanation of circular acceptance does not make it clear that it applies to your whole entered code, however long, as your explanation makes it look as if it only applies when you haven't reached 3 characters yet. $\endgroup$ – Jaap Scherphuis Mar 23 '18 at 10:17
  • 2
    $\begingroup$ It also is not clear what the machine does when you enter a fourth digit. Does it only consider the reverse and rotations of the last 3 digits you entered? Do you have to press cancel after entering 3 digits? $\endgroup$ – Jaap Scherphuis Mar 23 '18 at 10:21
  • $\begingroup$ I'm afraid it still is very unclear to me. $\endgroup$ – Jaap Scherphuis Mar 23 '18 at 10:30
6
$\begingroup$

I can do it in

11 presses

Using the following combination:

$12223233313$

The following table shows the currently pressed digit as well as the digits in memory and the found combinations for each step. Reversed combinations are in parentheses.

$\begin{array}{r|c|l|l} \text{memory} & \text{c} &\text{memory} &\text{combinations} \\ \hline 11 & 1 & 11 & 111 \\ 21 & 2 & 12 & 212, 121 \\ 12 & 2 & 12 & 122 (221) \\ 22 & 2 & 12 & 222 \\ 22 & 3 & 12 & 223 (322), 231 (132), 312 (213) \\ 23 & 2 & 12 & 232, 321 (123) \\ 32 & 3 & 12 & 323 \\ 23 & 3 & 12 & 233 (332), 331 (133) \\ 33 & 3 & 12 & 333 \\ 33 & 1 & 12 & 311 (113), 112 (211) \\ 31 & 3 & 12 & 313, 131 \\ \end{array}$

Observations and path to solution:

We basically have combinations of the form xxx, xxy, xyx and xyz.

To get xxy we need 2 x after each other in our sequence (Cycling of short sequences does not help here). To get as many of those combinations as possible, we probably want yxxz in our sequence.
When we already have a sequence like that, we might as well expand it to yxxxz to get xxx as well. Thanks to the cycling of short sequences we only need this for 2 of our 3 digits. We will try to create sequences with 12223 and 23331 in them.
Next up are combinations of type xyx. We can get xyx and yxy with a sequence cxy or by using either xyxy or yxyx. Same as before we only need this for 2 of our 3 digits.

There are now two promising sequences: Merging them with overlap for 12223331 and then adding c32 which will end up something like 12223313c32 which sadly misses 123 and 321. The other possibility is merging them without overlap to get 232 and 323: 1222323331 (This also gives us the missing 123 and 321 from before). This sequence only misses the combinations 313 and 131 which we can get by simply adding another 3.

This leaves us with just 11 button presses to get all 27 combinations and no need for the cancel button. The shortest sequence I found using the cancel button required 12 presses.

$\endgroup$
  • $\begingroup$ @Oray In that case it seems 13 is optimal. Time to rewrite. $\endgroup$ – w l Mar 23 '18 at 11:21
  • $\begingroup$ fyi: 13 is not optimal. $\endgroup$ – Oray Mar 23 '18 at 12:52
  • $\begingroup$ @Oray I hope it is correct now. Quite easy to miss some combinations. $\endgroup$ – w l Mar 23 '18 at 14:00
  • 1
    $\begingroup$ Brute force confirms this latest number of presses is optimal. I found this solution a few minutes too late. :) $\endgroup$ – Rubio Mar 23 '18 at 14:46
  • 1
    $\begingroup$ @wl Shortest using cancel is one longer than shortest without it. In the interest of completeness, here are equivalent sequences for shortest without cancel, and the first I found with it (select to reveal): >$\color{white}{12223233313, 13332322212, 21113133323, 23331311121, 31112122232, 32221211131; 122231332c32}$< $\endgroup$ – Rubio Mar 23 '18 at 16:38
4
$\begingroup$

The password can be three different number (abc, in any other order), two numbers (aba or bab), or the same number three times

three different numbers:

by reverse acceptance, 123=321, 132=231 and 312=213. three attempt is enough to cover them, one cancel between each attempt

two diferent numbers:

by circular acceptance, you just have to press ab to input aba and bab passwords. it can be 121/212, 131/313 or 232/323. another time, three attempt.
It can also be aab, baa, abb or bba. (thanks to @Saeïdryl to correct this).

same number three times:

by circular acceptance, you just have to press a to input aaa passwords. three attempt is enough : 111,222 and 333

solution:

three atempt is enough to cover abc, aba/bab and aaa cases. but one atempt can be used for all three kind of password: 123 (cover 111, 121, 212, 123 and 321), 231 (cover 222,232,323,231 and 132) and 312 (cover 333, 313, 131, 312 and 213) We know need to handle the aab/abb/baa/bba combinations.
We can siply add one number to each combinations to hanndle it:
123 becomes 1233 (covers 233, 332, 331, 133), 231 becomes 2311 (covers 311, 113, 211, 112) and 312 becomes 3122 (covers 122,221,223, 322)
three codes of 4 charcaters, separated by two cancel:
we press 14 buttons

$\endgroup$
  • 1
    $\begingroup$ You missed some of them: 331 (aab & baa) $\endgroup$ – Saeïdryl Mar 23 '18 at 8:30
  • $\begingroup$ @Saeïdryl thanks, i edit it, but I'm not sure to have an otpimal answer anymore $\endgroup$ – Kepotx Mar 23 '18 at 8:54
  • $\begingroup$ I found 35 too :) $\endgroup$ – Saeïdryl Mar 23 '18 at 9:04
  • $\begingroup$ Note that: 123 covers 132, 213, 312 and 231 as well considering reverse and circular properties at the same time. $\endgroup$ – Oray Mar 23 '18 at 9:17
  • 1
    $\begingroup$ updated again. is there a policy about improved/updated answers as in Programming Puzzles & Code Golf? I edit it two times, I don't know if I need to keep a track of it in my answer $\endgroup$ – Kepotx Mar 23 '18 at 9:35
4
$\begingroup$

I am not sure if my answer is correct , but my guess is

13 key presses

Reason being

If I press the keys in the order
1 - 111
2 - 121,212
3 - 123, 231,312(cyclic) and 321(reverse) and 213,231(reverse cyclic)
3 - 233,331 and 332,133(reverse)
1 - 311,112 and 133,113,211(reverse)
Now I press cancel and start with
2 - 222
3 - 232,323
12 - 122,223 and 322(reverse)
Now I press cancel and start
3 - 333
1 - 131,313

$\endgroup$
  • 1
    $\begingroup$ gladly someone understands the question :) $\endgroup$ – Oray Mar 23 '18 at 10:47
  • $\begingroup$ Is it still not correct?? $\endgroup$ – Gokul Mar 23 '18 at 10:53
  • $\begingroup$ it is correct even though it is missing 113 on the 6th row. lets see if someone can come up with a better answer $\endgroup$ – Oray Mar 23 '18 at 10:55
  • $\begingroup$ there are mistakes in your list. such as 223 is missing and you have already covered 313 on the 5th row but you did not add in the list. $\endgroup$ – Oray Mar 23 '18 at 13:03
  • $\begingroup$ Sorry, missed 223.Now added to 10th row. 313 is anyway present in the last row $\endgroup$ – Gokul Mar 23 '18 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.