import java.util.*;

class NumberMaze {

  public static void main(String[] args) {
    int n = (int) 1e9;
    int m = (int) 1e9 - 5;
    System.out.println("> Initial timings:");
    timedSearch(n);
    timedSearch(m);
    for (int i=0; i<1000; i++) findPath(n); // warmup
    System.out.println("> Timings after warmup:");
    timedSearch(n);
    timedSearch(m);
  }

  public static void timedSearch(int n) {
    long start = System.nanoTime();
    ArrayDeque<Integer> path = findPath(n);
    long end = System.nanoTime();
    double total = (end - start) * 1e-6;
    System.out.printf("Path from %d to 1:%n%s%n", n, path);
    System.out.printf("Path length was %d%n", path.size());
    System.out.printf("Total time was about %.3fms.%n", total);
  }

  public static ArrayDeque<Integer> findPath(int n) {
    Map<Integer, Integer> seen = new HashMap<>();
    List<Integer> active = Arrays.asList(n);
    seen.put(n, n);
    int pathLength = 0;
    // Find the path
    while (!seen.containsKey(1)) {
      List<Integer> newActive = new ArrayList<>(active.size()*3);
      for (int x : active) {
        if (x % 3 == 0 && !seen.containsKey(x/3)) {
          newActive.add(x/3);
          seen.put(x/3, x);
        }
        if (x % 2 == 0 && !seen.containsKey(x/2)) {
          newActive.add(x/2);
          seen.put(x/2, x);
        }
        if (!seen.containsKey(x-1)) {
          newActive.add(x-1);
          seen.put(x-1, x);
        }
        active = newActive;
      }
    }
    // Reconstruct the path
    ArrayDeque<Integer> path = new ArrayDeque<>(pathLength);
    int x = 1;
    int y = seen.get(x);
    while (x != y) {
      path.push(y / x);
      x = y;
      y = seen.get(x);
    }
    return path;
  }

}