import java.util.*;
import java.lang.*;
import java.io.*;
import java.security.*;
import java.awt.image.*;
import java.awt.*;
import javax.imageio.*;

public class KnightsMoveCipher {
    String message;
    static String output;
    String cipher;
    int N;		//message is NxN characters long
    int len;
    int[] delta;
    SecureRandom r;
    void generate(String seed) {
        try {
            r = SecureRandom.getInstance("SHA1PRNG");
            r.setSeed(Long.parseLong(seed));

            //get the message to encode
            int start,len;
            FileInputStream fis = new FileInputStream("all.txt");
            byte[] b = new byte[100000000];
            int read = fis.read(b);

            //GET THE TEXT
            String[] texts = new String(b,0,read).split("\r\n");
            String text;
            do{
                text = texts[r.nextInt(texts.length)];
                text = text.replaceAll("[^a-zA-Z ]","").replaceAll(" +"," ").trim().toUpperCase();
            }while(text.length() < 25);
            //	String text = "TEST MESSAGE";


            /*	N = r.nextInt(16)+5;
                len = r.nextInt(2*N-1) + (N-1)*(N-1) + 1;	//message length between (N-1)^2 (not including) and N^2 (including)
                */
            len = r.nextInt(text.length()-24)+25;
            while(len < text.length() && text.charAt(len) != ' ') len++;
            N = (int)(Math.floor(Math.sqrt(len-1))+1);
            start = 0;//r.nextInt(text.length()-len);
            message = text.substring(start, start+len);
            System.out.println("Message = "+message);


            //do the encoding
            int row, col, nrow, ncol, d, maxd, i, j, n, dr, dc;
            char[][] grid;
            int[] empty = new int[4*N];
            int[] rr = new int[len];
            int[] cc = new int[len];
            boolean ok;
            do {
                ok = true;
                grid = new char[N][N];
                delta = new int[len-1];
                for (i=0; i<N; i++)
                    for (j=0; j<N; j++)
                        grid[i][j] = '.';
                //choose starting position
                row = r.nextInt(N);
                col = r.nextInt(N);
                for (i=0; i<len-1; i++) {
                    rr[i] = row;
                    cc[i] = col;
                    //put the current character of the message to the current cell
                    grid[row][col] = message.charAt(i);
                    //find max distance to a cell of the grid
                    maxd = Math.max(row, N-1-row) + Math.max(col, N-1-col);
                    //choose next cell
                    nrow = ncol = -1;
                    for (d=3; d<=maxd; d++) {
                        //with prob 0.2 continue to the next d immediately
                        if (r.nextDouble()<0.2) continue;
                        //build a set of cells which are at distance d from the current one 
                        //but not in the same row/col with it (it's a knight, after all)
                        n=0;
                        for (j=0; j<N; j++) {
                            //at most 2 cells in row j
                            dr = Math.abs(j-row);
                            if (dr>=d || j==row) continue;
                            dc = d-dr;
                            if (col-dc>=0 && grid[j][col-dc]=='.') {
                                //add cell (j,col-dc)
                                empty[2*n]=j;
                                empty[2*n+1]=col-dc;
                                n++;
                            }
                            if (col+dc<N && grid[j][col+dc]=='.') {
                                //add cell (j,col+dc)
                                empty[2*n]=j;
                                empty[2*n+1]=col+dc;
                                n++;
                            }
                        }
                        //no empty cells
                        if (n==0) continue;
                        //choose a random cell from the set
                        j = r.nextInt(n);
                        nrow = empty[2*j];
                        ncol = empty[2*j+1];
                        break;
                    }
                    if (nrow==-1)
                    {   //failed to generate a valid grid - repeat from the start
                        ok = false;
                        break;
                    }
                    //store dr+dc (to be given as a param)
                    delta[i] = Math.abs(row-nrow) + Math.abs(col-ncol);
                    //move
                    row = nrow;
                    col = ncol;
                }
                rr[len-1] = row;
                cc[len-1] = col;
                //last character
                grid[row][col] = message.charAt(len-1);
            } while (!ok);

            //if the text had spaces, replace them with '.' in the grid
            for (i=0; i<N; i++)
                for (j=0; j<N; j++)
                    if (grid[i][j]==' ') 
                        grid[i][j]='.';
            if(output != null){
                BufferedImage bi = new BufferedImage(N*20,N*20,BufferedImage.TYPE_INT_RGB);
                Graphics2D g = (Graphics2D)bi.getGraphics();
                g.setColor(Color.white);
                g.fillRect(0,0,N*20,N*20);
                g.setFont(new Font("Arial",Font.BOLD,16));
                FontMetrics fm = g.getFontMetrics();
                char[] ch = new char[1];
                for(i = 0; i<rr.length; i++){
                    g.setColor(new Color(Color.HSBtoRGB(0.8f*i/delta.length,1,1)));
                    g.fillRect(cc[i]*20,rr[i]*20,20,20);
                    //g.drawLine(rr[i]*20+10,cc[i]*20+10,rr[i+1]*20+10,cc[i+1]*20+10);
                }
                g.setColor(Color.black);
                for(i = 0; i<N; i++){
                    for(j = 0;j<N; j++){
                        ch[0] = grid[j][i];
                        g.drawChars(ch,0,1,i*20+10-fm.charWidth(ch[0])/2,j*20+10+fm.getHeight()/2);
                    }
                }
                ImageIO.write(bi,"png",new File(output+".png"));
            }
            //and in the original message
            message = message.replaceAll(" ",".");

            cipher = "";
            for (i=0; i<N; i++)
                cipher += new String(grid[i]);

            /*System.out.println("Grid");
              for (i=0; i<N; i++)
              System.out.println(new String(grid[i]));
              System.out.println();*/
            System.out.println("Ciphertext = "+cipher);
            System.out.print("Delta = ("+delta[0]);
            for (i=1; i<len-1; i++)
                System.out.print(","+delta[i]);
            System.out.println(")");

        }
        catch (Exception e) { e.printStackTrace(); }
    }
    // -----------------------------------------
    public double runTest(String seed) {
        try {
            generate(seed);
            //get the result
            String guess = decipher(cipher, delta);
            System.out.println("Your guess = "+guess);

            //check the 'A-'Z' rule
            for (int i=0; i<guess.length(); i++)
                if ((guess.charAt(i)<'A' || guess.charAt(i)>'Z') && guess.charAt(i)!='.')
                {	System.out.println("Your return contained illegal characters.");
                    return 0.0;
                }

            //score the result
            if (guess.length() != message.length())
            {   System.out.println("Your return was of incorrect length.");
                return 0.0;
            }
            char[] c1 = guess.toCharArray();
            char[] c2 = message.toCharArray();
            int i,j,m=0;
            int[][] lcs = new int[c1.length+1][c1.length+1];
            for (i=0; i<c1.length+1; i++)
                lcs[0][i] = lcs[i][0] = 0;
            for (i=1; i<c1.length+1; i++)
                for (j=1; j<c1.length+1; j++)
                    if (c1[i-1]==c2[j-1])
                    {	lcs[i][j]=lcs[i-1][j-1]+1;
                        m = Math.max(m,lcs[i][j]);
                    }
                    else lcs[i][j]=0;
            return m*1.0/c1.length;
        }
        catch (Exception e) { 
            System.err.println("An exception occurred while trying to get your program's results.");
            e.printStackTrace(); 
            return 0.0;
        }
    }
    // ------------- visualization part ------------
    static String exec;
    static Process proc;
    InputStream is;
    OutputStream os;
    // -----------------------------------------
    String decipher(String c, int[] d) throws IOException {
        StringBuffer sb = new StringBuffer();
        sb.append(c).append('\n');
        sb.append(d.length).append('\n');
        for (int i=0; i<d.length; i++)
            sb.append(d[i]).append('\n');
        os.write(sb.toString().getBytes());
        os.flush();
        BufferedReader br = new BufferedReader(new InputStreamReader(is));
        String ret = br.readLine();
        return ret;
    }
    // -----------------------------------------
    public KnightsMoveCipher(String seed) {
        //interface for runTest
        if (exec != null) {
            try {
                Runtime rt = Runtime.getRuntime();
                proc = rt.exec(exec);
                os = proc.getOutputStream();
                is = proc.getInputStream();
                new ErrorReader(proc.getErrorStream()).start();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        System.out.println("Score = "+runTest(seed));
    }
    // -----------------------------------------
    public static void main(String[] args) {
        String seed = "1";
        for (int i = 0; i<args.length; i++) {
            if (args[i].equals("-seed"))
                seed = args[++i];
            if (args[i].equals("-exec"))
                exec = args[++i];
            if (args[i].equals("-output"))
                output = args[++i];
        }
        KnightsMoveCipher f = new KnightsMoveCipher(seed);
    }
}

class ErrorReader extends Thread{
    InputStream error;
    public ErrorReader(InputStream is) {
        error = is;
    }
    public void run() {
        try {
            byte[] ch = new byte[50000];
            int read;
            while ((read = error.read(ch)) > 0)
            {   String s = new String(ch,0,read);
                System.out.print(s);
                System.out.flush();
            }
        } catch(Exception e) { }
    }
}

