import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
class HanoiSort {
HanoiSort hanoi = new HanoiSort();
int N = 6;
for (int len = 1; len <= N; len++) {
List
<Integer
> inputList
= Arrays.
asList(input
); int max = N;
for (int i = 1; i < len; i++) max *= N;
for (int run = 0; run < max; run++) {
int n = run;
for (int i = 0; i < len; n /= N, i++) {
input[i] = (n % N)+1;
}
try {
hanoi.sort(inputList);
System.
out.
println(inputList
); e.
printStackTrace(System.
out); return;
}
}
}
hanoi.done();
}
private final Deque<Integer> main = new ArrayDeque<Integer>();
private final Deque<Integer> help1 = new ArrayDeque<Integer>();
private final Deque<Integer> help2 = new ArrayDeque<Integer>();
private int taskCount = 0;
private int opCount = 0;
private void sort(List<Integer> input) {
taskCount++;
main.addAll(input);
sortMain();
verify();
main.clear();
}
private void verify() {
if (!help1.isEmpty()) {
}
if (!help2.isEmpty()) {
}
int last = 0;
for (int i: main) {
if (last > i) {
}
last = i;
}
}
private void done() {
System.
out.
print(opCount
+ "/" + taskCount
); }
private void move(Deque<Integer> from, Deque<Integer> to) {
if (to != main && !to.isEmpty() && i > to.peek()) {
from + " " + i + " -> " + to);
}
to.push(i);
opCount++;
}
private String name
(Deque
<Integer
> stack
) { return stack == help1 ? "help1" :
stack == help2 ? "help2" :
"main";
}
return "main: " + main +
"\nhelp1: " + help1 +
"\nhelp2: " + help2;
}
private void ensureMain(Deque<Integer> stack) {
if (stack != main) {
}
}
private void ensureHelp(Deque<Integer> stack) {
if (stack == main) {
}
}
private void ensureHelpers(Deque<Integer> stack1, Deque<Integer> stack2) {
ensureHelp(stack1);
ensureHelp(stack2);
}
private void sortMain() {
int height = main.size();
int topIndex = height;
while (topIndex == height && height > 1) {
topIndex = lastIndexOfLargest(height, main);
height--;
}
if (topIndex == height) {
// is already sorted
return;
}
// split stack at largest element
int part1Count = topIndex;
int part2Count = height - topIndex;
// move largest and first part to help 1
moveFromMain(part1Count+1, help1, help2);
// merge both parts to help 2, leaving largest on 1
mergeToHelp(part2Count, main, part1Count, help1, help2);
// move largest to main
move(help1, main);
// move remaining to main
moveToMain(height, help2, help1);
}
/** Moves elements from main to helper, sorting them */
private void moveFromMain(int amount, Deque<Integer> target, Deque<Integer> help) {
if (amount < 1) return;
ensureHelpers(target, help);
int topIndex = lastIndexOfLargest(amount, main);
int part1Count = topIndex;
int part2Count = amount - topIndex - 1;
// move first part to help
moveFromMain(part1Count, help, target);
// move largest to target
move(main, target);
// merge both parts to target
mergeToHelp(part2Count, main, part1Count, help, target);
}
/** Moves elements from helper to main, keeping them sorted */
private void moveToMain(int amount, Deque<Integer> source, Deque<Integer> help) {
if (amount < 1) return;
ensureHelpers(source, help);
moveHelper(amount-1, source, help);
move(source, main);
moveToMain(amount-1, help, source);
}
/** Moves elements between helpers */
private void moveHelper(int amount, Deque<Integer> source, Deque<Integer> target) {
pushToMain(amount, source);
popFromMain(amount, target);
}
/** Merges top of main and helper to other helper */
private void mergeToHelp(int mainAmount, Deque<Integer> main, int helpAmount, Deque<Integer> help, Deque<Integer> target) {
ensureMain(main);
ensureHelpers(help, target);
if (mainAmount < 0) mainAmount = 0;
if (helpAmount < 0) helpAmount = 0;
while (mainAmount > 0 || helpAmount > 0) {
// while there is something to merge
int largestMain = valueOfLargest(mainAmount, main);
int largestHelp = valueOfLargest(helpAmount, help);
if (largestMain > largestHelp) {
// largest is in main
int index = firstIndexOfLargest(mainAmount, main);
if (index > 0) {
// move excess to help:
int mainTop = index;
int helpTop = elementsSmallerThan(help, largestMain);
if (helpTop > 0) {
// 1. move top of help to target
moveHelper(helpTop, help, target);
// 2. merge old top with excess from main
mergeToHelp(mainTop, main, helpTop, target, help);
} else {
moveFromMain(mainTop, help, target);
}
mainAmount -= mainTop;
helpAmount += mainTop;
}
move(main, target);
mainAmount--;
} else {
// largest is at bottom of help
int helpTop = helpAmount - 1; // largest is at bottom
// move top to main
pushToMain(helpTop, help);
mainAmount += helpTop;
// move largest to target
move(help, target);
helpAmount = 0;
}
}
}
private void pushToMain(int amount, Deque<Integer> from) {
for (; amount > 0; amount--) move(from, main);
}
private void popFromMain(int amount, Deque<Integer> to) {
for (; amount > 0; amount--) move(main, to);
}
private int firstIndexOfLargest(int height, Deque<Integer> stack) {
int topValue = 0;
int topIndex = 0;
int i = 0;
if (e > topValue) {
topValue = e;
topIndex = i;
}
if (++i == height) break;
}
return topIndex;
}
private int lastIndexOfLargest(int height, Deque<Integer> stack) {
int topValue = 0;
int topIndex = 0;
int i = 0;
if (e >= topValue) {
topValue = e;
topIndex = i;
}
if (++i == height) break;
}
return topIndex;
}
private int valueOfLargest(int height, Deque<Integer> stack) {
if (height-- == 0) break;
if (e > v) v = e;
}
return v;
}
private int elementsSmallerThan(Deque<Integer> stack, int value) {
int i = 0;
if (e >= value) return i;
i++;
}
return i;
}
}