Enigmatic Code

Programming Enigma Puzzles

Enigma 1101: Disappearing numbers

From New Scientist #2257, 23rd September 2000 [link]

This game starts when I give a row of numbers; some numbers in italic [red] and some in bold [green]. Your task is to make a series of changes to the row, with the aim of reducing it to a single number or to nothing at all. In each change you make, you select two numbers that are adjacent in the row and are of different font [colour], that is to say one is italic [red] and the other is bold [green]. If the numbers are equal, you delete them both from the row; otherwise you replace them by their difference in the font [colour] of the larger number.

For example, suppose I gave you the row:

3, 4, 3, 2, 5, 2.

One possibility is for you to go:

[I have indicated the pair of numbers that are selected at each stage by placing them in braces, the combined value (if any) is given on the line below in square brackets].

3, 4, 3, {2, 5}, 2
3, {4, 3}, [3], 2
{3, [1]}, 3, 2
[2], {3, 2}
2, [1]

You have come to a halt and failed in your task.

On the other hand you could go:

{3, 4}, 3, 2, 5, 2
[1], {3, 2}, 5, 2
{1, [1]}, 5, 2
{5, 2}
[3]

And you have succeeded in your task.

For which of the following can you succeed in your task?

Row A: 9, 4, 1, 4, 1, 7, 1, 3, 5, 4, 2, 6, 1, 4, 8, 3, 2.

Row B: 2, 3, 5, 9, 6, 3, 1, 4, 2, 3, 1.

Row C: 1, 2, 3, 4, 5, 6, …, 997, 998, 999, 1000, 3, 5, 7, 9, 11, …, 993, 995, 997, 999.

Row D: 3, 2, 1, 4, 5, 4, 3, 2, 4, 3, 7, 4, 1, 5, 1, 4, 2, 4, 3, 1, 2, 7, 9, 3, 7, 5, 3, 8, 6, 5, 8, 4, 1, 5, 2, 3, 1, 4, 10, 6, 3, 5, 7, 4, 1, 4.

I have coloured the numbers in italics red, and those in bold green in an attempt to ensure the different styles of numbers can be differentiated.

When the problem was originally published there was a problem with the typesetting and the following correction was published with Enigma 1104:

Due to a typographical error, three of the numbers in Enigma 1101 “Disappearing Numbers” appear in the wrong font. In each case, the following should have been printed in heavy bold type:

the second number 3 in the initial example;
the first number 5 in row B;
and the first number 4 in the second line of row D.

I have made the corrections to the puzzle text above.

[enigma1101]

One response to “Enigma 1101: Disappearing numbers

  1. Jim Randell 21 August 2017 at 8:53 am

    I originally tried a simple recursive solver that just plays the game as described, and this is enough to evaluate sequences A, B and C. But for sequence D you either need a lot of time, or a lot of RAM (if you use the [[ @cached ]] version of [[ solve() ]]), or both.

    So here is some analysis, that let me write a program to solve sequence D in a reasonable time.

    For any of the given sequences we can construct a corresponding sequence of integers. When we encounter a green number we write down its value, when we encounter a red number we write down its negative value.

    With this method the example sequence becomes:

    [3, −4, 3, −2, 5, −2]

    To make a change to a sequence we replace two adjacent elements with different signs with the sum of the two elements, unless the sum is zero, then we simply remove the two elements.

    In this way the sequence is reduced until all elements have the same sign. (0 can never appear in a sequence).

    If the sequence ends up with 0 or 1 elements, then we have successfully reduced it, if it has 2 or more elements, then we have failed to reduce it.

    Every element in a reduced sequence is the sum of one or more adjacent elements from the original sequence, elements are only removed when they have a sum of zero, so the final value of a fully reduced sequence is the sum of the elements of the original sequence, and the sum of the elements in the sequence remains the same throughout the process. (An empty sequence has a sum of 0).

    We can derive the following:

    The empty sequence is successfully reduced (to a value of 0).

    A sequence with only one element is successfully reduced (to a non-zero value equal to the value of the single element).

    A sequence with two elements can be successfully reduced if (and only if) the elements have different signs. The value of the sequence is the sum of the elements. If the value is zero, the sequence can be reduced to the empty sequence. Otherwise it can be reduced the a singleton sequence consisting of the value of the original sequence.

    A sequence with more than two elements can be reduced if we can find a suitable “split point” for the sequence. For a split point to work we need the subsequence on the left of the split point to be reducible, and the subsequence on the right of the split point to be reducible, and either at least one is reduced to 0, or they are reduced to non-zero values that have different signs. If one of the subsequences reduced to 0, we end up with a sequence of length 0 or 1, which are dealt with above, and if the subsequences reduce to non-zero values with different signs we end up with a sequence of length 2, which is also dealt with above.

    The following code uses this approach to solve the puzzle using recursion. We use the [[ @cached ]] decorator from the enigma.py library to avoid recalculating the result for sequences we have already seen.

    We can easily test to see if two numbers have different signs by evaluating their product. It they have different signs the product will be negative. If at least one of the numbers is zero the product will also be 0. If they have the same sign then the product will be positive.

    This program calculates the results for all 4 problem sequences in 94ms.

    Run: [ @repl.it ]

    from enigma import irange, cached, arg, printf
    
    # represent the red and green numbers
    (R, G) = (lambda n: -n, lambda n: n)
    
    # can sequence <s> be solved?
    @cached
    def _solve(s, n):
    
      # a sequence of length 0 or 1 is always possible
      if n < 2:
        return True
    
      # a sequence of length 2 is possible if the numbers have different signs
      if n == 2:
        return (s[0] * s[1] < 0)
    
      # for longer sequences consider possible split points
      n -= 1
      a = 0
      b = sum(s)
      i = 0
      while i < n:
        x = s[i]
        a += x
        b -= x
        i += 1
        if (a * b <= 0) and _solve(s[:i], i) and _solve(s[i:], n - i + 1):
          return True
    
      return False
    
    solve = lambda s: _solve(s, len(s))
    
    # helper functions for constructing problem sequences
    
    def _alternate(s, f, g):
      for x in s:
        yield f(x)
        (f, g) = (g, f)
    
    alternate = lambda s, f, g: tuple(_alternate(s, f, g))
    
    # sequences to check
    test = {
      # example sequence
      'X': alternate((3, 4, 3, 2, 5, 2), G, R),
      # puzzle sequences
      'A': alternate((9, 4, 1, 4, 1, 7, 1, 3, 5, 4, 2, 6, 1, 4, 8, 3, 2), R, G),
      'B': alternate((2, 3, 5, 9, 6, 3, 1, 4, 2, 3, 1), G, R),
      'C': alternate(tuple(irange(1, 1000)) + tuple(irange(3, 999, step=2)), G, R),
      'D': alternate((
        3, 2, 1, 4, 5, 4, 3, 2, 4, 3, 7, 4, 1, 5, 1, 4, 2, 4, 3, 1, 2, 7, 9,
        3, 7, 5, 3, 8, 6, 5, 8, 4, 1, 5, 2, 3, 1, 4, 10, 6, 3, 5, 7, 4, 1, 4
      ), R, G)
    }
    
    # we'll be doing some serious recursion
    import sys
    sys.setrecursionlimit(4000)
    
    # select sequences to check
    args = arg('ABCD', 0)
    
    for k in args:
      printf("checking sequence {k}...")
      r = solve(test[k])
      printf("{k} = {r}")
    

    Solutions: It is possible to successfully reduce sequences B and C. Sequences A and D cannot be successfully reduced.

    Special casing n = 2 is not strictly necessary, as the general case will handle it, but it is a bit faster.

    More compactly (but not necessarily more readably) we could write [[ solve(s) ]] as:

    def solve(s):
      return (len(s) < 2) or any(sum(s[:i]) * sum(s[i:]) <= 0 and solve(s[:i]) and solve(s[i:]) for i in irange(1, len(s) - 1))
    

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: