NEERC/garbling/garbling_re_slow.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 /**
   5  * This solutions simulates the game until the whole map state loops.
   6  * then it figures out repeating part.
   7  *
   8  * @author Roman Elizarov
   9  */
  10 public class garbling_re_slow {
  11         private static final boolean FULL_SIMULATION = false; // VERY SLOW MODE
  12
  13         static class Field implements Cloneable {
  14                 int[][] a;
  15
  16                 Field(int r, int c) {
  17                         a = new int[r][c];
  18                         int n = 0;
  19                         for (int i = 0; i < r; i++) {
  20                             for (int j = 0; j < c; j++) {
  21                                 a[i][j] = ++n;
  22                             }
  23                         }
  24                 }
  25
  26                 void garbleLeft(int i, int j) {
  27                         int t = a[i][j];
  28                         a[i][j] = a[i][j + 1];
  29                         a[i][j + 1] = a[i + 1][j + 1];
  30                         a[i + 1][j + 1] = a[i + 1][j];
  31                         a[i + 1][j] = t;
  32                 }
  33
  34                 void garbleRight(int i, int j) {
  35                         int t = a[i][j];
  36                         a[i][j] = a[i + 1][j];
  37                         a[i + 1][j] = a[i + 1][j + 1];
  38                         a[i + 1][j + 1] = a[i][j + 1];
  39                         a[i][j + 1] = t;
  40                 }
  41
  42                 @Override
  43                 public Field clone()  {
  44                         try {
  45                                 Field f = (Field)super.clone();
  46                                 f.a = f.a.clone();
  47                                 for (int i = 0; i < f.a.length; i++) {
  48                                     f.a[i] = f.a[i].clone();
  49                                 }
  50                                 return f;
  51                         } catch (CloneNotSupportedException e) {
  52                             throw new AssertionError(e);
  53                         }
  54                 }
  55
  56                 @Override
  57                 public boolean equals(Object obj) {
  58                         if (!(obj instanceof Field))
  59                                 return false;
  60                         int[][] b = ((Field)obj).a;
  61                         for (int i = 0; i < a.length; i++) {
  62                                 if (!Arrays.equals(a[i], b[i]))
  63                                         return false;
  64                         }
  65                         return true;
  66                 }
  67
  68                 @Override
  69                 public int hashCode() {
  70                         int result = 0;
  71                         for (int[] row : a) {
  72                                 result = result * 997 + Arrays.hashCode(row);
  73                         }
  74                         return result;
  75                 }
  76         }
  77
  78         static class State implements Cloneable {
  79                 long turns;
  80                 long[] written;
  81
  82                 State(int rc) {
  83                         written = new long[rc];
  84                 }
  85
  86                 @Override
  87                 public State clone()  {
  88                         try {
  89                                 State s = (State)super.clone();
  90                                 s.written = s.written.clone();
  91                                 return s;
  92                         } catch (CloneNotSupportedException e) {
  93                             throw new AssertionError(e);
  94                         }
  95                 }
  96         }
  97
  98         int r;
  99         int c;
 100         long n;
 101         char[][] map;
 102
 103         public static void main(String[] args) throws FileNotFoundException {
 104                 new garbling_re_slow().go();
 105         }
 106
 107         void go() throws FileNotFoundException {
 108                 read();
 109                 State s = solve();
 110                 write(s);
 111 //              stressTest();
 112         }
 113
 114         private void read() throws FileNotFoundException {
 115                 Scanner in = new Scanner(new File("garbling.in"));
 116                 r = in.nextInt();
 117                 c = in.nextInt();
 118                 n = in.nextLong();
 119                 map = new char[r - 1][];
 120                 for (int i = 0; i < r - 1; i++) {
 121                         map[i] = in.next().toCharArray();
 122                 }
 123                 in.close();
 124         }
 125
 126         private void write(State s) throws FileNotFoundException {
 127                 PrintWriter out = new PrintWriter(new File("garbling.out"));
 128                 for (int i = 0; i < r * c; i++) {
 129                         out.println(s.written[i]);
 130                 }
 131                 out.close();
 132         }
 133
 134 //      private void stressTest() {
 135 //              Random rnd = new Random(1);
 136 //              while (true) {
 137 //                      r = rnd.nextInt(11) + 90;
 138 //                      c = rnd.nextInt(11) + 90;
 139 //                      map = new char[r - 1][c - 1];
 140 //                      for (int i = 0; i < r - 1; i++) {
 141 //                              for (int j = 0; j < c - 1; j++) {
 142 //                                      int t = rnd.nextInt(4);
 143 //                                      map[i][j] = t <= 1 ? 'N' : t == 2 ? 'L' : 'R';
 144 //                              }
 145 //                      }
 146 //                      solve();
 147 //              }
 148 //      }
 149
 150         State solve() {
 151                 int rc = r * c;
 152                 Field f = new Field(r, c);
 153                 State s = new State(rc);
 154                 Map<Field, State> fields = new HashMap<Field, State>();
 155                 long time = System.currentTimeMillis();
 156                 while (FULL_SIMULATION || !fields.keySet().contains(f)) {
 157                         if (!FULL_SIMULATION)
 158                                 fields.put(f.clone(), s.clone());
 159                         if (garbleFieldOnce(f, s))
 160                                 break;
 161                 }
 162                 System.out.printf("%d turns on %d x %d field in %d ms%n",
 163                         s.turns, r, c, System.currentTimeMillis() - time);
 164                 if (s.turns >= n)
 165                         return s;
 166                 // whole field looped -- fastforward repeating part
 167                 State p = fields.get(f);
 168                 long stretch = s.turns - p.turns;
 169                 long times = (n - s.turns) / stretch;
 170                 s.turns += times * stretch;
 171                 for (int i = 0; i < rc; i++) {
 172                         s.written[i] += times * (s.written[i] - p.written[i]);
 173                 }
 174                 System.out.printf("Fast forward %d x %d turns%n", times, stretch);
 175                 // finish remaining steps
 176                 while (true) {
 177                         if (garbleFieldOnce(f, s))
 178                                 break;
 179                 }
 180                 return s;
 181         }
 182
 183         private boolean garbleFieldOnce(Field f, State s) {
 184                 for (int i = 0; i < r - 1; i++) {
 185                     for (int j = 0; j < c - 1; j++) {
 186                             if (s.turns >= n)
 187                                 return true;
 188                             s.turns++;
 189                             s.written[f.a[i][j] - 1]++;
 190                             switch (map[i][j]) {
 191                             case 'L': f.garbleLeft(i, j); break;
 192                             case 'R': f.garbleRight(i, j); break;
 193                             }
 194                     }
 195                 }
 196                 return false;
 197         }
 198
 199 //      private String showMap() {
 200 //              StringBuilder sb = new StringBuilder();
 201 //              sb.append('|');
 202 //              for (char[] row : map) {
 203 //                      sb.append(row);
 204 //                      sb.append('|');
 205 //              }
 206 //              return sb.toString();
 207 //      }
 208 }