Guest User

SO robot

a guest
Nov 13th, 2014
406
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package robotti2;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Scanner;
  5. import static robotti2.Robotti2.*;
  6.  
  7. class Maze {
  8.    
  9.     public final int[] layout;
  10.     public final int[] distances;
  11.     public int pos;
  12.     public boolean isAlive;
  13.    
  14.     public Maze(int[] layout) {
  15.         this.layout = layout;
  16.         this.distances = createDistanceMatrix();
  17.         this.pos = 0;
  18.         this.isAlive = true;
  19.     }
  20.    
  21.     public int getDistance() {
  22.         return distances[pos];
  23.     }
  24.    
  25.     public int getDistance(int dir) {
  26.         if (!canMove(layout, pos, dir)) return getDistance();
  27.         return distances[pos+dir];
  28.     }
  29.    
  30.     private int[] createDistanceMatrix() {
  31.         int a[] = new int[16];
  32.         for (int i = 0; i < 16; i++)
  33.             a[i] = (layout[i] == 1) ? 255 : 99;
  34.        
  35.         a[15] = 0;
  36.        
  37.         boolean f;
  38.         do {
  39.            
  40.             f = false;
  41.            
  42.             for (int i = 0; i < 16; i++) {            
  43.                 if (a[i] < 255) {
  44.                
  45.                     int min = a[i];
  46.                    
  47.                     for (int m : mov) {
  48. //                        if (i+m < 0 || i+m >= 16 || a[i+m] == -1) continue;
  49.  
  50.                         if (canMove(layout, i, m) && a[i+m] < min)
  51.                             min = a[i+m];
  52.  
  53.                     }
  54.                    
  55.                     if (a[i] > min + 1) {
  56.                         a[i] = min + 1;
  57.                         f = true;
  58.                     }
  59.                    
  60.                 }                
  61.             }
  62.            
  63.         } while (f);
  64.        
  65.         return a;
  66.     }
  67.    
  68.     public void move(int dir) {
  69.         int npos = pos + dir;
  70.         if (npos < 0 || npos >= 16) return;
  71.         if (layout[npos] == 1) return;
  72.         if (dir == 1 && pos % 4 == 3) return;
  73.         if (dir == -1 && pos % 4 == 0) return;
  74.         if (Math.abs((npos - pos) % 4) > 1) return;
  75.        
  76.         pos = npos;
  77.         if (pos == 15) this.isAlive = false;
  78.     }
  79.    
  80.     public void print() {
  81.         for (int i = 0; i < 4; i++) {
  82.             for (int j = 0; j < 4; j++)
  83.                 System.out.printf("%-2s", i*4 + j == pos ? "x" : layout[i*4 + j]);
  84.             System.out.println();
  85.         }
  86.         System.out.println();
  87.     }
  88. }
  89.  
  90. public class Robotti2 {
  91.    
  92.     public static final int R = 1;
  93.     public static final int L = -1;
  94.     public static final int U = -4;
  95.     public static final int D = 4;
  96.     public static final int[] mov = new int[] {R,L,U,D};
  97.  
  98.     public static ArrayList<Maze> mazes = new ArrayList<>();
  99.    
  100.     public static boolean isSolution(String s) {
  101.         int remaining = mazes.size();
  102.        
  103.         for (char c : s.toCharArray()) {
  104.             for (Maze maze : mazes) {
  105.                 if (!maze.isAlive) continue;
  106.                
  107.                 if (c == 'R')
  108.                     maze.move(R);
  109.                 if (c == 'L')
  110.                     maze.move(L);
  111.                 if (c == 'U')
  112.                     maze.move(U);
  113.                 if (c == 'D')
  114.                     maze.move(D);
  115.                
  116.                 if (!maze.isAlive) {
  117.                     remaining--;
  118.                 }
  119.                
  120.             }
  121.         }
  122.        
  123.         for (Maze maze : mazes) maze.isAlive = true;
  124.        
  125.         System.out.println(remaining);
  126.         return remaining == 0;
  127.     }
  128.    
  129.     public static void main(String[] args) {
  130.         generateMazes("0");
  131.         handGame();
  132.     }
  133.    
  134.     public static void handGame() {
  135.         int remaining = mazes.size();
  136.        
  137.         String seq = "";
  138.         Scanner sc = new Scanner(System.in);
  139.         while (remaining > 0) {
  140.             System.out.println("Sequence: " + seq + " Length: " + seq.length());
  141.             System.out.println("---------------------");
  142.             System.out.println("Removed: " + remaining);
  143.             System.out.println("Remaining: " + remaining);
  144.            
  145.             int _a = 0;
  146.             int[] a = new int[16];
  147.             int[] p = new int[16];
  148.             for (Maze maze : mazes) {
  149.                 if (!maze.isAlive) continue;
  150.                
  151.                 for (int i = 0; i < 16; i++) {
  152.                     a[i] += maze.layout[i];
  153.                     _a += a[i];
  154.                 }
  155.                
  156.                 p[maze.pos]++;
  157.             }
  158.            
  159.             System.out.println("");
  160.             System.out.printf("%-36s", "    | Obstacles");
  161.             System.out.printf(" | Current positions\n");
  162.             for (int i = 0; i < 4; i++) {
  163.                 System.out.print("    |    ");
  164.                 for (int j = 0; j < 4; j++) {
  165.                     System.out.printf("%4d", a[i*4 + j]);
  166.                     System.out.print("  ");
  167.                 }
  168.                 System.out.print("    |    ");
  169.                 for (int j = 0; j < 4; j++) {
  170.                     System.out.printf("%4d", p[i*4 + j]);
  171.                     System.out.print("  ");
  172.                 }
  173.                 System.out.println();
  174.             }
  175.             System.out.println();
  176.             System.out.print("Command: ");
  177.             String cmd = sc.nextLine();
  178.             seq += cmd.toUpperCase();
  179.            
  180.             for (Maze maze : mazes) {
  181.                 if (!maze.isAlive) continue;
  182.                
  183.                 if (cmd.equals("d"))
  184.                     maze.move(R);
  185.                 if (cmd.equals("a"))
  186.                     maze.move(L);
  187.                 if (cmd.equals("w"))
  188.                     maze.move(U);
  189.                 if (cmd.equals("s"))
  190.                     maze.move(D);
  191.                
  192.                 if (!maze.isAlive) {
  193.                     remaining--;
  194.                 }
  195.                
  196.             }
  197.         }
  198.     }
  199.    
  200.     public static void generateMazes(String layout) {
  201.         if (layout.length() == 16) {
  202.             if (layout.charAt(15) == '1') return;
  203.            
  204.             int[] a = new int[16];
  205.             for (int i = 0; i < 16; i++) a[i] = Character.digit(layout.charAt(i), 10);
  206.             if (solutionExists(a, 15)) mazes.add(new Maze(a));
  207.             return;
  208.         }
  209.        
  210.         generateMazes(layout+'1');
  211.         generateMazes(layout+'0');
  212.     }
  213.    
  214.     public static boolean solutionExists(int[] a, int k) {
  215.         if (a[0] == 2) return true;
  216.         if (a[k] == 2) return false;
  217.        
  218.         for (int m : mov) {
  219.             if (canMove(a, k, m)) {
  220.                 a[k] = 2;
  221.                 boolean f = solutionExists(a, k+m);
  222.                 a[k] = 0;
  223.                 if (f) return true;
  224.             }
  225.         }
  226.        
  227.         return false;
  228.     }
  229.    
  230.     public static boolean canMove(int[] a, int pos, int dir) {
  231.         int npos = pos + dir;
  232.         if (npos < 0 || npos >= 16) return false;
  233.         if (a[npos] == 1) return false;
  234.         if (dir == 1 && pos % 4 == 3) return false;
  235.         if (dir == -1 && pos % 4 == 0) return false;
  236.         return Math.abs((npos - pos) % 4) <= 1;
  237.     }
  238.    
  239.     public static int[] cpy(int[] arr) {
  240.         int[] a = new int[arr.length];
  241.         System.arraycopy(arr, 0, a, 0, a.length);
  242.         return a;
  243.     }
  244.    
  245. }
RAW Paste Data