fork(10) download
copy 
  1. //import static Main.*;
  2. import java.util.ArrayList;
  3. import java.util.Scanner;
  4.  
  5. public class Main {
  6.  
  7.     public static final int R = 1;
  8.     public static final int L = -1;
  9.     public static final int U = -4;
  10.     public static final int D = 4;
  11.     public static final int[] mov = new int[] {R,L,U,D};
  12.  
  13.     public static ArrayList<Maze> mazes = new ArrayList<>();
  14.  
  15.     public static void main(String[] args) {
  16.         generateMazes("0");
  17.         String sequence = "RRDRRDRLDRDLDLULLLDDRDDDURDRRDR";
  18.         // execSequence(sequence);
  19.         // int r = remaining(); // 0 if above sequence solves all mazes
  20.  
  21.         boolean isSolution = isSolution(sequence); // true if sequence solves all mazes
  22.  
  23.         System.out.println((isSolution ? "Sequence solves all " : "Sequence doesn't solve all ") + "mazes");
  24.  
  25.         // manualGame();
  26.     }
  27.  
  28.     public static boolean isSolution(String s) {
  29.         return mazes.size() - numberSolved(s) == 0;
  30.     }
  31.  
  32.     public static int numberSolved(String s) {
  33.         int sum = numberSolvedHard(s);
  34.  
  35.         for (Maze maze : mazes) {
  36.             maze.pos = 0;
  37.             maze.isAlive = true;
  38.         }
  39.  
  40.         return sum;
  41.     }
  42.  
  43.     public static int numberSolvedHard(String s) {
  44.         int sum = 0;
  45.         for (char c : s.toCharArray()) {
  46.             for (Maze maze : mazes) {
  47.                 if (!maze.isAlive) continue;
  48.  
  49.                 switch(c) {
  50.                     case 'R': maze.move(R);
  51.                         break;
  52.                     case 'L': maze.move(L);
  53.                         break;
  54.                     case 'U': maze.move(U);
  55.                         break;
  56.                     case 'D': maze.move(D);
  57.                         break;
  58.                 }
  59.  
  60.                 if (!maze.isAlive) {
  61.                     sum++;
  62.                 }
  63.  
  64.             }
  65.         }
  66.  
  67.         return sum;
  68.     }
  69.  
  70.     public static ArrayList<String> perms = new ArrayList<>();
  71.     public static ArrayList<String> invrs = new ArrayList<>();
  72.  
  73.     public static void doPerms(ArrayList<String> cont, String seq, String move) {
  74.         if (seq.length() >= 10)
  75.             return;
  76.  
  77.         if (seq.length() >= 8)
  78.             cont.add(seq + move);        
  79.  
  80.         seq += move;
  81.  
  82.         if (cont == perms) {
  83.             doPerms(cont, seq, "R");
  84.             doPerms(cont, seq, "D");
  85.             doPerms(cont, seq, "L");            
  86.             doPerms(cont, seq, "U");
  87.         } else {            
  88.             doPerms(cont, seq, "D");
  89.             doPerms(cont, seq, "R");
  90.             doPerms(cont, seq, "U");
  91.             doPerms(cont, seq, "L");
  92.         }
  93.     }
  94.  
  95.     public static void execSequence(String seq) {
  96.         for (char c : seq.toCharArray()) {
  97.             for (Maze maze : mazes) {
  98.                 switch(c) {
  99.                     case 'R': maze.move(R);
  100.                         break;
  101.                     case 'L': maze.move(L);
  102.                         break;
  103.                     case 'U': maze.move(U);
  104.                         break;
  105.                     case 'D': maze.move(D);
  106.                         break;
  107.                 }
  108.             }
  109.         }
  110.     }
  111.  
  112.     public static int remainingNotAtGoal(int goal) {
  113.         int tot = remaining();
  114.         for (Maze maze : mazes) {
  115.             if (maze.isAlive) {
  116.                 if (maze.pos == goal) tot--;
  117.             }
  118.         }
  119.         return tot;
  120.     }
  121.  
  122.     public static int remaining() {
  123.         int tot = mazes.size();
  124.         for (Maze maze : mazes) {
  125.             if (!maze.isAlive) tot--;
  126.         }
  127.         return tot;
  128.     }
  129.  
  130.     public static void manualGame() {
  131.         int r = remaining();
  132.  
  133.         String seq = "";
  134.         Scanner sc = new Scanner(System.in);
  135.         while (r > 0) {
  136.             System.out.println("Sequence: " + seq + " Length: " + seq.length());
  137.             System.out.println("---------------------");
  138.             System.out.println("Removed: " + (mazes.size() - r));
  139.             System.out.println("Remaining: " + r);
  140.  
  141.             int _a = 0;
  142.             int[] a = new int[16];
  143.             int[] p = new int[16];
  144.             int[] d = new int[16];
  145.             for (Maze maze : mazes) {
  146.                 if (!maze.isAlive) continue;
  147.  
  148.                 for (int i = 0; i < 16; i++) {
  149.                     a[i] += maze.layout[i];
  150.                     d[i] += maze.distances[i] == 255 ? 0 : maze.distances[i];
  151.                     _a += a[i];
  152.                 }
  153.  
  154.                 p[maze.pos]++;
  155.             }
  156.  
  157.             System.out.println("");
  158.             System.out.printf("%-36s", "    | Obstacles");
  159.             System.out.printf(" | Current positions\n");
  160.             for (int i = 0; i < 4; i++) {
  161.                 System.out.print("    |    ");
  162.                 for (int j = 0; j < 4; j++) {
  163.                     System.out.printf("%4d", a[i*4 + j]);
  164.                     System.out.print("  ");
  165.                 }
  166.                 System.out.print("    |    ");
  167.                 for (int j = 0; j < 4; j++) {
  168.                     System.out.printf("%4d", p[i*4 + j]);
  169.                     System.out.print("  ");
  170.                 }
  171.                 System.out.print("    |    ");
  172.                 for (int j = 0; j < 4; j++) {
  173.                     System.out.printf("%4d", d[i*4 + j]);
  174.                     System.out.print("  ");
  175.                 }
  176.                 System.out.println();
  177.             }
  178.             System.out.println();
  179.             System.out.print("Command: ");
  180.             String cmd = sc.nextLine();
  181.             seq += cmd.toUpperCase();
  182.  
  183.             for (Maze maze : mazes) {
  184.                 if (!maze.isAlive) continue;
  185.  
  186.                 if (cmd.equals("d"))
  187.                     maze.move(R);
  188.                 if (cmd.equals("a"))
  189.                     maze.move(L);
  190.                 if (cmd.equals("w"))
  191.                     maze.move(U);
  192.                 if (cmd.equals("s"))
  193.                     maze.move(D);
  194.                 if (cmd.equals("p")) {
  195.                     for (Maze m : mazes) {
  196.                         if (m.isAlive)
  197.                             m.printc();
  198.                     }
  199.                 }
  200.             }
  201.             r = remaining();
  202.         }
  203.     }
  204.  
  205.     public static void generateMazes(String layout) {
  206.         if (layout.length() == 16) {
  207.             if (layout.charAt(15) == '1') return;
  208.  
  209.             int[] a = new int[16];
  210.             for (int i = 0; i < 16; i++) a[i] = Character.digit(layout.charAt(i), 10);
  211.             if (solutionExists(a, 15)) mazes.add(new Maze(a));
  212.             return;
  213.         }
  214.  
  215.         generateMazes(layout+'1');
  216.         generateMazes(layout+'0');
  217.     }
  218.  
  219.     public static boolean solutionExists(int[] a, int k) {
  220.         if (a[0] == 2) return true;
  221.         if (a[k] == 2) return false;
  222.  
  223.         for (int m : mov) {
  224.             if (canMove(a, k, m)) {
  225.                 a[k] = 2;
  226.                 boolean f = solutionExists(a, k+m);
  227.                 a[k] = 0;
  228.                 if (f) return true;
  229.             }
  230.         }
  231.  
  232.         return false;
  233.     }
  234.  
  235.     public static boolean canMove(int[] a, int pos, int dir) {
  236.         int npos = pos + dir;
  237.         if (npos < 0 || npos >= 16) return false;
  238.         if (a[npos] == 1) return false;
  239.         if (dir == 1 && pos % 4 == 3) return false;
  240.         if (dir == -1 && pos % 4 == 0) return false;
  241.         return Math.abs((npos - pos) % 4) <= 1;
  242.     }
  243.  
  244.     public static int[] cpy(int[] arr) {
  245.         int[] a = new int[arr.length];
  246.         System.arraycopy(arr, 0, a, 0, a.length);
  247.         return a;
  248.     }
  249.  
  250. }
  251.  
  252. class Maze {
  253.  
  254.     public final int[] layout;
  255.  
  256.     public int[] distances;
  257.     public int pos;
  258.     public boolean isAlive;
  259.     public boolean softIsAlive;
  260.  
  261.     public Maze(int[] layout) {
  262.         this.layout = layout;
  263.         this.pos = 0;
  264.         this.isAlive = true;
  265.     }
  266.  
  267.     public int getDistance() {
  268.         return distances[pos];
  269.     }
  270.  
  271.     public int getDistance(int dir) {
  272.         if (!Main.canMove(layout, pos, dir)) return getDistance();
  273.         return distances[pos+dir];
  274.     }
  275.  
  276.     public void move(int dir) {
  277.         int npos = pos + dir;
  278.         if (npos < 0 || npos >= 16) return;
  279.         if (layout[npos] == 1) return;
  280.         if (dir == 1 && pos % 4 == 3) return;
  281.         if (dir == -1 && pos % 4 == 0) return;
  282.         if (Math.abs((npos - pos) % 4) > 1) return;
  283.  
  284.         pos = npos;
  285.         if (pos == 15) this.isAlive = false;
  286.     }
  287.  
  288.     public void print() {
  289.         for (int i = 0; i < 4; i++) {
  290.             for (int j = 0; j < 4; j++)
  291.                 System.out.printf("%-2s", i*4 + j == pos ? "x" : layout[i*4 + j]);
  292.             System.out.println();
  293.         }
  294.         System.out.println();
  295.     }
  296.     public void printd() {
  297.         for (int i = 0; i < 4; i++) {
  298.             for (int j = 0; j < 4; j++)
  299.                 System.out.printf("%-2s", distances[i*4 + j]);
  300.             System.out.println();
  301.         }
  302.         System.out.println();
  303.     }
  304.  
  305.     public void printc() {
  306.         for (int i = 0; i < 16; i++)
  307.             System.out.print(layout[i]);
  308.         System.out.println();
  309.     }
  310. }
Success #stdin #stdout 0.13s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sequence solves all mazes
https://ideone.com/E6eKpL
language:
Java (HotSpot 12)
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!