Skip to content

Instantly share code, notes, and snippets.

@coolcomputery

coolcomputery/LoopoverBFS.java

Created August 22, 2021 23:05
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/87c8969d46377585bcbcbf42ba2a1e44 to your computer and use it in GitHub Desktop.
Save coolcomputery/87c8969d46377585bcbcbf42ba2a1e44 to your computer and use it in GitHub Desktop.
Download ZIP
5x5 phases 3x3->4x4->5x5 in <= 27 moves
Raw
LoopoverBFS.java
import java.util.*;
public class LoopoverBFS {
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;
}
public static boolean[][] parseState(String s) {
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])};
}
private static boolean free(boolean[][] boardState, int r, int c) {
return boardState[0][r]||boardState[1][c];
}
//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 int R, C;
private int F;
private boolean[][] rcfree;
//a location (r,c) is free iff Rfree[r]||Cfree[c]
private int[] tofree, freeto;
//tofree[r*C+c]=i, where free location (r,c) is assigned to index i
public int K;
public int[] target; //list of pieces this tree tries to solve, in absolute indexing
private int[][] mvactions, mvs;
private int[][] solveactions, scrambleactions;
public static int[][] mvreduc(int[][] mvs) {
int M=mvs.length;
//move sequence reduction
//when doing two moves of the same type, one after the other: [t,a,r], [t,b,s]:
//WLOG a<=b, or else the two moves can be arranged to satisfy this condition without changing the final scramble
//if a==b, then r+s!=0, else the two moves cancel each other out
int[][] mvreduc=new int[M+1][];
for (int m=0; m<M; m++) {
List<Integer> l=new ArrayList<>();
for (int m2=0; m2<M; m2++)
if (mvs[m][0]!=mvs[m2][0]
||mvs[m][1]<mvs[m2][1]
||(mvs[m][1]==mvs[m2][1]&&mvs[m][2]+mvs[m2][2]!=0))
l.add(m2);
mvreduc[m]=new int[l.size()];
for (int i=0; i<l.size(); i++)
mvreduc[m][i]=l.get(i);
}
mvreduc[M]=new int[M];
for (int i=0; i<M; i++) mvreduc[M][i]=i;
return mvreduc;
}
private int M;
public int ncombos;
//bfs stuff
private long[] data;
private List<int[]> fronts; //BFS fronts
public int D; //(largest depth of BFS tree)+1
//c-->(depth,move from parent combo to c,parent combo)
public int[] tofree() {
return tofree;
}
public int[] freeto() {
return freeto;
}
private long compressed(int depth, int parent, int move) {
return ((long)depth*M+move)*ncombos+parent;
}
public int depth(int code) {
return data[code]==-1?-1:(int)(data[code]/ncombos/M);
}
private int par(int code) {
return data[code]==-1?-1:(int)(data[code]%ncombos);
}
private int mvi(int code) {
return data[code]==-1?-1:(int)((data[code]/ncombos)%M);
}
public LoopoverBFS(int R, int C, String state0, String state1) {
long st=System.currentTimeMillis();
this.R=R; this.C=C;
rcfree=parseState(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(rcfree,r,c)) {
tofree[r*C+c]=F;
freeto[F]=r*C+c;
F++;
}
else tofree[r*C+c]=-1;
freeto=Arrays.copyOfRange(freeto,0, F);
boolean[][] nrcfree=parseState(state1);
K=0; target =new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
if (free(rcfree,r,c)&&!free(nrcfree,r,c))
target[K++]=r*C+c;
target =Arrays.copyOfRange(target,0,K);
for (int r=0; r<R; r++) {
for (int c=0; c<C; c++)
System.out.printf("%4s",
free(rcfree,r,c)?
((free(nrcfree,r,c)?"":"'")+tofree[r*C+c]):
"X"
//': piece that this BFS tree tries to solve; *: gripped piece
);
System.out.println();
}
{
long tmp=1;
for (int rep=0; rep<K; rep++) tmp*=F-rep;
if (tmp>400_000_000) throw new RuntimeException("Too many combinations to handle.");
ncombos=(int)tmp;
}
System.out.println("ncombos="+ncombos);
//moves: every move is represented with [t,a,r]:
//t: type (0=row shift, 1=clm shift)
//a: the a-th (row if t==0, else clm)
//r: # units to shift (right if t==0, else down)
M=0;
for (boolean[] axis:rcfree)
for (boolean b:axis) if (b) M+=2;
mvactions=new int[M][]; mvs=new int[M][]; {
//mvactions[m][i]=free loc. that i-th free loc. will go to after move m is applied
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
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)];
}
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
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];
}
idx++;
}
}
int[][] mvreduc=mvreduc(mvs);
//BFS
solveactions=new int[ncombos][];
scrambleactions=new int[ncombos][];
data=new long[ncombos]; Arrays.fill(data,-1);
fronts=new ArrayList<>();
{
int[] solvedscrm=new int[K];
for (int i=0; i<K; i++)
solvedscrm[i]=tofree[target[i]];
int solvedscrmcode=comboCode(solvedscrm);
fronts.add(new int[] {solvedscrmcode});
data[solvedscrmcode]=0;
}
int[] nfront=new int[ncombos];
int reached=0;
for (D=0;; D++) {
if (fronts.get(D).length==0) break;
reached+=fronts.get(D).length;
System.out.print((D>0?" ":"")+D+":"+fronts.get(D).length);
int sz=0;
for (int f:fronts.get(D)) {
int[] scrm=codeCombo(f);
int[] mvlist=mvreduc[D==0?M:mvi(f)];
for (int mi:mvlist) {
int nf=comboCode(scrm,mvactions[mi]);
if (data[nf]==-1) {
data[nf]=compressed(D+1,f,mi);
nfront[sz++]=nf;
}
}
}
fronts.add(new int[sz]);
System.arraycopy(nfront,0,fronts.get(D+1),0,sz);
}
System.out.println("\n#reached="+reached);
System.out.println("D="+D);
System.out.println("total BFS time="+(System.currentTimeMillis()-st));
}
public void clearFronts() {
fronts=null;
}
public int[] codesAtDepth(int d) {
return fronts.get(d);
}
/*
encoding ordered combinations
A[0]...A[K-1], 0<=A[i]<N, all A[i] distinct
possible to transform permutation [0...N-1] into [....|A]
using a sequence of swaps (i,J_i) for i=N-1 to N-K inclusive
--> encode A as J_(N-1)+N*(J_(N-2)+(N-1)*(...+(N-K+2)*J_(N-K)...)
for this program, N=Nfree, K=K
*/
public 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;
}
public int codeAfterScramble(int[] scrm0) {
//A[i]=tofree[scrm0[scrm1[target[i]]]]
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[tofree[scrm0[target[i-(F-K)]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1) {
//A[i]=tofree[scrm0[scrm1[target[i]]]]
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[tofree[scrm0[scrm1[target[i-(F-K)]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public int codeAfterScramble(int[] scrm0, int[] scrm1, int[] scrm2) {
//A[i]=tofree[scrm0[scrm1[scrm2[target[i]]]]]
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[tofree[scrm0[scrm1[scrm2[target[i-(F-K)]]]]]];
int pi=P[i];
P[j]=pi;
L[pi]=j;
out+=pow*j;
pow*=i+1;
}
return out;
}
public 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 void computeAllActions() {
for (int code=0; code<ncombos; code++) if (data[code]!=-1) {
solveactions[code]=solveaction_help(code);
scrambleactions[code]=inv(solveactions[code]);
}
}
public int[] solveaction(int code) {
return solveactions[code]==null?solveaction_help(code):solveactions[code];
}
private int[] solveaction_help(int code) {
if (data[code]==-1) throw new RuntimeException("Invalid combination code: "+code);
int[] out=new int[F];
for (int i=0; i<F; i++) out[i]=i;
for (int c=code; depth(c)>0; c=par(c)) {
int[] mva=inv(mvactions[mvi(c)]);
int[] nout=new int[F];
for (int i=0; i<F; i++)
nout[i]=mva[out[i]];
out=nout;
}
return mva2abs(out);
}
public int[] scrambleaction(int code) {
return scrambleactions[code]==null?inv(solveaction(code)):scrambleactions[code];
}
public List<int[]> solvemvs(int code) {
List<int[]> out=new ArrayList<>();
for (int c=code; depth(c)>0; c=par(c)) {
int[] mv=mvs[mvi(c)];
out.add(new int[] {mv[0],mv[1],-mv[2]});
}
return out;
}
private static int[] inv(int[] P) {
//return inverse permutation of P
int[] I=new int[P.length];
for (int i=0; i<P.length; i++)
I[P[i]]=i;
return I;
}
private int[] mva2abs(int[] mva) {
//convert mva to array A
//where A[a]=b describes absolute location a being shifted to absolute location b
int[] out=new int[R*C];
for (int a=0; a<R*C; a++)
out[a]=tofree[a]==-1?a:freeto[mva[tofree[a]]];
return out;
}
}
Raw
LoopoverBFSImprove.java
import java.math.BigInteger;
import java.util.*;
/**
* given a start state S and end state E:
* ex. 5x5 Loopover states 11111x11111 and 00011x00011
* along with a list of middle states M[]:
* ex. 00111x00111, 00111x01011, 10011x01011, etc.
* use these midstates to find an upper bound on the God's number of transforming the starting state to the end state
*
* more formally, choose a threshold D
* choose a midstate M[a] to be the "default"
* then go through all scrambles such that naively using the two trees S-->M[a] and M[a]-->E yields a solution of >D moves
* for each scramble:
* for each i!=a, try solving it with the trees S-->M[i] and M[i]-->E until a solution of <=D moves is found
* if a solution is not found, try applying an arbitrary sequence of prefix moves to the scramble,
* and then try solving it with the trees S-->M[i] and M[i]-->E (this time including i==a)
* repeat for all possible prefix sequences of length 1, 2, ... until a short enough solution is found
*/
public class LoopoverBFSImprove {
private static int mod(int n, int k) {
return (n%k+k)%k;
}
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();
}
private static int[] inv(int[] P) { //inverse permutation
int[] Q=new int[P.length];
for (int i=0; i<P.length; i++) Q[P[i]]=i;
return Q;
}
private static int[] prod(int[] A, int[] B) { //return [ A[B[i]] for all i]
int[] out=new int[B.length];
for (int i=0; i<B.length; i++) out[i]=A[B[i]];
return out;
}
private static BigInteger perm2code(int[] A) {
BigInteger n=BigInteger.ZERO;
for (int i=0; i<A.length; i++)
n=n.add(new BigInteger(""+A[i]).multiply(new BigInteger(""+A.length).pow(i)));
return n;
}
private static int[] code2perm(BigInteger code, int N) {
int[] P=new int[N];
BigInteger h=code, nN=new BigInteger(""+N);
for (int i=0; i<N; i++) {
P[i]=h.mod(nN).intValue();
h=h.divide(nN);
}
return P;
}
private static int[] restoringPerm(int[] P, int[] T) {
//returns Q s.t. prod(P,Q)==T, null if no such Q exists
Map<Integer,Integer> locs=new HashMap<>();
for (int i=0; i<P.length; i++)
locs.put(P[i],i);
if (locs.size()!=P.length) throw new RuntimeException();
//System.out.println(locs);
int[] Q=new int[T.length];
for (int i=0; i<T.length; i++)
if (!locs.containsKey(T[i])) return null;
else Q[i]=locs.get(T[i]);
return Q;
}
private static List<int[]> safeTransformations(int R, int C, List<int[]> ptSets) {
List<int[]> out=new ArrayList<>();
for (int di=0; di<R*C; di++) for (int r0=0; r0<2; r0++) for (int r1=0; r1<2; r1++) for (int r2=0; r2<2; r2++) {
int[] S=new int[R*C];
for (int r=0; r<R; r++) for (int c=0; c<C; c++) {
int nr=(r+di/C)%R, nc=(c+di%C)%C;
if (r0==1) nr=R-1-nr;
if (r1==1) nc=C-1-nc;
if (r2==1) {
int t=nr; nr=nc; nc=t;
}
S[r*C+c]=nr*C+nc;
}
boolean good=true;
for (int[] p:ptSets) if (restoringPerm(prod(S,p),p)==null) {
good=false;
break;
}
if (good)
out.add(S);
}
return out;
}
private static int[] distinctScrambles(int R, int C, LoopoverBFS bfs0, int d0, LoopoverBFS bfs1) {
List<int[]> transformations=safeTransformations(R,C,Arrays.asList(bfs0.target,bfs1.target));
List<Integer> codes=new ArrayList<>();
boolean[] seen=new boolean[bfs0.ncombos];
int[] codes0=bfs0.codesAtDepth(d0); Arrays.sort(codes0);
for (int c0:codes0) if (!seen[c0]) {
codes.add(c0);
seen[c0]=true;
int[] Pf=bfs0.codeCombo(c0), P=prod(bfs0.freeto(),Pf);
for (int[] S:transformations) {
int[] tP=prod(inv(S),prod(P,restoringPerm(prod(inv(S),bfs0.target),bfs0.target)));
int[] tPf=prod(bfs0.tofree(),tP);
for (int i:tPf) if (i<0) throw new RuntimeException();
int nc0=bfs0.comboCode(tPf);
if (bfs0.depth(nc0)!=d0) throw new RuntimeException();
seen[nc0]=true;
}
}
int[] out=new int[codes.size()];
for (int i=0; i<out.length; i++) out[i]=codes.get(i);
return out;
}
/*private static void checkSolution(int R, int C, int[] target, int[] oscrmAction, List<List<int[]>> seqs, int threshold) {
if (seqs.size()>threshold) throw new RuntimeException("Too many moves in alternate solution.");
int[] ret=prod(oscrmAction,target);
for (List<int[]> seq:seqs)
for (int[] mv:seq) {
int mcoord=mv[1], s=mv[2];
int[] nscrm=new int[ret.length];
for (int i=0; i<ret.length; i++)
if (ret[i]==-1) nscrm[i]=-1;
else {
int r=ret[i]/C, c=ret[i]%C;
nscrm[i]=mv[0]==0?(r*C+(r==mcoord?mod(c+s,C):c)):
((c==mcoord?mod(r+s,R):r)*C+c);
}
ret=nscrm;
}
if (!Arrays.toString(ret).equals(Arrays.toString(target))) {
System.out.println("INVALID ALTERNATE SOLUTION");
System.out.println("seqs=");
for (List<int[]> tmp:seqs)
System.out.println(mvseqStr(tmp));
System.out.println("final result="+Arrays.toString(ret)+"!="+Arrays.toString(target));
throw new RuntimeException("Invalid alternate solution");
}
}*/
private static void improve(int R, int C, String ststate, String enstate, int threshold, String[] midstates, boolean computeAllscrms) {
System.out.println(R+"x"+C+": "+ststate+" --> ... --> "+enstate+
"\nthreshold="+threshold+", midstates="+Arrays.toString(midstates));
//moves for prefix move sequence generation
int M=0;
for (int c=0; c<ststate.length(); c++)
if (ststate.charAt(c)=='1') M+=2;
BigInteger nM=new BigInteger(""+M);
int[][] mvs, mvactions, mvreduc;
boolean[][] rcfree0=LoopoverBFS.parseState(ststate);
mvs=new int[M][]; mvactions=new int[M][]; {
int idx=0;
for (int mr=0; mr<R; mr++)
if (rcfree0[0][mr])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {0,mr,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=r*C+(r==mr?mod(c+s,C):c);
idx++;
}
for (int mc=0; mc<C; mc++)
if (rcfree0[1][mc])
for (int s=-1; s<=1; s+=2) {
mvs[idx]=new int[] {1,mc,s};
mvactions[idx]=new int[R*C];
for (int r=0; r<R; r++)
for (int c=0; c<C; c++)
mvactions[idx][r*C+c]=(c==mc?mod(r+s,R):r)*C+c;
idx++;
}
}
Map<String,int[]> mv2action=new HashMap<>(), action2mv=new HashMap<>();
for (int mi=0; mi<M; mi++) {
mv2action.put(Arrays.toString(mvs[mi]),mvactions[mi]);
action2mv.put(Arrays.toString(mvactions[mi]),mvs[mi]);
}
mvreduc=LoopoverBFS.mvreduc(mvs);
//prefix move sequence BFS
List<List<BigInteger>> fronts=new ArrayList<>();
{
int[] id=new int[R*C]; for (int i=0; i<R*C; i++) id[i]=i;
fronts.add(new ArrayList<>(Arrays.asList(perm2code(id))));
}
Map<BigInteger,BigInteger> data=new HashMap<>();
//data.get(code)=(code of parent scramble)*M+(id of previous move)
data.put(fronts.get(0).get(0),new BigInteger("-2"));
//preparing two-phase BFS trees
int A=midstates.length;
long timest=System.currentTimeMillis();
LoopoverBFS[][] trees=new LoopoverBFS[A][2];
for (int a=0; a<A; a++) {
trees[a][0]=new LoopoverBFS(R,C,ststate,midstates[a]);
trees[a][1]=new LoopoverBFS(R,C,midstates[a],enstate);
if (computeAllscrms)
trees[a][0].computeAllActions();
}
System.out.println("total tree preprocessing time="+(System.currentTimeMillis()-timest));
//decide which midstate minimizes the total # of scrambles we must process
int bestidx=0;
long bscr=Long.MAX_VALUE;
for (int a=0; a<A; a++) {
LoopoverBFS bfs0=trees[a][0], bfs1=trees[a][1];
long scr=0;
for (int d0=0; d0<trees[a][0].D; d0++) {
int[] codes0=distinctScrambles(R,C,bfs0,d0,bfs1);
for (int d1=0; d1<trees[a][1].D; d1++)
if (d0+d1>threshold)
scr+=codes0.length*(long)bfs1.codesAtDepth(d1).length;
}
System.out.println(midstates[a]+":"+scr);
if (scr<bscr) {
bscr=scr;
bestidx=a;
}
}
for (int a=0; a<A; a++) if (a!=bestidx) {
trees[a][0].clearFronts();
trees[a][1].clearFronts();
}
System.out.println("main midstate="+midstates[bestidx]);
LoopoverBFS tree0=trees[bestidx][0], tree1=trees[bestidx][1];
System.out.printf("total combos to improve=%,d%n",bscr);
//start improvement
int[] target=new int[tree0.K+tree1.K];
System.arraycopy(tree0.target,0,target,0,tree0.K);
System.arraycopy(tree1.target,0,target,tree0.K,tree1.K);
List<int[]> symmetries=safeTransformations(R,C,Arrays.asList(target)), restorings=new ArrayList<>();
for (int[] S:symmetries)
restorings.add(restoringPerm(prod(S,target),target));
timest=System.currentTimeMillis();
long ntrials=0, ntries=0, maxtries=0;
for (int d0=0; d0<tree0.D; d0++) {
int[] bin0=distinctScrambles(R,C,tree0,d0,tree1);
for (int d1=0; d1<tree1.D; d1++) if (d0+d1>threshold) {
int[] bin1=tree1.codesAtDepth(d1);
long st=System.currentTimeMillis();
int[][] scrms0=new int[bin0.length][], scrms1=new int[bin1.length][];
for (int idx0=0; idx0<bin0.length; idx0++)
scrms0[idx0]=tree0.scrambleaction(bin0[idx0]);
for (int idx1=0; idx1<bin1.length; idx1++)
scrms1[idx1]=tree1.scrambleaction(bin1[idx1]);
System.out.println("memoizing scramble actions: "+(System.currentTimeMillis()-st)+" ms");
System.out.println(d0+","+d1+": ncombos="+String.format("%,d",bin0.length*(long)bin1.length));
long stage=1, mark0=10_000, mark=mark0;
String form="%12s%20s%n";
System.out.printf(form,"elapsed ms","#combos");
long reps=0;
st=System.currentTimeMillis();
for (int idx0=0; idx0<bin0.length; idx0++)
for (int idx1=0; idx1<bin1.length; idx1++) {
int[] oscrmAction=prod(scrms0[idx0],scrms1[idx1]);
//a piece in location i is moved to location oscrmAction[i]
//abbreviate oscrmAction as P and target as T
//if there exists A s.t. APT=T,
//then, letting B=SA*inv(S) for some S s.t. STQ=T for some Q,
//B*(SPTQ)=T
//let B=SA*inv(S) --> A=inv(S)*BS
//def invT(A)=C s.t. C[T[i]]=A[i] for all i, and all other elems of C are -1
//then invT(A)*T=A --> SPTQ=invT(SPTQ)*T
boolean reduced=false;
ntrials++;
long ntries0=ntries;
ALTSOL: for (int a=0; a<A; a++) for (int si=(a==bestidx?1:0); si<symmetries.size(); si++) {
ntries++;
int[] S=symmetries.get(si), tmp=prod(S,prod(prod(oscrmAction,target),restorings.get(si)));
int[] scrm=new int[R*C]; Arrays.fill(scrm,-1);
for (int ti=0; ti<tmp.length; ti++)
scrm[target[ti]]=tmp[ti];
int code0=trees[a][0].codeAfterScramble(scrm);
int[] action0=trees[a][0].solveaction(code0);
int code1=trees[a][1].codeAfterScramble(action0,scrm);
if (trees[a][0].depth(code0)+trees[a][1].depth(code1)<=threshold) {
reduced=true;
/*List<List<int[]>> seqs=new ArrayList<>(Arrays.asList(trees[a][0].solvemvs(code0),
trees[a][1].solvemvs(code1)));
for (List<int[]> seq:seqs)
for (int i=0; i<seq.size(); i++)
seq.set(i,action2mv.get(Arrays.toString(
prod(inv(S),prod(mv2action.get(Arrays.toString(seq.get(i))),S))
)));
checkSolution(R,C,target,oscrmAction,seqs,threshold);*/
break ALTSOL;
}
}
if (!reduced)
PREFIXANDALTBLOCK:
for (int depth=1;; depth++) {
if (fronts.size()==depth) {
fronts.add(new ArrayList<>());
for (BigInteger f:fronts.get(depth-1)) {
int[] action=code2perm(f,R*C);
int[] mvlist=mvreduc[data.get(f).compareTo(BigInteger.ZERO)<0?M:
data.get(f).mod(nM).intValue()];
for (int mi:mvlist) {
BigInteger nf=perm2code(prod(mvactions[mi],action));
if (!data.containsKey(nf)) {
data.put(nf,f.multiply(nM).add(BigInteger.valueOf(mi)));
fronts.get(depth).add(nf);
}
}
}
System.out.println("max depth-->"+depth+" (#scrambles="+fronts.get(depth).size()+")");
}
for (BigInteger f:fronts.get(depth)) {
int[] prefixaction=code2perm(f,R*C);
for (int a=0; a<A; a++) for (int si=0; si<symmetries.size(); si++) {
ntries++;
int[] S=symmetries.get(si), tmp=prod(S,prod(prod(oscrmAction,target),restorings.get(si)));
int[] scrm=new int[R*C]; Arrays.fill(scrm,-1);
for (int ti=0; ti<tmp.length; ti++)
scrm[target[ti]]=tmp[ti];
int code0=trees[a][0].codeAfterScramble(prefixaction,scrm);
int code1=trees[a][1].codeAfterScramble(trees[a][0].solveaction(code0),prefixaction,scrm);
if (depth+trees[a][0].depth(code0)+trees[a][1].depth(code1)<=threshold) {
/*List<List<int[]>> seqs=new ArrayList<>();
seqs.add(new ArrayList<>());
for (BigInteger code=f; data.get(code).compareTo(BigInteger.ZERO)>=0;
code=data.get(code).divide(nM))
seqs.get(0).add(mvs[data.get(code).mod(nM).intValue()]);
seqs.add(trees[a][0].solvemvs(code0));
seqs.add(trees[a][1].solvemvs(code1));
for (List<int[]> seq:seqs)
for (int i=0; i<seq.size(); i++)
seq.set(i,action2mv.get(Arrays.toString(
prod(inv(S),prod(mv2action.get(Arrays.toString(seq.get(i))),S))
)));
checkSolution(R,C,target,oscrmAction,seqs,threshold);*/
break PREFIXANDALTBLOCK;
}
}
}
}
maxtries=Math.max(maxtries,ntries-ntries0);
reps++;
long time=System.currentTimeMillis()-st;
if (time>=mark) {
System.out.printf(form,String.format("%,d",time),String.format("%,d",reps));
stage++;
mark=(long)(mark0*Math.pow(stage,2.5));
}
}
System.out.printf(form,String.format("%,d",System.currentTimeMillis()-st),String.format("%,d",reps));
}
}
System.out.println("improvement time="+(System.currentTimeMillis()-timest));
System.out.println("mean # alternate attempted solutions per scramble="+ntries+"/"+ntrials+"="+(ntries/(double)ntrials));
System.out.println("maximum # attempts on a scramble="+maxtries);
}
public static void main(String[] args) {
//TODO: 5x5:0x0->3x3, 6x6:0x0->3x3
long st=System.currentTimeMillis();
LoopoverBFSImprove.improve(5,5,"00011x00011","00000x00000",
27,
new String[] {
"00001x00001",
},
false
);
System.out.println("total program time="+(System.currentTimeMillis()-st));
}
}
Raw
stdouts.txt
5x5: 00011x00011 --> ... --> 00000x00000
threshold=27, midstates=[00001x00001]
X X X '0 1
X X X '2 3
X X X '4 5
'6 '7 '8 '9 10
11 12 13 14 15
ncombos=57657600
0:1 1:4 2:20 3:99 4:446 5:1975 6:8480 7:34865 8:136901 9:500300 10:1658797 11:4805567 12:11120723 13:17679617 14:15542104 15:5611876 16:545774 17:9995 18:56
#reached=57657600
D=19
total BFS time=48136
X X X X '0
X X X X '1
X X X X '2
X X X X '3
'4 '5 '6 '7 '8
ncombos=362880
0:1 1:4 2:12 3:32 4:88 5:240 6:644 7:1720 8:4424 9:10278 10:21556 11:38506 12:51846 13:40213 14:11104 15:713 16:57 17:2
#reached=181440
D=18
total BFS time=57
total tree preprocessing time=48195
00001x00001:274724883578
main midstate=00001x00001
total combos to improve=274,724,883,578
memoizing scramble actions: 3203 ms
11,17: ncombos=4,805,734
elapsed ms #combos
max depth-->1 (#scrambles=8)
10,000 3,184,852
15,275 4,805,734
memoizing scramble actions: 8348 ms
12,16: ncombos=316,952,262
elapsed ms #combos
10,000 4,448,960
56,568 26,459,505
155,884 71,654,947
320,000 146,654,903
559,016 257,945,016
691,158 316,952,262
memoizing scramble actions: 7992 ms
12,17: ncombos=11,121,132
elapsed ms #combos
10,000 3,193,138
34,424 11,121,132
memoizing scramble actions: 14842 ms
13,15: ncombos=6,303,047,627
elapsed ms #combos
10,000 4,784,587
56,568 27,004,741
155,884 76,506,643
320,000 154,776,580
559,016 270,414,627
max depth-->2 (#scrambles=48)
881,816 429,720,695
1,296,418 635,489,019
1,810,193 888,562,654
2,430,000 1,188,037,689
3,162,277 1,529,825,783
4,013,115 1,920,714,726
4,988,306 2,374,642,249
6,093,381 2,920,845,478
7,333,648 3,524,052,338
8,714,212 4,180,557,762
10,240,000 4,932,876,114
11,915,775 5,742,733,064
13,066,399 6,303,047,627
memoizing scramble actions: 14682 ms
13,16: ncombos=503,890,203
elapsed ms #combos
10,000 4,534,595
56,568 26,499,664
155,884 73,960,034
320,000 148,584,443
559,016 260,431,682
881,816 412,239,303
1,076,169 503,890,203
memoizing scramble actions: 14709 ms
13,17: ncombos=17,680,358
elapsed ms #combos
10,000 3,378,897
52,318 17,680,358
memoizing scramble actions: 14366 ms
14,14: ncombos=86,294,680,480
elapsed ms #combos
10,000 5,311,654
56,568 28,958,298
155,884 80,055,816
320,000 161,218,401
559,016 278,930,149
881,816 439,131,917
1,296,418 650,492,693
1,810,193 918,773,635
2,430,000 1,226,397,380
3,162,277 1,581,317,089
4,013,115 1,995,232,314
4,988,306 2,470,402,522
6,093,381 3,003,193,135
7,333,648 3,611,439,688
8,714,212 4,300,893,786
10,240,000 5,049,591,798
11,915,775 5,872,103,000
13,746,155 6,774,465,449
15,735,625 7,781,223,798
17,888,543 8,854,645,793
20,209,158 10,018,719,080
22,701,612 11,292,239,332
25,369,948 12,648,486,970
28,218,121 14,065,759,862
31,250,000 15,579,516,270
34,469,371 17,159,345,734
37,879,951 18,788,631,357
41,485,380 20,541,103,158
45,289,236 22,299,579,549
49,295,030 24,240,048,250
53,506,215 26,206,134,766
57,926,187 28,326,651,830
62,558,287 30,552,154,733
67,405,803 32,870,352,371
72,471,977 35,290,772,945
77,760,000 37,913,693,382
83,273,019 40,676,780,930
89,014,138 43,613,615,773
94,986,419 46,603,590,999
101,192,885 49,593,483,999
107,636,518 52,741,954,342
114,320,265 55,982,330,748
121,247,038 59,336,916,336
max depth-->3 (#scrambles=272)
max depth-->4 (#scrambles=1512)
128,419,711 62,899,220,590
135,841,129 66,688,077,979
143,514,102 70,489,619,505
151,441,410 74,315,606,336
159,625,802 78,278,290,548
168,070,000 82,659,268,272
175,207,567 86,294,680,480
memoizing scramble actions: 14518 ms
14,15: ncombos=5,541,075,935
elapsed ms #combos
10,000 4,911,047
56,568 27,372,135
155,884 76,569,643
320,000 154,574,253
559,016 269,269,833
881,816 424,328,746
1,296,418 627,156,560
1,810,193 879,534,402
2,430,000 1,176,444,544
3,162,277 1,519,289,309
4,013,115 1,915,665,097
4,988,306 2,375,883,214
6,093,381 2,919,780,915
7,333,648 3,510,459,821
8,714,212 4,175,540,844
10,240,000 4,923,016,767
11,476,849 5,541,075,935
memoizing scramble actions: 14224 ms
14,16: ncombos=442,975,215
elapsed ms #combos
10,000 4,649,556
56,568 26,101,140
155,884 72,860,169
320,000 147,343,292
559,016 258,164,897
881,816 409,838,702
950,685 442,975,215
memoizing scramble actions: 14248 ms
14,17: ncombos=15,542,990
elapsed ms #combos
10,000 3,479,136
44,356 15,542,990
memoizing scramble actions: 5702 ms
15,13: ncombos=112,849,339,770
elapsed ms #combos
10,000 4,899,044
56,568 27,451,573
155,884 76,279,364
320,000 154,001,171
559,016 269,163,151
881,816 423,048,059
1,296,418 623,402,553
1,810,193 871,334,935
2,430,000 1,166,437,249
3,162,277 1,502,678,181
4,013,115 1,901,828,234
4,988,306 2,354,820,424
6,093,381 2,861,116,343
7,333,648 3,446,289,203
8,714,212 4,088,010,411
10,240,000 4,794,336,339
11,915,775 5,586,989,467
13,746,155 6,439,932,296
15,735,625 7,365,608,177
17,888,543 8,370,513,520
20,209,158 9,439,538,014
22,701,612 10,612,773,835
25,369,948 11,866,966,612
28,218,121 13,201,814,392
31,250,000 14,627,942,326
34,469,371 16,164,806,542
37,879,951 17,795,312,459
41,485,380 19,486,491,572
45,289,236 21,278,766,602
49,295,030 23,149,003,679
53,506,215 25,087,657,603
57,926,187 27,139,253,824
62,558,287 29,276,103,131
67,405,803 31,457,526,998
72,471,977 33,791,857,932
77,760,000 36,199,880,593
83,273,019 38,663,650,797
89,014,138 41,271,987,613
94,986,419 44,043,071,515
101,192,885 46,890,071,332
107,636,518 49,834,679,701
114,320,265 52,888,589,065
121,247,038 56,147,930,120
128,419,711 59,517,197,650
135,841,129 63,056,409,726
143,514,102 66,648,594,215
151,441,410 70,306,550,261
159,625,802 74,120,091,881
168,070,000 78,015,939,531
176,776,695 82,058,539,126
185,748,553 86,207,294,982
194,988,212 90,547,855,354
204,498,286 95,085,225,649
214,281,362 99,646,102,549
224,340,004 104,381,701,318
234,676,751 109,304,475,911
242,163,051 112,849,339,770
memoizing scramble actions: 5680 ms
15,14: ncombos=31,161,044,160
elapsed ms #combos
10,000 4,697,365
56,568 27,049,175
155,884 73,811,861
320,000 151,077,980
559,016 264,188,957
881,816 412,052,614
1,296,418 601,895,846
1,810,193 834,614,049
2,430,000 1,119,355,392
3,162,277 1,454,618,092
4,013,115 1,846,432,939
4,988,306 2,292,776,943
6,093,381 2,795,919,371
7,333,648 3,369,802,680
8,714,212 4,006,667,555
10,240,000 4,721,371,223
11,915,775 5,496,106,360
13,746,155 6,341,382,057
15,735,625 7,248,999,654
17,888,543 8,225,266,660
20,209,158 9,270,494,192
22,701,612 10,384,618,273
25,369,948 11,583,885,800
28,218,121 12,879,400,455
31,250,000 14,243,682,855
34,469,371 15,718,970,276
37,879,951 17,308,036,799
41,485,380 18,961,287,381
45,289,236 20,715,100,265
49,295,030 22,542,084,059
53,506,215 24,466,737,041
57,926,187 26,530,784,812
62,558,287 28,676,144,595
67,405,803 30,940,640,240
67,876,519 31,161,044,160
memoizing scramble actions: 5668 ms
15,15: ncombos=2,000,884,770
elapsed ms #combos
10,000 4,523,914
56,568 25,663,045
155,884 69,872,734
320,000 143,293,566
559,016 250,368,661
881,816 396,075,773
1,296,418 579,743,302
1,810,193 806,144,759
2,430,000 1,082,156,530
3,162,277 1,410,823,430
4,013,115 1,793,718,592
4,468,098 2,000,884,770
memoizing scramble actions: 5666 ms
15,16: ncombos=159,958,530
elapsed ms #combos
10,000 4,209,834
56,568 24,457,505
155,884 67,208,680
320,000 138,730,949
367,852 159,958,530
memoizing scramble actions: 5646 ms
15,17: ncombos=5,612,580
elapsed ms #combos
10,000 3,070,860
18,198 5,612,580
memoizing scramble actions: 640 ms
16,12: ncombos=14,156,135,532
elapsed ms #combos
10,000 3,828,053
56,568 21,968,898
155,884 61,886,119
320,000 126,652,318
559,016 221,506,211
881,816 347,921,522
1,296,418 509,476,340
1,810,193 714,277,264
2,430,000 960,644,513
3,162,277 1,245,831,411
4,013,115 1,582,915,051
4,988,306 1,967,095,545
6,093,381 2,398,862,186
7,333,648 2,889,249,059
8,714,212 3,429,893,636
10,240,000 4,021,818,058
11,915,775 4,674,470,999
13,746,155 5,372,288,980
15,735,625 6,125,615,588
17,888,543 6,947,935,252
20,209,158 7,858,085,551
22,701,612 8,842,829,410
25,369,948 9,885,003,264
28,218,121 10,981,192,408
31,250,000 12,168,101,989
34,469,371 13,439,126,860
36,330,263 14,156,135,532
memoizing scramble actions: 626 ms
16,13: ncombos=10,979,837,946
elapsed ms #combos
10,000 3,929,159
56,568 22,252,363
155,884 61,973,819
320,000 126,797,657
559,016 221,026,442
881,816 345,735,137
1,296,418 509,699,775
1,810,193 713,335,546
2,430,000 954,218,751
3,162,277 1,243,228,003
4,013,115 1,577,201,935
4,988,306 1,956,910,304
6,093,381 2,389,354,029
7,333,648 2,874,150,341
8,714,212 3,405,795,798
Process finished with exit code 130 (interrupted by signal 2: SIGINT)
5x5: 00011x00011 --> ... --> 00000x00000
threshold=27, midstates=[00001x00001]
X X X '0 1
X X X '2 3
X X X '4 5
'6 '7 '8 '9 10
11 12 13 14 15
ncombos=57657600
0:1 1:4 2:20 3:99 4:446 5:1975 6:8480 7:34865 8:136901 9:500300 10:1658797 11:4805567 12:11120723 13:17679617 14:15542104 15:5611876 16:545774 17:9995 18:56
#reached=57657600
D=19
total BFS time=48158
X X X X '0
X X X X '1
X X X X '2
X X X X '3
'4 '5 '6 '7 '8
ncombos=362880
0:1 1:4 2:12 3:32 4:88 5:240 6:644 7:1720 8:4424 9:10278 10:21556 11:38506 12:51846 13:40213 14:11104 15:713 16:57 17:2
#reached=181440
D=18
total BFS time=55
total tree preprocessing time=48216
00001x00001:274724883578
main midstate=00001x00001
total combos to improve=274,724,883,578
memoizing scramble actions: 737 ms
16,13: ncombos=10,979,837,946
elapsed ms #combos
max depth-->1 (#scrambles=8)
10,000 3,551,847
56,568 21,447,269
155,884 60,447,124
320,000 125,500,366
559,016 220,170,395
881,816 345,564,019
1,296,418 510,376,624
1,810,193 715,005,724
2,430,000 956,925,302
3,162,277 1,247,374,499
4,013,115 1,583,083,832
4,988,306 1,964,480,054
6,093,381 2,398,423,779
7,333,648 2,887,882,805
max depth-->2 (#scrambles=48)
8,714,212 3,421,795,284
10,240,000 4,014,184,197
11,915,775 4,649,049,136
13,746,155 5,347,441,351
15,735,625 6,124,302,453
17,888,543 6,974,650,823
20,209,158 7,880,435,355
22,701,612 8,837,041,144
25,369,948 9,892,207,738
28,158,113 10,979,837,946
memoizing scramble actions: 603 ms
16,14: ncombos=3,031,858,368
elapsed ms #combos
10,000 3,878,478
56,568 22,447,262
155,884 61,586,368
320,000 125,704,550
559,016 219,990,967
881,816 346,255,755
1,296,418 507,926,956
1,810,193 709,408,729
2,430,000 949,668,776
3,162,277 1,230,069,450
4,013,115 1,554,179,309
4,988,306 1,934,642,906
6,093,381 2,360,687,082
7,333,648 2,845,159,509
7,817,784 3,031,858,368
memoizing scramble actions: 580 ms
16,15: ncombos=194,678,946
elapsed ms #combos
10,000 3,868,256
56,568 21,843,699
155,884 60,000,165
320,000 122,220,868
509,887 194,678,946
memoizing scramble actions: 581 ms
16,16: ncombos=15,563,394
elapsed ms #combos
10,000 3,652,352
42,054 15,563,394
memoizing scramble actions: 588 ms
16,17: ncombos=546,084
elapsed ms #combos
2,132 546,084
memoizing scramble actions: 51 ms
17,11: ncombos=192,761,036
elapsed ms #combos
10,000 3,348,064
56,568 19,179,518
155,884 52,005,643
320,000 106,219,461
559,016 187,945,738
574,309 192,761,036
memoizing scramble actions: 55 ms
17,12: ncombos=259,541,076
elapsed ms #combos
10,000 3,438,190
56,568 19,445,673
155,884 52,470,044
320,000 104,184,156
559,016 186,495,246
777,335 259,541,076
memoizing scramble actions: 48 ms
17,13: ncombos=201,306,278
elapsed ms #combos
10,000 3,386,205
56,568 19,140,479
155,884 51,874,099
320,000 105,228,573
559,016 186,174,965
605,094 201,306,278
memoizing scramble actions: 23 ms
17,14: ncombos=55,586,624
elapsed ms #combos
10,000 3,388,595
56,568 18,463,000
155,884 51,769,404
167,527 55,586,624
memoizing scramble actions: 10 ms
17,15: ncombos=3,569,278
elapsed ms #combos
10,000 3,284,748
10,871 3,569,278
memoizing scramble actions: 10 ms
17,16: ncombos=285,342
elapsed ms #combos
904 285,342
memoizing scramble actions: 10 ms
17,17: ncombos=10,012
elapsed ms #combos
45 10,012
memoizing scramble actions: 21 ms
18,10: ncombos=603,568
elapsed ms #combos
2,100 603,568
memoizing scramble actions: 30 ms
18,11: ncombos=1,078,168
elapsed ms #combos
3,729 1,078,168
memoizing scramble actions: 45 ms
18,12: ncombos=1,451,688
elapsed ms #combos
5,057 1,451,688
memoizing scramble actions: 38 ms
18,13: ncombos=1,125,964
elapsed ms #combos
3,923 1,125,964
memoizing scramble actions: 11 ms
18,14: ncombos=310,912
elapsed ms #combos
1,079 310,912
memoizing scramble actions: 1 ms
18,15: ncombos=19,964
elapsed ms #combos
69 19,964
memoizing scramble actions: 0 ms
18,16: ncombos=1,596
elapsed ms #combos
6 1,596
memoizing scramble actions: 0 ms
18,17: ncombos=56
elapsed ms #combos
0 56
improvement time=38685688
mean # alternate attempted solutions per scramble=25175309387/14940136300=1.685078963235429
maximum # attempts on a scramble=255
total program time=38758720
Process finished with exit code 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment