/* PrimeTriangle.java

   Routines to build "prime triangles" which are rows of numbers
   arranged such that each row is one longer than the preceeding row,
   and within each row the sum of any number and it's neighbor (right or left)
   is prime.  This is derived from code from Christopher Lane <cdl@best.com>.
   
   Rich Acuff <Rich@Dr-Amy.com>
   28-Sep-97
 */

import java.util.*;

public class PrimeTriangle {
    static boolean[] pCache = null;
    static final int pCacheSize = 64000;  //yeah, it should grow dynamically...
    myStack state = null;
    
    public PrimeTriangle () {
        if (pCache == null) {preComputePrimes(pCacheSize);}
        //state = new myStack (4000, 2000);
        if (state == null) state = new myStack ();
        state.clear();
    }
    
    public int[][] triangle (int rows) throws NoSolution {
        int[][] tri = new int[rows][];

        tri[0] = new int[1];
        tri[0][0] = 1;
        
        for (int i = 1; i < tri.length; i++) {
            tri[i] = nextRow(tri[i-1]);
        }
        return tri;
    }
    
/* Initial version, pretty much */
    public int[] nextRow(int[] prev) throws NoSolution {
        int[] array = new int[prev.length +1];
        int length = array.length;
        
        //The previous row is a good starting place, so copy it and tack on the next number
        for (int j = 0; j < (length - 1); j++) {
            array[j] = prev[j];
        }
        array[length - 1] = length;
        
        //shortcut: if the newly added number works ok as-is, take it
        if (!isPrime(array[length - 2] + length)) {
            if (!rearrange(array, 0)) {
                throw new NoSolution("No solution for row " + length);
            }
        }
        return array;
    } 

/* don't use the prev row as the starting place if it doesn't work out right away 
   RDA: empirically, this seems to take a lot of extra time over the long haul.
    public int[] nextRow(int[] prev) throws NoSolution {
        int[] array = new int[prev.length +1];
        int length = array.length;
        
        //shortcut: if the newly added number works ok as-is, take it
        if (isPrime(prev[length - 2] + length)) {
            for (int j = 0; j < (length - 1); j++) {
                array[j] = prev[j];
            }
            array[length - 1] = length;
        } else {  //make a new start
            for (int j = 0; j < length; j++) {
                array[j] = j + 1;
            }
            if (!rearrange(array, 0)) {
                throw new NoSolution("No solution for row " + length);
            }
        }
        return array;
   }   
*/

    public int[] row(int row_number) throws NoSolution {
        int[] array = new int[row_number];
        for (int j = 0; j < row_number; j++) {
            array[j] = j + 1;
        }
        return row(array);
    }
    
    public int[] row(int[] array) throws NoSolution {
        //assumes odds are next to evens
        if (array.length > 1) {
            if (!rearrange(array, 0)) {
                throw new NoSolution("No solution for row " + array.length);
            }
        }
        return array;        
    }
        
/* initial version 
    //Ensure the sum of all adjacent ints in array are prime, else return false
    boolean rearrange(int array[], int i) {     
        //Down to the last possiblity?
        if (i == (array.length - 2)) return isPrime(array[i] + array[i + 1]);

        for (int alternate = i + 1; alternate < (array.length - 1); alternate += 2) {
                if (!isPrime(array[i] + array[alternate])) continue;
                if (alternate > (i + 1)) {
                    swap (array, i + 1, alternate);
                }
                if (rearrange(array, i + 1)) return true;
        }
        return false;
    }
    */

/* "forward" version (RDA's rework of CDL's method)
      boolean rearrange(int array[], int i) {     
        //assumes all elements before i are ok and that odd is always next to even
        //Down to the last possiblity?
        if (i == (array.length - 2)) return isPrime(array[i] + array[i + 1]);

        for (int alternate = i + 1; alternate < (array.length - 1); alternate += 2) {
            if (isPrime(array[i] + array[alternate])) {
                if (alternate > (i + 1)) {
                    swap (array, i + 1, alternate);
                }
                if (rearrange(array, i + 1)) return true;
            }
        }
        return false;
    }
*/
    
    /* "backward" version 
    boolean rearrange(int array[], int i) {   
        //assumes all elements above i are ok and that odd is always next to even
        
        //Down to the last possiblity?
        if (i == 1) return isPrime(array[0] + array[1]);
        if (i == 0) {i = array.length - 1;} //default for backward compatibility

        for (int alternate = i - 1; alternate > 0; alternate -= 2) {
            if (isPrime(array[i] + array[alternate])) {
                if (alternate < (i - 1)) {
                    swap (array, i - 1, alternate);
                }
                if (rearrange(array, i - 1)) return true;
            }
        }
        return false;
    }
    
 */   
 
    /* "backward" version, non-recursive */
    boolean rearrange(int array[], int i) {   
        //assumes that odd is always next to even; ignores i for backward compatibility
        int current = array.length - 1;
        int alternate = current - 1;
        RState prev = new RState();
        state.clear();
        
        while (true) { 
            //to get here, everything higher must check out ok
            if (current == 1) {
                if (isPrime(array[0] + array[1])) return true; //done!
                //bummer; force a backtrack
                alternate = -1;
            }  
            if (alternate < 0) {  //ran out of options
                try {                               //backtrack
                    state.pop(prev);   //I long for multiple value returns
                    current = prev.current;
                    alternate = prev.alternate - 2;
                    continue;  //test again
                }
                catch (EmptyStackException e) {return false;}   //uh-oh
            } 
            if (isPrime(array[current] + array[alternate])) {  //got one!
                //swap if we have to
                if (alternate < (current - 1)) {
                    swap (array, current - 1, alternate);
                    //System.out.print(PrimeTriangleApplet.rowToString(array));
                }
                //remember this place
                state.push(current, alternate);
                //move on
                current--;
                alternate = current - 1;
            } else {
                alternate -= 2;  //try another
            }
        }
    }

    void swap (int[] array, int i, int j) {
        int x = array[i];
        array[i] = array[j];
        array[j] = x;
    }
    
    static void preComputePrimes (int upTo) {
        pCache = new boolean[(upTo + 1) / 2];
        for (int i = 3; i < (pCache.length * 2); i += 2) {
            pCache[i/2] = _isPrime(i);
        }
    }
    
    static void growPrimes() {
        boolean[] newP = new boolean[pCache.length + pCacheSize];
        System.arraycopy (pCache, 0, newP, 0, pCache.length -1);
        for (int i = pCache.length * 2; i < (newP.length * 2); i += 2) {
            newP[i/2] = _isPrime(i);
        }
        pCache = newP;
    }
    
    
    /* simple caching version */
    boolean isPrime(int number) {
        if (number == 2) return true;
        if ((number < 2) || (number % 2) == 0) return false;
        
        int i = number / 2;
        if (!(i < pCache.length)) growPrimes();
        return pCache[number / 2];
        /* bounds checking seems to be more expensive than the exception
        int i = number / 2;
        if (i < (pCache.length - 1)) {return pCache[i];}
        else {return _isPrime(number);}
        */
    }
  
    static boolean _isPrime(int number) {
        if (number == 2) return true;
        else if ((number < 2) || (number % 2) == 0) return false;

        for (int i = 3; (i * i) <= number; i += 2) {
            if ((number % i) == 0) return false;
        }

        return true;
    }
    
    public boolean verifyRow (int[] row) {
        int l = row.length - 1;
        for (int i = 0; i < l; i++) {
            if (!isPrime(row[i] + row[i + 1])) {return false;}
        }
        return true;
    }
}

class NoSolution extends Exception {
    public NoSolution() { super(); }
    public NoSolution(String s) { super(s); }
}

class RState {
    int current, alternate;
}

class myStack {
    int[] data;
    int top;
    static final int defaultSize = 16000;
    
    myStack (int initialSize) {
        data = new int[initialSize];
        top = -1;
    }
    
    myStack () {
        this(defaultSize);
    }
    
    public void push(int current, int alternate) {
        if ((top + 3) > data.length) grow();
        data[top + 1] = current;
        data[top + 2] = alternate;
        top += 2;
    }
            
    public void pop(RState r) {
        if (top < 1) throw new EmptyStackException();
        r.alternate = data[top];
        top--;
        r.current = data[top];
        top--;
    }

    public void peek(RState r) {
        if (top < 1) throw new EmptyStackException();
        r.alternate = data[top];
        r.current = data[top];    
    }
    public boolean empty() {
	    return top < 1;
    }
    
    public void clear() {
        top = -1;
    }
    
    private void grow() {
        int l = data.length + defaultSize;
        int[] newData = new int[l];
        System.arraycopy (data, 0, newData, 0, data.length - 1);
        data = newData;
    }
}