Enigmatic Code

Programming Enigma Puzzles

Enigma 1687: Predictive powers

From New Scientist #2854, 3rd March 2012 [link]

On my mobile phone the buttons can be used for more than one letter, and the machine predicts your intended word. So, for example, to text “STOP” I type the buttons shown below, but the machine could also interpret that as “SUMS”.

This desire for compact gadgetry has spread to calculators. The digits of mine are on just five buttons, A to E, as shown below. So when I type in a number the machine has to predict what I want. Recently I pushed buttons intending to display a three-figure prime number, but the machine displayed a different three-figure prime. Then I pushed some more buttons intending to display a three-figure square, but the machine displayed a different three-figure square. When typing these two numbers I had pushed each button at least once.

Which six buttons, listed in order, did I push?

[enigma1687]

Advertisements

2 responses to “Enigma 1687: Predictive powers

  1. Jim Randell 29 February 2012 at 9:51 pm

    The following Python code runs in 45ms.

    from collections import defaultdict
    from enigma import is_prime, printf
    
    # map numbers to buttons
    button = {
      '0': 'A', '1': 'A', '2': 'B', '3': 'B', '4': 'C',
      '5': 'C', '6': 'D', '7': 'D', '8': 'E', '9': 'E'
    }
    
    # collect 3-digit primes by code
    p = defaultdict(list)
    for n in range(101, 1001, 2):
      if not is_prime(n): continue
      keys = ''.join(button[i] for i in list(str(n)))
      p[keys].append(n)
    
    # collect 3-digit squares by code
    s = defaultdict(list)
    for i in range(10, 32):
      n = pow(i, 2)
      keys = ''.join(button[i] for i in list(str(n)))
      s[keys].append(n)
    
    # look for multiple squares with the same code
    for sk, sv in s.items():
      if len(sv) < 2: continue
      # look for primes with the remaining letters
      letters = set(list('ABCDE')).difference(list(sk))
      for (pk, pv) in p.items():
        if len(pv) < 2: continue
        if not letters.issubset(set(list(pk))): continue
        printf("prime={pk} {pv}, square={sk} {sv}")
    

    Solution: The buttons pushed are: D, A, E, B, B, C.

  2. Brian Gladman 3 March 2012 at 10:02 am

    Here is an alternative version:

    from itertools import product
    from collections import defaultdict
    
    # create a dictionary of primes
    def prime_dict(n) :
      sieve = [False, False] + [True] * (n - 1)
      for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] :
          m = n // i - i
          sieve[i * i : n + 1 : i] = [False] * (m + 1)
      return dict((i, 1) for i in range(n + 1) if sieve[i])
    
    pr = prime_dict(1000)
    
    # create a dictionary of squares
    sq = dict((x ** 2, x) for x in range(10, 32))
    
    # compute possible primes and squares for each sequence 
    # of 3 key presses and put them in dictionaries indexed
    # on the key sequence (dp for primes, dq for squares)
    dp, dq = defaultdict(list), defaultdict(list)
    for k in product(range(5), repeat=3):
      # each sequence must have at least two different keys
      if len(set(k)) > 1:
        # now look at all the combinations of the two
        # possible interpretations of each key to
        # find 3 digit primes and squares
        rk = (range(2 * i, 2 * i + 2) for i in k) 
        for k1, k2, k3 in product(*rk):
          n = 10 * (10 * k1 + k2) + k3
          if 100 <= n < 1000:
            if n in pr:
              dp[k] += [n]
            if n in sq:
              dq[k] += [n]
    
    for p in dp:
      # for each key sequence that gives two or more primes
      if len(dp[p]) > 1:
        for q in dq:
          # for each key sequence that gives two or more squares
          if len(dq[q]) > 1:
            # if all keys are used at least once
            if len(set(p) | set(q)) >= 5:
              print(tuple(chr(ord('A') + x) for x in (p + q)))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: