We have a circular track on which a number of loaded cars are located. Each
car has its own specified unloading position along the track. The cars can be
moved in either direction along the track, but cannot pass each other.
We want to make a worklist, specifying the order in which the cars should be
moved. The order of cars in the worklist must allow each car to be moved just
once all the way to its unloading position. How many different orders will
allow this?
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 can be moved to their
destinations: a then c then b, a then b then c, or b then a then c.
Given the
original positions of the cars and destinations in a String circle,
return the number of different orders in which the
cars can be moved. If there are more than 2,000,000,000 orders return 1.
If no order is possible, your method should return 0.
