import java.awt.*;

public class Mars extends Thread {
	// implement the classes that Robot sees: Sensor, DiagnosticPanel, Motor
	// most of the methods simply call synchronized methods from Mars --
	// indeed, almost all the Mars methods are synchronized, to maintain
	// consistency


	private class MySensor extends Sensor {
		private int val;
		public int value() {
			return val;
		}
	}
        
	private class MyDiagnosticPanel extends DiagnosticPanel {
		public void registerPlan(int s, int[] col, int[] row) { 
			regPlan(s,col,row);
			// sleep to give plan a chance to be seen on screen?
			// try { sleep(10); } catch     (InterruptedException e) { }
		}
		public void registerRock(int x, int y){
			regRock(x,y);
		}
	}

	private class MyMotor extends Motor {

		// x,y are from Motor, mx,my from Mars
		public MyMotor() {
			x = mx;
			y = my;
		}

		public void move(int direction) {
			mymove(direction);
		}
	
		public int clock() {
			// sleep, to reduce load on processor (delay is from Mars)
			try {
				sleep(Math.max(1,delay));
			} catch (InterruptedException e) { }
                        
			return theclock; // theclock is declared below
		}
	}


	// variables and methods for moving motor

	private int threshold = 0;				// tick *just* after motor compltes a move
	private boolean wantmove = false;		// = "motor trying to move?" 
	private int wantx, wanty;				// if wantmove, where motor wants to go
	private int theclock = 0;				// simulator's system clock

	synchronized private void mymove(int direction) {
		int numDirections = 4; // could be 8
		if (wantmove) {
			System.out.println("Motor moved too soon -- still doing old move!");
			return;
		}
		// fancy encoding of directions: i-th bits for i-th direction,
		// where x, y are positive offsets, X,Y are negative offsets,
		// and bits are labeled "IBM-style" in a byte
		int y = 128 + 8 + 1, Y = 16 + 4 + 2;
		int x = 64 + 8 + 2, X = 32 + 4 + 1;
		if (direction<0 || direction >= numDirections)
			throw new RuntimeException("Illegal direction " + direction);
		direction = 7-direction;
		wantx = mx.val + ((x>>direction) & 1) - ((X>>direction) & 1);
		wanty = my.val + ((y>>direction) & 1) - ((Y>>direction) & 1);
		threshold = theclock + 5;
		wantmove = true;
	}

	// variables and methods for diagnostic panel
	// current plan is in plans[whichPlan][0..steps[whichPlan]][0..1]
	// previous plan is in plans[1-whichPlan][0..steps[1-whichPlan]][0..1]
        
	private int[][][] plans;
	private int[] steps = { 0, 0 };
	private int whichPlan = 0;
        
	// register rock: do extensive error-checking
	synchronized private void regRock(int x, int y){
		if (y<0 || y>known.length || x<0 || x>known[0].length)
			System.out.println("Bad rock location "+ x + " " + y);
		else if (y==0 || x==0 || y==known.length-1 || x==known[0].length)
			; // ok to register rocks on boundary
		else if (x != bumpx || y != bumpy)
			if (bumpx == -1)
				System.out.println
					("Tried to register a rock without bumping into any");
			else
				System.out.println("Tried to register " + x + " "
								   + y + " as a rock instead of the rock " +
								   "bumped into at " + bumpx + " " + bumpy);
			else if (known[y][x])
				System.out.println("Tried to re-register rock at " + x + " " + y);
			else if (!grid[y][x])
				System.out.println("Tried to register non-existent rock at " + x + " " + y);
			else
				known[y][x] = true;
	}

	// register plan: save plan, erase old, draw new/current plan
	synchronized private void regPlan(int s, int[] col, int[] row) {
		int newPlan = 1-whichPlan; // toggle old vs new plans
		
		// copy/save new plan
		steps[newPlan] = s;
		for (int i = 0; i<=s; i++) {
			int size = i==0 ? 1 : Math.abs(col[i]-col[i-1])+Math.abs(row[i]-row[i-1]);
			if (size != 1)
				System.out.println("Bad planning step of size " + size + 
								   "!= 1 from " + col[i-1] + " " + row[i-1] + " to " +
								   col[i] + " " + row[i]);
			plans[newPlan][i][0] = row[i];
			plans[newPlan][i][1] = col[i];
		}
		Graphics g = myGraphics();
		drawPlan(g,true); // erase old plan
		whichPlan = newPlan; drawPlan(g,false); // draw new plan
	}


	public CUCSDrawing d; // drawing window
	public boolean bump; // whether to jiggle the world when robot bumps rocks
	public int delay; // delay between gnat's moves (animation speed)
	private boolean[][] grid; // = "is there a rock?", with a border of rocks
	private boolean[][] known; // = "does robot know (registered) this rock?"
	private int dx = 1, dy = 0; // current direction of gnat
	private int gnatrow, gnatcol; // location of gnat
	private MySensor gx = new MySensor(), gy = new MySensor(); // gnat sensors
	private MySensor mx = new MySensor(), my = new MySensor(); // motor sensors
	private int bumpx = -1, bumpy = 0; // last rock robot bumped into
	private MyMotor motor;
	private MyDiagnosticPanel panel;
	private Robot robot;
	public final static int pen = 8; // pen size to draw each element of grid

	// return the graphics context for drawing in Drawing window
	public Graphics myGraphics() {
		Graphics g = d.getGraphics();
		g.translate(d.getInsets().left-pen,d.getInsets().top-pen);
		return g;
	}

	// constructor: build Mars, robot
	public Mars(int size, CUCSDrawing dr, boolean bump, int delay) {
		super("Mars"); // get thread named and mostly set up
		this.delay = delay;
		this.bump = bump;
		d = dr;
		grid = new boolean[1+size+1][1+size+1];
		known = new boolean[1+size+1][1+size+1];
		plans = new int[2][size*10][2]; // *10 seems large enough for 50x50 grid
		int max = 1+size;
		
		// place rocks on border
		for (int i = 0; i<1+size+1; i++)
			grid[i][0] = grid[i][max] = grid[0][i] = grid[max][i] = true;
		
		// place rock formations: choose location (i,j), direction (dx,dy)
		// place down some random number/length l of rocks without going
		// outside the grid (pin at borders)
		int blocks = size*size/3;
		while (blocks>0) {
			int dx = 1, dy = 0;
			int i = (int) (Math.random()*size) + 1;
			int j = (int) (Math.random()*size) + 1;
	
			// rotate direction 90 degrees random number of times
			for (int d = (int)(Math.random()*4); d>0; d--) {
				int tmp = dx; dx = dy;
				dy = -tmp;
			}
			int l = (int) (Math.random()*10)+3;
			blocks -= l;
			for ( ; l>0; l--) {
				i = Math.min(size-1,Math.max(1,i+dy));
				j = Math.min(size-1,Math.max(1,j+dx));
				grid[i][j] = true;
			}
		}
		
		// in case robot moves diagonally, fill in corners "@" to prevent
		// robot from slipping through:
		//   # and #   become  @#  #
		//  #       #          #   @#
		for (int i = 1; i<size; i++)
			for (int j = 1; j<size; j++)
				grid[i][j] |= grid[i][j+1] &&
							  (grid[i+1][j] && !grid[i+1][j+1] ||
							   grid[i-1][j] && !grid[i-1][j+1]);
		// set up gnat and motor and diagnostic panel
		gy.val = gnatrow = 1; gx.val = gnatcol = 1;
		grid[gnatrow][gnatcol] = false; // make place for gnat
		mx.val = size/2; my.val = size/2;
		grid[my.val][mx.val] = false; // make place for Robot
		motor = new MyMotor();
		panel = new MyDiagnosticPanel();
		robot = new Robot(size, motor, gx,gy, panel);
	}
        
	// complete (re) draw grid element at (j,i)
	synchronized private void paintCell(Graphics g, int i, int j) {
		int x = j*pen, y = i*pen;
		if (grid[i][j]) {
			boolean unknown = !known[i][j];
			g.setColor(unknown && i == bumpy && j == bumpx ?
					   Color.red : unknown ? Color.green : Color.magenta);
			g.fillRect(x,y,pen,pen);
			if (unknown)
				g.clearRect(x+2,y+2,pen-4,pen-4);
		}
		else if (i == gnatrow && j == gnatcol)
			drawGnat(g);
		else if (i == my.val && j == mx.val) drawRobot(g);
		else g.clearRect(x,y,pen,pen);
	}

	// draw entire grid and also draw current plan
	synchronized public void paint(Graphics g) {
		for (int i = 1; i<grid.length-1; i++)
			for (int j = 1; j<grid[0].length-1; j++)
				paintCell(g,i,j);
		drawPlan(g,false);
	}
       
	// completely erase grid element at (j,i)
	synchronized private void erase(Graphics g, int i, int j) {
		g.clearRect(j*pen,i*pen,pen,pen);
	}
       
	// draw gnat
	synchronized private void drawGnat(Graphics g) {
		int x = gnatcol*pen, y = gnatrow*pen;
		g.clearRect(x,y,pen,pen);
		g.setColor(Color.black);
		g.fillOval(x+1,y+1,pen-2,pen-2);
	}
       
	// draw robot
	synchronized private void drawRobot(Graphics g) {
		int x = mx.val*pen, y = my.val*pen;
		g.clearRect(x,y,pen,pen);
		g.setColor(Color.blue);
		g.drawOval(x+1,y+1,pen-2,pen-2);
		g.drawOval(x+2,y+2,pen-4,pen-4);
	}
        
	// move and redraw gnat
	synchronized private void moveGnat() {
		double r = Math.random(); // help decide whether to go straight or turn

		// turn: 0 = straight, 1/-1 = left/right or vice versa: no matter
		int turn = 0; // as long as 1/-1 used consistently
		int x, y, count = 0; 

		// generally go straight, but randomly turn
		if (r<.15)
			turn = 1;
		else if (r>1-.15)
			turn = -1;

		// choose direction: if current direction hits a rock, keep turning
		// until find free space or give up.
		do {
			int tmp = dx;
			if (turn == 1) {
				dx = dy;
				dy = -tmp; 
			} 
			else if (turn == -1) {
				dx = -dy;
				dy = tmp;
			}
			x = gnatcol + dx;
			y = gnatrow + dy;
			if (turn == 0)
				if (Math.random()<.5)
					turn = 1;
				else
					turn = -1;
			count++;
		} while (grid[y][x] && count<4);
                
		// if won't hit rock, move gnat and redraw gnat
		// redraw robot if used to be on top of robot
		if (!grid[y][x]) {
			Graphics g = myGraphics();
			erase(g,gnatrow,gnatcol);
			gnatrow = y; gnatcol = x;
			drawGnat(g);
			if (y == my.val && x == my.val)
				drawRobot(g);
		}
	}

	// set gnat sensors to gnat location    
	synchronized private void senseGnat() {
		gx.val = gnatcol;
		gy.val = gnatrow;
	}
        
	// draw/erase robot's plan (erase = "erase?")
	synchronized private void drawPlan(Graphics g, boolean erase) {
		int[][] plan = plans[whichPlan];
		int steps = this.steps[whichPlan];
		g.setColor(erase ? Color.white : Color.black);
		g.translate(pen/2,pen/2);
		for (int i = 1; i<=steps; i++)
			g.drawLine(plan[i][1]*pen, plan[i][0]*pen,
					   plan[i-1][1]*pen, plan[i-1][0]*pen);
			g.translate(-pen/2,-pen/2);
			// if erase plan, then redraw cells underneath: still need to erase
			// lines (as above) since lines might go through corners of neighbor
			// cells (yes, this means neighbor cells can have missing pixels)
			if (erase) for (int i = 0; i<=steps; i++)
				paintCell(g,plan[i][0],plan[i][1]);
	}


	// move robot according to the move the motor specified (assume wantmove)
	synchronized private void moveRobot() {
		Graphics g = myGraphics();
		if (!grid[wanty][wantx]) {
			// no rock: can move and redraw robot
			erase(g,my.val,mx.val);
			mx.val = wantx; my.val = wanty;
			drawRobot(g);
		} else if (known[wanty][wantx])
			throw new RuntimeException("Bumped AGAIN into rock " + 
										wantx + " " + wanty);
		else {
			// bumped into rock: make sure previously bumped rock was registered
			if (bumpx!=-1 && !known[bumpy][bumpx])
				System.out.println("Forgot to register rock " + bumpx + " " + bumpy);
			// remember currently bumped rock
			bumpx = wantx; bumpy = wanty;

			// jiggle screen (if requested)
			if (bump) {
				int p = (pen+1)/2, tx = p*(wantx-mx.val);
				int ty = p*(wanty-my.val);
				g.translate(tx,ty); paint(g);
				g.translate(-tx, -ty); paint(g);
			}
			else
				paintCell(g,wanty,wantx);
		}
		wantmove = false;
	}


	// run simulator: move and sense gnat and move robot
	// NOT synchronized, since that would lock the robot out
	public void run() {
		try { sleep(1000); } catch (InterruptedException e) { }
			new Thread(robot,"Robot").start(); // start robot thread
		while (true) {
			moveGnat();
				
			// periodically sense gnat
			if (theclock % 17 == 0)
				senseGnat();
		
			// moveRobot at threshold-1 -- otherwise robot might see 
			// the clock = threshold and move before motor is ready
			if (theclock+1 == threshold && wantmove)
				moveRobot();
			theclock++;
			try { 
				sleep(delay);
			} catch (InterruptedException e) { }
		}
	}
}


// drawing window
public class CUCSDrawing extends Frame {
	public Mars mars;
	public CUCSDrawing(int size, boolean bump, int delay) {
		super();
		show(); // show; apparently needed to getInsets
		mars = new Mars(size,this,bump,delay);

		setSize(getInsets().left+getInsets().right+Mars.pen*size,
				getInsets().top+getInsets().bottom+Mars.pen*size);
		setBackground(Color.white);
	}
    
	public void paint(Graphics g) {
		if (mars != null)
			mars.paint(mars.myGraphics());
	}

	// update: don't erase, just Mars.paint, since that suffices
	public void update(Graphics g) {
		paint(g);
	}
}
  
// target class, with loop to read and reset bump, delay parameters
public class CUCSGraphicsApplication {
	final private static boolean bump = true;
	final private static int delay = 5;
	final private static int size = 50;
	public static void main(String[] args) {
		TokenReader in = new TokenReader(System.in);
		CUCSDrawing d = new CUCSDrawing(size,bump,delay);
		d.setLocation(0,75);
		d.setTitle("Drawing");
		d.toFront();
		d.mars.start(); // start mars thread
		while (true) {
			System.out.print("You may enter delay>=0:");
			//System.out.print
			//      ("You may enter delay>=0 and whether to bump (0=no,1=yes):");
			System.out.flush();
			d.mars.delay = Math.max(0,in.readInt());
			//d.mars.bump = in.readInt() != 0;
		}
	}
}