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**:

I have made the corrections to the puzzle text above.

I originally tried a simple recursive solver that just plays the game as described, and this is enough to evaluate sequences

A,BandC. But for sequenceDyou 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

Din 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:

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 theenigma.pylibrary 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 ]Solutions:It is possible to successfully reduce sequencesBandC. SequencesAandDcannotbe successfully reduced.Special casing

n = 2is 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: