Hey there. I have started using Julia today or yesterday, and there is something happening here that is driving me a little bit crazy.
I wanted to model a group of permutations (specifically, the permutation group of a 2x2x2 Rubik’s Cube), which I decided to implement using two arrays: a permutation one, and an orientation one (doesn’t matter too much if you don’t follow that decision, but with these two arrays any valid position of a 2x2x2 puzzle can be represented), as follows:
cp = (1,2,3,4,5,6,7,8) # position of each piece (8 pieces on a 2x2x2 cube)
co = (0,0,0,0,0,0,0,0) # orientation of each piece (how a certain corner is twisted, each one having 3 possible orientations)
The cube has six faces which can be turned 0, 90, 180, or 270 degrees.
My goal is to be able to represent a cube permutation as a single function, given a string of moves like “R U F’ B2” (R=right, U=up, etc).
I then defined some functions that either swap certain elements of one array, or perform a simple addition + mod 3 to the elements of the other:
# Atoms
Rp((a,b,c,d,e,f,g,h)) = (a,c,f,d,e,g,b,h)
Ro(a) = @. (a + [0,1,2,0,0,1,2,0]) % 3
Up((a,b,c,d,e,f,g,h)) = (d,a,b,c,e,f,g,h)
# Uo is not needed since it equals identity
xp((a,b,c,d,e,f,g,h)) = (d,c,f,e,h,g,b,a)
xo(a) = @. (a + [2,1,2,1,2,1,2,1]) % 3
Then, I defined the ‘broader’ functions that use these atoms to act on a tuple that will look like (cp, co), knowing that each move has to first permute both arrays according to their definition, then update the orientation array, again according to their definition:
# Movedefs
R((p,o)) = Rp(p), (Ro∘Rp)(o)
U((p,o)) = Up(p), Up(o) # again no Uo because it is the identity func
x((p,o)) = xp(p), (xo∘xp)(o)
Finally, I defined a bunch of other functions (corresponding to each face + rotations of the cube) using composition (again, doesn’t matter if you’re not familiar with the Rubik’s Cube notation, but x, y, z are rotations that follow R, U, F faces respectively):
D = x ∘ x ∘ U ∘ x ∘ x
y = U ∘ D ∘ D ∘ D
F = x ∘ x ∘ x ∘ U ∘ x
B = y ∘ y ∘ F ∘ y ∘ y
z = F ∘ B ∘ B ∘ B
L = y ∘ y ∘ R ∘ y ∘ y
Then, I wanted to create another procedure that, given a string like “R U F’ B2”, decomposed that into a single function that represents that permutation.
For that example string, it would be this function: B(B(F(F(F(U(R( tuple ))))))). (2 means apply twice, ’ means apply it three times).
So, Googling a little I found about the getfield() func to retrieve a function from a Symbol, and I did this:
# Single move (string) to Move (func) ( i.e. "R" to R(), "F2" to F(F()) )
function m_to_mf(m)
func = getfield(Main,Symbol(m[1]))
length(m)==2 ? (m[2]=="2" ? (func∘func) : (func∘func∘func)) : func
end
# String of moves to single func
str_to_func(string) = foldl(∘, map(m_to_mf, reverse(split(string))))
I was all happy with this with the cool looking ∘ and the nice syntax of Julia, but when I timed the execution time I was rather disappointed…
# Running
scramble = "R' U' F R2 B' L2 F2 y x"
cube = (cp, co)
pos = str_to_func(scramble)
@time pos(cube)
# 0.385912 seconds (1.08 M allocations: 56.017 MiB, 1.07% gc time)
Woah! Hold up a second! 1 million allocations? Almost 0.4 seconds for this task?
I am aware that my algorithm isn’t as efficient as it could be, but I believe something is very wrong here (probably with my code, since this is basically my first program in Julia!)
With all that said, what is up with this? How can this be implemented more efficiently, keeping the same idea of defining Move Functions based on others, and transforming a string with moves into a single function?
Thank you for the read!
