fork download
  1. import java.util.ArrayDeque;
  2. import java.util.Arrays;
  3. import java.util.Deque;
  4. import java.util.List;
  5.  
  6. class HanoiSort {
  7.  
  8. public static void main(String[] args) throws Exception {
  9. HanoiSort hanoi = new HanoiSort();
  10. int N = 6;
  11. for (int len = 1; len <= N; len++) {
  12. Integer[] input = new Integer[len];
  13. List<Integer> inputList = Arrays.asList(input);
  14. int max = N;
  15. for (int i = 1; i < len; i++) max *= N;
  16. for (int run = 0; run < max; run++) {
  17. int n = run;
  18. for (int i = 0; i < len; n /= N, i++) {
  19. input[i] = (n % N)+1;
  20. }
  21. try {
  22. hanoi.sort(inputList);
  23. } catch (Exception e) {
  24. System.out.println(inputList);
  25. e.printStackTrace(System.out);
  26. return;
  27. }
  28. }
  29. }
  30. hanoi.done();
  31. }
  32.  
  33. private final Deque<Integer> main = new ArrayDeque<Integer>();
  34. private final Deque<Integer> help1 = new ArrayDeque<Integer>();
  35. private final Deque<Integer> help2 = new ArrayDeque<Integer>();
  36.  
  37. private int taskCount = 0;
  38. private int opCount = 0;
  39.  
  40. private void sort(List<Integer> input) {
  41. taskCount++;
  42. main.addAll(input);
  43. sortMain();
  44. verify();
  45. main.clear();
  46. }
  47.  
  48. private void verify() {
  49. if (!help1.isEmpty()) {
  50. throw new IllegalStateException("non-empty help1\n" + state());
  51. }
  52. if (!help2.isEmpty()) {
  53. throw new IllegalStateException("non-empty help2\n" + state());
  54. }
  55. int last = 0;
  56. for (int i: main) {
  57. if (last > i) {
  58. throw new IllegalStateException("unsorted main: " + main);
  59. }
  60. last = i;
  61. }
  62. }
  63.  
  64. private void done() {
  65. System.out.println();
  66. System.out.print(opCount + "/" + taskCount);
  67. }
  68.  
  69. private void move(Deque<Integer> from, Deque<Integer> to) {
  70. if (from == to) throw new IllegalArgumentException("moving from/to " + from);
  71. Integer i = from.pop();
  72. if (to != main && !to.isEmpty() && i > to.peek()) {
  73. from + " " + i + " -> " + to);
  74. }
  75. to.push(i);
  76. opCount++;
  77. }
  78.  
  79. private String name(Deque<Integer> stack) {
  80. return stack == help1 ? "help1" :
  81. stack == help2 ? "help2" :
  82. "main";
  83. }
  84.  
  85. private String state() {
  86. return "main: " + main +
  87. "\nhelp1: " + help1 +
  88. "\nhelp2: " + help2;
  89. }
  90.  
  91. private void ensureMain(Deque<Integer> stack) {
  92. if (stack != main) {
  93. throw new IllegalArgumentException("Expected main, got " + name(stack) + "\n" + state());
  94. }
  95. }
  96.  
  97. private void ensureHelp(Deque<Integer> stack) {
  98. if (stack == main) {
  99. throw new IllegalArgumentException("Expected help, got main\n" + state());
  100. }
  101. }
  102.  
  103. private void ensureHelpers(Deque<Integer> stack1, Deque<Integer> stack2) {
  104. ensureHelp(stack1);
  105. ensureHelp(stack2);
  106. }
  107.  
  108. private void sortMain() {
  109. int height = main.size();
  110. int topIndex = height;
  111. while (topIndex == height && height > 1) {
  112. topIndex = lastIndexOfLargest(height, main);
  113. height--;
  114. }
  115. if (topIndex == height) {
  116. // is already sorted
  117. return;
  118. }
  119. // split stack at largest element
  120. int part1Count = topIndex;
  121. int part2Count = height - topIndex;
  122. // move largest and first part to help 1
  123. moveFromMain(part1Count+1, help1, help2);
  124. // merge both parts to help 2, leaving largest on 1
  125. mergeToHelp(part2Count, main, part1Count, help1, help2);
  126. // move largest to main
  127. move(help1, main);
  128. // move remaining to main
  129. moveToMain(height, help2, help1);
  130. }
  131.  
  132. /** Moves elements from main to helper, sorting them */
  133. private void moveFromMain(int amount, Deque<Integer> target, Deque<Integer> help) {
  134. if (amount < 1) return;
  135. ensureHelpers(target, help);
  136. int topIndex = lastIndexOfLargest(amount, main);
  137. int part1Count = topIndex;
  138. int part2Count = amount - topIndex - 1;
  139. // move first part to help
  140. moveFromMain(part1Count, help, target);
  141. // move largest to target
  142. move(main, target);
  143. // merge both parts to target
  144. mergeToHelp(part2Count, main, part1Count, help, target);
  145. }
  146.  
  147. /** Moves elements from helper to main, keeping them sorted */
  148. private void moveToMain(int amount, Deque<Integer> source, Deque<Integer> help) {
  149. if (amount < 1) return;
  150. ensureHelpers(source, help);
  151. moveHelper(amount-1, source, help);
  152. move(source, main);
  153. moveToMain(amount-1, help, source);
  154. }
  155.  
  156. /** Moves elements between helpers */
  157. private void moveHelper(int amount, Deque<Integer> source, Deque<Integer> target) {
  158. pushToMain(amount, source);
  159. popFromMain(amount, target);
  160. }
  161.  
  162. /** Merges top of main and helper to other helper */
  163. private void mergeToHelp(int mainAmount, Deque<Integer> main, int helpAmount, Deque<Integer> help, Deque<Integer> target) {
  164. ensureMain(main);
  165. ensureHelpers(help, target);
  166. if (mainAmount < 0) mainAmount = 0;
  167. if (helpAmount < 0) helpAmount = 0;
  168. while (mainAmount > 0 || helpAmount > 0) {
  169. // while there is something to merge
  170. int largestMain = valueOfLargest(mainAmount, main);
  171. int largestHelp = valueOfLargest(helpAmount, help);
  172. if (largestMain > largestHelp) {
  173. // largest is in main
  174. int index = firstIndexOfLargest(mainAmount, main);
  175. if (index > 0) {
  176. // move excess to help:
  177. int mainTop = index;
  178. int helpTop = elementsSmallerThan(help, largestMain);
  179. if (helpTop > 0) {
  180. // 1. move top of help to target
  181. moveHelper(helpTop, help, target);
  182. // 2. merge old top with excess from main
  183. mergeToHelp(mainTop, main, helpTop, target, help);
  184. } else {
  185. moveFromMain(mainTop, help, target);
  186. }
  187. mainAmount -= mainTop;
  188. helpAmount += mainTop;
  189. }
  190. move(main, target);
  191. mainAmount--;
  192. } else {
  193. // largest is at bottom of help
  194. int helpTop = helpAmount - 1; // largest is at bottom
  195. // move top to main
  196. pushToMain(helpTop, help);
  197. mainAmount += helpTop;
  198. // move largest to target
  199. move(help, target);
  200. helpAmount = 0;
  201. }
  202. }
  203. }
  204.  
  205. private void pushToMain(int amount, Deque<Integer> from) {
  206. for (; amount > 0; amount--) move(from, main);
  207. }
  208.  
  209. private void popFromMain(int amount, Deque<Integer> to) {
  210. for (; amount > 0; amount--) move(main, to);
  211. }
  212.  
  213. private int firstIndexOfLargest(int height, Deque<Integer> stack) {
  214. if (height == 0) throw new IllegalArgumentException("height == 0");
  215. int topValue = 0;
  216. int topIndex = 0;
  217. int i = 0;
  218. for (Integer e: stack) {
  219. if (e > topValue) {
  220. topValue = e;
  221. topIndex = i;
  222. }
  223. if (++i == height) break;
  224. }
  225. return topIndex;
  226. }
  227.  
  228. private int lastIndexOfLargest(int height, Deque<Integer> stack) {
  229. if (height == 0) throw new IllegalArgumentException("height == 0");
  230. int topValue = 0;
  231. int topIndex = 0;
  232. int i = 0;
  233. for (Integer e: stack) {
  234. if (e >= topValue) {
  235. topValue = e;
  236. topIndex = i;
  237. }
  238. if (++i == height) break;
  239. }
  240. return topIndex;
  241. }
  242.  
  243. private int valueOfLargest(int height, Deque<Integer> stack) {
  244. int v = Integer.MIN_VALUE;
  245. for (Integer e: stack) {
  246. if (height-- == 0) break;
  247. if (e > v) v = e;
  248. }
  249. return v;
  250. }
  251.  
  252. private int elementsSmallerThan(Deque<Integer> stack, int value) {
  253. int i = 0;
  254. for (Integer e: stack) {
  255. if (e >= value) return i;
  256. i++;
  257. }
  258. return i;
  259. }
  260. }
  261.  
Success #stdin #stdout 0.32s 380160KB
stdin
Standard input is empty
stdout
2083142/55986