Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>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:</p> <p>Idea is simple - cache all of the results for the brute-force search. It will become something like this:</p> <pre><code>function findBestStep(currentArray, cache) { if (!cache.contains(currentArray)) { for (all possible moves) { find best move recursively } cache.set(currentArray, bestMove); } return cache.get(currentArray); } </code></pre> <p>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.</p> <p>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.</p> <p><strong>Added:</strong> 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 <code>0,1,0,1,0,1,0,1,0,1,0,1,0,1,2,2</code> computes in 1 second, eating ~60mb memory resulting in 7 step sorting.</p> <pre><code>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&lt;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&lt;NumberSet&gt; getNextPositionalSteps() { final Collection&lt;NumberSet&gt; result = new LinkedList&lt;NumberSet&gt;(); for (int i=0;i&lt;=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&lt;NumberSet&gt; getNextSteps() { final Collection&lt;NumberSet&gt; result = new LinkedList&lt;NumberSet&gt;(); for (int i=0;i&lt;=uuPosition-2;i++) { result.add(getNextNumberSet(i)); } for (int i=uuPosition+2;i&lt;numberSet.length-1;i++) { result.add(getNextNumberSet(i)); } return result; } public boolean isFinished() { boolean ones = false; for (int i=0;i&lt;numberSet.length;i++) { if (numberSet[i] == 1) ones = true; else if (numberSet[i] == 0 &amp;&amp; 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&lt;NumberSet, NumberSet&gt; setMap, int length, NumberSet endSet) { int[] startArray = new int[length*2]; for (int i=0;i&lt;length;i++) startArray[i]=0; for (int i=length;i&lt;length*2;i++) startArray[i]=1; NumberSet currentSet = new NumberSet(startArray); Collection&lt;NumberSet&gt; nextSteps = currentSet.getNextPositionalSteps(); List&lt;NumberSet&gt; nextNextSteps = new LinkedList&lt;NumberSet&gt;(); int depth = 1; while (nextSteps.size() &gt; 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&lt;NumberSet&gt;(); depth++; } } public Main() { final Map&lt;NumberSet, NumberSet&gt; cache = new HashMap&lt;NumberSet, NumberSet&gt;(); 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 &amp;&amp; cachedSet.parent != null) { System.out.println(cachedSet.getUUPosition()); cachedSet = cachedSet.getParent(); } } } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload