/* * WormRule - Tim Tyler 2000. * * WormRule generates the transition rules for a reversible cellular automata * that supports self-replication. * * This code has been placed in the public domain. * This means that you can do what you like with it. * Please note that this code comes with no warranty. * */ /* * To Do: * */ // import java.util.Random; public class WormRule { final static int MAX_N = 8192; static int[] data1 = new int[MAX_N]; static int[] data2 = new int[MAX_N]; static int[] rotate = new int[MAX_N]; static boolean[] allocated = new boolean[MAX_N]; static JUR rnd = new JUR(); // 189 states in total (= 3 x 3 x 3 x 7)... // exterior cell states: final static int EMPTY = 0; final static int CARRY_ON = 1; final static int TURN_LEFT = 3; final static int TURN_RIGHT = 2; // interior cell states: final static int C_EMPTY = 0; final static int C_CARRY_ON = 1; final static int C_TURN_LEFT = 3; final static int C_TURN_RIGHT = 2; final static int nw_max = 4; final static int sw_max = 4; final static int e_max = 4; final static int c_nw_max = 4; final static int c_sw_max = 4; final static int c_e_max = 4; final static int TOTAL_STATES = e_max * sw_max * nw_max * c_nw_max * c_sw_max * c_e_max; final static int nw_sh = 0; final static int c_nw_sh = 2; final static int sw_sh = 4; final static int c_sw_sh = 6; final static int e_sh = 8; final static int c_e_sh = 10; final static int mask_nw = 3 << nw_sh; final static int mask_sw = 3 << sw_sh; final static int mask_e = 3 << e_sh; final static int c_mask_nw = 3 << c_nw_sh; final static int c_mask_sw = 3 << c_sw_sh; final static int c_mask_e = 3 << c_e_sh; final static int mask_centre = c_mask_nw | c_mask_sw | c_mask_e; static void makeRotate(boolean edges) { int idx; int new_nw = -1; int new_sw = -1; int new_e = -1; int new_c_nw = -1; int new_c_sw = -1; int new_c_e = -1; // take two clock ticks...! ;-) // blank... for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); if (edges) { rotate[idx] = 0; // (2 << c_sw_sh) | (2 << c_nw_sh) | (2 << c_e_sh); } else { rotate[idx] = (c_e << e_sh) | (c_sw << sw_sh) | (c_nw << nw_sh) | (e << c_sw_sh) | (sw << c_nw_sh) | (nw << c_e_sh); } } } } } } } } ///////////NEW RULE/////////////////// static void makeRule2() { int idx; int res; int new_nw = -1; int new_sw = -1; int new_e = -1; int new_c_nw = -1; int new_c_sw = -1; int new_c_e = -1; int split = 0; int merge = 0; // blank... for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); data2[idx] = -1; allocated[idx] = false; } } } } } } for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); //boolean active_splitter = isActiveSplitter(c_sw, c_nw, c_e); //boolean double_splitter = isDoubleSplitter(c_sw, c_nw, c_e); int temp; new_nw = nw; new_e = e; new_sw = sw; new_c_nw = c_nw; new_c_sw = c_sw; new_c_e = c_e; // flow along top of caterpillar tracks... if (c_sw == C_TURN_RIGHT) { temp = new_nw; new_nw = new_sw; new_sw = temp; } if (c_nw == C_TURN_RIGHT) { temp = new_e; new_e = new_nw; new_nw = temp; } if (c_e == C_TURN_RIGHT) { temp = new_sw; new_sw = new_e; new_e = temp; } // left turn... if (c_sw == C_TURN_LEFT) { temp = new_sw; new_sw = new_e; new_e = temp; } if (c_nw == C_TURN_LEFT) { temp = new_nw; new_nw = new_sw; new_sw = temp; } if (c_e == C_TURN_LEFT) { temp = new_e; new_e = new_nw; new_nw = temp; } // ...end of caterpillar section... data2[idx] = (new_sw << sw_sh) | (new_nw << nw_sh) | (new_e << e_sh) | (new_c_sw << c_sw_sh) | (new_c_nw << c_nw_sh) | (new_c_e << c_e_sh); } } } } } } Log.log("split" + split); Log.log("merge" + merge); makeIntoPermutation(data2); } static void makeRule1() { int idx; int res = -1; int new_nw = -1; int new_sw = -1; int new_e = -1; int new_c_nw = -1; int new_c_sw = -1; int new_c_e = -1; int up = 0; int down = 0; // blank... for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); data1[idx] = -1; allocated[idx] = false; } } } } } } for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); // boolean active_splitter = isActiveSplitter(c_sw, c_nw, c_e); // boolean double_splitter = isDoubleSplitter(c_sw, c_nw, c_e); int temp; new_nw = nw; new_e = e; new_sw = sw; new_c_nw = c_nw; new_c_sw = c_sw; new_c_e = c_e; // flow along top of caterpillar tracks... if (c_sw == C_TURN_RIGHT) { temp = new_nw; new_nw = new_sw; new_sw = temp; } if (c_nw == C_TURN_RIGHT) { temp = new_e; new_e = new_nw; new_nw = temp; } if (c_e == C_TURN_RIGHT) { temp = new_sw; new_sw = new_e; new_e = temp; } // left turn... if (c_sw == C_TURN_LEFT) { temp = new_sw; new_sw = new_e; new_e = temp; } if (c_nw == C_TURN_LEFT) { temp = new_nw; new_nw = new_sw; new_sw = temp; } if (c_e == C_TURN_LEFT) { temp = new_e; new_e = new_nw; new_nw = temp; } // ...end of caterpillar section... // deal with the case where a central cell needs to be lifted up... // if (nw == EMPTY) { // no incoming signal... if ((nw == EMPTY) && (sw == EMPTY) && (e == EMPTY)) { // no incoming signal... //if (c_nw != C_EMPTY) { if ((c_sw == C_EMPTY) && (c_nw != C_EMPTY) && (c_e == C_EMPTY)) { switch (c_nw) { case C_TURN_LEFT: temp = new_sw; new_sw = new_c_nw; new_c_nw = temp; break; case C_TURN_RIGHT: temp = new_e; new_e = new_c_nw; new_c_nw = temp; break; default: temp = new_nw; new_nw = new_c_nw; new_c_nw = temp; break; } // new_c_nw = C_EMPTY; up++; } //if ((nw == EMPTY) && (sw == EMPTY) && (e == EMPTY)){ // no incoming signal... // if (sw == EMPTY) { // no incoming signal... //if (c_sw != C_EMPTY) { if ((c_sw != C_EMPTY) && (c_nw == C_EMPTY) && (c_e == C_EMPTY)) { switch (c_sw) { case C_TURN_LEFT: temp = new_e; new_e = new_c_sw; new_c_sw = temp; break; case C_TURN_RIGHT: temp = new_nw; new_nw = new_c_sw; new_c_sw = temp; break; default: temp = new_sw; new_sw = new_c_sw; new_c_sw = temp; break; } // new_c_sw = C_EMPTY; up++; } //} //if (e == EMPTY) { // no incoming signal... // if (c_e != C_EMPTY) { if ((c_sw == C_EMPTY) && (c_nw == C_EMPTY) && (c_e != C_EMPTY)) { switch (c_e) { case C_TURN_LEFT: temp = new_nw; new_nw = new_c_e; new_c_e = temp; break; case C_TURN_RIGHT: temp = new_sw; new_sw = new_c_e; new_c_e = temp; break; default: temp = new_e; new_e = new_c_e; new_c_e = temp; break; } // new_c_e = C_EMPTY; up++; } } // deal with the case where an external cell needs to be placed down... // nothing there already... // if (c_sw == C_EMPTY) { if ((c_nw == C_EMPTY) && (c_sw == C_EMPTY) && (c_e == C_EMPTY)) { // no incoming signal... if ((sw != C_EMPTY) && (nw == C_EMPTY) && (e == C_EMPTY)) { //if (sw != EMPTY) { temp = new_sw; new_sw = new_c_sw; new_c_sw = temp; down++; } //} // if (c_nw == C_EMPTY) { //if ((c_nw == C_EMPTY) && (c_sw == C_EMPTY) && (c_e == C_EMPTY)){ // no incoming signal... //if (nw != EMPTY) { if ((sw == C_EMPTY) && (nw != C_EMPTY) && (e == C_EMPTY)) { temp = new_nw; new_nw = new_c_nw; new_c_nw = temp; down++; } //} // if (c_e == C_EMPTY) { //if ((c_nw == C_EMPTY) && (c_sw == C_EMPTY) && (c_e == C_EMPTY)){ // no incoming signal... //if (e != EMPTY) { if ((sw == C_EMPTY) && (nw == C_EMPTY) && (e != C_EMPTY)) { temp = new_e; new_e = new_c_e; new_c_e = temp; down++; } } data1[idx] = (new_sw << sw_sh) | (new_nw << nw_sh) | (new_e << e_sh) | (new_c_sw << c_sw_sh) | (new_c_nw << c_nw_sh) | (new_c_e << c_e_sh); } } } } } } // int e, int nw, int sw, int c_e, int c_nw, int c_sw, // applyAllRotationsOf(1,1,0,2,2,) Log.log("U:" + up); Log.log("D:" + down); // vacancies(data1); makeIntoPermutation(data1); } /////////////////// END NEW RULES /////////////////// /* static boolean isActiveSplitter(int a, int b, int c) { if ((a == C_TURN_RIGHT) && (b == C_EMPTY) && (c == C_EMPTY)) { return true; } if ((a == C_EMPTY) && (b == C_TURN_RIGHT) && (c == C_EMPTY)) { return true; } if ((a == C_EMPTY) && (b == C_EMPTY) && (c == C_TURN_RIGHT)) { return true; } return false; } static boolean isDoubleSplitter(int a, int b, int c) { if ((a == C_TURN_RIGHT) && (b == C_TURN_RIGHT) && (c == C_EMPTY)) { return true; } if ((a == C_EMPTY) && (b == C_TURN_RIGHT) && (c == C_TURN_RIGHT)) { return true; } if ((a == C_TURN_RIGHT) && (b == C_EMPTY) && (c == C_TURN_RIGHT)) { return true; } return false; } */ static boolean logging = false; static void makeIntoPermutation(int[] data) { Log.log("makeIntoPermutation"); int size = data.length; int val; int idx; int spare_slots = TOTAL_STATES; for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); allocated[idx] = false; } } } } } } // check (and set up) "allocated" table... for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); val = data[idx]; if (val != -1) { if (allocated[val]) { if (logging) { Log.log("PROBLEMS: nw:" + nw + " sw:" + sw + " e:" + e + " cnw:" + c_nw + " csw:" + c_sw + " ce:" + c_e); Log.log("...maps to: nw:" + ((val >> nw_sh) & 3) + " sw:" + ((val >> sw_sh) & 3) + " e:" + ((val >> e_sh) & 3) + " cnw:" + ((val >> c_nw_sh) & 3) + " csw:" + ((val >> c_sw_sh) & 3) + " ce:" + ((val >> c_e_sh) & 3) + "... which is taken."); values(val, data); } // Log.log("BY: nw:" + nw + " sw:" + sw + " e:" + e + " cnw:" + c_nw + " csw:" + c_sw + " ce:" + c_e); // + "nw:" + nw + "nw:" + nw + "nw:" + nw + " value duplicated:" + val); } else { allocated[val] = true; spare_slots--; // Log.log("Work done:" + val); } } else { if (logging) { Log.log("PROBLEM - blank!"); } } // Log.log("DUMP:" + idx + " value:" + val); } } } } } } vacancies(data); /* //while (spare_slots > 0) { for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); val = data[idx]; if (val == -1) { boolean found = false; do { int rv_nw = rnd.nextInt(nw_max) - 0; int rv_sw = rnd.nextInt(sw_max) - 0; int rv_e = rnd.nextInt(e_max) - 0; int rv_c = rnd.nextInt(c_max) - 0; // Log.log("SS:" + spare_slots); int idx2 = (rv_c << c_sh) | (rv_sw << sw_sh) | (rv_nw << nw_sh) | (rv_e << e_sh); if (!allocated[idx2]) { data[idx] = idx2; allocated[idx2] = true; spare_slots--; found = true; } } while (!found); } } } } } } } */ } static void vacancies(int[] data) { int unalloc = 0; for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { int idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); if (!allocated[idx]){ if (logging) { Log.log("UNALLOCATED: nw:" + nw + " sw:" + sw + " e:" + e + " cnw:" + c_nw + " csw:" + c_sw + " ce:" + c_e); } unalloc++; } } } } } } } Log.log("Unallocated: " + unalloc); } static void applyAllRotationsOf(int e, int nw, int sw, int c_e, int c_nw, int c_sw, int de, int dnw, int dsw, int dc_e, int dc_nw, int dc_sw, int[] data) { int idx; int val; idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); val = (dsw << sw_sh) | (dnw << nw_sh) | (de << e_sh) | (dc_sw << c_sw_sh) | (dc_nw << c_nw_sh) | (dc_e << c_e_sh); data[idx] = val; idx = (e << sw_sh) | (sw << nw_sh) | (nw << e_sh) | (c_e << c_sw_sh) | (c_sw << c_nw_sh) | (c_nw << c_e_sh); val = (de << sw_sh) | (dsw << nw_sh) | (dnw << e_sh) | (dc_e << c_sw_sh) | (dc_sw << c_nw_sh) | (dc_nw << c_e_sh); data[idx] = val; idx = (nw << sw_sh) | (e << nw_sh) | (sw << e_sh) | (c_nw << c_sw_sh) | (c_e << c_nw_sh) | (c_sw << c_e_sh); val = (dnw << sw_sh) | (de << nw_sh) | (dsw << e_sh) | (dc_nw << c_sw_sh) | (dc_e << c_nw_sh) | (dc_sw << c_e_sh); data[idx] = val; } static void values(int v, int[] data) { int idx; int val; for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); val = data[idx]; if (v == val) { Log.log(" ...by: nw:" + nw + " sw:" + sw + " e:" + e + " cnw:" + c_nw + " csw:" + c_sw + " ce:" + c_e); } } } } } } } } void setIfNotAllocatedAlready(int[] data, int idx, int val) { if (!allocated[val]) { data[idx] = val; allocated[val] = true; } } public static void invert(int[] data) { int len = data.length; int[] wksp = new int[len]; // int i; for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { int idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); wksp[idx] = data[idx]; } } } } } } for (int nw = 0; nw < nw_max; nw++) { for (int sw = 0; sw < sw_max; sw++) { for (int e = 0; e < e_max; e++) { for (int c_nw = 0; c_nw < c_nw_max; c_nw++) { for (int c_sw = 0; c_sw < c_sw_max; c_sw++) { for (int c_e = 0; c_e < c_e_max; c_e++) { int idx = (sw << sw_sh) | (nw << nw_sh) | (e << e_sh) | (c_sw << c_sw_sh) | (c_nw << c_nw_sh) | (c_e << c_e_sh); data[wksp[idx]] = idx; } } } } } } } public static void main(String args[]) { R2D.main(args); } }