# 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]

### 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

• Hugh Casement 5 November 2016 at 11:38 am

Thanks, Jim.  I got a bit bogged down when I tried to write a program for that.

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( * (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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.