I have the following problem, but I can't find a good approach.
There are n stacks and p types of items (1 < p < n). Each type has exactly 4 items distributed across stacks. Each stack can hold a maximum of 4 items.
I need to find best way to move items in order to obtain only matching items in each stack.
Example:
Starting by having 4 stacks and 2 types of items
Stack 1: A, B, B, A
Stack 2: A, B, A
Stack 3: B
Stack 4: empty
stack1|stack2|stack3|stack4
ABBA | ABA- | B--- | ---- <- move from stack1 to stack4
ABB- | ABA- | B--- | A--- <- move from stack1 to stack3
AB-- | ABA- | BB-- | A--- <- move from stack1 to stack3
A--- | ABA- | BBB- | A--- <- stack2 to stack1
AA-- | AB-- | BBB- | A--- <- stack2 to stack3
AA-- | A--- | BBBB | A--- <- stack2 to stack1
AAA- | ---- | BBBB | A--- <- stack4 to stack1
AAAA | ---- | BBBB | ---- <- DONE
LATER EDIT ~ Real life example:
Stacks can be seen as tables and items like plates of different colors. Note that plates are stacked so you can perform only the following action: pop then push (take(pop) a plate and put(push) it on another table, even if the table is empty nor it already has a stack of 1 to 3 plates)
Target: Sort the plates colorwise using the minimum number of actions.
Below is an outline of an algorithm to sort the stacks heuristically. I have tried to break it and so far have not been able to do so, BUT, it is by no means rigorously tested!!
if any stack is full of one type:
rule 0:
exclude the stack from further processing.
if all (non excluded) stacks are homegenous, or any two stacks are homogenous of the same type:
rule 1:
combine any stacks with the same type of items, using a stack with the least number of items of a type, and using a stack with a greatest number of items of the type as the destination.
if any stack not homogenous:
rule 5:
if a stack has an overburden of 3 and the lowest stack has only one item, move the one item to create an empty stack.
rule 6:
if a stack has an overburden of 3 and there is an empty stack, move an overburden item to the empty stack.
rule 7:
if there are two or more stacks with the same top overburden type, and there is an empty stack, move one of those overburden items to the empty stack.
rule 2:
identify as target stacks those stacks which have a greatest number of an item of a type at their base. if there are two or more such stacks then target the stack which has a least overburden, being the lowest number of types in the overburden. if there are two or more such stacks then target the stacks which has the least number of items in the over burden of those stacks.
if there is any homogenous stack or empty stack:
move an item from a target stack to a homogenous stack of the same type, or to an empty stack if no homogenous stack of the same type.
rule 3:
identify as target stacks those stacks which have a second overburden item the same type as a homogenous stack, or if none, then those stacks which have a third overburden item the same type as a homogenous stack, or if none then the remaining stacks.
move a top item from a target stack to the lowest stack.
rule 4:
move an item from the lowest stack to the next lowest stack.
repeat from the top until there is only one stack of each type.
Your note re test cases being under 20 moves is interesting. I think the case:
ACDB | ABCD | DBCA | ---- | ADBC
cannot be done much under 24 moves?
The above algorithm should always be low in its number of moves, but it is heuristically predeterministic, and does not search for "other" move combinations.
Below is a "first cut" implementation is javascript.
var stacks = [
[ "A", "B", "B", "A" ],
[ "A", "B", "A" ],
[ "B" ],
[]
];
var stacks = [
[ "C" ],
[ "A" ],
[ "A", "A" ],
[ "C" ],
[ "B", "B" ],
[ "C" ],
[ "B", "B" ],
[ "A" ],
[ "C" ]
]
var stacks = [
[ "D", "E"],
[ "D", "D", "F" ],
[ "F", "E" ],
[ "E", "F" ],
[ "D", "F", "E" ]
];
var stacks = [
[ "A", "B", "C", "D" ],
[ "A", "C", "D", "B" ],
[ "A", "D", "B", "C" ],
[ "A", "B", "C", "D" ],
[]
]
var stacks = [
[ "A", "C", "D", "B" ],
[ "A", "B", "C", "D" ],
[ "A", "B", "C", "D" ],
[],
[ "A", "D", "B", "C" ]
]
var stacks = [
[ "A", "C", "D", "B" ],
[ "A", "B", "C", "D" ],
[ "D", "B", "C", "A" ],
[],
[ "A", "D", "B", "C" ]
]
work = []
for ( var stack of stacks ) {
work.push(stack)
}
function displayStacks(stacks, src, item, dst, rule) {
var text = (stacks[0].join('') + '----').slice(0,4);
for ( var stack of stacks.slice(1) ) {
text += " | " + (stack.join('') + '----').slice(0,4);
}
if ( src === "" ) {
move = "";
} else {
movesCount += 1;
move = nbsp.repeat(3) + "<- move " + item + " from stack " + src + " to stack " + dst + " <- rule " + rule + " : move " + movesCount;
}
var newStacks = document.createElement("div");
newStacks.innerHTML = text + move;
document.getElementById("moves").appendChild(newStacks);
}
function typesIn(stack) {
if ( stack.length == 0 ) return 0;
var types = [ stack[0] ];
for ( var item of stack.slice(1) ) {
if ( ! types.includes(item) ) types.push(item)
}
return types.length;
}
function noMixed(stacks) {
for ( var stack of stacks ) {
if ( typesIn(stack) > 1 ) return false;
}
return true;
}
function homogenous(stacks, trim) {
var homogenousStacks = [];
for ( var i = stacks.length - 1; i > -1; i-- ) {
var stack = stacks[i];
if ( typesIn(stack) == 1 ) {
if ( stack.length < 4 ) {
homogenousStacks.push(stack);
} else if ( trim ) {
stacks.splice(i, 1);
}
}
}
return homogenousStacks;
}
function sameType(stacks) {
var types = []
var counts = []
var typed = []
for ( var stack of stacks ) {
if ( stack.length > 0 ) {
if ( ! types.includes(stack[0]) ) {
types.push(stack[0]);
counts.push(1);
typed.push([stack])
} else {
var ndx = types.indexOf(stack[0]);
counts[ndx] += 1;
typed[ndx].push(stack);
}
}
}
return [ counts, typed ];
}
function nonHomogenous(stacks) {
var nonHomogenousStacks = [];
for ( var stack of stacks ) {
if ( typesIn(stack) > 1 ) {
nonHomogenousStacks.push(stack)
}
}
return nonHomogenousStacks;
}
function based(stacks) {
var basedStacks = [];
for ( var stack of stacks ) {
var type = stack[0];
var base = [ stack, type, 1 ];
for ( var item of stack.slice(1) ) {
if ( item == type ) {
base[2] += 1;
} else {
break;
}
}
var overtypes = [];
for ( var item of stack.slice(base[2]) ) {
if ( ! overtypes.includes(item) ) {
overtypes.push(item);
}
}
base.push(overtypes.length);
base.push(stack.length - base[2]);
basedStacks.push(base);
}
basedStacks.sort(
(a,b) => {
if ( a[2] < b[2] ) return 1; if ( a[2] > b[2] ) return -1;
if ( a[3] > b[3] ) return 1; if ( a[3] < b[3] ) return -1;
if ( a[4] > b[4] ) return 1; if ( a[4] < b[4] ) return -1;
return 0; }
);
return basedStacks;
}
function empty(stacks) {
for ( var stack of stacks ) {
if ( stack.length == 0 ) return [ stack ];
}
}
function typeStacks(stacks) {
var homogenousTypes = [];
for ( var stack of stacks ) {
homogenousTypes.push(stack[0]);
}
return homogenousTypes;
}
function overHomogenousBurden(stacks) {
overBurdens = [];
for (stack of stacks ) {
type = stack[stack.length-1];
count = 1
for ( var i = stack.length-2; i > -1; i-- ) {
if ( stack[i] == type ) {
count += 1;
} else {
overBurdens.push([ stack, type, count ]);
break;
}
}
}
overBurdens.sort(
(a,b) => {
if ( a[2] > b[2] ) return -1;
if ( a[2] < b[2] ) return 1;
return 0;
}
);
return overBurdens;
}
function commonOHB(OHBs) {
types = [ OHBs[0][1] ];
commons = [ [ OHBs[0][0] ] ];
for ( var ohb of OHBs.slice(1) ) {
if ( types.includes(ohb[1]) ) {
commons[types.indexOf(ohb[1])].push(ohb[0]);
} else {
types.push(ohb[1]);
commons.push([ ohb[0] ]);
}
}
commons.sort(
(a,b) => {
if ( a.length > b.length ) return -1;
if ( a.length < b.length ) return 1;
return 0;
}
);
return commons;
}
function nextMove() {
var src;
var item;
var dst;
var homogenousStacks = homogenous(work);
if ( noMixed(work) || homogenousStacks.length > 1 ) {
var sameStacks = sameType(homogenousStacks)
for ( var i = 0; i < sameStacks[0].length; i++ ) {
if ( sameStacks[0][i] > 1 ) {
sameStacks[1][i].sort(
(a,b) => {
if ( a.length < b.length ) return -1;
if ( a.length > b.length ) return 1;
return 0; }
);
src = sameStacks[1][i][0];
item = src.pop();
dst = sameStacks[1][i][sameStacks[1][i].length-1]
dst.push(item);
displayStacks(stacks, stacks.indexOf(src), item, stacks.indexOf(dst), 1);
}
}
}
var nonHomogenousStacks = nonHomogenous(work);
if ( homogenousStacks.length == 0 && nonHomogenousStacks.length == 0 ) {
document.getElementById("next").innerHTML = "Done - stacks sorted.";
return;
}
if ( nonHomogenousStacks.length > 0 ) {
var homgenousOverBurdens = overHomogenousBurden(work);
work.sort(
(a,b) => {
if ( a.length < b.length ) return -1; if ( a.length > b.length ) return 1;
return 0; }
);
if ( homgenousOverBurdens[0][2] == 3 && work[0].length == 1 ) {
src = work[0];
item = src.pop();
dst = work[1];
dst.push(item)
displayStacks(stacks, stacks.indexOf(src), item, stacks.indexOf(dst), 5);
return;
}
var emptyStacks = empty(stacks);
if ( homgenousOverBurdens[0][2] == 3 && emptyStacks ) {
src = homgenousOverBurdens[0][0];
item = src.pop();
dst = emptyStacks[0];
dst.push(item);
displayStacks(stacks, stacks.indexOf(src), item, stacks.indexOf(dst), 6);
return;
}
var commonOHBs = commonOHB(homgenousOverBurdens);
if ( commonOHBs[0].length > 1 && emptyStacks ) {
src = commonOHBs[0][0];
item = src.pop();
dst = emptyStacks[0];
dst.push(item);
displayStacks(stacks, stacks.indexOf(src), item, stacks.indexOf(dst), 7);
return;
}
dst = false;
var targetStacks = based(nonHomogenousStacks);
for ( var targetStack of targetStacks ) {
var item = targetStack[0][targetStack[0].length-1];
for ( var stack of homogenous(stacks, false) ) {
if ( stack[stack.length-1] == item ) {
dst = stack;
break;
}
}
if ( ! dst ) {
if ( emptyStacks ) {
dst = emptyStacks[0];
}
}
if ( dst ) {
targetStack[0].pop();
dst.push(item);
displayStacks(stacks, stacks.indexOf(targetStack[0]), item, stacks.indexOf(dst), 2);
break;
}
}
if ( ! dst ) {
var homogenousTypes = typeStacks(homogenous(stacks, false));
targetStacks.sort(
(a,b) => {
if ( homogenousTypes.includes(a[0][a[0].length-2]) ) return -1;
if ( homogenousTypes.includes(b[0][b[0].length-2]) ) return 1;
if ( homogenousTypes.includes(a[0][a[0].length-3]) ) return -1;
if ( homogenousTypes.includes(b[0][b[0].length-3]) ) return 1;
return 0; }
);
var sourceStack = targetStacks[0];
var item = sourceStack[0][sourceStack[0].length-1];
var destinationStacks = targetStacks.slice(1).sort(
(a,b) => {
if ( a[0].length == 4 ) return 1; if ( b[0].length == 4 ) return -1;
if ( a[0].length < b[0].length ) return -1; if ( a[0].length > b[0].length ) return 1;
if ( a[0][a[0].length-1] == item ) return -1; if ( b[0][b[0].length-1] == item ) return 1;
return 0; }
);
if ( destinationStacks[0][0].length != 4 ) {
dst = destinationStacks[0][0];
sourceStack[0].pop();
dst.push(item)
displayStacks(stacks, stacks.indexOf(sourceStack[0]), item, stacks.indexOf(dst), 3);
}
if ( ! dst ) {
work.sort(
(a,b) => {
if ( a.length < b.length ) return -1;
if ( a.length > b.length ) return 1;
if ( typesIn(a) > typesIn(b) ) return 1;
return 0; }
);
sourceStack = work[0];
dst = work[1];
item = sourceStack.pop();
dst.push(item)
displayStacks(stacks, stacks.indexOf(sourceStack), item, stacks.indexOf(dst), 4);
}
}
}
}
movesCount = 0
const nbsp = " ";
function load() {
var heads = nbsp + "0" + nbsp.repeat(3) + "|";
for ( var i = 1; i < stacks.length; i++ ) {
heads += nbsp.repeat(2) + i + nbsp.repeat(3 - Math.floor(Math.log10(i))) + "|";
}
document.getElementById("heads").innerHTML = heads;
displayStacks(stacks, '', '', '')
}#next {
border-radius: 5px;
border: 2px solid black;
background-color: wheat;
margin: 20px;
padding: 10px;
}
#heads {
background-color: lightblue;
}
#moves > div:nth-of-type(even) {
background-color: beige;
}<body onload="load()">
<div id="next" onclick="nextMove()">Click here for next moves.</div>
<code id="heads"></code>
<code id="moves"></code>
</body>