9
$\begingroup$

You have a basic but very problematic four function calculator. That is, the keys are 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, x, /, and =. However, all the keys are scrambled up in an unknown order, and have no markings. Not only that, but the screen will only display anything if a valid math problem is typed in and the equals key is pressed. After it displays an answer, the screen goes blank when another key is pressed. It follows order of operations.

Some examples:

= gives you a blank screen.

2= gives you a 2.

1+= gives you a blank screen.

10-2x3= gives you 4 (not 28)

0-2= gives you -2

-2= gives you a blank screen

The problem is: what is the most efficient way to go about figuring out what all of the keys are?

$\endgroup$
  • $\begingroup$ so, just to be clear, it's known that the calculator is a correctly operating four-function calculator EXCEPT that you don't know which key is which, and the question is how efficiently you can figure that out? $\endgroup$ – Gareth McCaughan Sep 30 '16 at 23:36
  • $\begingroup$ OP, do you know what the most efficient solution is?I'm not asking for the answer, rather I just want to be sure whether you yourself know it or not. $\endgroup$ – Buffer Over Read Oct 1 '16 at 11:33
4
$\begingroup$

Here just for reference is a strawman strategy, as a benchmark for improvements by being less stupid. Nothing is spoilered because this is pretty much the path of least resistance, doesn't try to be efficient, and will quickly be superseded by other cleverer answers.

First of all, try every combination of the form xyxy until you find one that makes the calculator display something after the third or fourth key. If you do xyxy then you don't need to do yxyx. There are $\binom{15}{2}=105$ such combinations, hence a maximum of 420 keypresses (actually the figure is a bit less but never mind) before you get a sequence =x= where x is a digit. At that point you know which key is = and also one of the digits.

Now repeatedly do x= for each other key x. That takes you at most another 26 keypresses, and after that you know where all the digits are.

Now repeatedly do 2x3= for three of the remaining keys x. That takes another 12 keypresses, and after that you know what those keys are and hence also what the last one is.

Therefore, we can identify all the keys in at most 420+26+12 = 458 keypresses.

(The worst case is actually a bit better than this, especially if you are clever about the ordering of your xyxys, but figuring out how much better and how to be clever about it is explicitly outside the scope of this answer. I'm trying to indicate where deliberate stupidity gets you, and then we can see how much better cleverness is.)

$\endgroup$
  • 1
    $\begingroup$ The worst case is better than the upper bound I give here, because the first time you hit (equals) (digit) (equals) can't actually be the very last xyxy that you try. (Because there are lots of digits.) If you choose the order of the xyxy's well, you can probably guarantee that it happens quite a lot sooner than the end. $\endgroup$ – Gareth McCaughan Sep 30 '16 at 23:58
  • 2
    $\begingroup$ E.g., pick one x and do all the xyxy's (14x4=56 keys). If x is either = or a digit, you're now done. Otherwise you know that x is one of the four arithmetic operations. Now do it again with a different x (13x4=52 keys), and if necessary again (12x4=48) and again (11x4=44). That's 200 keys now and if you aren't done yet you know which keys are +-*/ although not in what order. Now press the other 11 in any order, twice, and by the end you're guaranteed to have found =. That's 222 keys instead of 420, and you've discovered a bit more extra info than I said. $\endgroup$ – Gareth McCaughan Oct 1 '16 at 0:03
  • 1
    $\begingroup$ I think it will actually be difficult to improve much on this solution, although minor improvements are certainly possible. $\endgroup$ – GentlePurpleRain Oct 1 '16 at 1:44
4
$\begingroup$

I can find the keys in at most

139 135 presses.

First, split the keys into 3 sets: set 1 is $(K_1, K_4, K_7, K_{10}, K_{13})$, set 2 is $(K_2, K_5, K_8, K_{11}, K_{14})$ and set 3 is $(K_3, K_6, K_9, K_{12}, K_{15})$.

For each of the sets in turn, say the keys in the set are ABCDE. Type the following sequence:

EAEABABCBCDCDEDEBEBDBDADACACECE

This sequence has 31 presses, but for the first set the first E can be omitted, leading to a total of 92 presses so far. We can verify that for every a, b in the set we try the sequence "aba" at some point. This means that we will find = unless we're unlucky enough that one of the sets contains only = and the 4 arithmetic operations.

In the worst case, then, we still have to find =. Press the following sequence:

$ K_1 K_2 K_3 ... K_{15} K_1 K_2 ... K_{14}$

(I didn't press $K_{15}$ as the last key because the last press before this was already $K_{15}$).

Remember that we know that two sets consist of only digits, and a third set is only arithmetic operations and =. This means that, no matter which key = is, the string between the two presses of = above will be a valid arithmetic expression (it's two digits, an operator, two digits, an operator...).

Therefore, after at most 29 more presses (121 total), we now know the identity of =, as well as which keys are digits.

Pressing 9 of the digit keys followed by =, we now have the value of those digits (131 presses total). The tenth digit is the one we didn't press.

Given the result of the big arithmetic expression we computed earlier, we can now deduce all operators if we know one of them. (I did some bruteforcing to check that this is indeed true in all cases, if my code has no bugs). So 4 more presses (total 135) are enough:

2?a3=

$\endgroup$
  • $\begingroup$ I really like this solution! I would mention that when the = key is found during the first 92 presses then it is not known what keys are digits – except for one – and a different approach must be used to identify them. It's not hard to figure out though. $\endgroup$ – GOTO 0 Oct 4 '16 at 2:40
3
$\begingroup$

The first step is noting that the key sequence …=?= will produce an output whenever ? is a digit, regardless of what other keys were pressed before the first = key. This property allows us to locate the = key by trial and error in a maximum of 127 presses ($10 + 9 \times 13$).

There are 15 keys on the calculator, call them $K_1,K_2\cdots K_{15}$. Suppose that $K_1$ is =. Then at least one of the key combinations

$$K_6K_1, K_5K_1, K_4K_1, K_3K_1, K_2K_1$$ will print something (10 presses). It doesn't really matter what keys we press before $K_1$, as long they are all different, at least one of them must be a digit, and so pressing $K_1$ after it should yield some output.

If nothing happens, assume that the = key is the second-to-last button pressed in our previous attempt instead, here $K_2$. Pressing this key once again should now produce an output if the last key ($K_1$) was a digit (11 presses so far). Otherwise, holding our assumption that $K_2$ is the = key indeed, one of the combinations $$K_6K_2, K_5K_2, K_4K_2, K_3K_2$$ should print something (19 presses), for the reason that on of the keys pressed before $K_2$ must be a digit.

If still nothing happens, we continue by assuming that $K_3,K_4\cdots K_{14}$ is the = key until something is actually printed (127 presses), after which we will know that the previous key was =.

If still nothing happens, the = can only be $K_{15}$.

Once = is found, the digits 0 through 9 can be found by trial and error in a maximum of 26 presses (153 presses overall) by pressing one of 13 keys followed by = (if one of the digits was not printed, it will be the 14th key).

Once the position of = and all the other digits are known, a maximum of 8 more keypresses can determine what the +, -, × and / keys are, for example by typing:

2?a3?b4?c5=

where any combination of different operators will yield different results.

This leaves us with a total of

161 keypresses

in the worst case.

And I'm sure there is still room for improvements.

$\endgroup$
  • $\begingroup$ I think you may be too optimistic at the start. A sequence like 53+*6= will not, as I understand it, display anything. (That's why my strawman solution tried to make sure we got something of the form ={digit}=.) $\endgroup$ – Gareth McCaughan Oct 2 '16 at 10:32
  • $\begingroup$ @GarethMcCaughan My method would never produce a sequence like that at the start, because every second key would be the same. Could be 53+363, 50+060, etc. until you get 5=+=6= and that would always print a 6, because not only the key after 6 is a =, but also the one before. $\endgroup$ – GOTO 0 Oct 2 '16 at 10:39
  • $\begingroup$ Ah, OK. My apologies for missing that. $\endgroup$ – Gareth McCaughan Oct 2 '16 at 14:20
2
$\begingroup$

Here is my attempt to improve on Gareth's solution.

Total is

228 218

Using most of what's in Gareth's answer

pick one key (a) do all combinations of yxyx, you can drop the last x of the last set since if x is = you would have already found it. If we don't get any display we know a is an arithmatic operator. This takes 14*4-1 = (55 keys)

Do the same with b without comparing it to x it takes 13*4-1 = (51 keys)

Same with c (don't compare to x,b) = 12*4-1 = (47 keys)

d = (43 keys)

Total so far = 196 keys and you know which keys are the operators

Of the remaining keys press 010 (to check if the equal sign is in slot 0) then 23456789 (now you know = so press it again. With the two = presses you will have displayed all digits on the calculator so you know them all (12 keys)

Press the remaining 11 keys and you will have found = since if its the first one you press you will still have a blank after all 11 presses. (11 keys)

Now press the 10 keys with = last and it will give you all your digits (11 keys)

Then press 1 x 2 b 3 = (6 keys) this gives a unique answer for any combination of a and b. (This is the numeric values of 1,2,3 not the key positions used above.)

Then press 1 c 2 = (4 keys) which gives you the third operator, last one you know by elimination

$\endgroup$

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.