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)

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: