Interesting sorting problem
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();
}
}
}
}
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.
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"
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.