# Enigmatic Code

Programming Enigma Puzzles

## Enigma 500: Child’s play

From New Scientist #1652, 18th February 1989 [link]

The children at the village school have a number game they play. A child begins by writing a list of numbers across the page, with just one condition, that no number in the list may be bigger than the number of numbers in the list. The rest of the game involves writing a second list of numbers underneath the first; this is done in the following way. Look at the first number — that is, the left-hand one, as we always count from the left. Say it is 6, then find the sixth number in the list — counting from the left — and write that number in the first place in the second row — so it will go below the 6. Repeat for the second number in the list, and so on. In the following example, the top row was written down, and then playing the game gave the bottom row:

6,  2,  2,  7,  1,  4, 10,  8,  4,  2,  1
4,  2,  2, 10,  6,  7,  2,  8,  7,  2,  6

The girls in the school use the game to decide which boys are their sweethearts. For example, Ann chose the list of numbers:

2,  3,  1,  5,  6,  4

For a boy to become Ann’s sweetheart he has to write down a list of numbers, play the game, and end with Ann’s list on the bottom row.

Bea chose the list:

2,  3,  2,  1,  2

and Cath the list:

3,  4,  5,  6,  7,  1,  2,  5,  7,  3,  6,  9

Find all the lists, if any, which enable a boy to become the sweetheart of Ann, of Bea, and of Cath.

Enigma 1736 is also called “Child’s play”.

[enigma500]

### One response to “Enigma 500: Child’s play”

1. Jim Randell 20 May 2019 at 8:59 am

In this Python program I use [[ dict() ]] objects to hold the sequences, to simplify the use of 1-based indices. It runs in 241ms.

Run: [ @repl.it ]

from enigma import irange, printf

# consistently update a dict with (k, v) pairs
def update(s, ps):
s = s.copy()
for (i, v) in ps:
x = s.get(i)
if x is None:
s[i] = v
elif x != v:
return None
return s

# solve remaining slots
# t = target sequence (as dict)
# i = slot to examine
# n = number of slots
# s = source sequence (as dict)
def _solve(t, i, n, s):
if i > n:
yield s
else:
# find the next value
v = t[i]
# choose a slot for v
for j in irange(1, n):
# can we update the source list
s2 = update(s, [(j, v), (i, j)])
if s2:
yield from _solve(t, i + 1, n, s2)

# find sources for a particular target sequence
def solve(t):
for s in _solve(dict(enumerate(t, start=1)), 1, len(t), dict()):
yield list(s[i] for i in sorted(s.keys()))

# targets in the question
targets = (
[2, 3, 1, 5, 6, 4],
[2, 3, 2, 1, 2],
[3, 4, 5, 6, 7, 1, 2, 5, 7, 3, 6, 9],
)

# solve for each target
for (i, t) in zip("ABC", targets):
for s in solve(t):
printf("{i}: {s} -> {t}")

Solution: For Ann any of these four lists will work: (3, 1, 2, 6, 4, 5); (4, 5, 6, 2, 3, 1); (5, 6, 4, 1, 2, 3); (6, 4, 5, 3, 1, 2). For Bea there are no lists that work. For Cath the following list works: (2, 3, 4, 5, 6, 7, 1, 4, 6, 2, 9, 11).

There are 8 sequences that will give the second sequence given in the example:

(5, 2, 2, 6, 4, 10, 2, 8, 10, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(5, 2, 7, 6, 4, 10, 2, 8, 3, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(5, 2, 7, 6, 4, 10, 2, 8, 10, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(6, 2, 2, 7, 1, 4, 10, 8, 4, 2, 1) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(6, 2, 10, 7, 1, 4, 10, 8, 4, 2, 1) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(11, 2, 2, 6, 4, 10, 2, 8, 10, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(11, 2, 7, 6, 4, 10, 2, 8, 3, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)
(11, 2, 7, 6, 4, 10, 2, 8, 10, 7, 4) → (4, 2, 2, 10, 6, 7, 2, 8, 7, 2, 6)

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