Book of programming problems

Complexity (1-100): 90

A plant consists of two devices A and B, connected by three hoses, laying on ground. Each device has three nipples, numbered 1 to 3, as it is shown on fig.1. Each hose connects nipples with the same number. Hoses may lay in an arbitrary order with one exception: the distance between any point on a hose and device A should increase while moving from A to B.

In order to improve the throughput, it was decided to reorder the hoses, so that there would be no crosses (see Fig. 2). To do so, an inspector was instructed to record information about crosses throughout the hoses from device A to device B. For each cross, the inspector has recorded a pair of numbers: the number of hose below, and the number of hose above (no three hoses cross at the same point). So, for example, for fig. 1 the recording would be


Write a program which, given a space-separated sequence of hose numbers the inspector recorded, would detect:

• are there errors in recording made by the inspector, and
• is it possible to untangle hoses without disconnecting them from nipples.

The program should print one of the three messages:

• "Incorrect data", if the recordings are incorrect,
• "Untanglable", if there is a way to straighten up the hoses,
• "Not untanglable", if the hoses cannot be straighten up without disconnecting them from the nipples.

Self-tests:

Input data	Result
3 2 2 3 2 1 1 2 2 3 3 2 1 2 2 1	Not untanglable
3 2 2 3 2 1 1 2 2 3 3 2 1 2 2 1 2 1 1 2 3 2 2 3 1 2 2 1 2 3 3 2	Untanglable

The simplest approach to the problem is to look at hoses from a different point of view: from device A to device B. At this point of view, each cross between hoses is a turn by 180^o, either clockwise or anticlockwise, between the hoses. Crosses (a,b) (where a is the number of hose below and b is the number of hose above) can then be easily replaced by turns (a,b)ⁿ (where n is 1 for clock-wise turn by 180^o and (-1) for anticlockwise turns, a and b are hose numbers in any order). It is obvious that subsequent turns can be merged and zero turns can be removed:


Solving the problem for two hoses in this "space of turns" is rather simple: just check that all ns add up to zero. Now, let's add the third hose... What if we straighten up any two of hoses and look how the third hose twists around the first two? For example, let us straighten hoses 1 and 3. The result would look like this:

The turn list for this example is (2,3)²(1,2)²(2,3)^-2(1,2)^-2. It can be seen that the result will always be the repetition of the following forms: (1,2)^2k or (2,3)^2k. If recurring application of merge rules (*) can reduce the turn list to an empty list, than the hoses can be untangled.

Now, to the problem of straighting up hoses 1 and 3. We will need to change our point of view once again. Imagine, that while hoses 1 and 3 cross, we turn out point of view accordingly, so that hose 1 is always above hose 3. When that happen (hoses 1 and 3 cross and we turn our head by 180^o), hose 2 turns over both hoses 1 and 3 in an opposite direction. Speaking of formulas, (1,3)⁺¹ will become either (1,2)^-1(2,3)^-1 or (2,3)^-1(1,2)^-1, depending on the current position of hose 2 with relation to hoses 1 and 3.

There is one last thing we should take care about: we cannot turn devices, thus we should check that the sum of all (1,3)^k in the turn list is zero.