| We have a circular train track on which a number of loaded cars are located. Each
car has its own specified unloading position on the track. The cars can be
moved in either direction along the track, but cannot pass each other.
We want to specify the order in which the cars should be
moved. The order of cars must allow each car to be moved just
once all the way to its unloading position where it will remain.
The cars are each named with a lowercase letter, and their destinations with
the same letter but in uppercase. The positions of the cars and of their
destinations are given by a sequence of letters that is regarded as circular by
wrapping around the ends. So, for example, "BACacb" describes a situation in
which going clockwise around the track we encounter B, A, C, a, c, b, and then
return back to B. Here
there are 3 different orders in which the cars could be moved to their
destinations: 'a' then 'c' then 'b', 'a' then 'b' then 'c', or 'b' then 'a' then 'c'.
Create a class CircleOrder that contains a method firstOrder that is given the
original positions in a String circle and that returns the order in which they
can be moved as a String, with the first character naming the first
car to move, the second naming the second car, etc.
If there is more
than one order possible, give the one that comes first alphabetically.
If no order is possible, your method should return the 4-letter String "NONE".
|