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