fork(1) download
copy 
  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.             throw new IllegalStateException(
  74.                     from + " " + i + " -> " + to);
  75.         }
  76.         to.push(i);
  77.         opCount++;
  78.     }
  79.  
  80.     private String name(Deque<Integer> stack) {
  81.         return stack == help1 ? "help1" :
  82.                stack == help2 ? "help2" :
  83.                "main";
  84.     }
  85.  
  86.     private String state() {
  87.         return "main:  " + main + 
  88.                 "\nhelp1: " + help1 +
  89.                 "\nhelp2: " + help2;
  90.     }
  91.  
  92.     private void ensureMain(Deque<Integer> stack) {
  93.         if (stack != main) {
  94.             throw new IllegalArgumentException("Expected main, got " + name(stack) + "\n" + state());
  95.         }
  96.     }
  97.  
  98.     private void ensureHelp(Deque<Integer> stack) {
  99.         if (stack == main) {
  100.             throw new IllegalArgumentException("Expected help, got main\n" + state());
  101.         }
  102.     }
  103.  
  104.     private void ensureHelpers(Deque<Integer> stack1, Deque<Integer> stack2) {
  105.         ensureHelp(stack1);
  106.         ensureHelp(stack2);
  107.     }
  108.  
  109.     private void sortMain() {
  110.         int height = main.size();
  111.         int topIndex = height;
  112.         while (topIndex == height && height > 1) {
  113.             topIndex = lastIndexOfLargest(height, main);
  114.             height--;
  115.         }
  116.         if (topIndex == height) { 
  117.             // is already sorted
  118.             return;
  119.         }
  120.         // split stack at largest element
  121.         int part1Count = topIndex;
  122.         int part2Count = height - topIndex;
  123.         // move largest and first part to help 1
  124.         moveFromMain(part1Count+1, help1, help2);
  125.         // merge both parts to help 2, leaving largest on 1
  126.         mergeToHelp(part2Count, main, part1Count, help1, help2);
  127.         // move largest to main
  128.         move(help1, main);
  129.         // move remaining to main
  130.         moveToMain(height, help2, help1);
  131.     }
  132.  
  133.     /** Moves elements from main to helper, sorting them */
  134.     private void moveFromMain(int amount, Deque<Integer> target, Deque<Integer> help) {
  135.         if (amount < 1) return;
  136.         ensureHelpers(target, help);
  137.         int topIndex = lastIndexOfLargest(amount, main);
  138.         int part1Count = topIndex;
  139.         int part2Count = amount - topIndex - 1;
  140.         // move first part to help
  141.         moveFromMain(part1Count, help, target);
  142.         // move largest to target
  143.         move(main, target);
  144.         // merge both parts to target
  145.         mergeToHelp(part2Count, main, part1Count, help, target);
  146.     }
  147.  
  148.     /** Moves elements from helper to main, keeping them sorted */
  149.     private void moveToMain(int amount, Deque<Integer> source, Deque<Integer> help) {
  150.         if (amount < 1) return;
  151.         ensureHelpers(source, help);
  152.         moveHelper(amount-1, source, help);
  153.         move(source, main);
  154.         moveToMain(amount-1, help, source);
  155.     }
  156.  
  157.     /** Moves elements between helpers */
  158.     private void moveHelper(int amount, Deque<Integer> source, Deque<Integer> target) {
  159.         pushToMain(amount, source);
  160.         popFromMain(amount, target);
  161.     }
  162.  
  163.     /** Merges top of main and helper to other helper */
  164.     private void mergeToHelp(int mainAmount, Deque<Integer> main, int helpAmount, Deque<Integer> help, Deque<Integer> target) {
  165.         ensureMain(main);
  166.         ensureHelpers(help, target);
  167.         if (mainAmount < 0) mainAmount = 0;
  168.         if (helpAmount < 0) helpAmount = 0;
  169.         while (mainAmount > 0 || helpAmount > 0) {
  170.             // while there is something to merge
  171.             int largestMain = valueOfLargest(mainAmount, main);
  172.             int largestHelp = valueOfLargest(helpAmount, help);
  173.             if (largestMain > largestHelp) {
  174.                 // largest is in main
  175.                 int index = firstIndexOfLargest(mainAmount, main);
  176.                 if (index > 0) {
  177.                     // move excess to help:
  178.                     int mainTop = index;
  179.                     int helpTop = elementsSmallerThan(help, largestMain);
  180.                     if (helpTop > 0) {
  181.                         // 1. move top of help to target
  182.                         moveHelper(helpTop, help, target);
  183.                         // 2. merge old top with excess from main
  184.                         mergeToHelp(mainTop, main, helpTop, target, help);
  185.                     } else {
  186.                         moveFromMain(mainTop, help, target);
  187.                     }
  188.                     mainAmount -= mainTop;
  189.                     helpAmount += mainTop;
  190.                 }
  191.                 move(main, target);
  192.                 mainAmount--;
  193.             } else {
  194.                 // largest is at bottom of help
  195.                 int helpTop = helpAmount - 1; // largest is at bottom
  196.                 // move top to main
  197.                 pushToMain(helpTop, help);
  198.                 mainAmount += helpTop;
  199.                 // move largest to target
  200.                 move(help, target);
  201.                 helpAmount = 0;
  202.             }
  203.         }
  204.     }
  205.  
  206.     private void pushToMain(int amount, Deque<Integer> from) {
  207.         for (; amount > 0; amount--) move(from, main);
  208.     }
  209.  
  210.     private void popFromMain(int amount, Deque<Integer> to) {
  211.         for (; amount > 0; amount--) move(main, to);
  212.     }
  213.  
  214.     private int firstIndexOfLargest(int height, Deque<Integer> stack) {
  215.         if (height == 0) throw new IllegalArgumentException("height == 0");
  216.         int topValue = 0;
  217.         int topIndex = 0;
  218.         int i = 0;
  219.         for (Integer e: stack) {
  220.             if (e > topValue) {
  221.                 topValue = e;
  222.                 topIndex = i;
  223.             }
  224.             if (++i == height) break;
  225.         }
  226.         return topIndex;
  227.     }
  228.  
  229.     private int lastIndexOfLargest(int height, Deque<Integer> stack) {
  230.         if (height == 0) throw new IllegalArgumentException("height == 0");
  231.         int topValue = 0;
  232.         int topIndex = 0;
  233.         int i = 0;
  234.         for (Integer e: stack) {
  235.             if (e >= topValue) {
  236.                 topValue = e;
  237.                 topIndex = i;
  238.             }
  239.             if (++i == height) break;
  240.         }
  241.         return topIndex;
  242.     }
  243.  
  244.     private int valueOfLargest(int height, Deque<Integer> stack) {
  245.         int v = Integer.MIN_VALUE;
  246.         for (Integer e: stack) {
  247.             if (height-- == 0) break;
  248.             if (e > v) v = e;
  249.         }
  250.         return v;
  251.     }
  252.  
  253.     private int elementsSmallerThan(Deque<Integer> stack, int value) {
  254.         int i = 0;
  255.         for (Integer e: stack) {
  256.             if (e >= value) return i;
  257.             i++;
  258.         }
  259.         return i;
  260.     }
  261. }
  262.  
Success #stdin #stdout 0.32s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2083142/55986
https://ideone.com/EA0zNg
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!