Skip to content

Instantly share code, notes, and snippets.

@coolcomputery

coolcomputery/LoopoverNRGBFSLarge.java Secret

Created July 20, 2021 02:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save coolcomputery/5c2d67014d6b03f5fdfd8c09769d23a1 to your computer and use it in GitHub Desktop.
Save coolcomputery/5c2d67014d6b03f5fdfd8c09769d23a1 to your computer and use it in GitHub Desktop.
Download ZIP
4x4NRG GN <= 28+94=122
Raw
LoopoverNRGBFSLarge.java
import java.util.*;
import java.io.*;
public class LoopoverNRGBFSLarge {
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static boolean[] mask(String s) {
boolean[] out=new boolean[s.length()];
for (int i=0; i<s.length(); i++)
out[i]=s.charAt(i)=='1';
return out;
}
private static StringBuilder bb95j(long n, int len) { //BACKWARDS base 95
StringBuilder tmp=new StringBuilder();
while (n>0) {
tmp.append((char)(n%95+32));
n/=95;
}
while (tmp.length()<len) tmp.append(' ');
return tmp;
}
private static StringBuilder bb95(long n) { //BACKWARDS base 95
if (n==0) return new StringBuilder(" ");
StringBuilder tmp=new StringBuilder();
while (n>0) {
tmp.append((char)(n%95+32));
n/=95;
}
return tmp;
}
private static long num(String bb95) {
long out=0;
for (int i=bb95.length()-1; i>-1; i--)
out=out*95+(bb95.charAt(i)-32);
return out;
}
public static boolean[][] parse(String s) {
String[] rows=s.split(",");
if (rows.length>1) {
boolean[][] out=new boolean[rows.length][rows[0].length()];
for (int i=0; i<out.length; i++)
for (int j=0; j<rows[i].length(); j++) {
char c=rows[i].charAt(j);
if (c=='0') out[i][j]=false;
else if (c=='1') out[i][j]=true;
else throw new RuntimeException("Not parseable as a binary matrix.");
}
return out;
}
else {
String[] pcs=s.split("x");
if (pcs.length!=2) throw new RuntimeException("Not in 2 pieces: "+s);
return new boolean[][] {mask(pcs[0]),mask(pcs[1])};
}
}
//define absolute indexing as mapping coordinate (r,c) to index r*C+c
//every scramble is represented by an array L[], where piece i is at location L[i]
private String folder;
private int R, C, gr, gc;
private int F;
private boolean[][] rcfree, enstatemat;
private boolean free(int r, int c) {
return rcfree[0][r]||rcfree[1][c];
}
private int[] tofree, freeto;
//tofree[r*C+c]=i, where free location (r,c) is assigned to index i
public int K;
private int[][] mvactions;
private int M;
public long ncombos;
//bfs stuff
private long[] visited;
public int D;
private int codelen, mvilen;
private void add(long n) {
visited[(int)(n/64)]|=1L<<(n%64);
}
private boolean contains(long n) {
return (visited[(int)(n/64)]&(1L<<(n%64)))!=0;
}
public LoopoverNRGBFSLarge(int R, int C, int gr, int gc, String state0, String state1) {
folder=R+"x"+C+"NRG("+gr+","+gc+")-"+state0+"-"+state1+"\\";
System.out.println(folder);
new File(folder).mkdir();
this.R=R; this.C=C; this.gr=gr; this.gc=gc;
rcfree=parse(state0);
tofree=new int[R*C]; freeto=new int[R*C];
F=0;
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(r,c)) {
tofree[r*C+c]= F;
freeto[F]=r*C+c;
F++;
}
else tofree[r*C+c]=-1;
enstatemat=parse(state1);
if (state1.indexOf('x')!=-1) {
boolean[][] tmp=new boolean[R][C];
for (int i=0; i<R; i++)
for (int j=0; j<C; j++) tmp[i][j]=enstatemat[0][i]||enstatemat[1][j];
enstatemat=tmp;
}
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
System.out.printf("%4s",
free(r,c)?
((r==gr&&c==gc?"*":(enstatemat[r][c]?"":"'"))
+tofree[r*C+c])
:"X"
//X: locked; ': piece that this BFS tree tries to solve; *: gripped piece
);
System.out.println();
}
K=1; //include gripped piece
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(r,c)&&!enstatemat[r][c])
K++;
ncombos=1;
for (int rep=0; rep<K; rep++) ncombos*=F-rep;
System.out.println("ncombos="+ncombos);
if (ncombos/64>400_000_000) throw new RuntimeException("Too many combinations to handle.");
codelen=bb95(ncombos).length();
System.out.println("every combo represented with "+ codelen +" character(s)");
M=2*R+2*C;
M=2*R+2*C;
mvactions=new int[M][]; {
//mvactions[m][i]=free loc. that i-th free loc. will go to after the m-th move is applied
//mv [0,mr,s] --> idx=mr*2+(s+1)/2
int idx=0;
for (int mr=0; mr<R; mr++)
for (int s=-1; s<=1; s+=2) {
if (rcfree[0][mr]) {
mvactions[idx]=new int[F];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(r,c))
mvactions[idx][tofree[r*C+c]]=tofree[r*C+(r==mr?mod(c+s,C):c)];
}
else mvactions[idx]=null;
idx++;
}
//mv [1,mc,s] --> idx=2*R+mc*2+(s+1)/2
for (int mc=0; mc<C; mc++)
for (int s=-1; s<=1; s+=2) {
if (rcfree[1][mc]) {
mvactions[idx]=new int[F];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(r,c))
mvactions[idx][tofree[r*C+c]]=tofree[(c==mc?mod(r+s,R):r)*C+c];
}
else mvactions[idx]=null;
idx++;
}
}
mvilen=bb95(M).length();
System.out.println("every final move represented with "+mvilen+" character(s)");
}
public void bfs() throws IOException {
visited=new long[(int)(ncombos/64+1)];
boolean[] rnfree=new boolean[R], cnfree=new boolean[C];
Arrays.fill(rnfree,true); Arrays.fill(cnfree,true);
for (int r=0; r<R; r++) for (int c=0; c<C; c++) if (!enstatemat[r][c]) rnfree[r]=cnfree[c]=false;
boolean existsrfree=false, existscfree=false;
for (boolean v:rnfree) if (v) existsrfree=true;
for (boolean v:cnfree) if (v) existscfree=true;
PrintWriter fout=new PrintWriter(new FileWriter(folder+"0.txt")); {
for (int grow=0; grow<R; grow++)
for (int gclm=0; gclm<C; gclm++)
if (enstatemat[gr][gc]?
(existsrfree&&existscfree?(rnfree[grow]||cnfree[gclm]):
((gclm==gc||rnfree[gr])&&(grow==gr||cnfree[gc]))):
(grow==gr&&gclm==gc)) {
int[] solvedscrm=new int[K];
solvedscrm[0]=tofree[grow*C+gclm];
for (int r=0, idx=1; r<R; r++)
for (int c=0; c<C; c++)
if (free(r,c)&&!enstatemat[r][c])
solvedscrm[idx++]=tofree[r*C+c];
System.out.println(Arrays.toString(solvedscrm));
long solvedscrmcode=comboCode(solvedscrm);
add(solvedscrmcode);
fout.print(bb95j(solvedscrmcode,codelen).append(bb95j(0,mvilen)));
}
fout.close();
}
long reached=0;
for (D=0;; D++) {
BufferedReader fin=new BufferedReader(new FileReader(folder+D+".txt"));
fout=new PrintWriter(new FileWriter(folder+(D+1)+".txt"));
StringBuilder toPrint=new StringBuilder();
long fsz=0, sz=0;
while (true) {
StringBuilder code=new StringBuilder();
for (int i=0; i<codelen; i++) {
int r=fin.read();
if (r==-1) break;
code.append((char)r);
}
if (code.length()==0) break;
if (code.length()!=codelen) throw new RuntimeException("\""+code+"\".length()!="+codelen);
fsz++;
long f=num(code.toString());
int[] scrm=codeCombo(f);
//if (D==0) System.out.println("-->"+Arrays.toString(scrm));
StringBuilder mvibb95=new StringBuilder();
for (int i=0; i<mvilen; i++)
mvibb95.append((char)fin.read());
int mr=freeto[scrm[0]]/C, mc=freeto[scrm[0]]%C;
int[] mvlist=new int[] {mr*2,mr*2+1,2*R+mc*2,2*R+mc*2+1};
int invprevmv=D==0?-1:((int)num(mvibb95.toString())^1);
for (int mi:mvlist)
if (mvactions[mi]!=null&&mi!=invprevmv) {
long nf=comboCode(scrm,mvactions[mi]);
if (!contains(nf)) {
add(nf);
toPrint.append(bb95j(nf,codelen)).append(bb95j(mi,mvilen));
sz++;
if (sz%1000_000==0) {
fout.print(toPrint);
toPrint=new StringBuilder();
}
}
}
}
fout.print(toPrint);
fout.close();
System.out.println(D+":"+fsz);
reached+=fsz;
if (sz==0) break;
}
System.out.println("\n#reached="+reached);
if (reached!=ncombos)
System.out.printf("WARNING: reached=%d!=ncombos=%d%n",reached,ncombos);
System.out.println("D="+D);
}
private long comboCode(int[] A) {
int[] P=new int[F];
for (int i = 0; i< F; i++) P[i]=i;
int[] L=P.clone();
long out=0, pow=1;
for (int i = F -1; i>= F -K; i--) {
//swap idxs i and L[A[i-(N-K)]] in P
int j=L[A[i-(F -K)]];
int pi=P[i];//, pj=P[j];
//P[i]=pj; //<--idx i will never be touched again
P[j]=pi;
L[pi]=j;
//L[pj]=i;
//J_i==j
out+=pow*j;
pow*=i+1;
}
return out;
}
private long comboCode(int[] A, int[] f) {
int[] P=new int[F];
for (int i = 0; i< F; i++) P[i]=i;
int[] L=P.clone();
long out=0, pow=1;
for (int i =F-1; i>=F-K; i--) {
int j=L[f[A[i-(F-K)]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
private int[] codeCombo(long code) {
int[] P=new int[F];
for (int i = 0; i< F; i++) P[i]=i;
for (int v = F; v>F-K; v--) {
int i=v-1, j=(int)(code%v);
code/=v;
int pi=P[i]; P[i]=P[j]; P[j]=pi;
}
int[] out=new int[K];
System.arraycopy(P,F-K,out,0,K);
return out;
}
public static void main(String[] args) throws IOException {
long st=System.currentTimeMillis();
new LoopoverNRGBFSLarge(4,4,0,0,"1111x1111","1100x0000").bfs();
System.out.println("time="+(System.currentTimeMillis()-st));
}
}
Raw
LoopoverNRGBFSLarge_stdout.txt
NOTE: CREATES EXTERNAL FILES ONTO HARD DRIVE TOTALLING ~25 GB IN SPACE
4x4NRG(0,0)-1111x1111-1100x0000\
*0 1 2 3
4 5 6 7
'8 '9 '10 '11
'12 '13 '14 '15
ncombos=4151347200
every combo represented with 5 character(s)
every final move represented with 1 character(s)
[0, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 8, 9, 10, 11, 12, 13, 14, 15]
[2, 8, 9, 10, 11, 12, 13, 14, 15]
[3, 8, 9, 10, 11, 12, 13, 14, 15]
0:4
1:8
2:20
3:48
4:116
5:280
6:676
7:1632
8:3940
9:9512
10:22804
11:54700
12:130920
13:312812
14:746048
15:1776116
16:4220496
17:10003508
18:23609012
19:55279696
20:127370140
21:283778084
22:586311004
23:1024503560
24:1240534304
25:700809528
26:91155564
27:712604
28:64
#reached=4151347200
D=28
time=3129725
Process finished with exit code 0
Raw
LoopoverNRGDijkstra.java
import java.util.*;
/**
* consider a NxN NRG Loopover board with a binary matrix A
* where the piece at location (r,c) is solved iff A[r][c]==false
* and the gripped piece is solved and at (gr,gc)
* we say that we are currently at the "state" A
* furthermore, we want to go from state A to state B
* where B is another matrix satisfying (!A[r][c]-->!B[r][c]) for all r,c
* i.e. if A[r][c]==false then B[r][c] must also be false
* we will restrict ourselves to solving every scramble with 3-cycles, 2,2-cycles (more generally, blobs),
* and single moves that by themselves do not move any already solved pieces
* we never make move any already solved pieces, except during the process of performing a blob
* i.e. after each blob and each single move, all (r,c) s.t. A[r][c]==true are still in their solved positions
*/
public class LoopoverNRGDijkstra {
private static int mod(int n, int k) {
return (n%k+k)%k;
}
private static String inv(String mvs) {
StringBuilder out=new StringBuilder();
for (int i=mvs.length()-1; i>-1; i--) {
char c=mvs.charAt(i);
out.append(c=='D'?'U':c=='R'?'L':c=='U'?'D':'R');
}
return out.toString();
}
public static String mvseqStr(List<int[]> S) {
StringBuilder str=new StringBuilder();
for (int[] m:S)
str.append(" ").append(m[0]==0?"R":"C").append(m[1]).append(m[2]==1?"":m[2]==-1?"'":("("+m[2]+")"));
return str.toString();
}
public static boolean[][] tobmat(String[] rows) {
boolean[][] out=new boolean[rows.length][rows[0].length()];
for (int i=0; i<out.length; i++)
for (int j=0; j<rows[i].length(); j++) {
char c=rows[i].charAt(j);
if (c=='0') out[i][j]=false;
else if (c=='1') out[i][j]=true;
else throw new RuntimeException("Not parseable as a binary matrix.");
}
return out;
}
private int R, C;
private int F; //F=number of locations that are not locked
private int[] tofree, freeto; //freeto[f]=l=location of the f-th unlocked location; tofree[l]=f
public int K;
//BFS stuff
public int ncombos;
private LoopoverNRGSetup[] bfss;
private int[] depth, par, tuplecode;
public int diam;
public LoopoverNRGDijkstra(int gr, int gc, String A, String B) {
this(gr,gc,tobmat(A.split(",")),tobmat(B.split(",")));
}
private LoopoverNRGDijkstra(int gr, int gc, boolean[][] A, boolean[][] B) {
this(gr,gc,A,B,null);
}
private LoopoverNRGDijkstra(int gr, int gc, boolean[][] A, boolean[][] B, LoopoverNRGSetup[] bfss) {
long st=System.currentTimeMillis();
R=A.length; C=A[0].length;
if (R!=C) throw new RuntimeException("Only square board sizes allowed."); //need to refactor LoopoverNRGSetup before I can remove this constraint
if (R!=B.length||C!=B[0].length) throw new RuntimeException("Mismatch in dimensions.");
if (!A[gr][gc]) throw new RuntimeException("Gripped pieces locked at starting state.");
for (int r=0; r<R; r++) for (int c=0; c<C; c++)
if (!A[r][c]&&B[r][c]) throw new RuntimeException("Set of solved pieces in A does not subset set of solved pieces in B.");
boolean[] rfree=new boolean[R], cfree=new boolean[C];
Arrays.fill(rfree,true); Arrays.fill(cfree,true);
for (int r=0; r<R; r++) for (int c=0; c<C; c++) if (!A[r][c]) rfree[r]=cfree[c]=false;
F=0; tofree=new int[R*C]; freeto=new int[R*C];
for (int r=0; r<R; r++) for (int c=0; c<C; c++) if (A[r][c]) {
tofree[r*C+c]=F;
freeto[F]=r*C+c;
F++;
}
freeto=Arrays.copyOfRange(freeto,0,F);
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
System.out.printf("%4s",
A[r][c]?
((B[r][c]?(r==gr&&c==gc?"g":""):(r==gr&&c==gc?"G":"'")))+tofree[r*C+c]
:"X"
//X: locked
//': piece that this BFS tree tries to solve
//g: gripped piece, does not have to go to home position
//G: gripped piece, has to go to home position
);
System.out.println();
}
int M=2*R+2*C;
int[][] mvactions=new int[M][]; {
//mvactions[m][i]=free loc. that i-th free loc. will go to after the m-th move is applied
//mv [0,mr,s] --> idx=mr*2+(s+1)/2
for (int mr=0; mr<R; mr++) if (rfree[mr])
for (int s=-1; s<=1; s+=2) {
int idx=mr*2+(s+1)/2;
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[r*C+(r==mr?mod(c+s,C):c)];
}
}
//mv [1,mc,s] --> idx=2*R+mc*2+(s+1)/2
for (int mc=0; mc<C; mc++) if (cfree[mc])
for (int s=-1; s<=1; s+=2) {
int idx=2*R+mc*2+(s+1)/2;
mvactions[idx]=new int[F];
for (int i=0; i<F; i++) {
int r=freeto[i]/C, c=freeto[i]%C;
mvactions[idx][i]=tofree[(c==mc?mod(r+s,R):r)*C+c];
}
}
}
//BFS
K=1;
for (int r=0; r<R; r++) for (int c=0; c<C; c++) if ((r!=gr||c!=gc)&&A[r][c]&&!B[r][c]) K++;
long tmp=1;
for (int rep=0; rep<K; rep++)
tmp*=F-rep;
if (tmp>400_000_000) throw new RuntimeException("Too many combos: "+tmp);
ncombos=(int)tmp;
System.out.println("ncombos="+ncombos);
depth=new int[ncombos]; Arrays.fill(depth,Integer.MAX_VALUE); par=new int[ncombos]; tuplecode=new int[ncombos];
System.out.print("list of allowed positions for gripped piece after solving:"); {
//gripped piece must be in a position after solving that is reachable to home position under state B
boolean[] Brf=new boolean[R], Bcf=new boolean[C]; Arrays.fill(Brf,true); Arrays.fill(Bcf,true);
for (int r=0; r<R; r++) for (int c=0; c<C; c++) if (!B[r][c]) Brf[r]=Bcf[c]=false;
for (int gl=0; gl<R*C; gl++)
if ((B[gr][gc]&&(Brf[gl/C]||Bcf[gl%C]))||gl==gr*C+gc) {
int[] solvedscrm=new int[K]; solvedscrm[0]=tofree[gl];
for (int r=0, i=1; r<R; r++) for (int c=0; c<C; c++) if ((r!=gr||c!=gc)&&A[r][c]&&!B[r][c])
solvedscrm[i++]=tofree[r*C+c];
System.out.print(" "+solvedscrm[0]);
int solvedcode=comboCode(solvedscrm);
depth[solvedcode]=0; par[solvedcode]=-1;
}
} System.out.println();
int reached=0;
if (bfss==null) bfss=new LoopoverNRGSetup[] {LoopoverNRGSetup.cyc3(R), LoopoverNRGSetup.cyc2n2(R)};
this.bfss=bfss;
List<List<int[][]>> cycleInfos=new ArrayList<>();
for (int bfsi=0; bfsi<bfss.length; bfsi++)
if (bfss[bfsi]==null) cycleInfos.add(null);
else {
cycleInfos.add(new ArrayList<>());
LoopoverNRGSetup bfs=bfss[bfsi];
int nP=bfs.tP.length;
int[] tuple=new int[nP];
//we want to cycle the pieces at locations freeto[tuple[i]]
while (tuple[nP-1]<F) {
boolean good=true;
for (int i=0; i<nP; i++)
for (int j=0; j<i; j++)
if (tuple[i]==tuple[j]) good=false;
if (good) {
int[] L=new int[nP];
for (int i=0; i<nP; i++)
L[i]=freeto[tuple[i]];
int[] action=new int[F];
for (int i=0; i<F; i++) action[i]=i;
for (int i=0; i<nP; i++) action[tofree[L[i]]]=tofree[L[bfs.tP[i]]];
cycleInfos.get(bfsi).add(new int[][] {L,action});
}
tuple[0]++;
for (int i=0; i<nP-1&&tuple[i]==F; i++) {
tuple[i]=0;
tuple[i+1]++;
}
}
}
diam=0;
for (int D=0;; D++) {
boolean finished=true;
int fsz=0;
for (int f=0; f<ncombos; f++)
if (depth[f]>D&&depth[f]!=Integer.MAX_VALUE) finished=false;
else if (depth[f]==D) {
fsz++;
finished=false;
int[] scrm=codeCombo(f);
int lr=freeto[scrm[0]]/C, lc=freeto[scrm[0]]%C;
int[] mvis={lr*2,lr*2+1,2*R+lc*2,2*R+lc*2+1};
for (int mvi:mvis) if (mvactions[mvi]!=null) {
int nf=comboCode(scrm,mvactions[mvi]);
int ndepth=depth[f]+1;
if (ndepth<depth[nf]) {
depth[nf]=ndepth;
par[nf]=f;
tuplecode[nf]=(mvi<2*R?(mvi%2==0?0:1):(mvi%2==0?2:3))*(bfss.length+1);
}
}
for (int bfsi=0; bfsi<bfss.length; bfsi++) if (bfss[bfsi]!=null) {
LoopoverNRGSetup bfs=bfss[bfsi];
for (int[][] cycinfo:cycleInfos.get(bfsi)) if (cycinfo[1][scrm[0]]==scrm[0]) {
int[] L=cycinfo[0], action=cycinfo[1];
int nf=comboCode(scrm,action);
int tcode=bfs.tupleCode(L,lr,lc);
int ndepth=depth[f]+bfs.cost(tcode);
if (ndepth<depth[nf]) {
depth[nf]=ndepth;
par[nf]=f;
tuplecode[nf]=tcode*(bfss.length+1)+bfsi+1;
}
}
}
}
if (fsz>0) {
System.out.print((D>0?" ":"")+D+":"+fsz);
diam=Math.max(diam,D);
}
reached+=fsz;
if (finished) break;
}
System.out.println("\n# combos reached="+reached);
if (reached!=ncombos) System.out.println("Warning: ncombos="+ncombos+"!=reached="+reached+" (could be the result of a restriction on parity or reachable locations of the gripped piece).");
System.out.println("diameter="+diam);
System.out.println("BFS time (ms)="+(System.currentTimeMillis()-st));
}
private int comboCode(int[] A) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
//swap idxs i and L[A[i-(N-K)]] in P
int j=L[A[i-(F-K)]];
int pi=P[i];//, pj=P[j];
//P[i]=pj; //<--idx i will never be touched again
P[j]=pi;
L[pi]=j;
//L[pj]=i;
//J_i==j
out+=pow*j;
pow*=i+1;
}
return out;
}
private int comboCode(int[] A, int[] f) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
int[] L=P.clone();
int out=0;
for (int i=F-1, pow=1; i>=F-K; i--) {
int j=L[f[A[i-(F-K)]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
private int[] codeCombo(int code) {
int[] P=new int[F];
for (int i=0; i<F; i++) P[i]=i;
for (int v=F; v>F-K; v--) {
int i=v-1, j=code%v;
code/=v;
int pi=P[i]; P[i]=P[j]; P[j]=pi;
}
int[] out=new int[K];
System.arraycopy(P,F-K,out,0,K);
return out;
}
public String solveseq(int code) {
if (depth[code]==Integer.MAX_VALUE)
throw new RuntimeException("No solution.");
StringBuilder out=new StringBuilder();
for (int c=code; depth[c]>0; c=par[c]) {
int i=tuplecode[c];
int bfsi=i%(bfss.length+1)-1; i/=bfss.length+1;
out.append(inv(
bfsi==-1?(new String[] {"L","R","U","D"}[i]):
bfss[bfsi].sol(i)
)).append(" ");
}
return out.toString();
}
public String test() {
for (int code=0; code<ncombos; code++) if (depth[code]!=Integer.MAX_VALUE) {
System.out.println("tscrm="+Arrays.toString(codeCombo(code)));
return solveseq(code);
}
return null;
}
public static void main(String[] args) {
new LoopoverNRGDijkstra(0,0,"1111,1111,0000,0000","0000,0000,0000,0000");
}
}
Raw
LoopoverNRGDijkstra_stdout.txt
G0 '1 '2 '3
'4 '5 '6 '7
X X X X
X X X X
ncombos=40320
list of allowed positions for gripped piece after solving: 0
16:36 18:48 20:120 22:288 24:984 26:1584 28:2712 30:4416 32:5880 34:3936
final distribution:
16:18 18:24 20:60 22:120 24:300 26:408 28:576 30:600 32:432 34:192
N=4,tP=[1, 2, 0],diameter=34,BFS time=325
0:1 1:2 2:1 24:6 25:16 26:20 27:16 28:16 29:24 30:26 31:44 32:62 33:40 34:10 48:20 49:68 50:106 51:116 52:132 53:168 54:196 55:374 56:517 57:398 58:273 59:278 60:240 61:200 62:252 63:176 64:42 72:32 73:152 74:244 75:280 76:336 77:432 78:454 79:594 80:660 81:500 82:466 83:550 84:404 85:272 86:302 87:184 88:106 89:60 90:28 91:48 92:76 93:48 94:12
# combos reached=10080
Warning: ncombos=40320!=reached=10080 (could be the result of a restriction on parity or reachable locations of the gripped piece).
diameter=94
BFS time (ms)=1076
Process finished with exit code 0
Raw
LoopoverNRGSetup.java
import java.util.*;
public class LoopoverNRGSetup {
public static final char[] dirNames={'D','R','U','L'};
private static int mod(int n, int k) {
return (n%k+k)%k;
}
public static List<int[]> perms(int N) {
List<int[]> out=new ArrayList<>();
if (N==1) out.add(new int[] {0});
else {
List<int[]> help=perms(N-1);
for (int[] h:help)
for (int i=0; i<N; i++) {
int[] p=new int[N];
System.arraycopy(h,0,p,0,i);
p[i]=N-1;
if (i<N-1) System.arraycopy(h,i,p,i+1,N-1-i);
out.add(p);
}
}
return out;
}
public static class Board {
int N;
int[][] board;
int lr, lc;
StringBuilder mvs;
private int loc(int pc) {
for (int i=0; i<N*N; i++)
if (board[i/N][i%N]==pc)
return i;
return -1;
}
Board(int N, int gr, int gc) {
this.N=N;
board=new int[N][N];
for (int i=0; i<N*N; i++)
board[i/N][i%N]=i;
int loc=loc(gr*N+gc);
lr=loc/N; lc=loc%N;
mvs=new StringBuilder();
}
private void move(int type, int shift) {
shift=mod(shift,N);
if (shift>N/2) shift-=N;
char c;
if (type==0) {
int[] T=new int[N];
for (int j=0; j<N; j++) T[j]=board[lr][j];
for (int j=0; j<N; j++) board[lr][mod(j+shift,N)]=T[j];
c=shift<0?'L':'R';
lc=mod(lc+shift,N);
}
else if (type==1) {
int[] T=new int[N];
for (int i=0; i<N; i++) T[i]=board[i][lc];
for (int i=0; i<N; i++) board[mod(i+shift,N)][lc]=T[i];
c=shift<0?'U':'D';
lr=mod(lr+shift,N);
}
else throw new RuntimeException();
for (int rep=0; rep<Math.abs(shift); rep++)
mvs.append(c);
}
private void move(String mvs) {
for (int i=0; i<mvs.length(); i++) {
char c=mvs.charAt(i);
if (c=='D') move(1,1);
else if (c=='R') move(0,1);
else if (c=='U') move(1,-1);
else if (c=='L') move(0,-1);
else throw new RuntimeException();
}
}
private String display() {
StringBuilder str=new StringBuilder();
for (int[] r:board) {
for (int v:r)
str.append((N*N<=26?(char)(v+'A'):String.format("%3d",v)));
str.append("\n");
}
return str.toString();
}
}
private static String inv(String mvs) {
StringBuilder out=new StringBuilder();
for (int i=mvs.length()-1; i>-1; i--) {
char c=mvs.charAt(i);
out.append(c=='D'?'U':c=='R'?'L':c=='U'?'D':'R');
}
return out.toString();
}
public static String comm(String A, String B) {
return A+B+inv(A)+inv(B);
}
private static String transf(String mvs, int type) {
if (type<0||type>=4) throw new RuntimeException("invalid transformation type: "+type);
if (type==3) return inv(mvs);
StringBuilder out=new StringBuilder();
for (int i=0; i<mvs.length(); i++) {
char mv=mvs.charAt(i);
out.append(
type==0?(mv=='L'?'R':mv=='R'?'L':mv): //reflect board left-right
type==1?(mv=='U'?'D':mv=='D'?'U':mv): //reflect board top-down
(mv=='D'?'R':mv=='R'?'D':mv=='U'?'L':'U') //transpose board
);
}
return out.toString();
}
public static String transformed(String alg, int b) {
String ret=alg;
for (int t=0; t<4; t++)
if((b&(1<<t))!=0)
ret=transf(ret,t);
return ret;
}
public static int[][] effect(int N, String alg) {
//return {L,tP}
//where L is an array of locations on the NxN board
//and the algorithm moves the piece from location L[i] to location L[tP[i]] for each i
Board bd=new Board(N,0,0);
bd.move(alg);
int[] perm=new int[N*N];
//perm[i]=location that the piece at location i goes to
for (int i=0; i<N*N; i++) {
int pc=bd.board[i/N][i%N];
perm[pc]=i;
}
int[] toMovedLocs=new int[N*N]; Arrays.fill(toMovedLocs,-1);
List<Integer> movedLocs=new ArrayList<>();
for (int i=0; i<N*N; i++)
if (perm[i]!=i) {
toMovedLocs[i]=movedLocs.size();
movedLocs.add(i);
}
int K=movedLocs.size();
int[] L=new int[K];
for (int i=0; i<K; i++) L[i]=movedLocs.get(i);
int[] P=new int[K];
for (int i=0; i<K; i++)
P[i]=toMovedLocs[perm[L[i]]];
return new int[][] {L,P};
}
public static String canonical(int N, String alg) {
//remove redundant moves from alg
StringBuilder str=new StringBuilder();
for (int i=0; i<alg.length(); i++)
if (str.length()>0&&inv(""+str.charAt(str.length()-1)).equals(""+alg.charAt(i)))
str.deleteCharAt(str.length()-1);
else
str.append(alg.charAt(i));
StringBuilder out=new StringBuilder();
for (int i=0; i<str.length();) {
int j=i;
while (j<str.length()&&str.charAt(i)==str.charAt(j))
j++;
int len=(j-i)%N;
char mv=str.charAt(i);
if (len>N/2) {
len=N-len;
mv=inv(""+mv).charAt(0);
}
else if (2*len==N)
mv=mv=='L'?'R':mv=='U'?'D':mv;
for (int k=0; k<len; k++)
out.append(mv);
i=j;
}
return out.toString();
}
//start of BFS part
private int N, V, K;
public int[] tP;
private String[] algs, sols;
private List<List<int[]>> ptsetss;
public int diam;
private int code(int[] vs) {
//map every tuple of K int.s in range [0,V) to a number
int out=0;
for (int i=0, pow=1; i<K; i++, pow*=V)
out+=vs[i]*pow;
return out;
}
private int[] decode(int code) {
int[] out=new int[K];
for (int i=0; i<K; i++, code/=V)
out[i]=code%V;
return out;
}
public LoopoverNRGSetup(int N, Collection<String> algs_init, int[] tP) {
this.N=N; V=N*N;
this.tP=tP;
{
Set<String> tmp=new TreeSet<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length()==o2.length()?o1.compareTo(o2):o1.length()-o2.length();
}
});
//include inverses and reflections of the initial algorithms
for (String alg_init:algs_init) {
String red=canonical(N,alg_init);
//say two move sequences A,B are similar if there exists a move sequence S s.t. A=S B inv(S)
//then if A and B are blobs, they cycle the same number of pieces in the same fashion
// i.e. if A is a 3-cycle, then so is B; if a is a 2,2-cycle, then so is B
//for A=[A[0], A[1], ... A[K-1]], define (A<<a) to be [A[a], A[a+1], ... A[K-1], A[0], ..., A[a-1]]
//then A is similar to (A<<a) for all A,a
//we want to rotate A s.t. the beginning and end moves are not both horizontal or both vertical
//this is so that for any S, canonical(S+A+inv(S)).length() >= canonical(A).length()
while (red.length()>1) {
char s=red.charAt(0), e=red.charAt(red.length()-1);
boolean sh=s=='R'||s=='L', eh=e=='R'||e=='L';
if (sh==eh)
red=canonical(N,red.substring(1)+""+s);
else break;
}
for (int b=0; b<16; b++) {
String ret=canonical(N,transformed(red,b));
tmp.add(ret);
}
}
//System.out.println("# algs after rotations/inverses/reflections="+tmp.size());
this.algs=new String[tmp.size()];
int i=0;
for (String s:tmp) algs[i++]=s;
}
K=tP.length;
ptsetss=new ArrayList<>();
List<int[]> Qs=perms(K);
for (int i=0; i<algs.length; i++) {
int[][] effect=effect(N,algs[i]);
int[] L=effect[0], P=effect[1];
if (K!=L.length)
throw new RuntimeException("Mismatch in # changed pieces: "+Arrays.toString(L)+".length!="+K);
//(L,P) describes the permutation action "location L[i] --> location L[P[i]] for all i"
//convert L to L' s.t. (L,P) and (L',tP) describe equivalent permutation actions
//find all Q s.t. "L[i]-->L[P[i]] for all i" == "L[Q[i]]-->L[Q[tP[i]] for all i"
//--> find all Q s.t. "i-->P[i]" == "Q[i]-->Q[tP[i]]"
//--> find all Q s.t. P[Q[i]]=Q[tP[i]] for all i
ptsetss.add(new ArrayList<>());
for (int[] Q:Qs) {
boolean match=true;
for (int k=0; k<K && match; k++)
if (P[Q[k]]!=Q[tP[k]]) match=false;
if (match) {
int[] ptset=new int[K];
for (int k=0; k<K; k++) ptset[k]=L[Q[k]];
ptsetss.get(i).add(ptset);
}
}
//System.out.print(algs[i]); for (int[] ptset:ptsetss.get(i)) System.out.print(" "+Arrays.toString(ptset)); System.out.println();
if (ptsetss.get(i).size()==0)
throw new RuntimeException("Incongruent permutations: "+Arrays.toString(P)+"!=tP="+Arrays.toString(tP));
}
search();
}
private void search() {
long sttime=System.currentTimeMillis();
int AMT=1; for (int rep=0; rep<K; rep++) AMT*=V;
sols=new String[AMT];
long expreached=1;
for (int rep=0; rep<K; rep++) expreached*=N*N-1-rep;
class Pc {
int code; String sol, orig;
Pc(int c, String s, String o) {
code=c;
sol=s;
orig=o;
}
public String toString() {
return code+","+sol+","+orig;
}
}
Set<String> seen=new HashSet<>();
List<List<Pc>> fronts=new ArrayList<>();
for (int ai=0; ai<algs.length; ai++) {
String a=algs[ai];
int c=a.length();
//System.out.println(a);
for (int[] ptset:ptsetss.get(ai)) {
int code=code(ptset);
sols[code]=a;
while (c>=fronts.size()) fronts.add(new ArrayList<>());
fronts.get(c).add(new Pc(code,a,a));
}
}
for (int co=0; co<fronts.size(); co++) if (fronts.get(co).size()>0) {
List<Pc> front=fronts.get(co);
int fsz=0;
for (int fi=0; fi<front.size(); fi++) {
/*if (front.get(fi).sol.equals("LURULDRDDLDRULURULURDLDDRDLURU"))
System.out.println(front.get(fi)+" co="+co+"; ...="+sols[front.get(fi).code].length());*/
if (sols[front.get(fi).code].length()==co&&!seen.contains(front.get(fi).toString())) {
fsz++;
seen.add(front.get(fi).toString());
int f=front.get(fi).code;
int[] locs=decode(f);
for (int d=0; d<4; d++) { //D, R, U, L
int shift=d/2==0?-1:1; //imagine moving the gripped piece in direction d
//then relative to the gripped piece, all other pieces move in the opposite direction
int[] nlocs=new int[locs.length];
for (int i=0; i<locs.length; i++) {
int r=locs[i]/N, c=locs[i]%N;
if (d%2==0) {
if (c!=0) r=mod(r-shift,N);
}
else {
if (r!=0) c=mod(c-shift,N);
}
nlocs[i]=r*N+c;
}
String nalg=canonical(N,(""+dirNames[d])+front.get(fi).sol+(""+dirNames[(d+2)%4]));
int nco=nalg.length();
int code=code(nlocs);
if (sols[code]==null||nco<=sols[code].length()) {
if (nco<co&&(sols[code]==null||nco<sols[code].length()))
throw new RuntimeException("Negative-weight edge in configuration graph: "
+front.get(fi).sol+" --> "+nalg+" (orig="+front.get(fi).orig+") (code="+code+")");
//^^^only throw this exception if we actually try traversing a negative-weight edge
if (sols[code]==null||nco<sols[code].length())
sols[code]=nalg;
/*if (nalg.equals("LLURULDRDDLDRULURULURDLDDRDLURUR"))
System.out.println(sols[code]+" "+code);*/
if (nco==co) {
front.add(new Pc(code,nalg,front.get(fi).orig));
//System.out.println(sols[f]+" --> "+nalg);
}
else {
while (nco>=fronts.size()) fronts.add(new ArrayList<>());
fronts.get(nco).add(new Pc(code,nalg,front.get(fi).orig));
}
}
}
}
}
System.out.print(" "+co+":"+fsz);
}
System.out.println();
diam=0;
for (int code=0; code<AMT; code++)
if (sols[code]!=null) diam=Math.max(diam,sols[code].length());
int[] freq=new int[diam+1];
for (int code=0; code<AMT; code++) if (sols[code]!=null) freq[sols[code].length()]++;
System.out.println("final distribution:");
for (int d=0; d<=diam; d++) if (freq[d]>0) System.out.print(" "+d+":"+freq[d]);
int reached=0; for (int v:freq) reached+=v;
if (reached!=expreached) throw new RuntimeException("Unexpected # of nodes reached: "+reached+" instead of "+expreached);
System.out.printf("\nN=%d,tP=%s,diameter=%d,BFS time=%d%n",N,Arrays.toString(tP),diam,(System.currentTimeMillis()-sttime));
}
//end of BFS part
//L[] is an array of locations on the board
public int tupleCode(int[] L, int lr, int lc) {
if (L.length!=K) throw new RuntimeException("Mismatch in number of pieces: "+L.length+"!="+K);
int[] nL=new int[K];
for (int i=0; i<K; i++) nL[i]=mod(L[i]/N-lr,N)*N+mod(L[i]%N-lc,N);
return code(nL);
}
public int cost(int v) {
return sols[v]==null?-1:sols[v].length();
}
public int cost(int[] L, int lr, int lc) {
return cost(tupleCode(L,lr,lc));
}
public String sol(int v) {
return sols[v];
}
public String sol(int[] L, int lr, int lc) {
return sol(tupleCode(L,lr,lc));
}
public static LoopoverNRGSetup cyc3(int N) {
List<String> algs=new ArrayList<>();
if (N>=4)
algs.add("RDLUURDLDLURDRULLDRUULDRDRULDLUR"); //32-move 3-cycle
if (N==5) {
algs.addAll(Arrays.asList(
"DDLDLDRULURRUURULDRDLDLLDRDLURURURULURDL",
"DDLDLURULDRDRUULURDDRDRULURDLDLUURUL" //36-move 3-cycle found by DFS search
));
}
else if (N>5)
algs.addAll(Arrays.asList(
"DDDDLDRULURUUULDRDLURDDLDRDLURUUULDRULUR",
"DDDDLDRULURUUURDLDRULDDLDRDLURUUURDLURUL"
));
if (N%2==0) {
for (int height=1; height<=N/2; height++) {
StringBuilder rd=new StringBuilder();
for (int r=0; r<N/2; r++) rd.append('R');
for (int r=0; r<height; r++) rd.append('D');
StringBuilder alg=new StringBuilder();
alg.append(rd).append(rd);
if (height<N/2)
for (int i=0; i<N+2*height; i++)
alg.append(inv(""+alg.charAt(i)));
alg.append(alg);
algs.add(alg.toString());
}
}
return algs.size()>0?
new LoopoverNRGSetup(N,algs,new int[] {1,2,0}):
null;
}
public static LoopoverNRGSetup cyc2n2(int N) {
if (N<5) return null;
List<String> algs=new ArrayList<>(Arrays.asList(
"DDLDRULURULURDLDDRDLURULURULDR",
"DDLDLURDRUURDLDLUULDRDRUURULDLUR",
"DDLDRULURURULDRDLLDRDLURURULURDL",
"DLDLDRURULULDRDLURDRULDRDLULURUR"
));
if (N==5) {
algs.addAll(Arrays.asList(
"DDLDLURDRDDRDRULDLDDLULDRURURURDLUL",
"DDLDRDLURDDLURDLDRDDLDRULURULURULDR",
"DDLDRDLURDDRULDRDLDDLDRULURURULURDL",
"DDLDLDRULURRUULDRDLURDLLDRDLURURULDRULUR",
"DDLDLDRULURRUULURDLDRDLLDRDLURURULURULDR"
));
//below algorithms found with brute-force search of all 5x5 NRG "strict blobs"
algs.addAll(Arrays.asList(
"DDLURDRDLDRDLDLURDDRULDLDRDLDRDRUL, DDLDLURDRDDRDRULDLDDLULDRURURURDLUL, DDLDRDLURDDLURDLDRDDLDRULURULURULDR, DDLDRDLURDDRULDRDLDDLDRULURURULURDL, DDLDDRULUULDRDLURURULDRDLDRDLURUULUR".split(", ")
));
}
else if (N==6)
algs.addAll(Arrays.asList(
"DDLDRDDLURDDLDRDDLURDDLDRDDLUR, DDLDRULURULURDLDDRDLURULURULDR, DDDLDRULURUULURDDLDDRDLURULURUULDR, DDDLDRULURUURULDDRDLLDRDLURURULUURDL, DDLDDLDRULURURUULDRDDLLDRDLURURUULUR, DDDLDLURDRDDRDRULDLDDDLULDRURUURURDLUL, DDDLDRDLURDDLURDDLDRDDLDRULURULURUULDR, DDDLDRDLURDDLURDLDRDDDLDRULURUULURULDR, DDDLDRDLURDDRULDDRDLDDLDRULURURULUURDL, DDDLDRDLURDDRULDRDLDDDLDRULURUURULURDL, DDDLDDRULUURUULDRDLURDLDDRDLUURUULDRULUR, DDDLDDRULUURUULURDLDRDLDDRDLUURUULURULDR, DDDLDDRULUURUURDLDRULDLDDRDLUURUURDLURUL, DDDLDDRULUURUURULDRDLDLDDRDLUURUURULURDL, DDDLDLLURDRRDDRURDLULULLULDRRURDDRDRULDL, DDDLDLURDRDDRRURDLLULULULDRURDDRDRRULDLL, DDLDLDRULURRUULDRDLURDLLDRDLURURULDRULUR".split(", ")
));
else
algs.addAll(Arrays.asList(
"DDLDRULURULURDLDDRDLURULURULDR, DDDDLDRUULURUULDRDDDDLURUULDRUULUR, DDDLDRULURUULURDDLDDRDLURULURUULDR, DDDLDRULURUURULDDRDLLDRDLURURULUURDL, DDLDDLDRULURURUULDRDDLLDRDLURURUULUR, DDDDLDRUULURUULURDDLDDRDDLURUULURUULDR, DDDLDDRULUURUULURDDLDDDRDLUURULURUULDR, DDDDLDRUULURUURULDDRDLLDRDDLURUURULUURDL, DDDDLULDRURUUURDRULDLDDLDLURDRUUURURDLUL, DDDDLURULDRUUULDRDLURDDLURDLDRUUULDRULUR, DDDDLURULDRUUURDLDRULDDLURDLDRUUURDLURUL, DDDLDDRULUURUULDRDLURDLDDRDLUURUULDRULUR, DDDLDDRULUURUURDLDRULDLDDRDLUURUURDLURUL, DDDLDDRULUURUURULDDRDLLDDRDLUURURULUURDL, DDDLLULDRRURUURDRULDLDLDLLURDRRUURURDLUL, DDDLULDRURUURDRRULDLLDLDLURDRUURRURDLLUL, DDLDDLDDRULUURURUULDRDDLLDDRDLUURURUULUR, DDLDLDRULURRUULDRDLURDLLDRDLURURULDRULUR".split(", ")
));
return new LoopoverNRGSetup(N,algs,new int[] {1,0,3,2});
}
public static void verify(LoopoverNRGSetup bfs) {
if (bfs==null) return;
long st=System.currentTimeMillis();
int N=bfs.N, K=bfs.K;
int[] perm=bfs.tP;
//test every ordered tuple of K tiles in an NxN board, without the gripped piece
int[] att=new int[K];
int lr=N/2, lc=N/2;
int[] opens=new int[N*N-1];
for (int i=0, id=0; i<N*N; i++) {
if (i!=lr*N+lc) {
opens[id]=i;
id++;
}
}
int diam=0;
while (att[K-1]<N*N-1) {
boolean norepeat=true;
for (int i=0; i<K; i++)
for (int j=0; j<i; j++)
if (att[i]==att[j]) norepeat=false;
if (norepeat) {
int[] permd_locs=new int[K]; for (int i=0; i<K; i++) permd_locs[i]=opens[att[i]];
String sol=bfs.sol(permd_locs,lr,lc);
diam=Math.max(diam,sol.length());
Board b=new Board(N,lr,lc);
b.move(sol);
int[] loc=new int[N*N];
for (int i=0; i<N*N; i++)
loc[b.board[i/N][i%N]]=i;
int[] expected=new int[N*N];
for (int i=0; i<N*N; i++)
expected[i]=i;
for (int i=0; i<K; i++)
expected[permd_locs[i]]=permd_locs[perm[i]];
boolean match=true;
for (int i=0; i<N*N && match; i++)
if (loc[i]!=expected[i])
match=false;
if (!match) {
System.out.println("!!!ERROR!!!");
System.out.println("sol="+sol);
System.out.println("tP="+Arrays.toString(perm)
+",permd_locs="+Arrays.toString(permd_locs)
+"\n"+b.display());
return;
}
}
att[0]++;
for (int i=0; i<K-1 && att[i]==N*N-1; i++) {
att[i]=0;
att[i+1]++;
}
}
if (diam!=bfs.diam)
System.out.println("!!!MISMATCH: verifier's observed diameter="+diam);
System.out.println("verification time="+(System.currentTimeMillis()-st));
}
public static void main(String[] args) {
for (int N=4; N<=5; N++) {
verify(cyc3(N));
verify(cyc2n2(N));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment