# 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_1d.cpp (7073B)

```      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*T) + a)*A + r)*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   for (int t = T-1; t >= 0; t--) {
121     for (int a = 0; a <= A; a++)
122       for (int r = 0; r < R; r++)
123         for (int c = 0; c < C; c++) {
124           int bestda = 0, best = 0;
125           for (int da = -1; da <= 1; da++) {
126             if (a <= 1 && da < 0)
127               continue;
128             if (a + da > A)
129               continue;
130             Pt next = dest[a + da][r][c];
131             if (next.r < 0)
132               break;
133             int rscore = ((a + da) > 0 ? left[t+1][next.r][next.c] : 0) +
134               tab[(((t+1)*T + (a+da))*A + next.r)*R + next.c];
135             if (rscore > best || (rscore == best && (rand() % 2))) {
136               best = rscore;
137               bestda = da;
138             }
139           }
140           tab[(((t*T) + a)*A + r)*R + c] = best;
141           dir[(((t*T) + a)*A + r)*R + c] = bestda;
142         }
143   }
144   totscore += simulate(b, &decide_dyn);
146 }
147
148 void print_sol(int totscore) {
149   FILE *f = fopen(output, "w");
150
151   // print solution
152   fprintf(f, "score %d\n", totscore);
153
154   for (int t = 0; t < T; t++) {
155     for (int b = 0; b < B; b++)
156       fprintf(f, "%d ", solution[t][b]);
157     fprintf(f, "\n");
158   }
159
160   fclose(f);
161 }
162
163 int main(int argc, char **argv) {
164   int TOREPLAN = atoi(argv[1]);
165   srand(time(NULL));
166
167   if (argc == 1) {
168     printf("syntax: ./a.out NREPLANIFY INPUT OUTPUT\n");
169     return 1;
170   }
171   output = argv[3];
172
173
174   scanf("%d%d%d", &R, &C, &A);
175   scanf("%d%d%d%d", &L, &V, &B, &T);
176   scanf("%d%d", &rs, &cs);
177   for (int l = 0; l < L; l++) {
178     int r, c;
179     scanf("%d%d", &r, &c);
180     target[l] = Pt(r, c);
181   }
182   for (int r = 0; r < R; r++)
183     for (int c = 0; c < C; c++) {
184       dest[0][r][c] = Pt(r, c);
185     }
186   for (int a = 1; a <= A; a++)
187     for (int r = 0; r < R; r++)
188       for (int c = 0; c < C; c++) {
189         int dr, dc;
190         scanf("%d%d", &dr, &dc);
191         int destr, destc;
192         destr = r + dr;
193         destc = (c + dc + C) % C;
194         if (destr < 0 || destr >= R)
195           destr = destc = -1; // out
196         dest[a][r][c] = Pt(destr, destc);
197       }
198   calccoverage();
199   //for (int r = 0; r < R; r++) {
200   //  for (int c = 0; c < C; c++)
201   //    printf("%d ", (int) coverage[r][c].size());
202   //  printf("\n");
203   //}
204
205   int totscore = 0;
206
207   if (argc > 3) {
209
210     FILE *fsol = fopen(argv[2], "r");
211     for (int t = 0; t < T; t++)
212       for (int b = 0; b < B; b++)
213         fscanf(fsol, "%d", &(solution[t][b]));
214     fclose(fsol);
215     for (int b = 0; b < B; b++)
216       totscore += simulate(b, &decide_sol);
217     printf("existing sol has score %d\n", totscore);
218   } else {
219     for (int b = 0; b < B; b++) {
220       printf("%d\n", b);
221       totscore += planify(b);
222     }
223     printf("score %d\n", totscore);
224     print_sol(totscore);
225   }
226
227   int prevscore;
228   int counter = 0;
229   while(true) {
230     counter++;
231     counter = counter % B;
232     // keep old solution
233     for (int t = 0; t <= T; t++)
234       for (int b = 0; b <= B; b++)
235         oldsol[t][b] = solution[t][b];
236     // choice of replanify
237     bool toreplan[MAXB];
238     for (int b = 0; b < B; b++)
239       toreplan[b] = false;
240     //if (TOREPLAN == 1) {
241       // if one to replan, do it sequentially
242     //  toreplan[counter] = true;
243 //    } else {
244       for (int numb = 0; numb < TOREPLAN; numb++)
245         toreplan[rand() % B] = true;
246 //    }
247       for (int t = 0; t <= T; t++)
248         for (int l = 0; l < L; l++)
249           covered[t][l] = false;
250     // now simulate
251     prevscore = totscore;
252     totscore = 0;
253     for (int b = 0; b < B; b++) {
254       if (toreplan[b])
255         continue;
256       totscore += simulate(b, &decide_sol);
257     }
258     for (int b = 0; b < B; b++) {
259       if (!toreplan[b])
260         continue;
261       printf("i replanify %d\n", b);
262       totscore += planify(b);
263       simulate(b, &decide_dyn);
264     }
265
266     if (totscore > prevscore) {
267       printf("score was %d is %d\n", prevscore, totscore);
268       print_sol(totscore);
269     }
270     if (totscore == prevscore) {
271       print_sol(totscore);
272       //printf("score was %d is still %d\n", prevscore, totscore);
273     }
274
275     if (totscore < prevscore) {
276       printf("score was %d is now %d, rollback!!\n", prevscore, totscore);
277       // rollback
278       for (int t = 0; t <= T; t++)
279         for (int b = 0; b <= B; b++)
280           solution[t][b] = oldsol[t][b];
281       totscore = prevscore;
282     }
283   }
284
285   return 0;
286 }
287
```