Representing a Rubik’s cube in Clojure

I’ve just finished a working draft of my first Clojure program, which is a representation of a Rubik’s cube in code. The cube can be transformed using the usual Rubik’s cube moves of rotating a face through the x, y or z axes, and each side of a cube can be ‘rendered’ as text.

;; (get-face :N cube)
((:blue :blue :blue)
 (:blue :blue :blue)
 (:red :red :red))

This exercise touched several programming concepts I’d never come into contact with before, in particular 3D transformations. It was also my first Clojure project, too, so I had some adventures in that direction.

In this and following posts I’ll write about some things I learned about Clojure and about cubes while I did this.

Starting out

Before doing any manipulating or rendering it was necessary to model the cube in some kind of data structure. I dug up some suggestions from the internet and evaluated them:

An array of arrays

The idea is to have six 3×3 arrays of colours, and this looks simple but feels like it gets ugly quite quickly. What happens, for example, when you rotate a layer? The colours on that layer do not change, but the adjacent colours all do. These colours need to be accessed by numerical array indices and them rotated in the correct direction. This felt like it was going to be fiddly, especially when it was necessary to rotate around three different axes, and I was likely to make mistakes. Also, the implementation would have involved a lot of swapping things around in arrays, which doesn’t make for very readable code.

Interlocking linked lists

Another suggestion from Stackoverflow was to use interlocking linked lists. At first I thought this would be ideal: Lisp is linked lists all the way down, right? This approach defines each cube piece as a struct containing pointers to its vertical and horizontal neighbours, plus its colour. The idea of everything being defined relative to everything else was rather exciting, but it made me uneasy about rendering the state of the cube: I imagined a situation where I got lost in the middle of these linked lists without knowing where faces began and ended. I suppose I’d maintain a pointer to a single piece in a known position and use that as the starting point to figure out where everything else is. Anyway, this felt like biting off a bit more than I could chew; perhaps I’ll try it in future.

An array of objects

In the end I went for the most verbose data structure available, which is the one described in this Stackoverflow answer. The author uses objects to represent the bits of the cube, noting that this verbose approach is not terribly efficient. To me it it is the most readable and that’s what I care about.

Of course, this is Clojure and there are no objects, so I chose to use maps. In this structure, each piece is defined by its co-ordinates in space and a map of planes to colours which tells us what the orientation of the piece is. Here, for example, is the definition of a piece:

{:position {:x 1 :y -1 :z 1}
:colors {
:y :green
: x :red
:z :white
}}

To put that in context, here is an artist’s impression of the cube with some axes attached. The piece described is the one at the near corner of the white top of the cube:

Screen Shot 2017-05-07 at 21.27.52

The :colors key maps colours to axes. If we’re looking at a piece from the top or the bottom of the cube we care about its z-axis; from the East, the x-axis; from the South, the y-axis. It’s an amusing quirk, and possibly a technical flaw, of this implementation that we do not need to care about which direction we’re looking at a piece from as long as we’re looking at it in the right axis.

At the heart of the program is a (def default-cube) which defines a 26-element vector of maps like the above, which collectively describe an entire cube in the completed state. The rest of the program a) chooses and b) tweaks elements of this vector to return a whole new 26-element vector representing the new state of the cube, which it can then render.

In the next post I’ll write about how that happens.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s