Hex Artifact Content
Not logged in

Artifact 0bb4050087a6fb3f53ef5a516cd7759f02325de4:


0000: 69 6d 70 6f 72 74 20 75 74 69 6c 3b 0a 69 6d 70  import util;.imp
0010: 6f 72 74 20 67 61 6d 65 3b 0a 69 6d 70 6f 72 74  ort game;.import
0020: 20 64 72 69 76 65 72 3b 0a 0a 2f 2a 0a 69 6e 74   driver;../*.int
0030: 65 72 66 61 63 65 20 53 6f 6c 76 65 72 0a 7b 0a  erface Solver.{.
0040: 09 74 68 69 73 28 63 6f 6e 73 74 28 47 61 6d 65  .this(const(Game
0050: 29 20 67 29 3b 0a 09 63 68 61 72 20 73 69 6e 67  ) g);..char sing
0060: 6c 65 5f 73 74 65 70 28 29 3b 0a 7d 0a 2a 2f 0a  le_step();.}.*/.
0070: 0a 63 6c 61 73 73 20 53 6f 6c 76 65 72 5f 30 0a  .class Solver_0.
0080: 7b 0a 09 74 68 69 73 28 63 6f 6e 73 74 28 47 61  {..this(const(Ga
0090: 6d 65 29 20 67 29 20 7b 7d 0a 09 63 68 61 72 20  me) g) {}..char 
00a0: 73 69 6e 67 6c 65 5f 73 74 65 70 28 29 20 7b 20  single_step() { 
00b0: 72 65 74 75 72 6e 20 27 57 27 3b 20 7d 0a 7d 0a  return 'W'; }.}.
00c0: 0a 63 6c 61 73 73 20 53 6f 6c 76 65 72 5f 31 0a  .class Solver_1.
00d0: 7b 0a 09 69 6e 74 20 67 5f 77 63 20 3d 20 30 3b  {..int g_wc = 0;
00e0: 0a 0a 09 47 61 6d 65 20 67 3b 0a 09 74 68 69 73  ...Game g;..this
00f0: 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 0a  (const(Game) g).
0100: 09 7b 0a 09 09 74 68 69 73 2e 67 20 3d 20 67 2e  .{...this.g = g.
0110: 63 6c 6f 6e 65 28 29 3b 0a 09 7d 0a 0a 09 63 68  clone();..}...ch
0120: 61 72 20 73 69 6e 67 6c 65 5f 73 74 65 70 28 29  ar single_step()
0130: 0a 09 7b 0a 09 09 63 68 61 72 20 63 20 3d 20 61  ..{...char c = a
0140: 63 74 28 67 29 3b 0a 09 09 67 2e 63 6f 6d 6d 61  ct(g);...g.comma
0150: 6e 64 28 63 29 3b 0a 09 09 72 65 74 75 72 6e 20  nd(c);...return 
0160: 63 3b 0a 09 7d 0a 0a 09 63 68 61 72 20 61 63 74  c;..}...char act
0170: 28 63 6f 6e 73 74 28 47 61 6d 65 29 20 67 29 0a  (const(Game) g).
0180: 09 7b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 20 20  .{...const Pos  
0190: 20 72 6f 20 3d 20 67 2e 6d 61 70 2e 72 6f 62 6f   ro = g.map.robo
01a0: 74 3b 0a 09 09 63 6f 6e 73 74 20 50 6f 73 5b 5d  t;...const Pos[]
01b0: 20 6c 61 20 3d 20 67 2e 6d 61 70 2e 6c 61 6d 62   la = g.map.lamb
01c0: 64 61 73 28 29 3b 0a 09 09 63 6f 6e 73 74 20 50  das();...const P
01d0: 6f 73 20 20 20 6c 69 20 3d 20 67 2e 6d 61 70 2e  os   li = g.map.
01e0: 6c 69 66 74 3b 0a 0a 09 09 63 68 61 72 20 63 20  lift;....char c 
01f0: 3d 20 27 57 27 3b 0a 09 09 69 66 28 20 6c 61 2e  = 'W';...if( la.
0200: 65 6d 70 74 79 20 29 20 7b 0a 09 09 09 61 75 74  empty ) {....aut
0210: 6f 20 72 20 3d 20 73 65 61 72 63 68 28 67 2c 20  o r = search(g, 
0220: 72 6f 2c 20 6c 69 29 3b 0a 09 09 09 63 20 3d 20  ro, li);....c = 
0230: 72 5b 30 5d 3b 0a 09 09 7d 20 65 6c 73 65 20 7b  r[0];...} else {
0240: 0a 09 09 09 54 75 70 6c 65 21 28 63 68 61 72 2c  ....Tuple!(char,
0250: 69 6e 74 29 5b 5d 20 63 61 6e 64 3b 0a 09 09 09  int)[] cand;....
0260: 66 6f 72 65 61 63 68 28 6c 61 6d 3b 20 6c 61 29  foreach(lam; la)
0270: 0a 09 09 09 09 63 61 6e 64 20 7e 3d 20 73 65 61  .....cand ~= sea
0280: 72 63 68 28 67 2c 20 72 6f 2c 20 6c 61 6d 29 3b  rch(g, ro, lam);
0290: 0a 09 09 09 73 6f 72 74 21 28 28 54 75 70 6c 65  ....sort!((Tuple
02a0: 21 28 63 68 61 72 2c 69 6e 74 29 20 63 31 2c 20  !(char,int) c1, 
02b0: 54 75 70 6c 65 21 28 63 68 61 72 2c 69 6e 74 29  Tuple!(char,int)
02c0: 20 63 32 29 7b 0a 09 09 09 09 69 66 28 63 31 5b   c2){.....if(c1[
02d0: 31 5d 20 21 3d 20 63 32 5b 31 5d 29 0a 09 09 09  1] != c2[1])....
02e0: 09 09 72 65 74 75 72 6e 20 63 31 5b 31 5d 20 3c  ..return c1[1] <
02f0: 20 63 32 5b 31 5d 3b 0a 09 09 09 09 72 65 74 75   c2[1];.....retu
0300: 72 6e 20 63 31 5b 30 5d 20 3c 20 63 32 5b 30 5d  rn c1[0] < c2[0]
0310: 3b 0a 09 09 09 7d 29 28 63 61 6e 64 29 3b 0a 09  ;....})(cand);..
0320: 09 09 63 20 3d 20 63 61 6e 64 5b 30 5d 5b 30 5d  ..c = cand[0][0]
0330: 3b 0a 09 09 7d 0a 09 09 69 66 28 63 3d 3d 27 57  ;...}...if(c=='W
0340: 27 29 20 7b 0a 09 09 09 67 5f 77 63 2b 2b 3b 0a  ') {....g_wc++;.
0350: 09 09 09 69 66 28 67 5f 77 63 20 3e 20 31 30 29  ...if(g_wc > 10)
0360: 0a 09 09 09 09 63 20 3d 20 27 41 27 3b 0a 09 09  .....c = 'A';...
0370: 7d 0a 09 09 65 6c 73 65 0a 09 09 09 67 5f 77 63  }...else....g_wc
0380: 20 3d 20 30 3b 0a 09 09 72 65 74 75 72 6e 20 63   = 0;...return c
0390: 3b 0a 09 7d 0a 0a 09 54 75 70 6c 65 21 28 63 68  ;..}...Tuple!(ch
03a0: 61 72 2c 69 6e 74 29 20 73 65 61 72 63 68 28 69  ar,int) search(i
03b0: 6e 20 47 61 6d 65 20 67 2c 20 69 6e 20 50 6f 73  n Game g, in Pos
03c0: 20 73 2c 20 69 6e 20 50 6f 73 20 6f 29 0a 09 7b   s, in Pos o)..{
03d0: 0a 09 09 63 6f 6e 73 74 28 50 6f 73 29 5b 5d 20  ...const(Pos)[] 
03e0: 71 20 3d 20 5b 6f 5d 3b 0a 09 09 62 6f 6f 6c 5b  q = [o];...bool[
03f0: 5d 5b 5d 20 76 20 3d 20 6e 65 77 20 62 6f 6f 6c  ][] v = new bool
0400: 5b 5d 5b 5d 28 67 2e 6d 61 70 2e 48 2b 32 2c 20  [][](g.map.H+2, 
0410: 67 2e 6d 61 70 2e 57 2b 32 29 3b 0a 09 09 66 6f  g.map.W+2);...fo
0420: 72 28 69 6e 74 20 73 74 65 70 3d 31 3b 20 71 2e  r(int step=1; q.
0430: 6c 65 6e 67 74 68 3b 20 2b 2b 73 74 65 70 29 20  length; ++step) 
0440: 7b 0a 09 09 09 50 6f 73 5b 5d 20 71 32 3b 0a 09  {....Pos[] q2;..
0450: 09 09 66 6f 72 65 61 63 68 28 70 3b 20 71 29 20  ..foreach(p; q) 
0460: 7b 0a 09 09 09 09 69 6e 74 5b 5d 20 64 79 3d 5b  {.....int[] dy=[
0470: 2d 31 2c 2b 31 2c 30 2c 30 5d 3b 0a 09 09 09 09  -1,+1,0,0];.....
0480: 69 6e 74 5b 5d 20 64 78 3d 5b 30 2c 30 2c 2d 31  int[] dx=[0,0,-1
0490: 2c 2b 31 5d 3b 0a 09 09 09 09 66 6f 72 28 69 6e  ,+1];.....for(in
04a0: 74 20 69 3d 30 3b 20 69 3c 34 3b 20 2b 2b 69 29  t i=0; i<4; ++i)
04b0: 20 7b 0a 09 09 09 09 09 69 6e 74 20 79 20 3d 20   {......int y = 
04c0: 70 2e 79 2b 64 79 5b 69 5d 3b 0a 09 09 09 09 09  p.y+dy[i];......
04d0: 69 6e 74 20 78 20 3d 20 70 2e 78 2b 64 78 5b 69  int x = p.x+dx[i
04e0: 5d 3b 0a 09 09 09 09 09 69 66 28 76 5b 79 5d 5b  ];......if(v[y][
04f0: 78 5d 29 20 63 6f 6e 74 69 6e 75 65 3b 0a 09 09  x]) continue;...
0500: 09 09 09 69 66 28 79 3d 3d 73 2e 79 20 26 26 20  ...if(y==s.y && 
0510: 78 3d 3d 73 2e 78 29 20 7b 0a 09 09 09 09 09 09  x==s.x) {.......
0520: 69 66 28 69 3d 3d 30 29 20 72 65 74 75 72 6e 20  if(i==0) return 
0530: 74 75 70 6c 65 28 27 55 27 2c 73 74 65 70 29 3b  tuple('U',step);
0540: 0a 09 09 09 09 09 09 69 66 28 69 3d 3d 31 29 20  .......if(i==1) 
0550: 72 65 74 75 72 6e 20 74 75 70 6c 65 28 27 44 27  return tuple('D'
0560: 2c 73 74 65 70 29 3b 0a 09 09 09 09 09 09 69 66  ,step);.......if
0570: 28 69 3d 3d 32 29 20 72 65 74 75 72 6e 20 74 75  (i==2) return tu
0580: 70 6c 65 28 27 52 27 2c 73 74 65 70 29 3b 0a 09  ple('R',step);..
0590: 09 09 09 09 09 69 66 28 69 3d 3d 33 29 20 72 65  .....if(i==3) re
05a0: 74 75 72 6e 20 74 75 70 6c 65 28 27 4c 27 2c 73  turn tuple('L',s
05b0: 74 65 70 29 3b 0a 09 09 09 09 09 7d 20 65 6c 73  tep);......} els
05c0: 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d  e if(g.map[y,x]=
05d0: 3d 27 20 27 7c 7c 67 2e 6d 61 70 5b 79 2c 78 5d  =' '||g.map[y,x]
05e0: 3d 3d 27 5c 5c 27 29 20 7b 0a 09 09 09 09 09 09  =='\\') {.......
05f0: 71 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c  q2 ~= new Pos(y,
0600: 78 29 3b 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78  x);.......v[y][x
0610: 5d 3d 74 72 75 65 3b 0a 09 09 09 09 09 7d 20 65  ]=true;......} e
0620: 6c 73 65 20 69 66 28 67 2e 6d 61 70 5b 79 2c 78  lse if(g.map[y,x
0630: 5d 3d 3d 27 2e 27 20 26 26 20 67 2e 6d 61 70 5b  ]=='.' && g.map[
0640: 79 2d 31 2c 78 5d 21 3d 27 2a 27 29 20 7b 0a 09  y-1,x]!='*') {..
0650: 09 09 09 09 09 71 32 20 7e 3d 20 6e 65 77 20 50  .....q2 ~= new P
0660: 6f 73 28 79 2c 78 29 3b 0a 09 09 09 09 09 09 76  os(y,x);.......v
0670: 5b 79 5d 5b 78 5d 3d 74 72 75 65 3b 0a 09 09 09  [y][x]=true;....
0680: 09 09 7d 0a 09 09 09 09 7d 0a 09 09 09 7d 0a 09  ..}.....}....}..
0690: 09 09 71 20 3d 20 71 32 3b 0a 09 09 7d 0a 09 09  ..q = q2;...}...
06a0: 71 20 3d 20 5b 6f 5d 3b 0a 09 09 76 20 3d 20 6e  q = [o];...v = n
06b0: 65 77 20 62 6f 6f 6c 5b 5d 5b 5d 28 67 2e 6d 61  ew bool[][](g.ma
06c0: 70 2e 48 2b 32 2c 20 67 2e 6d 61 70 2e 57 2b 32  p.H+2, g.map.W+2
06d0: 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 73 74 65  );...for(int ste
06e0: 70 3d 31 30 30 30 3b 20 71 2e 6c 65 6e 67 74 68  p=1000; q.length
06f0: 3b 20 2b 2b 73 74 65 70 29 20 7b 0a 09 09 09 50  ; ++step) {....P
0700: 6f 73 5b 5d 20 71 32 3b 0a 09 09 09 66 6f 72 65  os[] q2;....fore
0710: 61 63 68 28 70 3b 20 71 29 20 7b 0a 09 09 09 09  ach(p; q) {.....
0720: 69 6e 74 5b 5d 20 64 79 3d 5b 2d 31 2c 2b 31 2c  int[] dy=[-1,+1,
0730: 30 2c 30 5d 3b 0a 09 09 09 09 69 6e 74 5b 5d 20  0,0];.....int[] 
0740: 64 78 3d 5b 30 2c 30 2c 2d 31 2c 2b 31 5d 3b 0a  dx=[0,0,-1,+1];.
0750: 09 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b  ....for(int i=0;
0760: 20 69 3c 34 3b 20 2b 2b 69 29 20 7b 0a 09 09 09   i<4; ++i) {....
0770: 09 09 69 6e 74 20 79 20 3d 20 70 2e 79 2b 64 79  ..int y = p.y+dy
0780: 5b 69 5d 3b 0a 09 09 09 09 09 69 6e 74 20 78 20  [i];......int x 
0790: 3d 20 70 2e 78 2b 64 78 5b 69 5d 3b 0a 09 09 09  = p.x+dx[i];....
07a0: 09 09 69 66 28 76 5b 79 5d 5b 78 5d 29 20 63 6f  ..if(v[y][x]) co
07b0: 6e 74 69 6e 75 65 3b 0a 09 09 09 09 09 69 66 28  ntinue;......if(
07c0: 79 3d 3d 73 2e 79 20 26 26 20 78 3d 3d 73 2e 78  y==s.y && x==s.x
07d0: 29 20 7b 0a 09 09 09 09 09 09 69 66 28 69 3d 3d  ) {.......if(i==
07e0: 30 29 20 72 65 74 75 72 6e 20 74 75 70 6c 65 28  0) return tuple(
07f0: 27 55 27 2c 73 74 65 70 29 3b 0a 09 09 09 09 09  'U',step);......
0800: 09 69 66 28 69 3d 3d 31 29 20 72 65 74 75 72 6e  .if(i==1) return
0810: 20 74 75 70 6c 65 28 27 44 27 2c 73 74 65 70 29   tuple('D',step)
0820: 3b 0a 09 09 09 09 09 09 69 66 28 69 3d 3d 32 29  ;.......if(i==2)
0830: 20 72 65 74 75 72 6e 20 74 75 70 6c 65 28 27 52   return tuple('R
0840: 27 2c 73 74 65 70 29 3b 0a 09 09 09 09 09 09 69  ',step);.......i
0850: 66 28 69 3d 3d 33 29 20 72 65 74 75 72 6e 20 74  f(i==3) return t
0860: 75 70 6c 65 28 27 4c 27 2c 73 74 65 70 29 3b 0a  uple('L',step);.
0870: 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66 28 67  .....} else if(g
0880: 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 20 27 7c 7c  .map[y,x]==' '||
0890: 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 5c 5c 27  g.map[y,x]=='\\'
08a0: 29 20 7b 0a 09 09 09 09 09 09 71 32 20 7e 3d 20  ) {.......q2 ~= 
08b0: 6e 65 77 20 50 6f 73 28 79 2c 78 29 3b 0a 09 09  new Pos(y,x);...
08c0: 09 09 09 09 76 5b 79 5d 5b 78 5d 3d 74 72 75 65  ....v[y][x]=true
08d0: 3b 0a 09 09 09 09 09 7d 20 65 6c 73 65 20 69 66  ;......} else if
08e0: 28 67 2e 6d 61 70 5b 79 2c 78 5d 3d 3d 27 2e 27  (g.map[y,x]=='.'
08f0: 2f 2a 20 26 26 20 67 5b 79 2d 31 2c 78 5d 21 3d  /* && g[y-1,x]!=
0900: 27 2a 27 2a 2f 29 20 7b 0a 09 09 09 09 09 09 71  '*'*/) {.......q
0910: 32 20 7e 3d 20 6e 65 77 20 50 6f 73 28 79 2c 78  2 ~= new Pos(y,x
0920: 29 3b 0a 09 09 09 09 09 09 76 5b 79 5d 5b 78 5d  );.......v[y][x]
0930: 3d 74 72 75 65 3b 0a 09 09 09 09 09 7d 0a 09 09  =true;......}...
0940: 09 09 7d 0a 09 09 09 7d 0a 09 09 09 71 20 3d 20  ..}....}....q = 
0950: 71 32 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e  q2;...}...return
0960: 20 74 75 70 6c 65 28 27 57 27 2c 20 69 6e 74 2e   tuple('W', int.
0970: 6d 61 78 29 3b 0a 09 7d 0a 7d 0a                 max);..}.}.