// Written by Steve Butler
// last updated on 3 June 2009
//
// to use the program compile and from command line run
//   > java fourAP FILENAME n1 n2 n3 ...
// the program starts with an initial block coloring of
// n1 red, followed by n2 blue, followed by n3 red, ...
// it then perturbs first randomly and then back and forth
// sweeps until we get to a locally optimal coloring and
// then outputs the block structure to FILENAME.txt with
// under various modulos.  We then randomly flip ~40%
// of the colors and start over repeating the process
// 20 times
//
import java.math.*;
import java.lang.Integer;
import java.io.*;

public class fourAP {
	public static void main (String[] args){
		int length=0;
		String filename=args[0];
		int numBlocks=args.length-1;
		int counter=1;
// load the initial pattern
		for(int i=1; i<=numBlocks;i++){
			length=length+Integer.parseInt(args[i]);
		}
		int[] array=new int[length+2];
		int currentPosition=1; int currentColor=1;
		for(int i=1;i<=numBlocks;i++){
			for(int j=1; j<=Integer.parseInt(args[i]); j++){
				array[currentPosition]=currentColor;
				currentPosition++;
			}
			currentColor=1-currentColor;
		}

		int round=1,  iteration=0;
		long startingcount=countAPs(array,length);

		try{
			PrintStream out = new PrintStream(new FileOutputStream(filename+".txt"));
			out.println("Looks at perturbing coloring of interval length "+length);
			out.println("for minimizing monochromatic solutions of four term APs");
			out.println("");
			while(round<=20){  // 20 = number of rounds
				boolean trimmed=true;
				boolean skipRandom=false;
				while(trimmed==true){	
					trimmed=false;
					iteration++;
                    if(skipRandom==false){ // first update randomly
						int Rcounter=0;
						for(int tempi=1; tempi<=length; tempi++){
							int i=(int)((double)(length)*Math.random()+1);
							if(change(array,length,i)==true) { array[i]=1-array[i]; Rcounter++; }
						}
						if(Rcounter<length/1000){ skipRandom=true; } trimmed=true;
						System.out.print("."); // indicate end of a random round of updating
					}
					else{ // now do a sweep
						if(iteration%2==1){
							for(int i=1; i<=length; i++){
								if(change(array,length,i)==true) { array[i]=1-array[i]; trimmed=true; }
							}
						}
						else{
							for(int i=length; i>=1; i--){
								if(change(array,length,i)==true) { array[i]=1-array[i]; trimmed=true; }
							}
						}
					System.out.print("*"); // indicate end of a sweep round of updating
					}
				}
				int switches=1;
				for(int i=2; i<=length; i++){
					if(array[i]!=array[i-1]){ switches++; }
				}
				long numAPs=countAPs(array,length);
				System.out.println("");
				System.out.println("round "+round +": "+switches +"  (solutions: "+startingcount+" -> "+numAPs+")");

				out.println("Pattern for round "+round+" (uses "+switches+" blocks, has "+numAPs+" monochromatic solutions):");
				out.print("      ");
				int current=array[1]; int startoBlock=1;
				for(int i=2; i<=length; i++){
					if(array[i]!=current){
						out.print((i-startoBlock)+",");
						current=array[i];
						startoBlock=i;
					}
				}
				out.println(1+length-startoBlock);
				
				int[] skiparray=new int[length];
				for(int i=2; i<=5; i++){ // look at terms modular
					out.println("   Patterns from looking at terms modulo "+i+":");
					for(int j=0; j<i; j++){
						for(int k=1; k<length/i; k++){
							skiparray[k]=array[k*i-j];
						}
						current=skiparray[1];
						startoBlock=1;
						out.print("      ");
						for(int k=2; k<length/i; k++){
							if(skiparray[k]!=current){
								out.print((k-startoBlock)+",");
								current=skiparray[k];
								startoBlock=k;
							}
						}
						out.println(1+(length/i)-startoBlock);
					}
				}
				out.println("");
				
                for(int i=1; i<=length; i++){ // randomly flip ~40% of integers
					if(Math.random()<0.4){ array[i]=1-array[i]; }
				}
				startingcount=countAPs(array,length);
				round++; // now to the next round
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

// count the number of total 4APs	
	public static long countAPs(int[] array, int length){
		long runningCount=0;
		for(int i=1;i<=length-3;i++){
			for(int j=1;i+3*j<=length;j++){
				if(array[i]==array[i+j]&&array[i]==array[i+2*j]&&array[i]==array[i+3*j]){
					runningCount++;
				}
			}
		}
		return runningCount;
	}

// test if we should change the kth color
	public static boolean change(int[] array, int n, int k){
		int zerocount=0;
		int onecount=0;
		for(int i=1;i<=(n-k)/3;i++){
			if(array[k+i]==array[k+2*i]&&array[k+i]==array[k+3*i]){
				if(array[k+i]==0){ zerocount++; } else{ onecount++; }
			}
		}
		for(int i=1;i<=Math.min(k-1,(n-k)/2);i++){
			if(array[k-i]==array[k+i]&&array[k+i]==array[k+2*i]){
				if(array[k-i]==0){ zerocount++; } else{ onecount++; }
			}
		}
		for(int i=1;i<=Math.min((k-1)/2,n-k);i++){
			if(array[k-2*i]==array[k-i]&&array[k-i]==array[k+i]){
				if(array[k-2*i]==0){ zerocount++; } else{ onecount++; }
			}
		}
		for(int i=1;i<(k-1)/3;i++){
			if(array[k-3*i]==array[k-2*i]&&array[k-2*i]==array[k-i]){
				if(array[k-3*i]==0){ zerocount++; } else{ onecount++; }
			}
		}
		if((zerocount<onecount&&array[k]==1)||(onecount<zerocount&&array[k]==0)){ return true; } else { return false; }
	}
}