Take the 2-minute tour ×

There are ones, zeroes and ‘U’s in a particular order. (E.g. “1001UU0011”) The number of ones and zeroes are the same, and there’s always two ‘U’s next to each other. You can swap the pair of ‘U’s with any pair of adjacent digits. Here’s a sample move:

     /  \
1100UU0011 --> 11001100UU

The task is to put all the zeroes before the ones.

Here's a sample solution:

First step:
 /  \

Second step:
 /    \

000011UU11  --> DONE

It’s pretty easy to create a brute-force algorithm. But with that it takes hundreds or even thousands of moves to solve a simple one like my example. So I’m looking for something more “clever” algorithm.

It's not homework; it was a task in a competition. The contest is over but I can’t find the solution for this.

Edit: The task here is the create an algorithm that can sort those 0s and 1s - not just output N 0s and N 1s and 2 Us. You have to show the steps somehow, like in my example.

Edit 2: The task didn't ask for the result with the least moves or anything like that. But personally I would love the see an algorithm that provides that :)

share|improve this question
Nice problem. Has it been uploaded to an online judge after the contest? If yes could you link to it? –  IVlad Jun 22 '10 at 12:02
No, nothing was posted. –  KovBal Jun 22 '10 at 12:10
There isn't always a solution. For example: 1UU00. Also, 1UU0. –  Tomer Vromen Jun 22 '10 at 12:46
Do you have any examples more complex than the one you provided above? It'd be nice to have something to benchmark different answers on, and I'm pretty sure there aren't even "hundreds or thousands" of permutations of your sample string. :) –  Nick Johnson Jun 22 '10 at 13:13
@KovBal - can you settle something for us? Did the question ask for the minimum number of moves, or was any number was fine as long as your program didn't time out? –  IVlad Jun 22 '10 at 14:20
show 22 more comments

8 Answers

up vote 2 down vote accepted

If you use a WIDTH-first brute force, it's still brute force, but at least you are guaranteed to come up with the shortest sequence of moves, if there is an answer at all. Here's a quick Python solution using a width-first search.

from time import time

def generate(c):
    sep = "UU"
    c1, c2 = c.split(sep)
    for a in range(len(c1)-1):
        yield c1[0:a]+sep+c1[(a+2):]+c1[a:(a+2)]+c2
    for a in range(len(c2)-1):
        yield c1+c2[a:(a+2)]+c2[0:a]+sep+c2[(a+2):]

def solve(moves,used):
    solved = [cl for cl in moves if cl[-1].rindex('0') < cl[-1].index('1')]
    if len(solved) > 0: return solved[0]
    return solve([cl+[d] for cl in moves for d in generate(cl[-1]) if d not in used and not used.add(d)],used)

code = raw_input('enter the code:')

a = time()
print solve([[code]],set())
print "elapsed time:",(time()-a),"seconds"
share|improve this answer
@Brenda Holloway: Just wondering, what is the maximal set of numbers it can handle lets say... in 10 seconds? Also, could you please provide the result of calculating this: 0,1,0,1,0,1,0,1,0,1,0,1,0,1,U,U –  Max Jun 22 '10 at 16:37
solving that took 5.8 seconds. $ python sort.py enter the code:01010101010101UU depth 1 width 1 depth 2 width 13 depth 3 width 72 depth 4 width 527 depth 5 width 3697 depth 6 width 24342 depth 7 width 110597 depth 8 width 234299 ['01010101010101UU', '01UU010101010101', '01100UU101010101', '0110001101UU0101', '0110001101100UU1', '0UU0001101100111', '00000011011UU111', '000000UU01111111'] elapsed time: 5.82800006866 seconds –  Brenda Holloway Jun 22 '10 at 16:44
@Brenda Holloway: What about memory usage? Just wondering how Python generally performs. –  Max Jun 22 '10 at 17:37
@Max latest code (as shown above) performs this in 1.16 seconds, which isn't bad for a non-compiled language, though I do use lots of list comprehensions and other high level tricks that end up keeping a lot of the execution in the 'C' underpinnings. –  Brenda Holloway Jun 22 '10 at 18:51
@Brenda Holloway: Gonna share with you the secret how to make your script perform like my program. I changed single width search to a double search (not included in above post as it looks shitty). That means that I start (for example) from both 000111 and 010101. Then I start a width-first search from that 2 end-points simultaneously (was thinking about multi-threaded implementation but contests usually forbit it). When the width-searches intersect - the result is found. This way I can go twice as deep as before using same memory and same calculation amount. :D –  Max Jun 23 '10 at 11:26
show 3 more comments

I think this should work:

  • Iterate once to find the position of the U's. If they don't occupy the last two spots, move them there by swapping with the last two.
  • Create a variable to track the currently sorted elements, initially set to array.length - 1, meaning anything after it is sorted.
  • Iterate backwards. Every time you encounter a 1:
    • swap the the one and its element before it with the U's.
    • swap the U's back to the the currently sorted elements tracker -1, update variable
  • Continue until the beginning of the array.
share|improve this answer
It will work, but the task is to find an optimal solution, not any solution. –  Max Jun 22 '10 at 13:14
@JRL: You did not quite understand it. The result your algorithm will provide will be not the optimal one so it is not valid. Yes, it will be very fast (both algorithm and the resulting steps) but not optimal. Also, I've just tried to find some examples to prove my words and found out that your algorithm will fail most tests. Try doing it with: 1001UU or 1010UU or 001101. –  Max Jun 22 '10 at 13:31
@Daniel Brückner: In this kind of problems you need to give 'optimal' result only, not the 'close to optimal' one. –  Max Jun 22 '10 at 13:32
@Max: where did you see that the task was to find the optimal solution? –  JRL Jun 22 '10 at 13:36
+1. Nowhere does the question mention that the optimal number of moves is required. –  Aryabhatta Jun 22 '10 at 14:06
show 7 more comments

This is quite an interesting problem - so let's try to solve it. I will start with an precise analysis of the problem and see what one can find out. I will add piece by piece to this answer over the next days. Any help is welcome.

A problem of size n is a problem with exactly exactly n zeros, n ones, and two Us, hence it consists of 2n+2 symbols.

There are


different sequences of exactly n zeros and nones. Then there are 2n+1 possible positions to insert the two Us, hence there are

(2n)!         (2n+1)!
-----(2n+1) = -------
(n!)²          (n!)²

problem instances of size n.

Next I am looking for a way to assign a score to each problem instance and how this score changes under all possible moves hoping to find out what the minimal number of required moves is.

Instance of size one are either already sorted

--01   0--1   01--

(I think I will use hyphens instead of Us because they are easier to recognize) or cannot be sorted.

--10  ==only valid move==>  10--
-10-  no valid move
10--  ==only valid move==>  --10

In consequence I will assume n >= 2.

I am thinking about the inverse problem - what unordered sequences can be reached starting from an ordered sequence. The ordered sequences are determined up to the location of the both hyphens - so the next question is if it is possible to reach every ordered sequence from every other order sequence. Because a sequence of moves can be performed forward and backward it is sufficient to show that one specific ordered sequence is reachable from all other. I choose (0|n)(1|n)--. ((0|x) represents exactly x zeros. If x is not of the form n-m zero or more is assumed. There may be additional constraints like a+b+2=n not explicitly stated. ^^ indicates the swap position. The 0/1 border is obviously between the last zero and first one.)

// n >= 2, at least two zeros between -- and the 0/1 border
(0|a)--(0|b)00(1|n) => (0|n)--(1|n-2)11 => (0|n)(1|n)--
            ^^                       ^^
// n >= 3, one zero between -- and 0/1 boarder
(0|n-1)--01(1|n-1) => (0|n)1--(1|n-3)11 => (0|n)(1|n)--
         ^^                          ^^
// n >= 2, -- after last zero but at least two ones after --          
(0|n)(1|a)--(1|b)11 => (0|n)(1|n)--
// n >= 3, exactly one one after --
(0|n)(1|n-3)11--1 => (0|n)(1|n-3)--111 => (0|n)(1|n)--
            ^^                      ^^
// n >= 0, nothing to move

For the remaining two problems of size two - 0--011 and 001--1 - it seems not to be possible to reach 0011--. So for n >= 3 it is possible to reach every ordered sequence from every other ordered sequence in at most four moves (Probably less in all cases because I think it would have been better to choose (0|n)--(1|n) but I leave this for tomorrow.). The preliminary goal is to find out at what rate and under what conditions one can create (and in consequence remove) 010 and 101 because they seem to be the hard cases as already mentioned by others.

share|improve this answer
add comment

Well, the first thing that gets up to my mind is top-down dynamic programming approach. It's kind of easy to understand but could eat a lot of memory. While I'm trying to apply a bottom-up approach you can try this one:

Idea is simple - cache all of the results for the brute-force search. It will become something like this:

function findBestStep(currentArray, cache) {
    if (!cache.contains(currentArray)) {
        for (all possible moves) {
            find best move recursively
        cache.set(currentArray, bestMove);

    return cache.get(currentArray);

This method complexity would be... O(2^n) which is creepy. However I see no logical way it can be smaller as any move is allowed.

If if find a way to apply bottom-up algorithm it could be a little faster (it does not need a cache) but it will still have O(2^n) complexity.

Added: Ok, I've implemented this thing in Java. Code is long, as it always is in Java, so don't get scared of it's size. The main algorithm is pretty simple and can be found at the bottom. I don't think there can be any way faster than this (this is more of a mathematical question if it can be faster). It eats tonns of memory but still computes it all pretty fast. This 0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2 computes in 1 second, eating ~60mb memory resulting in 7 step sorting.

public class Main {

    public static final int UU_CODE = 2;

    public static void main(String[] args) {
        new Main();

    private static class NumberSet {
        private final int uuPosition;
        private final int[] numberSet;
        private final NumberSet parent;

        public NumberSet(int[] numberSet) {
            this(numberSet, null, findUUPosition(numberSet));

        public NumberSet(int[] numberSet, NumberSet parent, int uuPosition) {
            this.numberSet = numberSet;
            this.parent = parent;
            this.uuPosition = uuPosition;

        public static int findUUPosition(int[] numberSet) {
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == UU_CODE) {
                    return i;
            return -1;

        protected NumberSet getNextNumberSet(int uuMovePos) {
            final int[] nextNumberSet = new int[numberSet.length];
            System.arraycopy(numberSet, 0, nextNumberSet, 0, numberSet.length);
            System.arraycopy(this.getNumberSet(), uuMovePos, nextNumberSet, uuPosition, 2);
            System.arraycopy(this.getNumberSet(), uuPosition, nextNumberSet, uuMovePos, 2);
            return new NumberSet(nextNumberSet, this, uuMovePos);

        public Collection<NumberSet> getNextPositionalSteps() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=numberSet.length;i++) {
                final int[] nextNumberSet = new int[numberSet.length+2];
                System.arraycopy(numberSet, 0, nextNumberSet, 0, i);
                Arrays.fill(nextNumberSet, i, i+2, UU_CODE);
                System.arraycopy(numberSet, i, nextNumberSet, i+2, numberSet.length-i);
                result.add(new NumberSet(nextNumberSet, this, i));
            return result;

        public Collection<NumberSet> getNextSteps() {

            for (int i=0;i<=uuPosition-2;i++) {

            for (int i=uuPosition+2;i<numberSet.length-1;i++) {

            return result;

        public boolean isFinished() {
            boolean ones = false;
                if (numberSet[i] == 1)
                    ones = true;
                else if (numberSet[i] == 0 && ones)
                    return false;
            return true;

        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            if (getClass() != obj.getClass()) {
                return false;
            final NumberSet other = (NumberSet) obj;
            if (!Arrays.equals(this.numberSet, other.numberSet)) {
                return false;
            return true;

        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Arrays.hashCode(this.numberSet);
            return hash;

        public int[] getNumberSet() {
            return this.numberSet;

        public NumberSet getParent() {
            return parent;

        public int getUUPosition() {
            return uuPosition;

    void precacheNumberMap(Map<NumberSet, NumberSet> setMap, int length, NumberSet endSet) {
        int[] startArray = new int[length*2];
        for (int i=0;i<length;i++) startArray[i]=0;
        for (int i=length;i<length*2;i++) startArray[i]=1;
        NumberSet currentSet = new NumberSet(startArray);

        Collection<NumberSet> nextSteps = currentSet.getNextPositionalSteps();
        List<NumberSet> nextNextSteps = new LinkedList<NumberSet>();
        int depth = 1;

        while (nextSteps.size() > 0) {
            for (NumberSet nextSet : nextSteps) {
                if (!setMap.containsKey(nextSet)) {
                    setMap.put(nextSet, nextSet);
                    if (nextSet.equals(endSet)) {
            nextSteps = nextNextSteps;
            nextNextSteps = new LinkedList<NumberSet>();

    public Main() {
        final Map<NumberSet, NumberSet> cache = new HashMap<NumberSet, NumberSet>();
        final NumberSet startSet = new NumberSet(new int[] {0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2});

        precacheNumberMap(cache, (startSet.getNumberSet().length-2)/2, startSet);

        if (cache.containsKey(startSet) == false) {
            System.out.println("No solutions");
        } else {
            NumberSet cachedSet = cache.get(startSet).getParent();
            while (cachedSet != null && cachedSet.parent != null) {
                cachedSet = cachedSet.getParent();
share|improve this answer
I don't see how this approach is O(nlogn). While the method itself is O(nlogn), to solve the problem you might theoretically have to go through all the permutations (where the 2 U's are adjacent), which is O(n!). –  Tomer Vromen Jun 22 '10 at 13:01
@Tomer Vromen: Yeah, I've just figured it out too. However it will be not a O(n!) but a O(2^n) complexity, as we need to calculate best move for each combination of zeroes and ones - which is 2^n. And as I wrote in my answer - I can't find a logical way this complexity can be better as any move is possible and we can not predict that some specific move will take less/more steps than the currently calculated one. –  Max Jun 22 '10 at 13:05
My width first solver also solved it in about ten seconds in Python: ['01010101010101UU', '01UU010101010101', '01100UU101010101', '0110001101UU0101', '0110001101100UU1', '0UU0001101100111', '00000011011UU111', '000000UU01111111'] –  Brenda Holloway Jun 22 '10 at 16:41
and this is why I use Java at work but love Python for actually figuring things out. –  Brenda Holloway Jun 22 '10 at 16:48
+1 for being a working solution that produces an optimal answer. –  Brenda Holloway Jun 23 '10 at 11:21
add comment

Here's a try:

  let c1 = the total number of 1s
  let c0 = the total number of 0s
  if the UU is at the right end of the string, goto StartFromLeft
  starting at the right end of the string, move left, counting 1s, 
  until you reach a 0 or the UU.  
  If you've reached the UU, goto StartFromLeft.
  If the count of 1s equals c1, you are done.  
  Else, swap UU with the 0 and its left neighbor if possible.  
  If not, goto StartFromLeft.
  starting at the left end of the string, move right, counting 0s,
  until you reach a 1 or the UU.
  If you've reached the UU, goto StartFromRight.
  If the count of 0s equals c0, you are done.
  Else, swap UU with the 1 and its right neighbor, if possible.  
  If not, goto StartFromRight
  Then goto StartFromRight.

So, for the original 1100UU0011:

1100UU0011 - original
110000UU11 - start from right, swap UU with 00
UU00001111 - start from left, swap UU with 11

For the trickier 0101UU01

0101UU01 - original
0UU11001 - start from right, can't swap UU with U0, so start from left and swap UU with 10
00011UU1 - start from right, swap UU with 00

However, this won't solve something like 01UU0...but that could be fixed by a flag - if you've gone through the whole algorithm once, made no swaps and it isn't solved...do something.

share|improve this answer
I did not really understand the algorithm, but can you please provide the steps it will do to sort this: 01010101010101UU? –  Max Jun 22 '10 at 17:36
Actually, I realized after posting that my solution fails for some bit patterns; generally one's that end up something like this: 00000UU11111110 -- my algorithm ends up in an infinite loop switching UU and the 10 back and forth forever. I was trying to figure out an elegant way to get it out of that pattern but I ran out of time to play around with it. ;) –  Bob Montgomery Jun 23 '10 at 3:39
add comment

About the question... It never asked for the optimal solution and these types of questions do not want that. You need to write a general purpose algorithm to handle this problem and a brute-force search to find the best solution is not feasible for strings that may be megabytes in length. Also I noticed late that there are guaranteed to be the same number of 0s and 1s, but I think it's more interesting to work with the general case where there may be different numbers of 0s and 1s. There actually isn't guaranteed to be a solution in every case if the length of the input string is less than 7, even in the case where you have 2 0s and 2 1s.

Size 3: Only one digit so it is sorted by definition (UU0 UU1 0UU 1UU)

Size 4: No way to alter the order. There are no moves if UU is in the middle, and only swap with both digits if it is at an end (1UU0 no moves, UU10->10UU->UU10, etc)

Size 5: UU in the middle can only move to the far end and not change the order of the 0s and 1s (1UU10->110UU). UU at an end can move to middle and not change order, but only move back to the same end so there is no use for it (UU110->11UU0->UU110). The only way to change digits is if the UU is at an end and to swap with the opposite end. (UUABC->BCAUU or ABCUU->UUCAB). This means that if UU is at positions 0 or 2 it can solve if 0 is in the middle (UU101->011UU or UU100->001UU) and if UU is at positions 1 or 3 it can solve if 1 is in the middle (010UU->UU001 or 110UU->UU011). Anything else is already solved or is unsolvable. If we need to handle this case, I would say hard-code it. If sorted, return result (no moves). If UU is in the middle somewhere, move it to the end. Swap from the end to the other end and that is the only possible swap whether it is now sorted or not.

Size 6: Now we get so a position where we can have a string specified according to the rules where we can make moves but where there can be no solution. This is the problem point with any algorithm, because I would think a condition of any solution should be that it will let you know if it cannot be solved. For instance 0010, 0100, 1000, 1011, 1100, 1101, and 1110 can be solved no matter where the UU is placed and the worst cases take 4 moves to solve. 0101 and 1010 can only be solved if UU is in an odd position. 0110 and 1001 can only be solved if UU is in an even position (either end or middle).

I think the best way will be something like the following, but I haven't written it yet. First, make sure you place a '1' at the end of the list. If the end is currently 0, move UU to the end then move it to the last '1' position - 1. After that you continually move UU to the first '1', then to the first '0' after the new UU. This will move all the 0s to the start of the list. I've seen a similar answer the other way, but it didn't take into account the final character on either end. This can run into issues with small values still (i.e. 001UU01, cannot move to first 1, move to end 00101UU lets us move to start but leaves 0 at end 00UU110).

My guess is that you can hard-code special cases like that. I'm thinking there may be a better algorithm though. For instance you could use the first two characters as a 'temporary swap variable. You would put UU there and then do combinations of operations on others to leave UY back at the start. For instance, UUABCDE can swap AB with CD or DE or BC WITH DE (BCAUUDE->BCADEUU->UUADEBC).

Another possible thing would be to treat the characters as two blocks of two base-3 bits 0101UU0101 will show up as 11C11 or 3593. Maybe also something like a combination of hard-coded swaps. For instance if you ever see 11UU, move UU left 2. If you ever see UU00, move UU right two. If you see UU100, or UU101, move UU right 2 to get 001UU or 011UU.

Maybe another possibility would be some algorithm to move 0s left of center and 1s right of center (if it is given that there are the same number of 0s and 1s.

Maybe it would be better to work on an a structure that contained only 0s and 1s with a position for UU.

Maybe look at the resulting condition better, allowing for UU to be anywhere in the string, these conditions MUST be satisfied: No 0s after Length/2 No 1s before (Length/2-1)

Maybe there are more general rules, like it's really good to swap UU with 10 in this case '10111UU0' because a '0' is after UU now and that would let you move the new 00 back to where the 10 was (10111UU0->UU111100->001111UU).

Anyway, here's the brute force code in C#. The input is a string and an empty Dictionary. It fills the dictionary with every possible resulting string as the keys and the list of shortest steps to get there as the value:


m_Steps = new Dictionary<string, List<string>>();
DoSort("UU1010011101", new List<string>);

It includes DoTests() which calls DoSort for every possible string with the given number of digits (not including UU):

Dictionary<string, List<string>> m_Steps = new Dictionary<string, List<string>>();

public void DoStep(string state, List<string> moves) {
 if (m_Steps.ContainsKey(state) && m_Steps[state].Count <= moves.Count + 1) // have better already

 // we have a better (or new) solution to get to this state, so set it to the moves we used to get here
 List<string> newMoves = new List<string>(moves);
 m_Steps[state] = newMoves;

 // if the state is a valid solution, stop here
 if (state.IndexOf('1') > state.LastIndexOf('0'))

 // try all moves
 int upos = state.IndexOf('U');
 for (int i = 0; i < state.Length - 1; i++) {
  // need to be at least 2 before or 2 after the UU position (00UU11 upos is 2, so can only move to 0 or 4)
  if (i > upos - 2 && i < upos + 2)

  char[] chars = state.ToCharArray();
  chars[upos] = chars[i];
  chars[upos + 1] = chars[i + 1];
  chars[i] = chars[i + 1] = 'U';
  DoStep(new String(chars), newMoves);

public void DoTests(int digits) { // try all combinations
 char[] chars = new char[digits + 2];
 for (int value = 0; value < (2 << digits); value++) {
  for (int uupos = 0; uupos < chars.Length - 1; uupos++) {
    if (i < uupos)
     chars[i] = ((value >> i) & 0x01) > 0 ? '1' : '0';
    else if (i > uupos + 1)
     chars[i] = ((value >> (i - 2)) & 0x01) > 0 ? '1' : '0';
     chars[i] = 'U';
   DoSort(new string(chars), new List<string>);
   foreach (string key in m_Steps.AllKeys))
    if (key.IndexOf('1') > key.LastIndexOf('0')) { // winner
     foreach (string step in m_Steps[key])
      Console.Write("{0}\t", step);
share|improve this answer
add comment

Counting sort.

If A is the number of 0s, A is also the number of 1s, and U is the number of Us:

   data[i] = '0';
   data[A+i] = '1';
for(int i=0; i<U; i++)
   data[A+A+i] = 'U';
share|improve this answer
I think you're supposed to output the minimum number of moves and maybe the moves themselves, not just output the string in correct order. –  IVlad Jun 22 '10 at 12:07
If A and U are unknouwn you should count them (n). Then put them as you described (n). Algorithm is 2n ~ O(n). That's the best you can do with that problem, because you must read at least once to know how many Us. –  Fabio F. Jun 22 '10 at 12:10
The problem is not to sort the array of things, but to do that by only moving the 'UU' part around and then output the resulting list of moves. –  Max Jun 22 '10 at 12:15
@Fabio F. - I'm not talking about the time complexity. I'm talking about the minimum number of moves - which the problem most likely asks you to output. –  IVlad Jun 22 '10 at 12:17
add comment

There are only 2 Us?

Why not just count the number of 0s and store the position of the us:

numberOfZeros = 0
uPosition = []
for i, value in enumerate(sample):
    if value = 0:
        numberOfZeros += 1
    if value = U

result = []
for i in range(len(sample)):
    if i = uPosition[0]
    if numberOfZeros > 0:
       numberOfZeros -= 1

Would result in a runtime of O(n)

Or even better:

result = []
numberOfZeros = (len(sample)-2)/2
for i, value in enumerate(sample):
    if value = U
    if numberOfZeros > 0:
       numberOfZeros -= 1
share|improve this answer
And again, the task is not to sort it but to sort it in the way that you only move UU around. Moreover, you need to output the resulting moves. –  Max Jun 22 '10 at 12:16
add comment

Your Answer


