import java.awt.*;
import java.util.*;
import java.awt.event.*;
import java.applet.Applet;

public class proj3 extends java.applet.Applet 
{
	ShowPanel showp;
    Controls control;
	Label status;

    public void init() {
 		status=new Label ("Add wall with the mouse.        ");
		showp=new ShowPanel(status);
		control = new Controls(showp);
		setLayout(new BorderLayout());
		add("Center", showp);
		add("South", control);
		add("North",status);
    }

    public void destroy() {
        remove(showp);
        remove(control);
    }

    public static void main(String args[]) {
        Frame f = new Frame("Proj3");
        proj3 project = new proj3();
        project.init();
        f.add("Center", project);
        f.setSize(500, 300);
        f.show();
    }
    public String getAppletInfo() {
        return "Reinforcement learning.By Adrian Barbu.";
    }
}

class ShowPanel extends Panel implements MouseListener, MouseMotionListener, Runnable {
	Label status;
	Thread t;
	Point cp=new Point (0,0),oldcp=cp; //current position
	int h=20,w=30,method=1, stepx,stepy,border=5,n=200,ntries=0;
	int T[][]=new int[w][h];  //memorises the table and the reards and walls
	double[][][] Q=new double[w][h][4]; //the Q function 
	double[][][] R=new double[w][h][4]; //memorizes the rewards for the 
	//actions done so far
	Vector V=new Vector();
	double alpha=0.99,temp=0.5;
	boolean drawcp=false, showint=true;
	
    public ShowPanel(Label status) {
		int i,j,k;
		this.status =status;
        setBackground(Color.lightGray );
        addMouseMotionListener(this);
        addMouseListener(this);
		t = new Thread(this);	
		stepx=(getSize().width-2*border)/w;
		stepy=(getSize().height-2*border)/h;
		resetT();
    }
	public void resetT(){// Resets the table to 0
		int i,j;
		for (j=0;j<h;j++)
			for (i=0;i<w;i++)
					T[i][j]=0;	

	}
	public void resetQ(){ //Resets the Q function to 0
		int i,j,k;
		for (j=0;j<h;j++)
			for (i=0;i<w;i++)
				for (k=0;k<4;k++)
						Q[i][j][k]=0;	
	}
	public void resetR(){ //Resets the stored rewards R to -1000
		int i,j,k;
		ntries=0;
		for (j=0;j<h;j++)
			for (i=0;i<w;i++)
				for (k=0;k<4;k++)
						R[i][j][k]=-1000;	
	}
	public void setDrawMode(int mode) {
    }
    public void mousePressed(MouseEvent e) {
		Point pt=e.getPoint ();
		boolean changed=false;
		int x=(pt.x-border)/stepx,y=(pt.y-border)/stepy;
		x=Math.min (x,w-1);y=Math.min (y,h-1);
		if ((method==1)&&(T[x][y]!=-1)){T[x][y]=-1;changed=true;}//wall
		if ((method==2)&&(T[x][y]!=2)) {T[x][y]=2;changed=true;}//reward
		if ((method==3)&&(T[x][y]!=3)) {T[x][y]=3;changed=true;}//neg rew.
		if ((method==4)&&(T[x][y]!=0)) {T[x][y]=0;changed=true;}//delete
		if (method==6){ //show path towards reward
			cp=new Point (x,y);
			t = new Thread(this);
			t.start();
		}
		if (changed) refresh(new Point (x,y));
	}
    public void mouseDragged(MouseEvent e) {
		Point pt=e.getPoint ();
		boolean changed=false;
		int x=(pt.x-border)/stepx,y=(pt.y-border)/stepy;
		x=Math.min (x,w-1);y=Math.min (y,h-1);
		if ((method==1)&&(T[x][y]!=-1)){T[x][y]=-1;changed=true;}//wall
		if ((method==2)&&(T[x][y]!=2)) {T[x][y]=2;changed=true;}//reward
		if ((method==3)&&(T[x][y]!=3)) {T[x][y]=3;changed=true;}//neg rew.
		if ((method==4)&&(T[x][y]!=0)) {T[x][y]=0;changed=true;}//delete
		if (changed) refresh(new Point (x,y));
	}
    public void mouseReleased(MouseEvent e) {
    }
    public void mouseMoved(MouseEvent e) {
    }
    public void mouseEntered(MouseEvent e) {
    }
    public void mouseExited(MouseEvent e) {
    }
    public void mouseClicked(MouseEvent e) {
    }
	public double reward(Point s){ 
		//the reward for arriving at position s
		int i=s.x,j=s.y;
		if (T[i][j]==2) return  10;
		if (T[i][j]==3) return -10;
		else return 0;
	}
	public double max(double[] a,int ne){ 
		//finds the max of an array a of length ne of positive numbers 
		double m=0;
		for(int k=0;k<ne;k++)
			if(a[k]>m) m=a[k];				
		return m;
	}
	public void delay(int t){//delays the process t miliseconds
		try {
		    Thread.currentThread().sleep(t);
		} catch (InterruptedException e) {}
	}
	public int pi(Point s){ //the action that is taken at s given Q
		//go randomly in one of the directions, with bigger probability
		//for bigger value of Q
		int i=s.x,j=s.y,k;
		double sum=0,x;
		for (k=0;k<4;k++) sum=sum+Math.exp(Q[i][j][k]/temp);
		x=Math.random ()*sum;
		sum=0;
		for (k=0;k<4;k++){
			sum=sum+Math.exp(Q[i][j][k]/temp);
			if (x<sum) return k;
		}
		return 0;
	}
	public int strategy(Point s){
		//the strategy of exploration. From a point, do an action not done yet 
		//at that point. if all actions have been done, do the pi action
		int i=s.x,j=s.y,a,na=0;
		double x;
		int[] av=new int[4];
		for (a=0;a<4;a++)
			if (R[i][j][a]==-1000){
				av[na]=a;na++;
			}
		x=Math.random ()*na;
		for (a=1;a<=na;a++)
			if (x<a) return av[a-1];
		return pi(s);
	}
	public Point rndPoint(){
		//gets a random point from the ones not visited yet
		int i,j,a;
		V.removeAllElements ();
		for (i=0;i<w;i++)
			for(j=0;j<h;j++)
				if(T[i][j]==0)
					for(a=0;a<4;a++)
						if(R[i][j][a]==-1000){
							//add all points not entirely visited
							V.addElement (new Point (i,j));
							break;}
		if (V.size ()>0){
			i=(int)(Math.random ()*(V.size ()-1));
			return (Point) V.elementAt (i);
		}
		else return new Point (-1,-1);
	}
	public Point d(Point s,int a){ //the delta function 
		//tells the new state when action a is applied on state s.
		int i=s.x,j=s.y,k; 
		if ((T[i][j]==0)){
			if ((a==0)&&(j>0))
				if (T[i][j-1]>=0) return (new Point (i,j-1));
			if ((a==1)&&(i<w-1)) 
				if (T[i+1][j]>=0) return (new Point (i+1,j));
			if ((a==2)&&(j<h-1)) 
				if (T[i][j+1]>=0) return (new Point (i,j+1));
			if ((a==3)&&(i>0)) 
				if (T[i-1][j]>=0) return (new Point (i-1,j));
			return s;
		}
		else return s;		
	}
	public double r(Point s, int a){ 
		//the reward to do action a at point s
		int i=s.x,j=s.y;
		double m=R[i][j][a];
		if (m==-1000){//check first if action has been done already
			ntries++;
			Point p=d(s,a);
			m=reward(p);
			R[i][j][a]=m;
		}
		return m;
	}
	public void run(){
		int i,j;
		String s=new String ("  ");
		drawcp=true;
		if (method==6){ //if mouse is clicked on the table show path
			temp=0.04;  //towards the reward
			runonce(true,100);
		}
		if (method==5){//the  actual algorithm
			repaint();
			for (i=0;i<n;i++){
				status.setText ("Trial "+s.valueOf (i+1));
				temp=1/Math.sqrt(i+2);
				cp=rndPoint ();drawcp=true;
				if (cp.x==-1) break;
				runonce(showint,5);
				for (j=0;j<30;j++) minimizer(); //get the most out of
				//the actions done so far
			}
			drawcp=false;temp=0.04;
			status.setText ("Done in "+s.valueOf (i)+" tries. Click mouse to see the path to reward.");
			repaint();
			method=6;
		}
	}
	public void runonce(boolean paint, int t){ 
		//does one search for the reward, starting from cp
		int a,k;
		boolean more;
		Point s1;
		V.removeAllElements ();
		refresh(oldcp);delay(t);refresh(cp);delay(t);
		more=(T[cp.x][cp.y]==0);
		for(k=0;more&&(k<1000);k++){
			//we first find a path to the reward, 
			if (T[cp.x][cp.y]==0){
				V.addElement (cp);//memorize the path
				a=strategy(cp);
				s1=d(cp,a);
				cp=s1;
				if (paint){refresh(oldcp);refresh(cp);delay(t);}			   
			}
			if (T[cp.x][cp.y]>0){ //we reached the reward
				more=false;}
		}
		for (k=V.size ()-1;k>=0;k--){
			//go backwards,do all actions on the path and update Q
			s1=(Point) V.elementAt (k);
			for (a=0;a<4;a++)
					adjustQ(s1,a);		
		}
		if ((V.size()>0)&&(!paint)) cp=(Point)V.elementAt (0);
	}
	public boolean adjustQ(Point s, int a){
		//the iteration in Q learning
		//returns true if it has been modified, false otherwise
		Point s1=d(s,a); 
		double x=r(s,a)+alpha*max(Q[s1.x][s1.y],4);
		if (Q[s.x][s.y][a]!=x) {Q[s.x][s.y][a]=x;refresh(s);return true;}
		else return false;
	}
	public void minimizer(){
		// adjust once all entries of Q for which the reward is known
		int i,j,a,k;
		for(i=0;i<w;i++)
			for(j=0;j<h;j++)
				for(a=0;a<4;a++)
					if (R[i][j][a]>-1000)
						adjustQ(new Point (i,j),a);
	}
	public void refresh(Point p){
		//refresh just the rectangle corresponding to point p
		repaint(border+p.x*stepx,border+p.y*stepy,stepx,stepy);
	}
    public void paint(Graphics g) {
		int i,j,k,xc,yc,a,xr,wr,yr,hr;
		double m;
		double[] l=new double[4];
		Rectangle r=g.getClipBounds ();
		g.setColor (Color.darkGray );
		stepx=(getSize().width-2*border)/w;
		stepy=(getSize().height-2*border)/h;
		xr=(r.x-border)/stepx;yr=(r.y-border)/stepy;
		//get the bounds for the elements corresp to the clipping rectangle
		wr=Math.min(xr+r.width /stepx,w);hr=Math.min(yr+r.height /stepy,h);
		for (i=xr;i<=wr;i++) //paint vert lines
			g.drawLine (border+i*stepx,border,border+i*stepx,border+h*stepy);
		for (j=yr;j<=hr;j++) //paint horz lines
			g.drawLine (border,border+j*stepy,border+w*stepx,border+j*stepy);
		for (i=xr;i<wr;i++)  
			for (j=yr;j<hr;j++){
				if(T[i][j]==-1){ //paint walls
					g.setColor (Color.gray );
					g.fill3DRect(border+i*stepx,border+j*stepy,stepx,stepy,true);
				}
				if(T[i][j]==2){ //paint 
					g.setColor (Color.red );
					g.fill3DRect(border+i*stepx+2,border+j*stepy+2,stepx-3,stepy-3,false);
				}
				if(T[i][j]==3){
					g.setColor (Color.blue);
					g.fill3DRect(border+i*stepx+2,border+j*stepy+2,stepx-3,stepy-3,false);
				}
					
			}
		if (drawcp){
			g.setColor (Color.yellow );
			g.fillRect(border+cp.x*stepx+stepx/2-5,border+cp.y*stepy+stepy/2-5,10,10);
		}
		g.setColor (Color.gray);
		for (i=xr;i<wr;i++)
			for (j=yr;j<hr;j++)
				if(T[i][j]==0){
					xc=border+i*stepx+stepx/2;
					yc=border+j*stepy+stepy/2;
					m=0;a=-1;
					for (k=0;k<4;k++){
						l[k]=2*Math.exp(Q[i][j][k]/temp);
						if (m<l[k]){ m=l[k];a=k;};
					}
					for (k=0;k<4;k++)l[k]=4*l[k]/m;
					g.drawLine (xc,yc,xc,yc-(int)l[0]);
					g.drawLine (xc,yc,xc+(int)l[1],yc);
					g.drawLine (xc,yc,xc,yc+(int)l[2]);
					g.drawLine (xc,yc,xc-(int)l[3],yc);
				}
		oldcp=cp;
	}
}

class Controls extends Panel implements ActionListener {
	ShowPanel showp;
	Button b1,b2,b3,b4,b5,b6,b7,b8;
	Label l1,l2,l3;
	Checkbox c;
	TextField a,n;
    public Controls(ShowPanel showp) {
		this.showp=showp;
        setLayout(new GridLayout(2,7));
		setBackground(Color.lightGray);
		l1=new Label ("                     Alpha=");
		l2=new Label ("                   N.trials=");
		a=new TextField ("0.99",4);
		n=new TextField ("200",4);
		c=new Checkbox("Show interm.", null, true);
		l3=new Label ("    position ");
		add(l1);
		add(a);
		add(c);
		b1 = new Button("Add Wall");
		b1.setForeground(Color.black);
		add(b1);
		b1.addActionListener (this);
		b2 = new Button("Add Reward");
		add(b2);
		b2.addActionListener (this);
		b2.setForeground(Color.red);
		b3 = new Button("Add Neg Reward");
		add(b3);
		b3.addActionListener (this);
		b3.setForeground(Color.blue);
		b4 = new Button("Delete");
		add(b4);
		b4.addActionListener (this);
		b4.setForeground(Color.black);
		add(l2);
		add(n);
		add(l3);
		b5 = new Button("Clear");
		add(b5);
		b5.addActionListener (this);
		b5.setForeground(Color.black);
		b6 = new Button("Fig.1");
		add(b6);
		b6.addActionListener (this);
		b6.setForeground(Color.black);
		b7 = new Button("Random Fig.");
		add(b7);
		b7.addActionListener (this);
		b7.setForeground(Color.black);
		b8 = new Button("Start");
		add(b8);
		b8.addActionListener (this);
		b8.setForeground(Color.black);
    }

    public void paint(Graphics g) {
        Rectangle r = getBounds();
		g.setColor(Color.lightGray);
        g.draw3DRect(0, 0, r.width-1, r.height-1, true);
    }
	public void actionPerformed(ActionEvent e) {
	Object src = e.getSource();
	if (src == b1) {
		showp.method=1; //Wall
		showp.drawcp =false;
		showp.status.setText ("Add wall with the mouse.");
	}  
	if (src == b2) {
		showp.method=2; //Reward
		showp.drawcp =false;
		showp.status.setText ("Add positive reward with the mouse.");
	}  
	if (src == b3) {
		showp.method=3;  //Neg. Reward
		showp.drawcp =false;
		showp.status.setText ("Add negative reward with the mouse.");
	}  
	if (src == b4) {
		showp.method=4;  //Delete
		showp.drawcp =false;
		showp.status.setText ("Delete objects with the mouse.");
	}  
	if (src == b5) {
		showp.resetT(); //Clear
		showp.resetQ();
		showp.drawcp =false;
		showp.status.setText ("Add wall elements with the mouse.");
		showp.method =1;
		if (showp.t.isAlive ()){showp.t.stop() ;}
		showp.repaint ();
	}
	if (src == b6) {   //Fig 1
		showp.resetT();
		showp.resetQ();
		showp.resetR();
		showp.drawcp =false;
		showp.status.setText ("Add wall elements with the mouse.");
		showp.method =1;
		showp.T[4][showp.h/2]=3;showp.T[25][showp.h/2]=2;
		showp.T[15][8]=-1;showp.T[16][8]=-1;
		showp.T[15][9]=-1;showp.T[16][9]=-1;
		showp.T[15][10]=-1;showp.T[16][10]=-1;
		showp.T[15][11]=-1;showp.T[16][11]=-1;
		showp.T[15][12]=-1;showp.T[16][12]=-1;
		if (showp.t.isAlive ()){showp.t.stop() ;}
		showp.repaint ();
	}
	if (src == b7) {  //Random Figure
		showp.resetT();
		showp.resetQ();
		showp.resetR();
		showp.drawcp =false;
		showp.status.setText ("Add wall elements with the mouse.");
		showp.method =1;
		int n=(int)(Math.random()*100);
		int i,k,j,w=showp.w,h=showp.h;
		for (k=0;k<n;k++){
			i=(int)(Math.random()*(w-1));
			j=(int)(Math.random()*(h-1));
			showp.T[i][j]=-1;
		}
		n=(int)(Math.random()*15);
		for (k=0;k<n;k++){
			i=(int)(Math.random()*(w-1));
			j=(int)(Math.random()*(h-1));
			showp.T[i][j]=3;
		}
		i=(int)(Math.random()*(w-1));
		j=(int)(Math.random()*(h-1));
		showp.T[i][j]=2;
		if (showp.t.isAlive ()){showp.t.stop() ;}
		showp.repaint ();
	}
	if (src == b8) { //Run
		showp.method =5;
		showp.resetQ();
		showp.resetR();
		showp.drawcp =false;
		Double d=new Double(a.getText ());
		showp.alpha =d.doubleValue ();
		d=d.valueOf (n.getText ());
		showp.n =d.intValue ();showp.showint =c.getState ();
		if (showp.t.isAlive ()){showp.t.stop() ;}
		showp.t = new Thread(showp);
        showp.t.start();
	}  
  }
}