fork(3) download
copy 
  1. import java.util.*;
  2.  
  3. class NumberMaze {
  4.  
  5.   public static void main(String[] args) {
  6.     int n = (int) 1e9;
  7.     int m = (int) 1e9 - 5;
  8.     System.out.println("> Initial timings:");
  9.     timedSearch(n);
  10.     timedSearch(m);
  11.     for (int i=0; i<1000; i++) findPath(n); // warmup
  12.     System.out.println("> Timings after warmup:");
  13.     timedSearch(n);
  14.     timedSearch(m);
  15.   }
  16.  
  17.   public static void timedSearch(int n) {
  18.     long start = System.nanoTime();
  19.     ArrayDeque<Integer> path = findPath(n);
  20.     long end = System.nanoTime();
  21.     double total = (end - start) * 1e-6;
  22.     System.out.printf("Path from %d to 1:%n%s%n", n, path);
  23.     System.out.printf("Path length was %d%n", path.size());
  24.     System.out.printf("Total time was about %.3fms.%n", total);
  25.   }
  26.  
  27.   public static ArrayDeque<Integer> findPath(int n) {
  28.     Map<Integer, Integer> seen = new HashMap<>();
  29.     List<Integer> active = Arrays.asList(n);
  30.     seen.put(n, n);
  31.     int pathLength = 0;
  32.     // Find the path
  33.     while (!seen.containsKey(1)) {
  34.       List<Integer> newActive = new ArrayList<>(active.size()*3);
  35.       for (int x : active) {
  36.         if (x % 3 == 0 && !seen.containsKey(x/3)) {
  37.           newActive.add(x/3);
  38.           seen.put(x/3, x);
  39.         }
  40.         if (x % 2 == 0 && !seen.containsKey(x/2)) {
  41.           newActive.add(x/2);
  42.           seen.put(x/2, x);
  43.         }
  44.         if (!seen.containsKey(x-1)) {
  45.           newActive.add(x-1);
  46.           seen.put(x-1, x);
  47.         }
  48.         active = newActive;
  49.       }
  50.     }
  51.     // Reconstruct the path
  52.     ArrayDeque<Integer> path = new ArrayDeque<>(pathLength);
  53.     int x = 1;
  54.     int y = seen.get(x);
  55.     while (x != y) {
  56.       path.push(y / x);
  57.       x = y;
  58.       y = seen.get(x);
  59.     }
  60.     return path;
  61.   }
  62.  
  63. }
  64.  
Success #stdin #stdout 0.92s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
> Initial timings:
Path from 1000000000 to 1:
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
Path length was 30
Total time was about 12.855ms.
Path from 999999995 to 1:
[1, 2, 1, 2, 2, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 3, 2, 2, 1, 3, 3, 2, 1, 1, 3, 3, 3, 3, 1, 1, 3, 3]
Path length was 34
Total time was about 4.643ms.
> Timings after warmup:
Path from 1000000000 to 1:
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
Path length was 30
Total time was about 0.762ms.
Path from 999999995 to 1:
[1, 2, 1, 2, 2, 1, 3, 2, 1, 3, 2, 2, 1, 1, 3, 3, 1, 3, 2, 2, 1, 3, 3, 2, 1, 1, 3, 3, 3, 3, 1, 1, 3, 3]
Path length was 34
Total time was about 0.767ms.
https://ideone.com/qWt0LE
language:
Java (12.0.1)
created:
11 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!