Enigmatic Code

Programming Enigma Puzzles

Enigma 369: A safe number

From New Scientist #1518, 24th July 1986 [link]

“My memory is poor, but accurate,” said Mooncalf. “I remember just enough of the characteristics of my safe combination to enable me to reconstruct the number when I forget it. It contains a pair of 1s separated by one digit, a pair of 2s separated by two digits, a pair of 3s separated by three digits and so on, there being twice as many digits in the number as the value of the highest digit. Yet I can’t even remember the highest pair of digits.”

“There must be many such numbers,” I opined, reaching for my notepad. “For example, 312132. That has two 1s separated by one digit, two 2s separated by two digits and two 3s separated by three digits.”

“Yes. But what makes my safe number unique is that it is the highest number that can be formed in this way. As an aide-mémoire, I have written part of it on a card. If anyone stumbles across it he is unlikely to tumble to its true significance. First I write the safe number backwards. Then, starting from the right I discard from this number, one by one, as many digits as I can, consistent with there occurring at least once in the number which remains each digit of the original number. This final number is my aide-mémoire.”

“You mean if it were 41312432 you would be left with 23421 on the card?”

“Exactly. But I have locked it away in the safe, and I want you to help me to deduce my combination so I can open the safe and retrieve it.”

Scratching my head, I got down to work. In no time at all I had deduced the number and had retrieved Mooncalf’s card.

What was the number inscribed on it?

[enigma369]

Advertisements

6 responses to “Enigma 369: A safe number

  1. Jim Randell 4 November 2016 at 7:24 am

    This Python 3 program runs in 393ms.

    from enigma import update, Accumulator, irange, printf
    
    # determine the sequence on the card from the combination <s>
    def card(s):
      for (i, x) in enumerate(s):
        if x in s[i + 1:]: continue
        return s[:i - 1:-1]
    
    # check the example given
    assert card([4, 1, 3, 1, 2, 4, 3, 2]) == [2, 3, 4, 2, 1]
    
    # generate sequences in <s> where numbers from <n> down 1
    # are separated by their respective number of elements
    def generate(s, n):
      if n == 0:
        yield s
      else:
        # find empty indices i and i - (n + 1)
        for (i, x) in enumerate(s):
          j = i - n - 1
          if j < 0: continue
          if not(x is None and s[j] is None): continue
          yield from generate(update(s, ((i, n), (j, n))), n - 1)
    
    # find the largest sequence
    r = Accumulator(fn=max)
    
    # consider sequences with numbers up to n
    for n in irange(9, 1, step=-1):
      for s in generate([None] * (2 * n), n):
        r.accumulate(s)
      # have we found a value?
      s = r.value
      if s is not None:
        printf("card = {card}, s = {s}", card=card(s))
        exit()
    

    Solution: The number on the card is 1317538642.

    The combination to the safe is 8642752468357131.

  2. Hugh Casement 4 November 2016 at 11:09 am

    I know it doesn’t fit the puzzle as stated, but would it work with a 00 somewhere?
    That’s a pair of zeros separated by no digits.

    • Jim Randell 4 November 2016 at 1:47 pm

      @Hugh: If we look for a sequence of 2n + 2 digits (instead of 2n digits), then we can get:

      867315136875420024

      as the highest such number.

      And the corresponding number on the card would be:

      420024578631

  3. Brian Gladman 4 November 2016 at 2:46 pm
    from functools import reduce
    
    # In a sequence of digits <seq> of length <ln> , place two 1s
    # separated by one digit, two 2s separated by two digits, and
    # so on, to create a sequence that is twice the length of the
    # highest digit present; set higher digits in place first.
    def place(seq, ln, lv):
      # are all digits placed?
      if not lv:
        yield seq
      else:
        # place the next pair of digits separated by lv digits
        for i in range(ln - lv - 1):
          # check there are spaces for the digits
          if seq[i] == seq[i + lv + 1] == 0:
            # place them and continue to set the digit pair
            seq[i] = seq[i + lv + 1] = lv
            yield from place(seq, ln, lv - 1)
            seq[i] = seq[i + lv + 1] = 0
    
    # find the maximum number formed in the above way
    def find_max():
      mx = 0
      # consider decreasing sequence lengths to find the
      # highest number possible
      for ln in range(9, 0, -1):
        for seq in place([0] * (2 * ln), 2 * ln, ln):
          # form the number and keep the largest one found
          nbr = reduce(lambda x, y: 10 * x + y, seq, 0)
          if nbr > mx:
            mx = nbr
        # return the number found
        if mx:
          return mx
    
    # find the largest number of the specified form
    comb = find_max()
    # reverse it
    mx = str(comb)[::-1]
    # and remove the final digits in turn while they are paired
    while mx.count(mx[-1]) == 2:
      mx = mx[:-1]
    print('The number was {} (the combination was {}).'.format(mx, comb))
    
  4. Julian Gray 5 November 2016 at 3:55 pm

    Did anyone find a way of testing and/or assembling the possible sequences of numbers without the benefit of a search with a program? I used a graphic approach but, inevitably, it was too time consuming as the number of digits increased.

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: