NEERC/garbling/gen_stress_garbling.java

   1 import java.util.*;
   2 import java.math.BigInteger;
   3
   4 /**
   5  * Generates stress-tests for garbling
   6  *
   7  * @author Roman Elizarov
   8  */
   9 public class gen_stress_garbling {
  10         private boolean FIND_LONGEST_LOOP = false;
  11
  12         static class Field implements Cloneable {
  13                 int[][] a;
  14                 final int r;
  15                 final int c;
  16
  17                 Field(int r, int c) {
  18                         this.r = r;
  19                         this.c = c;
  20                         a = new int[r][c];
  21                         int n = 0;
  22                         for (int i = 0; i < r; i++) {
  23                             for (int j = 0; j < c; j++) {
  24                                 a[i][j] = n++;
  25                             }
  26                         }
  27                 }
  28
  29                 void garbleLeft(int i, int j) {
  30                         int t = a[i][j];
  31                         a[i][j] = a[i][j + 1];
  32                         a[i][j + 1] = a[i + 1][j + 1];
  33                         a[i + 1][j + 1] = a[i + 1][j];
  34                         a[i + 1][j] = t;
  35                 }
  36
  37                 void garbleRight(int i, int j) {
  38                         int t = a[i][j];
  39                         a[i][j] = a[i + 1][j];
  40                         a[i + 1][j] = a[i + 1][j + 1];
  41                         a[i + 1][j + 1] = a[i][j + 1];
  42                         a[i][j + 1] = t;
  43                 }
  44         }
  45
  46         Random rnd = new Random();
  47         long besttime = System.currentTimeMillis();
  48         BigInteger besttotal = BigInteger.ZERO;
  49
  50         public static void main(String[] args) {
  51                 new gen_stress_garbling().go();
  52         }
  53
  54         void go() {
  55                 while (true) {
  56                         generateAndAnalyzeOne();
  57                 }
  58         }
  59
  60         private void generateAndAnalyzeOne() {
  61                 int r = 290 + rnd.nextInt(11);
  62                 int c = 290 + rnd.nextInt(11);
  63                 int pl = rnd.nextInt(101);
  64                 int pr = rnd.nextInt(101 - pl);
  65                 int seed = rnd.nextInt();
  66                 char[][] map = genRandom(r, c, pl, pr, seed);
  67                 Field f = new Field(r, c);
  68                 garbleFieldOnce(f, map);
  69                 BigInteger total = findLoopLength(f);
  70                 if (total.compareTo(besttotal) > 0) {
  71                         long time = System.currentTimeMillis();
  72                         printMap(map);
  73                         System.out.printf("-- Found %d with r=%d, c=%d, pl=%d, pr=%d, seed=%d in %d ms%n",
  74                                 total, r, c, pl, pr, seed, time - besttime);
  75                         besttotal = total;
  76                         besttime = time;
  77                 }
  78         }
  79
  80         private BigInteger findLoopLength(Field f) {
  81                 // find transposition of one garbling
  82                 int r = f.r;
  83                 int c = f.c;
  84                 int k = r * c;
  85                 int[] transpose = new int[k];
  86                 for (int i = 0; i < r; i++) {
  87                     for (int j = 0; j < c; j++) {
  88                         transpose[f.a[i][j]] = i * c + j;
  89                     }
  90                 }
  91                 // split transposition into loops
  92                 int[] lnum = new int[k];
  93                 int[] llen = new int[k];
  94                 int lc = 0;
  95                 Arrays.fill(lnum, -1);
  96                 for (int p = 0; p < k; p++) {
  97                     if (lnum[p] < 0) {
  98                             int cnt = 0;
  99                             do {
 100                                     cnt++;
 101                                     lnum[p] = lc;
 102                                     p = transpose[p];
 103                             } while (lnum[p] < 0);
 104                                 llen[lc++] = cnt;
 105                     }
 106                 }
 107                 // find total lenght
 108                 BigInteger total = BigInteger.ONE;
 109                 for (int q = 0; q < lc; q++) {
 110                         if (FIND_LONGEST_LOOP)
 111                                 total = llen[q] > total.longValue() ? BigInteger.valueOf(llen[q]) : total;
 112                         else
 113                         total = nok(total, BigInteger.valueOf(llen[q]));
 114                 }
 115                 return total;
 116         }
 117
 118         private BigInteger nok(BigInteger a, BigInteger b) {
 119                 return a.divide(a.gcd(b)).multiply(b);
 120         }
 121
 122         private static char[][] genRandom(int r, int c, int pl, int pr, int seed) {
 123                 char[][] map = new char[r - 1][c - 1];
 124                 Random rnd = new Random(seed);
 125                 for (int i = 0; i < r - 1; i++) {
 126                         for (int j = 0; j < c - 1; j++) {
 127                                 int p = rnd.nextInt(100);
 128                                 if (p < pl)
 129                                         map[i][j] = 'L';
 130                                 else if (p < pl + pr)
 131                                         map[i][j] = 'R';
 132                                 else
 133                                         map[i][j] = 'N';
 134                         }
 135                 }
 136                 return map;
 137         }
 138
 139         private void garbleFieldOnce(Field f, char[][] map) {
 140                 for (int i = 0; i < f.r - 1; i++) {
 141                     for (int j = 0; j < f.c - 1; j++) {
 142                             switch (map[i][j]) {
 143                             case 'L': f.garbleLeft(i, j); break;
 144                             case 'R': f.garbleRight(i, j); break;
 145                             }
 146                     }
 147                 }
 148         }
 149
 150         private void printMap(char[][] map) {
 151                 for (char[] row : map) {
 152                         System.out.println(new String(row));
 153                 }
 154         }
 155 }