Skip to content

Instantly share code, notes, and snippets.

@coolcomputery

coolcomputery/4x4->4x6.txt

Created March 21, 2023 15:15
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/e0204bc48abda3ff3ee9877aa808e7ca to your computer and use it in GitHub Desktop.
Save coolcomputery/e0204bc48abda3ff3ee9877aa808e7ca to your computer and use it in GitHub Desktop.
Download ZIP
6x6 (Dijkstra's + "L-conjugations"): 4x4->4x6 GN<=20, 4x6->6x6 GN<=21
Raw
4x4->4x6.txt
% java -Xmx10g src/DijkstraRegion.java
6x6: [0, 1, 2, 3, 6, 7, 8, 9, 12, 13, 14, 15, 18, 19, 20, 21] --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23]
#canonical_seqs=88
canonical_seqs=[[4C], [3R, 4C, 3R'], [2R, 4C, 2R'], [1R, 4C, 1R'], [0R', 5C, 0R], [1R, 4C2, 1R'], [3R, 4C2, 3R'], [0R', 5C2, 0R], [2R, 4C2, 2R'], [1R, 4C3, 1R'], [2R, 4C3, 2R'], [0R', 5C3, 0R], [3R, 4C3, 3R'], [1R, 4C4, 1R'], [2R, 4C4, 2R'], [3R, 4C4, 3R'], [0R', 5C4, 0R], [1R, 4C', 1R'], [4C'], [3R, 4C', 3R'], [2R, 4C', 2R'], [0R', 5C', 0R], [0R, 4C, 0R'], [1R', 5C, 1R], [2R', 5C, 2R], [3R', 5C, 3R], [5C], [2R', 5C2, 2R], [0R, 4C2, 0R'], [3R', 5C2, 3R], [1R', 5C2, 1R], [3R', 5C3, 3R], [0R, 4C3, 0R'], [2R', 5C3, 2R], [1R', 5C3, 1R], [0R, 4C4, 0R'], [3R', 5C4, 3R], [2R', 5C4, 2R], [1R', 5C4, 1R], [0R, 4C', 0R'], [2R', 5C', 2R], [3R', 5C', 3R], [5C'], [1R', 5C', 1R], [5R], [5R'], [3C', 5R3, 3C], [3C', 5R4, 3C], [3C', 5R', 3C], [3C', 5R, 3C], [3C', 5R2, 3C], [2C', 5R4, 2C], [2C', 5R', 2C], [2C', 5R, 2C], [2C', 5R2, 2C], [2C', 5R3, 2C], [0C, 4R, 0C'], [0C, 4R2, 0C'], [0C, 4R3, 0C'], [0C, 4R4, 0C'], [0C, 4R', 0C'], [1C', 5R', 1C], [1C', 5R, 1C], [1C', 5R2, 1C], [1C', 5R3, 1C], [1C', 5R4, 1C], [4R], [3C, 4R, 3C'], [2C, 4R, 2C'], [1C, 4R2, 1C'], [3C, 4R2, 3C'], [1C, 4R3, 1C'], [2C, 4R3, 2C'], [1C, 4R4, 1C'], [3C, 4R4, 3C'], [2C, 4R4, 2C'], [4R'], [3C, 4R', 3C'], [2C, 4R', 2C'], [1C, 4R', 1C'], [0C', 5R, 0C], [1C, 4R, 1C'], [0C', 5R2, 0C], [2C, 4R2, 2C'], [0C', 5R3, 0C], [3C, 4R3, 3C'], [0C', 5R4, 0C], [0C', 5R', 0C]]
cost_freq={1=8, 3=32, 4=32, 5=16}
ri2loc=[4, 5, 10, 11, 16, 17, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35] loc2ri=[-1, -1, -1, -1, 0, 1, -1, -1, -1, -1, 2, 3, -1, -1, -1, -1, 4, 5, -1, -1, -1, -1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
bridge=[4, 5, 10, 11, 16, 17, 22, 23]
nconfigs=5079110400
time=69 cnt=0 d=0
time=12781 cnt=1 d=1
time=25963 cnt=5 d=2
time=30117 cnt=17 d=2
time=40499 cnt=55 d=3
time=50117 cnt=107 d=3
time=60691 cnt=566 d=4
time=70096 cnt=2700 d=5
time=80040 cnt=9278 d=6
time=90002 cnt=23945 d=7
time=100000 cnt=67853 d=7
time=200000 cnt=5557746 d=10
time=300000 cnt=13969186 d=11
time=400000 cnt=22276301 d=11
time=500000 cnt=30118679 d=11
time=600000 cnt=38106741 d=12
time=700000 cnt=44004478 d=12
time=800000 cnt=51843483 d=12
time=900000 cnt=59580551 d=12
time=1000000 cnt=67328948 d=12
time=2000000 cnt=155420862 d=13
time=3000000 cnt=244102814 d=13
time=4000000 cnt=321616927 d=13
time=5000000 cnt=402977221 d=14
time=6000000 cnt=491848374 d=14
time=7000000 cnt=574675136 d=14
time=8000000 cnt=664965749 d=14
time=9000000 cnt=749889274 d=14
time=10000000 cnt=804581822 d=14
time=11000000 cnt=855868896 d=14
time=12000000 cnt=928483983 d=14
time=13000000 cnt=1021836214 d=15
time=14000000 cnt=1115548705 d=15
time=15000001 cnt=1189639508 d=15
time=16000000 cnt=1270327139 d=15
time=17000000 cnt=1347818441 d=15
time=18000000 cnt=1446946077 d=15
time=19000000 cnt=1544599281 d=15
time=20000000 cnt=1610347660 d=15
time=21000000 cnt=1704843240 d=15
time=22000000 cnt=1795375411 d=15
time=23000000 cnt=1900015956 d=15
time=24000000 cnt=1998762460 d=15
time=25000000 cnt=2115941269 d=15
time=26000000 cnt=2239954555 d=16
time=27000000 cnt=2363267633 d=16
time=28000000 cnt=2487609229 d=16
time=29000000 cnt=2611673565 d=16
time=30000000 cnt=2735050415 d=16
time=31000000 cnt=2859799777 d=16
time=32000000 cnt=2984277032 d=16
time=33000000 cnt=3110891863 d=16
time=34000000 cnt=3238314707 d=16
time=35000000 cnt=3365449975 d=16
time=36000000 cnt=3492512775 d=16
time=37000000 cnt=3616630336 d=17
time=38000000 cnt=3739857938 d=17
time=39000000 cnt=3861622383 d=17
time=40000000 cnt=3980536869 d=17
time=41000000 cnt=4099187094 d=17
time=42000000 cnt=4220472281 d=17
time=43000000 cnt=4347363326 d=17
time=44000000 cnt=4474249478 d=17
time=45000000 cnt=4599099437 d=17
time=46000000 cnt=4717302598 d=18
time=47000000 cnt=4826975967 d=18
time=48000000 cnt=4941746984 d=18
time=49000000 cnt=5054363461 d=19
time=49295192 cnt=5079110400
diameter=20
depth_freq={0=1, 1=4, 2=16, 3=90, 4=492, 5=2474, 6=12259, 7=59574, 8=283163, 9=1300242, 10=5666906, 11=22913610, 12=82863149, 13=254076682, 14=621818069, 15=1141541684, 16=1437263840, 17=1090325622, 18=390839599, 19=30045083, 20=97841}
sample antipode:
. . . . 18 .
. . . . . .
. . . . . .
. . . . . 17
. . 24 23 . 5
6 11 . 12 . .
sol (right-to-left): [[5C'], [1R, 4C, 1R'], [5C'], [5R], [4C], [4R], [5R], [4C], [5R], [4C], [4C], [4R], [5C'], [5C'], [5R], [5R], [5C], [4C]]
Raw
4x4->4x6_source-code.txt
import java.util.*;
public class DijkstraRegion {
public static final boolean inRange(int v, int N) { return 0<=v && v<N; }
public static final boolean inRange(long v, long N) { return 0<=v && v<N; }
public static final boolean allInRange(int[] S, int N) {
for (int v:S) if (!inRange(v,N)) return false;
return true;
}
public static final int[] range(int n) {
int[] out=new int[n];
for (int i=0; i<n; i++) out[i]=i;
return out;
}
public static final int[] list2arr(List<Integer> L) {
int[] A=new int[L.size()];
for (int i=0; i<A.length; i++) A[i]=L.get(i);
return A;
}
public static final int[] sortedArr(Set<Integer> S) {
List<Integer> vals=new ArrayList<>(S);
Collections.sort(vals);
return list2arr(vals);
}
public static int[][] fromto_idx(Set<Integer> S, int N) {
for (int v:S) if (!inRange(v,N)) throw new RuntimeException();
int[] idx2set=sortedArr(S);
final int INVALID=-1;
int[] set2idx=new int[N]; Arrays.fill(set2idx,INVALID);
for (int i=0; i<idx2set.length; i++)
set2idx[idx2set[i]]=i;
return new int[][] {idx2set,set2idx};
}
public static final Set<Integer> set(int... vals) {
Set<Integer> out=new HashSet<>();
for (int v:vals) out.add(v);
return out;
}
public static final Set<Integer> difference(Set<Integer> A, Collection<Integer> B) {
Set<Integer> out=new HashSet<>(A);
out.removeAll(B);
return out;
}
private static class BigByteArray {
private static final int CHUNK_SIZE=1<<30;
public final long N;
public byte[][] chunks;
public BigByteArray(long N, int val) {
if (val!=(byte)val) throw new RuntimeException(""+val);
this.N=N;
chunks=new byte[(int)(N/CHUNK_SIZE)+1][];
for (int c=0; CHUNK_SIZE*(long)c<N; c++) {
long lo=CHUNK_SIZE*(long)c;
chunks[c]=new byte[(int)( Math.min(N,lo+CHUNK_SIZE)-lo )];
}
for (byte[] chunk:chunks) Arrays.fill(chunk,(byte)val);
}
public byte get(long i) {
if (!inRange(i,N)) throw new RuntimeException();
return chunks[(int)(i/CHUNK_SIZE)][(int)(i%CHUNK_SIZE)];
}
public void set(long i, int v) {
if (!inRange(i,N)) throw new RuntimeException();
if (v!=(byte)v) throw new RuntimeException(""+v);
chunks[(int)(i/CHUNK_SIZE)][(int)(i%CHUNK_SIZE)]=(byte)v;
}
}
private static final int[] prod(int[] A, int[] B) {
int[] C=new int[B.length];
for (int i=0; i<B.length; i++) C[i]=A[B[i]];
return C;
}
private static class Move { //single-move permutation on a RxC loopover board
public static final int mod(int n, int k) { return ((n%k)+k)%k; }
public final int R, C, N;
public final boolean row_shift;
public final int coord, shift;
public Move(int R, int C, boolean row_shift, int coord, int shift) {
if (R<=0 || C<=0) throw new RuntimeException();
if (!inRange(coord,row_shift?R:C)) throw new RuntimeException();
this.R=R; this.C=C; N=R*C;
this.row_shift=row_shift;
this.coord=coord;
this.shift=mod(shift,row_shift?C:R);
if (!inRange(this.shift,row_shift?C:R)) throw new RuntimeException();
}
public boolean same_dimensions(Move o) {
return R==o.R && C==o.C;
}
public Move inv() {
return new Move(R,C,row_shift,coord,-shift);
}
public int cost() {
return Math.min(shift,(row_shift?C:R)-shift);
}
public int move(int v) {
if (!inRange(v,N)) throw new RuntimeException();
int r=v/C, c=mod(v,C);
if (row_shift) {
if (coord==r) c=mod(c+shift,C);
}
else {
if (coord==c) r=mod(r+shift,R);
}
return r*C+c;
}
public int[] action() {
int[] out=new int[N];
for (int i=0; i<N; i++) out[i]=move(i);
return out;
}
public String toString() {
return String.format("%d%s%s",
coord,
row_shift?"R":"C",
shift==1?"":shift==mod(-1,row_shift?C:R)?"'":shift
);
}
public static int cost(Iterable<Move> mvs) {
int out=0;
for (Move mv:mvs) out+=mv.cost();
return out;
}
public static List<Move> inv(List<Move> mvs) {
List<Move> out=new ArrayList<>();
for (int i=mvs.size()-1; i>=0; i--)
out.add(mvs.get(i).inv());
return out;
}
public static int[] action(List<Move> mvs) {
for (int i=1; i<mvs.size(); i++)
if (!mvs.get(0).same_dimensions(mvs.get(i))) throw new RuntimeException();
int[] out=range(mvs.get(0).N);
for (Move mv:mvs) out=prod(out,mv.action());
return out;
}
}
public static String display(int R, int C, int[] pcs, int[] locs) {
if (pcs.length!=locs.length) throw new RuntimeException();
final int BLANK=-1;
int[] board=new int[R*C]; Arrays.fill(board,BLANK);
for (int i=0; i<pcs.length; i++)
board[locs[i]]=pcs[i];
boolean alphaMode=R*C<=26;
int CHARS_PER_CELL=alphaMode?1:(1+(R*C+"").length());
String CELL_FORMAT="%"+CHARS_PER_CELL+"s";
StringBuilder s=new StringBuilder();
for (int loc=0; loc<R*C; loc++) {
int pc=board[loc];
s.append(
String.format(CELL_FORMAT,
pc==BLANK? ".": alphaMode? (""+(char)('A'+pc)): (pc+1)
)
).append(loc%C==C-1?"\n":"");
}
return s.substring(0,s.length()-1);
}
//bijection {K-length lists of numbers in [0,N)} <--> [0,(N choose K)*K!)
//must have (N choose K)*K! < Integer.MAX_VALUE for these methods to work properly
private static final long perm2code(int N, int[] P) {
//transform list L=[0,...,N-1] to [....]|P using swaps (i,J_i) for i=N-1...N-K;
// then encode [J_{N-1},...J_{N-K}] as a number using mixed-radix valuation
if (!allInRange(P,N)) throw new RuntimeException();
int[] L=range(N), locInL=range(N);
int K=P.length;
long out=0, pow=1;
for (int i=N-1, pi=K-1; i>=N-K; i--, pi--) {
int j=locInL[P[pi]];
int Li=L[i], Lj=L[j];
if (Lj!=P[pi]) throw new RuntimeException();
L[i]=Lj; L[j]=Li;
locInL[Li]=j; locInL[Lj]=i;
out+=j*pow;
pow*=(i+1);
}
return out;
}
private static final int[] code2perm(int N, int K, long code) {
int[] L=range(N);
for (int i=N-1; i>=N-K; i--) {
int j=(int)(code%(i+1));
int Li=L[i], Lj=L[j];
L[i]=Lj; L[j]=Li;
code/=(i+1);
}
if (code!=0) throw new RuntimeException(""+code);
return Arrays.copyOfRange(L,N-K,N);
}
public static void dijkstra(int R, int C, int[] start, int[] end, List<List<Move>> seqs0) {
System.out.printf("%dx%d: %s --> %s%n",R,C,Arrays.toString(start),Arrays.toString(end));
if (!allInRange(start,R*C) || !allInRange(end,R*C)) throw new RuntimeException();
for (List<Move> seq:seqs0) for (Move mv:seq) if (mv.R!=R || mv.C!=C) throw new RuntimeException();
int nActs; List<List<Move>> canonical_seqs; int[][] canonical_acts; int[] canonical_costs; {
int[] ID_ACT=range(R*C);
Map<String,List<Move>> act2seq=new HashMap<>();
for (boolean inv:new boolean[] {false,true})
for (List<Move> seq0:seqs0) {
List<Move> seq=inv?Move.inv(seq0):seq0;
int[] act=Move.action(seq);
//every action we use must preserve every element in the start array
// and not be equal to the identity (do-nothing) action
if (Arrays.equals(prod(act,start),start) && !Arrays.equals(act,ID_ACT)) {
String act_s=Arrays.toString(act);
if (!act2seq.containsKey(act_s)
|| Move.cost(seq)<Move.cost(act2seq.get(act_s)))
act2seq.put(act_s,seq);
}
}
List<String> act_ss=new ArrayList<>(act2seq.keySet());
Collections.sort(act_ss);
canonical_seqs=new ArrayList<>();
for (String act_s:act_ss)
canonical_seqs.add(act2seq.get(act_s));
System.out.printf("#canonical_seqs=%d%n",canonical_seqs.size());
System.out.printf("canonical_seqs=%s%n",canonical_seqs);
for (List<Move> seq:canonical_seqs) {
int[] act=Move.action(seq);
if (!Arrays.equals(prod(act,start),start))
throw new RuntimeException();
}
nActs=canonical_seqs.size();
canonical_acts=new int[nActs][]; canonical_costs=new int[nActs];
for (int i=0; i<nActs; i++) {
List<Move> seq=canonical_seqs.get(i);
canonical_acts[i]=Move.action(seq);
canonical_costs[i]=Move.cost(seq);
}
Map<Integer,Integer> cost_freq=new TreeMap<>();
for (List<Move> seq:canonical_seqs) {
int c=Move.cost(seq);
cost_freq.put(c,cost_freq.getOrDefault(c,0)+1);
}
System.out.printf("cost_freq=%s%n",cost_freq);
}
int N=R*C;
int[] ri2loc, loc2ri; {
int[][] fromto=fromto_idx(difference(set(range(N)),set(start)),N);
ri2loc=fromto[0]; loc2ri=fromto[1];
System.out.printf("ri2loc=%s loc2ri=%s%n",Arrays.toString(ri2loc),Arrays.toString(loc2ri));
}
class Config2Code {
public final int nRem=N-start.length, nBridge=end.length-start.length;
public long config2code(int[] config) {
if (config.length!=nBridge) throw new RuntimeException();
return perm2code(nRem,prod(loc2ri,config));
}
public int[] code2config(long code) {
return prod(ri2loc,code2perm(nRem,nBridge,code));
}
} Config2Code $=new Config2Code();
//assert that set(end) is a strict superset of set(start)
if (difference(set(start),set(end)).size()!=0 || end.length<=start.length) throw new RuntimeException();
int[] bridge=sortedArr(difference(set(end),set(start)));
System.out.printf("bridge=%s%n",Arrays.toString(bridge));
long nconfigs=1; for (int i=N-start.length; i>N-end.length; i--) nconfigs*=i;
System.out.printf("nconfigs=%d%n",nconfigs);
if (nconfigs>=(1L<<40)) throw new RuntimeException();
int INVALID_DEPTH=-1;
BigByteArray depths=new BigByteArray(nconfigs,INVALID_DEPTH); {
long solved_code=$.config2code(bridge);
depths.set(solved_code,0);
}
long cnt=0;
long st=System.currentTimeMillis(), mark=0;
for (int d=0;; d++) {
if (d>Byte.MAX_VALUE) throw new RuntimeException();
for (long code=0; code<nconfigs; code++)
if (depths.get(code)==d) {
long t=System.currentTimeMillis()-st;
if (t>=mark) {
System.out.printf("time=%d cnt=%d d=%d%n",t,cnt,d);
mark+=mark<100_000?10_000:mark<1000_000?100_000:1000_000;
}
int[] config=$.code2config(code);
for (int m=0; m<nActs; m++) {
long ncode=$.config2code(prod(canonical_acts[m],config));
int od=depths.get(ncode), nd=d+canonical_costs[m];
if (od==INVALID_DEPTH || nd<od)
depths.set(ncode,nd);
}
cnt++;
}
boolean finished=true;
for (long code=0; code<nconfigs; code++) {
int depth=depths.get(code);
if (depth!=INVALID_DEPTH && depth>=d) {
finished=false;
break;
}
}
if (finished) break;
}
System.out.printf("time=%d cnt=%d%n",System.currentTimeMillis()-st,cnt);
if (cnt!=nconfigs)
System.out.printf("WARNING: # of configs found=%d != %d=expected # of configs%s%n",
cnt,nconfigs,2*cnt==nconfigs?" (parity restriction?)":"");
int diam=0;
Map<Integer,Integer> depth_freq=new TreeMap<>();
for (long code=0; code<nconfigs; code++) {
int d=depths.get(code);
if (d!=INVALID_DEPTH) {
diam=Math.max(diam,d);
depth_freq.put(d,depth_freq.getOrDefault(d,0)+1);
}
}
System.out.printf("diameter=%d%ndepth_freq=%s%n",diam,depth_freq);
//print an antipode
class Solver {
public List<List<Move>> sol(long code) {
if (depths.get(code)==INVALID_DEPTH) throw new RuntimeException();
List<List<Move>> out=new ArrayList<>();
while (depths.get(code)>0) {
int[] config=$.code2config(code);
long bcode=-1; List<Move> bseq=null;
for (int m=0; m<nActs; m++) {
long ncode=$.config2code(prod(canonical_acts[m],config));
if (depths.get(ncode)+canonical_costs[m]==depths.get(code)) {
bcode=ncode;
bseq=canonical_seqs.get(m);
break;
}
}
if (bseq==null) throw new RuntimeException();
code=bcode;
out.add(bseq);
}
Collections.reverse(out); //use right-to-left convention (apply rightmost move, then left-most, etc.
//this is so that we match the reading convention within each sequence element of out
return out;
}
} Solver S$=new Solver();
System.out.println("sample antipode:");
for (long code=0; code<nconfigs; code++)
if (depths.get(code)==diam) {
System.out.println(display(R,C,bridge,$.code2config(code))+"\nsol (right-to-left): "+S$.sol(code));
break;
}
}
public static List<List<Move>> singleMoves(int R, int C) {
List<List<Move>> out=new ArrayList<>();
for (boolean row_shift:new boolean[] {true,false})
for (int coord=0; coord<(row_shift?R:C); coord++)
for (int shift:new int[] {-1,1})
out.add(Collections.singletonList(new Move(R,C,row_shift,coord,shift)));
return out;
}
public static void dijkstra(int R, int C, int[] start, int[] end) {
dijkstra(R,C,start,end,singleMoves(R,C));
}
public static List<List<Move>> Lconjugations(int R, int C, int[] region) {
boolean[] rowCovered=new boolean[R], clmCovered=new boolean[C];
for (int i:region) {
rowCovered[i/C]=true;
clmCovered[i%C]=true;
}
List<List<Move>> out=new ArrayList<>(singleMoves(R,C));
for (boolean conj_dim:new boolean[] {false,true})
for (int co=0; co<(conj_dim?R:C); co++)
if ((conj_dim?rowCovered:clmCovered)[co])
for (int co_sh=0; co_sh<(conj_dim?C:R); co_sh++) if (co_sh!=0) {
Move j=new Move(R,C,conj_dim,co,co_sh);
for (int sco=0; sco<(conj_dim?C:R); sco++)
for (int ssh=0; ssh<(conj_dim?R:C); ssh++)
out.add(Arrays.asList(j,new Move(R,C,!conj_dim,sco,ssh),j.inv()));
}
return out;
}
public static void dijkstra_Lconj(int R, int C, int[] start, int[] end) {
dijkstra(R,C,start,end,Lconjugations(R,C,start));
}
public static void main(String[] args) {
int R=6, C=6;
class RegionHelp {
public int[] blockRegion(int[] rs, int[] cs) {
Set<Integer> S=new HashSet<>();
for (int r:rs) for (int c:cs) S.add(r*C+c);
return sortedArr(S);
}
public int[] blockRegion(int[] rs) {
return blockRegion(rs,rs);
}
} RegionHelp $=new RegionHelp();
dijkstra_Lconj(R,C,$.blockRegion(range(4)),$.blockRegion(range(4),range(6)));
}
}
Raw
4x6->6x6.txt
6x6: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23] --> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
cost_freq={1=4, 2=4, 3=26, 4=24, 5=72, 6=60, 7=70, 8=40, 9=20}
ri2loc=[24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35] loc2ri=[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
bridge=[24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
nconfigs=479001600
time=320 cnt=0 d=0
time=10002 cnt=2806 d=6
time=20000 cnt=106688 d=9
time=30000 cnt=257775 d=10
time=40000 cnt=424177 d=10
time=50000 cnt=589686 d=10
time=60000 cnt=759268 d=10
time=70000 cnt=942680 d=11
time=80000 cnt=1137018 d=11
time=90000 cnt=1334102 d=11
time=100000 cnt=1529923 d=11
time=200000 cnt=3443149 d=12
time=300000 cnt=5405655 d=12
time=400000 cnt=7390190 d=12
time=500000 cnt=9509950 d=13
time=600000 cnt=11696146 d=13
time=700000 cnt=13925305 d=13
time=800000 cnt=16115873 d=13
time=900000 cnt=18347065 d=13
time=1000000 cnt=20558584 d=13
time=2000000 cnt=44269042 d=14
time=3000000 cnt=68253781 d=14
time=4000000 cnt=93602992 d=15
time=5000000 cnt=118971500 d=15
time=6000000 cnt=144366871 d=15
time=7000000 cnt=169854458 d=16
time=8000000 cnt=195774880 d=16
time=9000000 cnt=221817741 d=16
time=10000000 cnt=247844197 d=16
time=11000000 cnt=273867968 d=16
time=12000000 cnt=299822744 d=16
time=13000000 cnt=325729260 d=17
time=14000000 cnt=351530408 d=17
time=15000000 cnt=377248787 d=17
time=16000000 cnt=403043068 d=17
time=17000000 cnt=428763641 d=18
time=18000000 cnt=453206939 d=18
time=19000000 cnt=476835156 d=19
time=19111965 cnt=479001600
diameter=21
depth_freq={0=1, 1=4, 2=8, 3=34, 4=224, 5=892, 6=2965, 7=11110, 8=44124, 9=159060, 10=541924, 11=1801924, 12=5901323, 13=17132692, 14=44359213, 15=96249480, 16=141263572, 17=119398514, 18=47277902, 19=4745530, 20=109544, 21=1560}
Process finished with exit code 0
Raw
4x6->6x6_source-code.txt
import java.util.*;
public class DijkstraRegion {
public static final boolean inRange(int v, int N) { return 0<=v && v<N; }
public static final boolean allInRange(int[] S, int N) {
for (int v:S) if (!inRange(v,N)) return false;
return true;
}
public static final int[] range(int n) {
int[] out=new int[n];
for (int i=0; i<n; i++) out[i]=i;
return out;
}
public static final int[] list2arr(List<Integer> L) {
int[] A=new int[L.size()];
for (int i=0; i<A.length; i++) A[i]=L.get(i);
return A;
}
public static final int[] sortedArr(Set<Integer> S) {
List<Integer> vals=new ArrayList<>(S);
Collections.sort(vals);
return list2arr(vals);
}
public static int[][] fromto_idx(Set<Integer> S, int N) {
for (int v:S) if (!inRange(v,N)) throw new RuntimeException();
int[] idx2set=sortedArr(S);
final int INVALID=-1;
int[] set2idx=new int[N]; Arrays.fill(set2idx,INVALID);
for (int i=0; i<idx2set.length; i++)
set2idx[idx2set[i]]=i;
return new int[][] {idx2set,set2idx};
}
public static final Set<Integer> set(int... vals) {
Set<Integer> out=new HashSet<>();
for (int v:vals) out.add(v);
return out;
}
public static final Set<Integer> difference(Set<Integer> A, Collection<Integer> B) {
Set<Integer> out=new HashSet<>(A);
out.removeAll(B);
return out;
}
private static final int[] prod(int[] A, int[] B) {
int[] C=new int[B.length];
for (int i=0; i<B.length; i++) C[i]=A[B[i]];
return C;
}
private static class Move { //single-move permutation on a RxC loopover board
public static final int mod(int n, int k) { return ((n%k)+k)%k; }
public final int R, C, N;
public final boolean row_shift;
public final int coord, shift;
public Move(int R, int C, boolean row_shift, int coord, int shift) {
if (R<=0 || C<=0) throw new RuntimeException();
if (!inRange(coord,row_shift?R:C)) throw new RuntimeException();
this.R=R; this.C=C; N=R*C;
this.row_shift=row_shift;
this.coord=coord;
this.shift=mod(shift,row_shift?C:R);
if (!inRange(this.shift,row_shift?C:R)) throw new RuntimeException();
}
public boolean same_dimensions(Move o) {
return R==o.R && C==o.C;
}
public Move inv() {
return new Move(R,C,row_shift,coord,-shift);
}
public int cost() {
return Math.min(shift,(row_shift?C:R)-shift);
}
public int move(int v) {
if (!inRange(v,N)) throw new RuntimeException();
int r=v/C, c=mod(v,C);
if (row_shift) {
if (coord==r) c=mod(c+shift,C);
}
else {
if (coord==c) r=mod(r+shift,R);
}
return r*C+c;
}
public int[] action() {
int[] out=new int[N];
for (int i=0; i<N; i++) out[i]=move(i);
return out;
}
public String toString() {
return String.format("%d%s%s",
coord,
row_shift?"R":"C",
shift==1?"":shift==mod(-1,row_shift?C:R)?"'":shift
);
}
public static int cost(Iterable<Move> mvs) {
int out=0;
for (Move mv:mvs) out+=mv.cost();
return out;
}
public static List<Move> inv(List<Move> mvs) {
List<Move> out=new ArrayList<>();
for (int i=mvs.size()-1; i>=0; i--)
out.add(mvs.get(i).inv());
return out;
}
public static int[] action(List<Move> mvs) {
for (int i=1; i<mvs.size(); i++)
if (!mvs.get(0).same_dimensions(mvs.get(i))) throw new RuntimeException();
int[] out=range(mvs.get(0).N);
for (Move mv:mvs) out=prod(out,mv.action());
return out;
}
}
//bijection {K-length lists of numbers in [0,N)} <--> [0,(N choose K)*K!)
//must have (N choose K)*K! < Integer.MAX_VALUE for these methods to work properly
private static final long perm2code(int N, int[] P) {
//transform list L=[0,...,N-1] to [....]|P using swaps (i,J_i) for i=N-1...N-K;
// then encode [J_{N-1},...J_{N-K}] as a number using mixed-radix valuation
if (!allInRange(P,N)) throw new RuntimeException();
int[] L=range(N), locInL=range(N);
int K=P.length;
long out=0, pow=1;
for (int i=N-1, pi=K-1; i>=N-K; i--, pi--) {
int j=locInL[P[pi]];
int Li=L[i], Lj=L[j];
if (Lj!=P[pi]) throw new RuntimeException();
L[i]=Lj; L[j]=Li;
locInL[Li]=j; locInL[Lj]=i;
out+=j*pow;
pow*=(i+1);
}
return out;
}
private static final int[] code2perm(int N, int K, long code) {
int[] L=range(N);
for (int i=N-1; i>=N-K; i--) {
int j=(int)(code%(i+1));
int Li=L[i], Lj=L[j];
L[i]=Lj; L[j]=Li;
code/=(i+1);
}
if (code!=0) throw new RuntimeException(""+code);
return Arrays.copyOfRange(L,N-K,N);
}
public static void dijkstra(int R, int C, int[] start, int[] end, List<List<Move>> seqs0) {
System.out.printf("%dx%d: %s --> %s%n",R,C,Arrays.toString(start),Arrays.toString(end));
if (!allInRange(start,R*C) || !allInRange(end,R*C)) throw new RuntimeException();
for (List<Move> seq:seqs0) for (Move mv:seq) if (mv.R!=R || mv.C!=C) throw new RuntimeException();
int nActs; int[][] canonical_acts; int[] canonical_costs; {
int[] ID_ACT=range(R*C);
Map<String,List<Move>> act2seq=new HashMap<>();
for (boolean inv:new boolean[] {false,true})
for (List<Move> seq0:seqs0) {
List<Move> seq=inv?Move.inv(seq0):seq0;
int[] act=Move.action(seq);
//every action we use must preserve every element in the start array
// and not be equal to the identity (do-nothing) action
if (Arrays.equals(prod(act,start),start) && !Arrays.equals(act,ID_ACT)) {
String act_s=Arrays.toString(act);
if (!act2seq.containsKey(act_s)
|| Move.cost(seq)<Move.cost(act2seq.get(act_s)))
act2seq.put(act_s,seq);
}
}
List<String> act_ss=new ArrayList<>(act2seq.keySet());
Collections.sort(act_ss);
List<List<Move>> canonical_seqs;
canonical_seqs=new ArrayList<>();
for (String act_s:act_ss)
canonical_seqs.add(act2seq.get(act_s));
for (List<Move> seq:canonical_seqs) {
int[] act=Move.action(seq);
if (!Arrays.equals(prod(act,start),start))
throw new RuntimeException();
}
nActs=canonical_seqs.size();
canonical_acts=new int[nActs][]; canonical_costs=new int[nActs];
for (int i=0; i<nActs; i++) {
List<Move> seq=canonical_seqs.get(i);
canonical_acts[i]=Move.action(seq);
canonical_costs[i]=Move.cost(seq);
}
Map<Integer,Integer> cost_freq=new TreeMap<>();
for (List<Move> seq:canonical_seqs) {
int c=Move.cost(seq);
cost_freq.put(c,cost_freq.getOrDefault(c,0)+1);
}
System.out.printf("cost_freq=%s%n",cost_freq);
}
int N=R*C;
int[] ri2loc, loc2ri; {
int[][] fromto=fromto_idx(difference(set(range(N)),set(start)),N);
ri2loc=fromto[0]; loc2ri=fromto[1];
System.out.printf("ri2loc=%s loc2ri=%s%n",Arrays.toString(ri2loc),Arrays.toString(loc2ri));
}
class Config2Code {
public final int nRem=N-start.length, nBridge=end.length-start.length;
public long config2code(int[] config) {
if (config.length!=nBridge) throw new RuntimeException();
return perm2code(nRem,prod(loc2ri,config));
}
public int[] code2config(long code) {
return prod(ri2loc,code2perm(nRem,nBridge,code));
}
} Config2Code $=new Config2Code();
//assert that set(end) is a strict superset of set(start)
if (difference(set(start),set(end)).size()!=0 || end.length<=start.length) throw new RuntimeException();
int[] bridge=sortedArr(difference(set(end),set(start)));
System.out.printf("bridge=%s%n",Arrays.toString(bridge));
long nconfigs=1; for (int i=N-start.length; i>N-end.length; i--) nconfigs*=i;
System.out.printf("nconfigs=%d%n",nconfigs);
if (nconfigs>=Integer.MAX_VALUE) throw new RuntimeException();
int INVALID_DEPTH=Integer.MAX_VALUE;
int[] depths=new int[(int)nconfigs];
Arrays.fill(depths,INVALID_DEPTH); {
long solved_code=$.config2code(bridge);
depths[(int)solved_code]=0;
}
long cnt=0;
long st=System.currentTimeMillis(), mark=0;
for (int d=0;; d++) {
for (long code=0; code<nconfigs; code++)
if (depths[(int)code]==d) {
long t=System.currentTimeMillis()-st;
if (t>=mark) {
System.out.printf("time=%d cnt=%d d=%d%n",t,cnt,d);
mark+=mark<100_000?10_000:mark<1000_000?100_000:1000_000;
}
int[] config=$.code2config(code);
for (int m=0; m<nActs; m++) {
long ncode=$.config2code(prod(canonical_acts[m],config));
int nd=d+canonical_costs[m];
if (nd<depths[(int)ncode])
depths[(int)ncode]=nd;
}
cnt++;
}
boolean finished=true;
for (int depth:depths) if (depth!=INVALID_DEPTH && depth>=d) {
finished=false;
break;
}
if (finished) break;
}
System.out.printf("time=%d cnt=%d%n",System.currentTimeMillis()-st,cnt);
if (cnt!=nconfigs) {
System.out.printf("WARNING: # of configs found=%d != %d=expected # of configs%s%n",
cnt,nconfigs,
2*cnt==nconfigs?" (parity restriction?)":""
);
}
int diam=0; for (int d:depths) if (d!=INVALID_DEPTH) diam=Math.max(diam,d);
System.out.printf("diameter=%d%n",diam);
Map<Integer,Integer> depth_freq=new TreeMap<>();
for (int d:depths) if (d!=INVALID_DEPTH) depth_freq.put(d,depth_freq.getOrDefault(d,0)+1);
System.out.printf("depth_freq=%s%n",depth_freq);
}
public static void dijkstra(int R, int C, int[] start, int[] end) {
List<List<Move>> singleMvSeqs=new ArrayList<>();
for (boolean row_shift:new boolean[] {true,false})
for (int coord=0; coord<(row_shift?R:C); coord++)
for (int shift:new int[] {-1,1})
singleMvSeqs.add(Collections.singletonList(new Move(R,C,row_shift,coord,shift)));
dijkstra(R,C,start,end,singleMvSeqs);
}
public static void main(String[] args) {
int R=6, C=6;
List<List<Move>> comms=new ArrayList<>();
for (int[] row_csh:new int[][] {{R-1,-1},{R-2,1}}) {
int r=row_csh[0], csh=row_csh[1];
for (int mask=0; mask<(1<<C); mask++) {
List<Move> clm_shifts=new ArrayList<>();
for (int c=0; c<C; c++) if (((mask>>>c)&1)!=0)
clm_shifts.add(new Move(R,C,false,c,csh));
for (int rsh=0; rsh<C; rsh++) {
List<Move> comm=new ArrayList<>(clm_shifts);
comm.add(new Move(R,C,true,r,rsh));
comm.addAll(Move.inv(clm_shifts));
comms.add(comm);
}
}
}
dijkstra(R,C,range((R-2)*C),range(R*C),comms);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment