My trial to make a mapping of (2x2x2 rubik's cube, poket cube, mini cube)'s states with solutions.Recursive function wanted.


#1

Hello everyone,

I’m trying to make a pocket cube solver in Julia.

I would like some advises, remarks and ultimately some help to write a optimized recursive function to replace my “for loop”.

First some explanations of my method:

  1. I fix one of the 8 corners and move the others around it.

  2. I represent the cube with an a 1x21 Array{Int8,2} (3 faces for each 7 corners left).

Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]
  1. I use the permute!(v,p) function from the combinatorics.jl packages to rotate the cube.I define 6 permutations, one for every quarter turn possible (top,right,front+anticlockwise).
T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]
  1. I stock the cube states in a Int32[] array and one cube state is define by:
state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+(cube[16]-1)

So I look at one face of 6 corners and I made a integer in a 21 radix/base.

  1. I use string to remember the moves. “TFRtfr” mean rotate the cube (top clockwise then front clockwise then right clockwise then top anticlockwise then front anticlockwise then right anticlockwise).

Here is my code:

using Combinatorics

global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global cube = Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]

global stateslist=Int32[]
global rotlist=String[]
global rot=""
global numb=Int32(1)
global inversrot=String["t","f","r","T","F","R"]

function rotcube(r)
  global cube,rot,T,F,R,Ti,Fi,Ri
  if r==0 && !endswith(rot,"t") && !endswith(rot,"TT")
    permute!(cube,T)
    rot*="T"
    return 0
  elseif r==1 && !endswith(rot,"f") && !endswith(rot,"FF")
    permute!(cube,F)
    rot*="F"
    return 0
  elseif r==2 && !endswith(rot,"r") && !endswith(rot,"RR")
    permute!(cube,R)
    rot*="R"
    return 0
  elseif r==3 && !endswith(rot,"T") && !endswith(rot,"t")
    permute!(cube,Ti)
    rot*="t"
    return 0
  elseif r==4 && !endswith(rot,"F") && !endswith(rot,"f")
    permute!(cube,Fi)
    rot*="f"
    return 0
  elseif r==5 && !endswith(rot,"R") && !endswith(rot,"r")
    permute!(cube,Ri)
    rot*="r"
    return 0
  else
    return 1
  end
end

function jumpcube(way)
  global cube,T,F,R,Ti,Fi,Ri
  for i in way
    if i=='T'
      permute!(cube,T)
    elseif i=='F'
      permute!(cube,F)
    elseif i=='R'
      permute!(cube,R)
    elseif i=='t'
      permute!(cube,Ti)
    elseif i=='f'
      permute!(cube,Fi)
    elseif i=='r'
      permute!(cube,Ri)
    end
  end
end

function upstates()
  global cube,rot,stateslist,rotlist
  state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
  index=findin(stateslist,state)
  if index==[]
    push!(stateslist,state)
    push!(rotlist,rot)
  elseif length(rotlist[index[1]])>=length(rot) && findin([rot],split(rotlist[index[1]],'/'))==[]
    rotlist[index[1]]*="/"*rot
  end
end 

while sizeof(rot)<5 #the number of quarter turn, 14 is the maximum to solve any position of the cube.
  for i in 0:5
    flag=rotcube(i)
    upstates()
    if flag == 0
      jumpcube(inversrot[i+1])
      rot=chop(rot)
    end
  end
  cube = Int8[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21]
  jumpcube(split(rotlist[numb],'/')[1])
  rot=split(rotlist[numb],'/')[1]
  numb+=1
end

for o in rotlist
  print(o*"-|-")
end
println("---------------------------")

Please help me to improve this code, target the problems and bad use of coding.

I wanna replace the for loop with a recursive function but I need some advises.

Thanks you very much

rapasite


#2

You might be able to partially solve for the corner rotations individually, and then a greedy pathfinder with a distance metric could possibly work


#3

Hi @y4lu, I didn’t get your answer.

I am starting with the solved cube and exploring all the possibilities.
For every possibilities (state of the cube) I stock the configuration of the cube in “stateslist” and the corresponding moves to get there from the solve cube in “rotlist”.

So at rotlist[i] is a string who contain the moves to go to the stateslist[i] cube configuration from the solved cube (if you make the inverse of the moves in rotlist[i] you go back to the solved cube). Witch mean the cube is completely solve already.

Of course it is not convenient at the moment to take a scramble cube and get the best solution from my program to solve it. Once the code is optimized I plan to make a user friendly interface.

As for a corner rotation individually this is a impossible move to make on a rubik’s cube.

thx you

:sun_with_face:


#4

That’s okay, my answer isn’t certain to work, and it seems you have a working solver
It’s pretty nice really, I’d probably have written much more code to get something similar

In one move, yes, and just on it’s own, probably also yes-ish, but this may be half of what makes rubiks cubes tricky… You can do a sequence of down-left-up-up to rotate a corner 120 degrees and be back at the same corner position.
I had meant partially solving for both the position and corner-face-rotation as `rotation’ though, and you’d have to find a way of combining the individual solutions back into grouped turns of the cube

this may help visualize the corners
pocket-cube


#5

thanks, I am thinking a lot about this.

Since nobody answer yet for the recursive version I did some test on my own, Here is my new code:

It’s pretty AMAZING to solve all the (pocketcube,minicube,2x2x2 rubik’s cube) in LESS THAN 40 LINES OF JULIA CODE!!!

thanks julia :dragon_face:

using Combinatorics

global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global stateslist=Int32[]
global rotlist=String[]

cube=Int8[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20,21]
rot=""

function browsecube(cube,rot)
  if length(rot)>6
    return
  end
  state=Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
  index=findin(stateslist,state)
  if index!=[]
    if length(rot) < length(split(rotlist[index[1]],'/')[1])
      rotlist[index[1]]=rot
    elseif length(rot) == length(split(rotlist[index[1]],'/')[1])
      rotlist[index[1]]*="/"*rot
    else
      return
    end
  else
    push!(rotlist,rot)
    push!(stateslist,state)
  end
  browsecube(cube[T],rot*"T")
  browsecube(cube[F],rot*"F")
  browsecube(cube[R],rot*"R")
  browsecube(cube[Ti],rot*"t")
  browsecube(cube[Fi],rot*"f")
  browsecube(cube[Ri],rot*"r")
end

@time browsecube(cube,rot)

for o in rotlist
  print(o*"-|-")
end

Since I have a lot to learn about Julia I will be glad if someone point out the part slowing it down because it is very long to evaluate.
I know I am making some strange stuff so please ask me some questions if needed.

Tips needed to speed it up. :fireworks:

thx!


#6

You can save a bit of time by only keeping the shortest rotlist string, about +50% speed-up on the local machine

## version 2
## much faster
global const T =Int8[7 ,8 ,9 ,1 ,2 ,3 ,10,11,12,4 ,5 ,6 ,13,14,15,16,17,18,19,20,21]
global const Ti=Int8[4 ,5 ,6 ,10,11,12,1 ,2 ,3 ,7 ,8 ,9 ,13,14,15,16,17,18,19,20,21]
global const F =Int8[1 ,2 ,3 ,4 ,5 ,6 ,15,13,14,9 ,7 ,8 ,16,17,18,12,10,11,19,20,21]
global const Fi=Int8[1 ,2 ,3 ,4 ,5 ,6 ,11,12,10,17,18,16,8 ,9 ,7 ,13,14,15,19,20,21]
global const R =Int8[1 ,2 ,3 ,12,10,11,7 ,8 ,9 ,16,17,18,13,14,15,21,19,20,6 ,4 ,5 ]
global const Ri=Int8[1 ,2 ,3 ,20,21,19,7 ,8 ,9 ,5 ,6 ,4 ,13,14,15,10,11,12,17,18,16]

global const Tii=T[T];
global const Fii=F[F];
global const Rii=R[R];

println("T[Tii] == Ti ", T[Tii] == Ti );
println("F[Fii] == Fi ", F[Fii] == Fi );
println("R[Rii] == Ri ", R[Rii] == Ri );


mutable struct xcube
  id::Int32;
  cube::Array{Int8,1};
  parent::Int32;
  last::Int8;
  end;


function initcube()
  cube=Int8[1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20,21];
  rot="";
  local stateslist=Dict{Int32, xcube}();
  local rotlist=Int32[]

  println("begin");
  @time (sl, rl) = browsecubeW(cube,rot, stateslist, rotlist);

  return(sl, rl);
  end;


function stateid(cube)
    return Int32((cube[1]-1)*21^5+(cube[4]-1)*21^4+(cube[7]-1)*21^3+(cube[10]-1)*21^2+(cube[13]-1)*21+cube[16]-1)
    end;

function addstate(cube, sl, rl, p, r)
  cubeid = stateid(cube);
  x = get!(sl, cubeid, xcube(cubeid, cube, p, r));
  if((x.parent == p) & (x.last == r)) 
    push!(rl, cubeid);
    end;
  return(sl, rl);
  end;


function browsecubeW(cube,rot, sl, rl, b=0)
  xbreak = 0;
  sl, rl = addstate(cube, sl, rl, 0, 0);

  local iter = 1;
  local a1 = time();

  while(xbreak==0)

    local ccubeid = rl[iter];
    local ccube = sl[ccubeid];

    if(iter%10000 == 0)
      print(time() - a1, " ", length(sl), " ", iter, " ");
      end;
    if(ccube.last != 1)
      sl, rl = addstate(ccube.cube[T], sl, rl, iter, 1);
      sl, rl = addstate(ccube.cube[Ti], sl, rl, iter, 1);
      sl, rl = addstate(ccube.cube[Tii], sl, rl, iter, 1);
      end;
    if(ccube.last != 2)
      sl, rl = addstate(ccube.cube[F], sl, rl, iter, 2);
      sl, rl = addstate(ccube.cube[Fi], sl, rl, iter, 2);
      sl, rl = addstate(ccube.cube[Fii], sl, rl, iter, 2);
      end;    
    if(ccube.last != 3)
      sl, rl = addstate(ccube.cube[R], sl, rl, iter, 3);
      sl, rl = addstate(ccube.cube[Ri], sl, rl, iter, 3);
      sl, rl = addstate(ccube.cube[Rii], sl, rl, iter, 3);
      end;
    xbreak = 0 + (iter == size(rl, 1)) + (iter > 10000000);
    iter = iter+1;
    end;
  return(sl, rl);
  end

##for o in rotlist
  ##print(o*"-|-")
##end

@rapasite try this one :smile:
Should be even faster with a sizehint, i’m pretty sure it’s pausing to do rehash!


#7

Yeah, but I want all the best solutions to solve any cube’s scramble because I am thinking about making a tool for the speedcubers.

I figure we don’t need to use the deepcopy (I was using it a some point for some reasons) in the browsecube arguments (a speed up occur!).
I edit the code in my previous post and I am not sure the one you start with was working perfect.

Thanks you so much to dig inside my code It make me happy.

I will get more time in 3 hours to look a your code.

I am sure there is still space for a good optimization but I am not good enough as I am a noob^^.
I will try anyway hehe!

So to any experts on optimization around here thanks in advance.

Is there another good place to post my Julia code looking for optimized code?


#8

For those interested here is my last version:

using DataStructures

global const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
global const t=Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
global const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
global const f=Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
global const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
global const r=Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]

global slvcube=Int8[0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10,11,12,13,14,15,16,17,18,19,20]


function upstates(state,rot)
    get!(statesdict,Int32(T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]),"t"*rot)
    get!(statesdict,Int32(t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]),"T"*rot)
    get!(statesdict,Int32(F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]),"f"*rot)
    get!(statesdict,Int32(f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]),"F"*rot)
    get!(statesdict,Int32(R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]),"r"*rot)
    get!(statesdict,Int32(r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]),"R"*rot)
end

function cube(state)
    p=digits(state,21,6)
    c=setdiff(0:6,div.(p,3))[1]*3+(2*sum(p)%3)
    return Int8[p[6],p[6]-p[6]%3+(p[6]+1)%3,p[6]-p[6]%3+(p[6]+2)%3,p[5],p[5]-p[5]%3+(p[5]+1)%3,p[5]-p[5]%3+(p[5]+2)%3,p[4],p[4]-p[4]%3+(p[4]+1)%3,p[4]-p[4]%3+(p[4]+2)%3,p[3],p[3]-p[3]%3+(p[3]+1)%3,p[3]-p[3]%3+(p[3]+2)%3,p[2],p[2]-p[2]%3+(p[2]+1)%3,p[2]-p[2]%3+(p[2]+2)%3,p[1],p[1]-p[1]%3+(p[1]+1)%3,p[1]-p[1]%3+(p[1]+2)%3,c,3*(c÷3)+(c+1)%3,3*(c÷3)+(c+2)%3]
end

function state(cube)
    return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

function move(cube,movement)
    for rot in movement
        if rot=='T'
            cube=T[cube+1]
        end
        if rot=='t'
            cube=t[cube+1]
        end
        if rot=='F'
            cube=F[cube+1]
        end
        if rot=='f'
            cube=f[cube+1]
        end
        if rot=='R'
            cube=R[cube+1]
        end
        if rot=='r'
            cube=r[cube+1]
        end
    end
    return cube
end


global statesdict = OrderedDict{Int32,String}(643245=>"")
@time for i in keys(statesdict)
    upstates(i,statesdict[i])
end

statesdict

create a dictionary that contain all permutations of the (2x2x2 rubik’s cube, poket cube, mini cube) associated with one of the shortest solution!

It take about 9 seconds on my laptop :slight_smile:

special thanks to @y4lu


#9

Code doesn’t run, i is not defined.


#10

should i be 643245 in your example?


#11

I do not really understand your model (or the states), but on my computer things become about twice as fast
when I refrain from using global variables (is that needed for your use case?), also either inbounds or SVector might help.

On my computer my version uses half as much memory as yours (that is, if I interpreted the starting value for icorrectly)

using StaticArrays
using BenchmarkTools
using DataStructures

#=
global const T=@SVector Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
global const t=@SVector Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
global const F=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
global const f=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
global const R=@SVector Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
global const r=@SVector Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
=#

function upstates(statesdict,state,rot,T,F,R,t,f,r)
    @inbounds get!(statesdict,Int32(T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]),"T"*rot)
    @inbounds get!(statesdict,Int32(t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]),"t"*rot)
    @inbounds get!(statesdict,Int32(F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]),"F"*rot)
    @inbounds get!(statesdict,Int32(f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]),"f"*rot)
    @inbounds get!(statesdict,Int32(R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]),"R"*rot)
    @inbounds get!(statesdict,Int32(r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]),"r"*rot)
end

function me()
    statesdict = OrderedDict{Int32,String}(643245=>"")
     const T=@SVector Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
     const t=@SVector Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
     const F=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
     const f=@SVector Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
     const R=@SVector Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
     const r=@SVector Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
    for state in keys(statesdict)
       upstates(statesdict,state,statesdict[643245],T,F,R,t,f,r)
    end    
    statesdict
end

@benchmark result=me() #7.2 seconds about 780mb allocations


#12

I edited the code changing i by state

@bernhard i should be the iteration on the keys of statesdict, sorry about forgetting to change the value


#13

Instead of a string, we can represent a rotation as a UInt8 value

struct Rotation
    r::UInt8
end
const rotations = ["T", "t", "F", "f", "R", "r"]
Base.show(io::IO, r::Rotation) = print(io, rotations[r.r])

and then create the different rotations

for (i, r) in enumerate(rotations)
    @eval const $(Symbol(r)) = Rotation($i % UInt8)
end
julia> T
T

julia> F
F

julia> typeof(F)
Rotation

A set of rotation can be represented as a UInt128 containing the bits of the rotations.
This can represent a total of 128/8 = 16 rotations which should be enough for 2x2x2

struct RotationSet
    r::UInt128 # Can store 16 rotations, good enough for 2x2x2
    n::UInt8 # Number of rotations in the set
end
RotationSet() = RotationSet(UInt128(0), UInt8(0))
const EMPTY_ROT = RotationSet()

function Base.show(io::IO, set::RotationSet)
    print(io, '[')
    for i in 1:set.n
        shift = 8 * (16 - i)
        print(io, Rotation(UInt8((set.r << shift) >> 8*15)))
        i != set.n && print(io, ", ")
    end
    print(io, ']')
end
julia> EMPTY_ROT
[]

Adding a rotation to the rotation set is done by shifting the UInt8 the correct amount

function Base.:*(set::RotationSet, rot::Rotation)
    return RotationSet(set.r | (UInt128(rot.r) << UInt(8) * set.n), set.n + UInt8(1))
end
julia> EMPTY_ROT * R * t * T * f
[R, t, T, f]

julia> typeof(ans)
RotationSet

Running the code again (with some tweaks) we get

const Tv = Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const tv = Int8.((3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20))
const Fv = Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const fv = Int8.((0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20))
const Rv = Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))
const rv = Int8.((0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15))

function upstates(statesdict,state, set)
    I = ntuple(i -> state ÷ 21^(6-i) % 21 + 1, Val{6}())
    for (v, rot) in zip((Tv, tv, Fv, fv, Rv, rv), (T, t, F, f, R, r))
        s = Int32(0)
        @inbounds for i in 1:6
            s += Int32(v[I[i]] * 21^(5-i+1))
        end
        get!(statesdict, s, set * rot)
    end
end

function me()
    statesdict = OrderedDict{Int32,RotationSet}(643245 => RotationSet())

    for state in keys(statesdict)
       upstates(statesdict, state, statesdict[643245])
    end
    statesdict
end


using DataStructures
using BenchmarkTools
using StaticArrays
@time result = me()
julia> @time result = me()
  4.742019 seconds (8.67 k allocations: 178.256 MiB, 2.24% gc time)

The dictionary is probably the bottle neck now.


#14

I just edited my code because I made a mistake with the rotations (needed to save the reverse order of the inverse rotations to have the good solutions in the dictionary)

I added 3 functions for the ones who want to play around
a function to get the cube from the states:
it is very ugly lol

function cube(state)
    p=digits(state,21,6)
    c=setdiff(0:6,div.(p,3))[1]*3+(2*sum(p)%3)
    return Int8[p[6],p[6]-p[6]%3+(p[6]+1)%3,p[6]-p[6]%3+(p[6]+2)%3,p[5],p[5]-p[5]%3+(p[5]+1)%3,p[5]-p[5]%3+(p[5]+2)%3,p[4],p[4]-p[4]%3+(p[4]+1)%3,p[4]-p[4]%3+(p[4]+2)%3,p[3],p[3]-p[3]%3+(p[3]+1)%3,p[3]-p[3]%3+(p[3]+2)%3,p[2],p[2]-p[2]%3+(p[2]+1)%3,p[2]-p[2]%3+(p[2]+2)%3,p[1],p[1]-p[1]%3+(p[1]+1)%3,p[1]-p[1]%3+(p[1]+2)%3,c,3*(c÷3)+(c+1)%3,3*(c÷3)+(c+2)%3]
end

a function to get the state from any cube:

function state(cube)
    return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

a function to applies rotations on the cube:

function move(cube,movement)
    for rot in movement
        if rot=='T'
            cube=T[cube+1]
        else if rot=='t'
            cube=t[cube+1]
        else if rot=='F'
            cube=F[cube+1]
        else if rot=='f'
            cube=f[cube+1]
        else if rot=='R'
            cube=R[cube+1]
        else if rot=='r'
            cube=r[cube+1]
        end
    end
    return cube
end

@kristoffer.carlsson waaa you made a fine improvements in such a short time + your tweaks are neat!
can you update the rotations issues? (at the end of the get! it should be “t” for the T rotation)
I am still trying to understand some parts.
what about @inbounds in front of get! and the constants issues that point out @bernhard was it something real?

Thanks you very mutch all!


#15

Inbounds in front of get! should make no difference because the get calls has to do quite some work. I think the biggest difference there was to not have the statesdict as a global.


#16

This make my pc CRASH, any Ideas why?

using DataStructures

const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const t=Int8.((3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const f=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))
const r=Int8.((0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15))

function upstates(state,statesdict)
    push!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1])
    push!(statesdict,t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1])
    push!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1])
    push!(statesdict,f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1])
    push!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1])
    push!(statesdict,r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1])
end

function me()
    statesdict = OrderedSet{Int32}(643245)
    for i in statesdict
        upstates(i,statesdict)
    end
    statesdict
end

@time result=me()

#17

push! vs get! ?

@kristoffer.carlsson
I have a bit of code for a dict replacement, as it possibly doesn’t really need to do retrieval here

struct xbloom2
  m1::Int32
  m2::Int32
  v3::BitArray{2}
  xbloom2(x) = new(x,x+1, BitArray(x, x+1))
  end;

function checkval!(xb::xbloom2, checkval::Int, setval=0)
  i1 = (checkval % xb.m1) + 1;
  i2 = (checkval % xb.m2) + 1;
  if(setval==1)
    if(!xb.v3[i1, i2])
      xb.v3[i1, i2] = true;
      return(true);
      end;
    return(false);
    end;
  return(xb.v3[i1, i2]);
  end;

##initializing
  local bloomlist = xbloom2(round(Int, 10 + sqrt(stateid(collect(Int8, 21:-1:1)))));
  bloomlist.v3[:] = false;

#18

OKAY I think we did something amazing, here is my last version:

using DataStructures

const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))

function upstates(state,rot,statesdict)
    get!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1],rot%100==22 ? rot÷10-1 : rot*10+2)
    get!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1],rot%100==44 ? rot÷10-1 : rot*10+4)
    get!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1],rot%100==66 ? rot÷10-1 : rot*10+6)
end

function m()
    statesdict = OrderedDict{Int32,Int64}(643245=>0)
    for i in keys(statesdict)
        upstates(i,statesdict[i],statesdict)
    end
    return statesdict
end

@time result=m()

After computing result
You can get the string version of the solutions by using this simple function (you have to caus the order is inversed in the int64 value)

function strsolution(state)
    const rotval=['T','t','F','f','R','r']
    return String(rotval[digits(result[state])])
end

you can replace whitout any others changes this:

const T=Int8.((6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20))
const F=Int8.((0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20))
const R=Int8.((0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ))

by this:(it is slightly slower, I don’t get why exactly???)

const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]

so you can use the move function describe on my post above.

I am currently amaze that it is this easy and fast to optimaly solve all the (2x2x2 rubik’s cube, poket cube, mini cube)'s states!

Any further remark is welcome!

@kristoffer.carlsson I think in your ntuple you should put Val{6} instead of Val{6}()

thank you everyone again.

I would like to make a package with some 3D visualization of the cube and some other options to set the cube ,etc,…
Can anyone put me on track because I have no ideas how to do that.


#19

just as with statesdict, you could also have the T,F and R as local variables.
This reduces the time by approximately 33% on my computer

using BenchmarkTools
using DataStructures

function upstates(state,rot,statesdict,F,T,R)
    get!(statesdict,T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1],rot%100==22 ? rot÷10-1 : rot*10+2)
    get!(statesdict,F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1],rot%100==44 ? rot÷10-1 : rot*10+4)
    get!(statesdict,R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1],rot%100==66 ? rot÷10-1 : rot*10+6)
end

function m()
    statesdict = OrderedDict{Int32,Int64}(643245=>0)
    const T= Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
    const F= Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
    const R= Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
    for i in keys(statesdict)
        upstates(i,statesdict[i],statesdict,F,T,R)
    end
    return statesdict
end

#@btime result=m()
@benchmark m() #3.5 seconds

#20

I figured the previous version with only three rotations(F,T,R) where not correct because some solutions are not the smallest possible!

here is a version witch find all the optimal solutions for every position of the cube, it is quite slow.(350s on my laptop)

using DataStructures

function upstates(state,rot,statesdict,T,t,F,f,R,r)
    Tstate=T[state÷4084101%21+1]*4084101+T[state÷194481%21+1]*194481+T[state÷9261%21+1]*9261+T[state÷441%21+1]*441+T[state÷21%21+1]*21+T[state%21+1]
    Tset=setrot(rot,2)
    Tval=get!(statesdict,Tstate,Tset)
    if Tval!=Tset && ndigits(asetvalue(Tval))==ndigits(asetvalue(Tset))
        statesdict[Tstate]=statesdict[Tstate] ∪ Tset
    end
    tstate=t[state÷4084101%21+1]*4084101+t[state÷194481%21+1]*194481+t[state÷9261%21+1]*9261+t[state÷441%21+1]*441+t[state÷21%21+1]*21+t[state%21+1]
    tset=setrot(rot,1)
    tval=get!(statesdict,tstate,tset)
    if tval!=tset && ndigits(asetvalue(tval))==ndigits(asetvalue(tset))
        statesdict[tstate]=statesdict[tstate] ∪ tset
    end
    Fstate=F[state÷4084101%21+1]*4084101+F[state÷194481%21+1]*194481+F[state÷9261%21+1]*9261+F[state÷441%21+1]*441+F[state÷21%21+1]*21+F[state%21+1]
    Fset=setrot(rot,4)
    Fval=get!(statesdict,Fstate,Fset)
    if Fval!=Fset && ndigits(asetvalue(Fval))==ndigits(asetvalue(Fset))
        statesdict[Fstate]=statesdict[Fstate] ∪ Fset
    end
    fstate=f[state÷4084101%21+1]*4084101+f[state÷194481%21+1]*194481+f[state÷9261%21+1]*9261+f[state÷441%21+1]*441+f[state÷21%21+1]*21+f[state%21+1]
    fset=setrot(rot,3)
    fval=get!(statesdict,fstate,fset)
    if fval!=fset && ndigits(asetvalue(fval))==ndigits(asetvalue(fset))
        statesdict[fstate]=statesdict[fstate] ∪ fset
    end
    Rstate=R[state÷4084101%21+1]*4084101+R[state÷194481%21+1]*194481+R[state÷9261%21+1]*9261+R[state÷441%21+1]*441+R[state÷21%21+1]*21+R[state%21+1]
    Rset=setrot(rot,6)
    Rval=get!(statesdict,Rstate,Rset)
    if Rval!=Rset && ndigits(asetvalue(Rval))==ndigits(asetvalue(Rset))
        statesdict[Rstate]=statesdict[Rstate] ∪ Rset
    end
    rstate=r[state÷4084101%21+1]*4084101+r[state÷194481%21+1]*194481+r[state÷9261%21+1]*9261+r[state÷441%21+1]*441+r[state÷21%21+1]*21+r[state%21+1]
    rset=setrot(rot,5)
    rval=get!(statesdict,rstate,rset)
    if rval!=rset && ndigits(asetvalue(rval))==ndigits(asetvalue(rset))
        statesdict[rstate]=statesdict[rstate] ∪ rset
    end
end

function asetvalue(set)
    @inbounds for i in eachindex(set.dict.slots)
        if set.dict.slots[i]==0x01
            return set.dict.keys[i]
        end
    end
end

function setrot(S,r)
    C=Set{Int64}()
    for s in S
        v=s*10+r
        v=in(v%100,(11,33,55))?v+11:v
        push!(C,v)
    end
    return C
end

function rotway(rot)
    const rotval=['t','T','f','F','r','R']
    str=""
    while rot != 0
        str = str*rotval[rot.%10]
        rot ÷= 10
    end
    str
end

function rotstring(rot)
    const rotval=['T','t','F','f','R','r']
    str=""
    while rot != 0
        str = rotval[rot.%10]*str
        rot ÷= 10
    end
    str
end

function cube(state)
    cube=Int8[]
    d=digits(state,21,6)
    for i in 2*sum(d)%3+setdiff(0:6,d.÷3)[1]*3 ∪ d
        unshift!(cube,i,3*(i÷3)+(i+1)%3,3*(i÷3)+(i+2)%3)
    end
    return cube
end

function state(cube)
    return Int32(cube[1]*21^5+cube[4]*21^4+cube[7]*21^3+cube[10]*21^2+cube[13]*21+cube[16])
end

function move(cube,movement)
    for rot in movement
        if rot=='T'
            cube=cube[T+1]
        elseif rot=='t'
            cube=cube[t+1]
        elseif rot=='F'
            cube=cube[F+1]
        elseif rot=='f'
            cube=cube[f+1]
        elseif rot=='R'
            cube=cube[R+1]
        elseif rot=='r'
            cube=cube[r+1]
        end
    end
    return cube
end

function m()
    statesdict = OrderedDict{Int32,Set{Int64}}(643245=>Set{Int64}(0))
    const T=Int8[6 ,7 ,8 ,0 ,1 ,2 ,9 ,10,11,3 ,4 ,5 ,12,13,14,15,16,17,18,19,20]
    const t=Int8[3 ,4 ,5 ,9 ,10,11,0 ,1 ,2 ,6 ,7 ,8 ,12,13,14,15,16,17,18,19,20]
    const F=Int8[0 ,1 ,2 ,3 ,4 ,5 ,14,12,13,8 ,6 ,7 ,15,16,17,11,9 ,10,18,19,20]
    const f=Int8[0 ,1 ,2 ,3 ,4 ,5 ,10,11,9 ,16,17,15,7 ,8 ,6 ,12,13,14,18,19,20]
    const R=Int8[0 ,1 ,2 ,11,9 ,10,6 ,7 ,8 ,15,16,17,12,13,14,20,18,19,5 ,3 ,4 ]
    const r=Int8[0 ,1 ,2 ,19,20,18,6 ,7 ,8 ,4 ,5 ,3 ,12,13,14,9 ,10,11,16,17,15]
    for i in keys(statesdict)
        upstates(i,statesdict[i],statesdict,T,t,F,f,R,r)
    end
    return statesdict
end

@time statesdict=m()

gg=collect(values(statesdict))

Thx you again