# ens-ulm-1-2015

google hashcode 2015 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1-2015/
Log | Files | Refs

main.cpp (7240B)

```      1 #include <vector>
2 #include <cstdio>
3 #include <algorithm>
4 #include <map>
5 #include <time.h>
6
7 using namespace std;
8
9 #define MAXR 77
10 #define MAXC 302
11 #define MAXL 2252
12 #define MAXA 10
13 #define MAXT 402
14 #define MAXB 55
15
16 char* output;
17
18 int R, C, A;
19 int L, V, B, T;
20 int rs, cs;
21
22 struct Pt{
23   int r, c;
24   Pt(int r=0, int c=0) : r(r), c(c) {}
25 };
26
27 vector<int> coverage[MAXR][MAXC]; // which targets are covered in r c
28
29 Pt dest[MAXA][MAXR][MAXC]; // where does the wind take us: -1 -1 = out
30
31 Pt target[MAXL];
32
33 bool covered[MAXT][MAXL]; // does someone cover target l at time t
34 int left[MAXT][MAXR][MAXC]; // how many left to cover?
35
36 int solution[MAXT][MAXB];
37 int oldsol[MAXT][MAXB];
38
39 // for dynamic
40 int tab[MAXT][MAXA][MAXR][MAXC];
41 int dir[MAXT][MAXA][MAXR][MAXC];
42
43 int columndist(int c1, int c2) {
44   return min(abs(c1 - c2), C - abs(c1 - c2));
45 }
46
47 int iscovered(int l, int r, int c) {
48   // does a loon at r c cover l?
49   int u = target[l].r, v = target[l].c;
50   return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);
51 }
52
53
54 void calccoverage() {
55   // compute for each square which targets are covered
56   for (int r = 0; r < R; r++)
57     for (int c = 0; c < C; c++)
58       for (int l = 0; l < L; l++)
59         if (iscovered(l, r, c))
60           coverage[r][c].push_back(l);
61 }
62
63 int decide_dyn(int b, int t, int a, int r, int c) {
64   return dir[t][a][r][c];
65 }
66
67 int decide_sol(int b, int t, int a, int r, int c) {
68   return solution[t][b];
69 }
70
71 int simulate(int b, int (*decide)(int, int, int, int, int)) {
73   //
74   // ok now follow the best
75   int totscore = 0;
76   int r = rs, c = cs, a = 0;
77   for (int t = 0; t < T; t++) {
78     //printf("loon %d at time %d is %d %d %d\n", b, t, a, r, c);
79     int bestda = (*decide)(b, t, a, r, c);
80     //printf("i choose %d\n", bestda);
81     // ok, apply bestda
82     a += bestda;
83     solution[t][b] = bestda;
84     Pt next = dest[a][r][c];
85     r = next.r;
86     c = next.c;
87     if (r < 0) {
88       //printf("FAILLL\n");
89       break; // loon is out
90     }
91     if (a > 0 && r >= 0) {
92       // update covered targets
93       //printf("coverage %d %d\n", r, c);
94       for (unsigned int i = 0; i < coverage[r][c].size(); i++) {
95         int l = coverage[r][c][i];
96         totscore += covered[t+1][l] ? 0 : 1;
97         covered[t+1][l] = true;
98       }
99     }
100   }
102 }
103
104
105 int planify(int b) {
106   // planify one loon, b, based on the info of covered
108   int totscore = 0;
109   // compute left
110   for (int t = 0; t <= T; t++)
111     for (int r = 0; r < R; r++)
112       for (int c = 0; c < C; c++) {
113         int cscore = 0;
114         for (unsigned int i = 0; i < coverage[r][c].size(); i++) {
115           int l = coverage[r][c][i];
116           cscore += covered[t][l] ? 0 : 1;
117         }
118         left[t][r][c] = cscore;
119       }
120   // planify loon b, t == T is sentinel
121   for (int t = 0; t <= T; t++)
122     for (int a = 0; a <= A; a++)
123       for (int r = 0; r < R; r++)
124         for (int c = 0; c < C; c++)
125           tab[t][a][r][c] = dir[t][a][r][c] = 0;
126   for (int t = T-1; t >= 0; t--) {
127     for (int a = 0; a <= A; a++)
128       for (int r = 0; r < R; r++)
129         for (int c = 0; c < C; c++) {
130           int bestda = 0, best = 0;
131           for (int da = -1; da <= 1; da++) {
132             if (a <= 1 && da < 0)
133               continue;
134             if (a + da > A)
135               continue;
136             Pt next = dest[a + da][r][c];
137             if (next.r < 0)
138               break;
139             int rscore = ((a + da) > 0 ? left[t+1][next.r][next.c] : 0) +
140               tab[t+1][a+da][next.r][next.c];
141             if (rscore > best || (rscore == best && (rand() % 2))) {
142               best = rscore;
143               bestda = da;
144             }
145           }
146           tab[t][a][r][c] = best;
147           dir[t][a][r][c] = bestda;
148         }
149   }
150   totscore += simulate(b, &decide_dyn);
152 }
153
154 void print_sol(int totscore) {
155   FILE *f = fopen(output, "w");
156
157   // print solution
158   fprintf(f, "score %d\n", totscore);
159
160   for (int t = 0; t < T; t++) {
161     for (int b = 0; b < B; b++)
162       fprintf(f, "%d ", solution[t][b]);
163     fprintf(f, "\n");
164   }
165
166   fclose(f);
167 }
168
169 int main(int argc, char **argv) {
170   int TOREPLAN = atoi(argv[1]);
171   srand(time(NULL));
172
173   if (argc == 1) {
174     printf("syntax: ./a.out NREPLANIFY INPUT OUTPUT\n");
175     return 1;
176   }
177   output = argv[3];
178
179
180   scanf("%d%d%d", &R, &C, &A);
181   scanf("%d%d%d%d", &L, &V, &B, &T);
182   scanf("%d%d", &rs, &cs);
183   for (int l = 0; l < L; l++) {
184     int r, c;
185     scanf("%d%d", &r, &c);
186     target[l] = Pt(r, c);
187   }
188   for (int r = 0; r < R; r++)
189     for (int c = 0; c < C; c++) {
190       dest[0][r][c] = Pt(r, c);
191     }
192   for (int a = 1; a <= A; a++)
193     for (int r = 0; r < R; r++)
194       for (int c = 0; c < C; c++) {
195         int dr, dc;
196         scanf("%d%d", &dr, &dc);
197         int destr, destc;
198         destr = r + dr;
199         destc = (c + dc + C) % C;
200         if (destr < 0 || destr >= R)
201           destr = destc = -1; // out
202         dest[a][r][c] = Pt(destr, destc);
203       }
204   calccoverage();
205   //for (int r = 0; r < R; r++) {
206   //  for (int c = 0; c < C; c++)
207   //    printf("%d ", (int) coverage[r][c].size());
208   //  printf("\n");
209   //}
210
211   int totscore = 0;
212
213   if (argc > 3) {
215
216     FILE *fsol = fopen(argv[2], "r");
217     for (int t = 0; t < T; t++)
218       for (int b = 0; b < B; b++)
219         fscanf(fsol, "%d", &(solution[t][b]));
220     fclose(fsol);
221     for (int b = 0; b < B; b++)
222       totscore += simulate(b, &decide_sol);
223     printf("existing sol has score %d\n", totscore);
224   } else {
225     for (int b = 0; b < B; b++) {
226       printf("%d\n", b);
227       totscore += planify(b);
228     }
229     printf("score %d\n", totscore);
230     print_sol(totscore);
231   }
232
233   int prevscore;
234   int counter = 0;
235   while(true) {
236     counter++;
237     counter = counter % B;
238     // keep old solution
239     for (int t = 0; t <= T; t++)
240       for (int b = 0; b <= B; b++)
241         oldsol[t][b] = solution[t][b];
242     // choice of replanify
243     bool toreplan[MAXB];
244     for (int b = 0; b < B; b++)
245       toreplan[b] = false;
246     //if (TOREPLAN == 1) {
247       // if one to replan, do it sequentially
248     //  toreplan[counter] = true;
249 //    } else {
250       for (int numb = 0; numb < TOREPLAN; numb++)
251         toreplan[rand() % B] = true;
252 //    }
253       for (int t = 0; t <= T; t++)
254         for (int l = 0; l < L; l++)
255           covered[t][l] = false;
256     // now simulate
257     prevscore = totscore;
258     totscore = 0;
259     for (int b = 0; b < B; b++) {
260       if (toreplan[b])
261         continue;
262       totscore += simulate(b, &decide_sol);
263     }
264     for (int b = 0; b < B; b++) {
265       if (!toreplan[b])
266         continue;
267       printf("i replanify %d\n", b);
268       totscore += planify(b);
269       simulate(b, &decide_dyn);
270     }
271
272     if (totscore > prevscore) {
273       printf("score was %d is %d\n", prevscore, totscore);
274       print_sol(totscore);
275     }
276     if (totscore == prevscore) {
277       print_sol(totscore);
278       //printf("score was %d is still %d\n", prevscore, totscore);
279     }
280
281     if (totscore < prevscore) {
282       printf("score was %d is now %d, rollback!!\n", prevscore, totscore);
283       // rollback
284       for (int t = 0; t <= T; t++)
285         for (int b = 0; b <= B; b++)
286           solution[t][b] = oldsol[t][b];
287       totscore = prevscore;
288     }
289   }
290
291   return 0;
292 }
293
```