NEERC/funny/tests/doall.java

   1 import java.io.FileNotFoundException;
   2 import java.io.IOException;
   3 import java.io.PrintWriter;
   4 import java.util.ArrayList;
   5 import java.util.Arrays;
   6 import java.util.Collections;
   7 import java.util.HashSet;
   8 import java.util.List;
   9 import java.util.ListIterator;
  10 import java.util.Random;
  11 import java.util.Set;
  12
  13 public class doall {
  14         static final int MAX_N = 100;
  15         static final int MAX_M = 1000;
  16         static final int MAX_W = 100;
  17     static final int MIN_CH = 'A';
  18     static final int MAX_CH = 'Z';
  19     static final Random random = new Random(1932840934230493244L);
  20
  21     static PrintWriter out;
  22
  23     static int test = 0;
  24
  25     String description;
  26     final int n;
  27     List<String> words = new ArrayList<String>();
  28     Set<String> wordsSet = new HashSet<String>();
  29
  30     public doall(String description, int n) {
  31         this.description = description;
  32         this.n = n;
  33         }
  34
  35     public doall(int n) {
  36         this("", n);
  37         }
  38
  39         public void write() {
  40         test++;
  41
  42         System.out.println("Writing test " + test + " (" + description + ")");
  43         out.format("%02d %s\n", test, description);
  44
  45         assert 1 <= words.size() && words.size() <= MAX_M;
  46
  47         assert new HashSet<String>(words).size() == words.size();
  48
  49         for (String word : words) {
  50                 assert 1 <= word.length() && word.length() <= MAX_W;
  51             for (char ch : word.toCharArray()) {
  52                 assert MIN_CH <= ch && ch <= MAX_CH : word;
  53             }
  54         }
  55
  56         try {
  57             PrintWriter out = new PrintWriter(String.format("%02d", test));
  58             out.println(n + " " + words.size());
  59             for (String word : words) {
  60                 out.println(word);
  61             }
  62             out.close();
  63         } catch (IOException e){
  64             e.printStackTrace();
  65         }
  66     }
  67
  68     static int random(int max) {
  69         return random.nextInt(max);
  70     }
  71
  72     static int random(int min, int max) {
  73         return min + random(max - min);
  74     }
  75
  76         static char randomChar(int min, int max) {
  77                 return (char) random(min, max);
  78         }
  79
  80         static String randomWord(int w, int maxChar) {
  81                 StringBuilder sb = new StringBuilder();
  82         for (int i = 0; i < w; i++) {
  83                 sb.append(randomChar(MIN_CH, maxChar + 1));
  84         }
  85         return sb.toString();
  86         }
  87
  88     private doall hand(String... words) {
  89         description = Arrays.toString(words);
  90         this.words.addAll(Arrays.asList(words));
  91         this.wordsSet.addAll(Arrays.asList(words));
  92         return this;
  93     }
  94
  95         private void addWord(String word) {
  96                 if (wordsSet.add(word)) {
  97                         words.add(word);
  98                 }
  99         }
 100
 101         private doall repeat(int m, String ... words) {
 102                 for (String word : words) {
 103                         addDescription("1.." + m + "*" + word + " ");
 104                         StringBuilder sb = new StringBuilder();
 105                         for (int i = 0; i < m; i++) {
 106                                 sb.append(word);
 107                                 addWord(sb.toString());
 108                         }
 109                 }
 110                 return this;
 111         }
 112
 113         private doall randomWords(int m, int w, int dw, int maxChar) {
 114                 addDescription(m + " random " + (dw == 0 ? "" : (w - dw) + "..") + w + "-letter words");
 115                 for (int i = 0; i < m; i++) {
 116                         addWord(randomWord(w - random(dw + 1), maxChar));
 117                 }
 118                 return this;
 119         }
 120
 121         private String addLetters(String letters, String word) {
 122                 int i = 0;
 123                 int j = 0;
 124                 StringBuilder sb = new StringBuilder();
 125                 while (i < letters.length() && j < word.length()) {
 126                         sb.append(random(2) == 0 ? letters.charAt(i++) : word.charAt(j++));
 127                 }
 128                 while (i < letters.length()) {
 129                         sb.append(letters.charAt(i++));
 130                 }
 131                 while (j < word.length()) {
 132                         sb.append(word.charAt(j++));
 133                 }
 134                 return sb.toString();
 135         }
 136
 137         private doall addLetters(String letters) {
 138                 addDescription(" with " + letters.length() + " common letters");
 139                 for (ListIterator<String> i = words.listIterator(); i.hasNext(); ) {
 140                         i.set(addLetters(letters, i.next()));
 141                 }
 142                 wordsSet.clear();
 143                 wordsSet.addAll(words);
 144                 return this;
 145         }
 146
 147         private doall shuffle() {
 148                 Collections.shuffle(words, random);
 149                 return this;
 150         }
 151
 152         private doall sequences(int m, int w) {
 153                 for (int i = 0; i < m; i++) {
 154                         repeat(w, "" + (char) ('A' + i));
 155                 }
 156                 return this;
 157         }
 158
 159         private doall addDescription(String string) {
 160                 description += string;
 161                 return this;
 162         }
 163
 164         private doall addSmallWords() {
 165                 int c = Math.min(MAX_M - words.size(), words.size() / 10);
 166                 addDescription(", " + c + " 2-letter words added");
 167                 for (int i = 0; i < 26 && c > 0; i++) {
 168                         for (int j = 0; j < 26 && c > 0; j++) {
 169                                 addWord((char) ('A' + i) + "" + (char) ('A' + j));
 170                                 c--;
 171                         }
 172                 }
 173                 return this;
 174         }
 175
 176         private doall removeRandom(int m) {
 177                 addDescription(", " + m + " random words removed");
 178                 for (int i = 0; i < m; i++) {
 179                         String word = words.remove(random(words.size()));
 180                         wordsSet.remove(word);
 181                 }
 182                 return this;
 183         }
 184
 185         public static void main(String[] args) throws FileNotFoundException {
 186                 out = new PrintWriter("tests.lst");
 187
 188                 new doall("Example test", 3).hand("A", "ACM", "ICPC", "CONTEST", "NEERC").write();
 189                 new doall(2).hand("A", "AB", "ABA").write();
 190                 new doall("A, AA, AAA", 2).repeat(3, "A").write();
 191
 192                 new doall(10).randomWords(10, 3, 0, MIN_CH + 2).addDescription(" of ABC").write();
 193                 new doall(10).randomWords(10, 3, 0, MAX_CH).write();
 194                 new doall(10).randomWords(10, 10, 0, MAX_CH).write();
 195
 196                 new doall(MAX_N / 10).randomWords(MAX_M / 100, 10, 3, MAX_CH).removeRandom(1).addSmallWords().addLetters("RVL").write();
 197                 new doall(10).sequences(25, 3).removeRandom(3).addSmallWords().shuffle().write();
 198                 new doall(MAX_N / 10).repeat(Math.min(MAX_W / 4, MAX_M), "AB", "CD").removeRandom(3).addSmallWords().shuffle().write();
 199
 200                 new doall(MAX_N).sequences(MAX_M / MAX_W, MAX_W).removeRandom(5).shuffle().write();
 201                 new doall(MAX_N).repeat(Math.min(MAX_W / 2, MAX_M), "AB").removeRandom(10).shuffle().write();
 202                 new doall(MAX_N).repeat(Math.min(MAX_W / 10, MAX_M), "FD", "PQR").removeRandom(2).shuffle().write();
 203
 204                 new doall(MAX_N).repeat(Math.min(MAX_W, MAX_M), "C").removeRandom(MAX_W / 10).shuffle().write();
 205                 new doall(MAX_N / 10).randomWords(MAX_M / 10, 10, 3, MAX_CH).addLetters("QQQ").addSmallWords().write();
 206                 new doall(MAX_N / 2 - 17).randomWords(MAX_M / 3, MAX_W, 10, MAX_CH).addSmallWords().write();
 207                 new doall(MAX_N / 2 - 3).randomWords(MAX_M / 2, MAX_W, 0, MAX_CH).addSmallWords().write();
 208
 209                 new doall(MAX_N).randomWords(MAX_M * 9 / 10, MAX_W - 3, 10, MAX_CH).addLetters("GFK").write();
 210                 new doall(MAX_N).randomWords(MAX_M, MAX_W - 3, 10, MAX_CH).addLetters("AAA").write();
 211                 new doall(MAX_N).randomWords(MAX_M, MAX_W - 3, 10, MAX_CH).addLetters("QZF").write();
 212                 new doall("Random almost max test: ", MAX_N).randomWords(MAX_M, MAX_W, 10, MAX_CH).write();
 213                 new doall("Random max test: ", MAX_N).randomWords(MAX_M, MAX_W, 0, MAX_CH).write();
 214 //
 215 //              random.setSeed(3409543954354545522L);
 216 //              new doall("Random max test with max answer: ", MAX_N).randomWords(MAX_M, MAX_W, 0, MAX_CH - 10).write();
 217 //
 218 //              for (int i = 0; i < 1000; i++) {
 219 //                      random.setSeed(3409543954354545522L + i);
 220 //                      doall test = new doall("Random max test with max answer", MAX_N).randomWords(MAX_M, MAX_W, 0, MAX_CH - 10);
 221 //                      funny_gk funnyGk = new funny_gk();
 222 //                      funnyGk.solve(MAX_N, new HashSet<String>(test.words));
 223 //                      System.out.println(i + " " + funnyGk.c);
 224 //                      if (funnyGk.c == MAX_N * MAX_M) {
 225 //                              break;
 226 ////                            System.out.println(3409543954354545517L + i);
 227 //                      }
 228 //              }
 229                 out.close();
 230         }
 231 }