Interesting sorting problem

Question

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:
  __
 /  \
1100UU0011

Second step:
  ____
 /    \
UU00110011

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

Answer 1

Counting sort.

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

for(int i=0; i<A; i++)
   data[i] = '0';
for(int i=0; i<A; i++)
   data[A+i] = '1';
for(int i=0; i<U; i++)
   data[A+A+i] = 'U';

Answer 2

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
       uPosition.append(i)

result = []
for i in range(len(sample)):
    if i = uPosition[0]
       result.append('U')
       uPosition.pop(0)
       continue
    if numberOfZeros > 0:
       result.append('0')
       numberOfZeros -= 1
       continue
    result.append('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
       result.append('U')
       continue
    if numberOfZeros > 0:
       result.append(0)
       numberOfZeros -= 1
       continue
    result.append(1)

Answer 3

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() {
            final Collection<NumberSet> result = new LinkedList<NumberSet>();

            for (int i=0;i<=uuPosition-2;i++) {
                result.add(getNextNumberSet(i));
            }

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

            return result;
        }

        public boolean isFinished() {
            boolean ones = false;
            for (int i=0;i<numberSet.length;i++) {
                if (numberSet[i] == 1)
                    ones = true;
                else if (numberSet[i] == 0 && ones)
                    return false;
            }
            return true;
        }

        @Override
        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;
        }

        @Override
        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);
                    nextNextSteps.addAll(nextSet.getNextSteps());
                    if (nextSet.equals(endSet)) {
                        return;
                    }
                }
            }
            nextSteps = nextNextSteps;
            nextNextSteps = new LinkedList<NumberSet>();
            depth++;
        }
    }

    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) {
                System.out.println(cachedSet.getUUPosition());
                cachedSet = cachedSet.getParent();
            }
        }
    }
}

Answer 4

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.

Answer 5

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"

Answer 6

Here's a try:

Start:
  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
StartFromRight
  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.
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.

Answer 7

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

(2n)!
-----
(n!)²

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
(0|n)(1|n)--

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.

Answer 8

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:

Call:

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
  return;

 // 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);
 newMoves.Add(state);
 m_Steps[state] = newMoves;

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

 // 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)
   continue;

  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++) {
   for (int i = 0; i < chars.Length; i++) {
    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';
    else
     chars[i] = 'U';
   }
   m_Steps = new Dictionary<string, List<string>>();
   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);
     Console.WriteLine();
    }
  }
 }
}