Further reflections on the Rubik's Cube

 

Visual metaphor and pun

Since my previous  post I've been thinking a bit more about Rubik's Cubes.  I have been wondering what is the simplest way to represent their state mathematically, and by extension programatically.

Configurations of the cube clearly form a group, so I set myself the goal of creating objects in python which would represent individual configurations and which could be multiplied together to form new objects.  For example, $I$ would represent an unscrambled cube, $L$ a cube obtained from $I$ by moving the left face clockwise, $U$ a cube obtained from $I$ by moving the upper face clockwise and $L*U$ the cube obtained by rotating the left face first and then the upper face.

The question is: what is the most elegant representation for each of these objects?  I was initially drawn by the idea of labelling the stickers (other than the centre face ones) 1 to 48 and representing each object as a different permutation.  This makes multiplication very easy but has the drawback that you are forced to make some arbitrary decisions about how to label the stickers, and each generator object $\{L,R,U,D,F,B\}$ is a bespoke permutation that must be worked out by hand, with a lot of squinting while attempting to visualise.

Then I realised that we can instead simply store how each sub-cube is rotated relative to its original position.  If we treat the (fictitious) centre cube as occupying the origin then each sub-cube in the scrambled cube is simply rotated from its original position around a vector passing through the origin.  This means that all we need to represent the scrambled cube is a 3x3x3 array.  This actually gives us more information than a permutation of stickers since it also tells us how the centre-face cubes have been rotated.

The cherry on the top is that rotations can be represented by unitary quarternions.  So scrambled cubes can be represented by 3x3x3 arrays of quarternions, and once this representation is chosen the operations of multiplication and inverses are straightforward to implement.

The files are rubik.py and quarternion.py and you can experiment with them using the widget below.




NOTES:

There's a strange feature of this implementation which I've left in deliberately. If you have a unit quarternion
$$
q = cos\theta + sin\theta\mathbf{\hat{u}}
$$
Then $q v q^{-1}$ is $v$ rotated about $\mathbf{\hat{u}}$ clockwise (looking in the same direction as $\mathbf{\hat{u}}$). But the amount of rotation isn't $\theta$, it's $2\theta$. This means that there are two aliases for rotation of $v$ by $\theta$ namely
$$
\begin{align}
cos\left(\frac{\theta}{2}\right) + sin\left(\frac{\theta}{2}\right)\mathbf{\hat{u}} &= q \\
cos\left(\frac{\theta+2\pi}{2}\right) + sin\left(\frac{\theta+2\pi}{2}\right)\mathbf{\hat{u}} &= -q \\
\end{align}
$$
So if you see a $-1$ that means that a sub-cube has been fully rotated an odd number of times. This could be seen as a bug, but since it's useful information it seems a shame to strip it out.

Popular posts from this blog

How To Make ASCII Diagrams Beautifuller

Image
I've discovered an excellent tool in asciiflow.com .  The website makes it really easy to create ASCII box diagrams like this They put these things in fruit machines you know! This is ideal for source code banners, which I think should contain helpful documentation - but most programmers think it's a good place for the COPYRIGHT information and nothing else. But wait! we can make it beautifuller... and easier to read... by replacing some of the ASCII characters with ones available in UTF-8: There!  Isn't that better?  (Although some purists may object to non-ASCII characters in your code base.) SOURCE CODE: #!/usr/bin/python2 # coding: utf-8 # + gets converted in different ways depending on it's 4 neighbours # # . N . { nsew(N,S,E,W) has bit 3 set if N in "+|<>" # W + E { nsew(N,S,E,W) has bit 2 set if S in "+|<>" # . S . { nsew(N,S,E,W) has bit 1 set if W in "+-^v" # { nsew(N,S,E,W) has bit 0 set if E in
Read more

Calculation of ECS using simple convection model

Image
Contents Intro Simple stratified model Alternative convection model Tropospheric temperature gradient Approach used in convection model Calculation of Radiative Forcing from CO₂ increase Calculation of Radiative Forcing from H₂O increase Calculation of zero-feedback ECS Effect of including feedbacks Effect of water vapour Effect of cloud cover change Effect of sea ice loss Calculation of ECS including feedbacks Limitations One more thing: Changes to Troposphere depth Intro The goal of this post is to see if we can come up with an estimate of Equilibrium Climate Sensitivity using a simple model in which the atmosphere is treated as well-mixed.  By "simple" I mean that using the model will not require any advanced mathematics or computation, but will still be realistic enough to come up with an estimate within the likely range of 2.5 - 4.0°C predicted by the IPCC Assessment Report 6 .  I will try to take as little on trust as possible and show how the results are arrived at.
Read more

Why growth is falling in all developed countries (as a long term trend)

Image
In this post I argue that economic growth is not the normal state of affairs, it is a blip caused by the discovery of a one-off resource of non-renewable energy.   The logistic equation $$ \frac{dy}{dt} = y(1-y) $$ Here's a simple model.  Humans discover an exploitable but limited resource and start consuming it.  The amount consumed, $y(t)$, is a function of time.  The general form of the equation is $\frac{dy}{dt} = \alpha y (\beta - y)$, but if you choose the right units $\alpha$ and $\beta$ both become $1$. Why should this work, in principle? Early on, the factor $1-y$ is approximately $1$ and can be ignored.  So the model states that annual consumption $dy/dt$ starts off proportional to $y$.  In other words, $y$ grows exponentially at first.  This could happen if exploiting the resource enables further exploitation of the resource.  For example, suppose a few humans are shipwrecked on an island with 1000 trees: they take ages to cut down the first tree as they are using their
Read more