Differences From Artifact [3df785b1c1414432]:
- File
src/solver.d
- 2012-07-14 13:45:03 - part of checkin [62a5c6c47f] on branch trunk - Correctly implemented below-rock avoider. (user: kinaba) [annotate]
To Artifact [ee353f733f706a26]:
- File
src/solver.d
- 2012-07-14 14:13:31 - part of checkin [c4d04122d8] on branch trunk - Dead end avoider. (user: kinaba) [annotate]
20 { 20 {
21 int g_wc = 0; 21 int g_wc = 0;
22 22
23 Game g; 23 Game g;
24 this(const(Game) g) 24 this(const(Game) g)
25 { 25 {
26 this.g = g.clone(); 26 this.g = g.clone();
> 27 forbidden_cell = new bool[][](g.map.H+2, g.map.W+2);
27 } 28 }
28 29
29 char single_step() 30 char single_step()
30 { 31 {
> 32 Tuple!(string,int) de = death_move(g);
31 char c = act(g, death_move(g)); | 33 char c = act(g, de[0], de[1]);
32 g.command(c); 34 g.command(c);
33 return c; 35 return c;
34 } 36 }
35 37
36 string death_move(const(Game) g) | 38 Tuple!(string,int) death_move(const(Game) g)
37 { 39 {
38 string death; 40 string death;
> 41 int choice = 0;
39 foreach(char c; "UDLRW") { 42 foreach(char c; "UDLRW") {
40 Game gg = g.clone(); 43 Game gg = g.clone();
41 gg.command(c); 44 gg.command(c);
42 if( !gg.cleared && gg.dead ) 45 if( !gg.cleared && gg.dead )
43 death ~= c; 46 death ~= c;
> 47 else if( gg.map.robot != g.map.robot )
> 48 choice++;
44 } 49 }
45 return death; | 50 return tuple(death, choice);
46 } 51 }
47 52
> 53 Tuple!(Pos, int)[] log;
> 54 bool[][] forbidden_cell;
> 55
48 char act(const(Game) g, string death) | 56 char act(const(Game) g, string death, int breath)
49 { 57 {
50 const Pos ro = g.map.robot; 58 const Pos ro = g.map.robot;
51 const Pos[] la = g.map.lambdas(); 59 const Pos[] la = g.map.lambdas();
52 const Pos li = g.map.lift; 60 const Pos li = g.map.lift;
53 61
54 Tuple!(char,int)[] cand; 62 Tuple!(char,int)[] cand;
55 char c = 'W'; 63 char c = 'W';
56 if( la.empty ) { 64 if( la.empty ) {
57 cand = search(g, ro, li, death); 65 cand = search(g, ro, li, death);
58 } else { 66 } else {
59 foreach(lam; la) 67 foreach(lam; la)
60 cand ~= search(g, ro, lam, death); 68 cand ~= search(g, ro, lam, death);
61 } 69 }
> 70 cand ~= tuple('W',int.max);
62 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){ 71 sort!((Tuple!(char,int) c1, Tuple!(char,int) c2){
63 if(c1[1] != c2[1]) 72 if(c1[1] != c2[1])
64 return c1[1] < c2[1]; 73 return c1[1] < c2[1];
65 return c1[0] < c2[0]; 74 return c1[0] < c2[0];
66 })(cand); 75 })(cand);
67 c = cand[0][0]; 76 c = cand[0][0];
68 77
................................................................................................................................................................................
69 if(c=='W') { 78 if(c=='W') {
70 g_wc++; 79 g_wc++;
71 if(g_wc > 10) 80 if(g_wc > 10)
72 c = 'A'; 81 c = 'A';
73 } 82 }
74 else 83 else
75 g_wc = 0; 84 g_wc = 0;
> 85 bool[char] choice;
> 86 foreach(t; cand)
> 87 choice[t[0]] = true;
> 88 log ~= tuple(ro.clone(), cast(int)choice.length);
> 89 if(log.length > 5)
> 90 log = log[$-5..$];
> 91 int cnt = 0;
> 92 foreach(l; log)
> 93 if(l[0] == log[$-1][0])
> 94 ++cnt;
> 95 if( cnt >= 3 && breath==1 ) {
> 96 forbidden_cell[ro.y][ro.x] = true;
> 97 }
> 98
76 return c; 99 return c;
77 } 100 }
78 101
79 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death) 102 Tuple!(char,int)[] search(in Game g, in Pos s, in Pos o, string death)
80 { 103 {
81 bool danger(int y, int x) 104 bool danger(int y, int x)
82 { 105 {
................................................................................................................................................................................
108 int y = p.y+dy[i]; 131 int y = p.y+dy[i];
109 int x = p.x+dx[i]; 132 int x = p.x+dx[i];
110 if(v[y][x]) continue; 133 if(v[y][x]) continue;
111 if(y==s.y && x==s.x) { 134 if(y==s.y && x==s.x) {
112 char c = "UDRL"[ 135 char c = "UDRL"[
113 if( death.count( 136 if( death.count(
114 return [ 137 return [
> 138 } else if(forbidden_cell
115 } else if(g.map[y,x]==' 139 } else if(g.map[y,x]=='
116 if(danger(y,x)) 140 if(danger(y,x))
117 continue 141 continue
118 q2 ~= new Pos(y, 142 q2 ~= new Pos(y,
119 v[y][x]=true; 143 v[y][x]=true;
120 } 144 }
121 } 145 }
................................................................................................................................................................................
127 } 151 }
128 152
129 // any empty space is my ground 153 // any empty space is my ground
130 Tuple!(char,int)[] tryB() { 154 Tuple!(char,int)[] tryB() {
131 const(Pos)[] q = [o]; 155 const(Pos)[] q = [o];
132 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 156 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
133 v[o.y][o.x]=true; 157 v[o.y][o.x]=true;
134 for(int step=15; q.length; ++step) { | 158 for(int step=10; q.length; ++step) {
135 Pos[] q2; 159 Pos[] q2;
136 foreach(p; q) { 160 foreach(p; q) {
137 int[] dy=[-1,+1,0,0]; 161 int[] dy=[-1,+1,0,0];
138 int[] dx=[0,0,-1,+1]; 162 int[] dx=[0,0,-1,+1];
139 for(int i=0; i<4; ++i) { 163 for(int i=0; i<4; ++i) {
140 int y = p.y+dy[i]; 164 int y = p.y+dy[i];
141 int x = p.x+dx[i]; 165 int x = p.x+dx[i];
142 if(v[y][x]) continue; 166 if(v[y][x]) continue;
143 if(y==s.y && x==s.x) { 167 if(y==s.y && x==s.x) {
144 char c = "UDRL"[i]; 168 char c = "UDRL"[i];
145 if( death.count(c) == 0 169 if( death.count(c) == 0
146 return [tuple(c, 170 return [tuple(c,
> 171 } else if(forbidden_cell[y][x]){
147 } else if(g.map[y,x]==' '||g.map 172 } else if(g.map[y,x]==' '||g.map
148 q2 ~= new Pos(y,x); 173 q2 ~= new Pos(y,x);
149 v[y][x]=true; 174 v[y][x]=true;
150 } 175 }
151 } 176 }
152 } 177 }
153 q = q2; 178 q = q2;
................................................................................................................................................................................
156 } 181 }
157 182
158 // push rocks! 183 // push rocks!
159 Tuple!(char,int)[] tryC() { 184 Tuple!(char,int)[] tryC() {
160 const(Pos)[] q = [o]; 185 const(Pos)[] q = [o];
161 bool[][] v = new bool[][](g.map.H+2, g.map.W+2); 186 bool[][] v = new bool[][](g.map.H+2, g.map.W+2);
162 v[o.y][o.x]=true; 187 v[o.y][o.x]=true;
163 for(int step=30; q.length; ++step) { | 188 for(int step=20; q.length; ++step) {
164 Pos[] q2; 189 Pos[] q2;
165 foreach(p; q) { 190 foreach(p; q) {
166 int[] dy=[-1,+1,0,0]; 191 int[] dy=[-1,+1,0,0];
167 int[] dx=[0,0,-1,+1]; 192 int[] dx=[0,0,-1,+1];
168 for(int i=0; i<4; ++i) { 193 for(int i=0; i<4; ++i) {
169 int y = p.y+dy[i]; 194 int y = p.y+dy[i];
170 int x = p.x+dx[i]; 195 int x = p.x+dx[i];
171 if(v[y][x]) continue; 196 if(v[y][x]) continue;
172 if(y==s.y && x==s.x) { 197 if(y==s.y && x==s.x) {
173 char c = "UDRL"[i]; 198 char c = "UDRL"[i];
174 if( death.count(c) == 0 199 if( death.count(c) == 0
175 return [tuple(c, 200 return [tuple(c,
> 201 } else if(forbidden_cell[y][x]){
176 } else if(g.map[y,x]==' '||g.map 202 } else if(g.map[y,x]==' '||g.map
177 q2 ~= new Pos(y,x); 203 q2 ~= new Pos(y,x);
178 v[y][x]=true; 204 v[y][x]=true;
179 } else if(dy[i]==0 && g.map[p]== 205 } else if(dy[i]==0 && g.map[p]==
180 q2 ~= new Pos(y,x); 206 q2 ~= new Pos(y,x);
181 v[y][x]=true; 207 v[y][x]=true;
182 } 208 }
183 } 209 }
184 } 210 }
185 q = q2; 211 q = q2;
186 } 212 }
187 return []; 213 return [];
188 } 214 }
189 return tryA() ~ tryB() ~ tryC() ~ tuple('W', int.max); | 215 return tryA() ~ tryB() ~ tryC();
190 } 216 }
191 } 217 }