Wednesday, July 9, 2014

On Rubik's Cube

I love Rubik's cube. It's a puzzle that many people associate with intelligence, mathematical ability, and good problem solving skills, but being able to solve it actually has nothing to do with any of those. The only things you need are basic pattern recognition and muscle memory - both of which everyone has anyway.

    1. My first cubes

My first Rubik's cube was even older than I am. My dad bought two of them (one with standard colours, and one with pictures of fruit) some time in the early 80's when they first became popular, together with a short book explaining how to solve them. I found the book in 1996, shortly after we'd moved house. I asked my dad about it, and he found the two cubes for me. Not wanting to cheat, I scrambled one and tried solving it myself. It didn't take long to figure out how to solve one side, but I quickly realised that any turn inevitably messed up four sides, got frustrated, and moved on.

I came back to them a couple years later. This time, I actually tried reading the book. The first chapter was all about the internal mechanism, and how to take the cube apart. Naturally, I stopped reading there and did exactly that. I took them both apart, and put them back together in a solved state, and began to look at how various turns affected the faces. Whenever I got stuck in a position that I couldn't solve, I would take the cube apart, and put it back together. After a while, the core of one of the cubes broke while I was taking it apart. Having made very slow progress, and having lost a cube, my 12 year old brain decided it had more interesting things to do, so I moved on.

    2. Solving the damn thing

Once again, I came back the the cube a few years later. I think I was about 17 years old this time, and far more patient. I only had the cube with the fruit stickers left, so I had to be more careful. I decided to read the book, and I approached it the same way I would approach a school text book. I took a notepad and a pencil, and began to take notes.

The book described a very simple layer-by-layer method for solving the cube. You would start by inserting the four edges on the top face, and then execute a simple algorithm until they cycled into the correct positions. Then you would insert the four corners of that face, then the four edges of the middle layer. At this point, the top two layers of the cube were solved. To finish the last layer, you had to switch some corner pieces in the bottom layer to get them in the correct position, then execute an algorithm over and over until they were oriented correctly. Then, you would execute an algorithm to cycle the last four edges, until they were in the correct position, and finally you would execute one of three algorithms to flip them into the correct orientation. The book claimed that the method required an average of about 120 moves to solve the cube. There were a total of nine algorithms to learn, and it only took a couple of days to memorise them all (it's surprisingly easy if you just let muscle memory take over).

The catch was the centres. The book assumed that the cube had stickers with a solid colour, but my cube had little pictures of fruits. All of them would point the same direction except for the centres. I later learned that a cube like this is called a supercube, and some people draw arrows (or buy stickers with arrows) to turn their Rubik's cubes into supercubes. I was not content having my centres pointing the wrong way, so I sat down and figured out a couple of algorithms myself that would allow me to orient five of the six centres while solving the cube. I noticed that a couple of the algorithms I already knew rotated one or two centres if I repeated them three times, and with that, I could solve the cube, centres included.

Solving a Rubik's cube is a very relaxing task. It takes very little brain power, and is actually very meditative. Apart from occasionally glancing down to see which algorithm you need to execute next, you don't even really have to watch what you're doing. I used to solve my cube several times a week, just to meditate and relax.

    3. Moving on: new Cubes and new methods

My fruit cube lasted a surprisingly long time. After several years, it began to lock up occasionally. A couple years after that, pieces began to pop out every now and then. By late 2012, the pieces became so loose that it reached a stage where it would lock up on almost every turn, and it became almost impossible to solve without the whole thing exploding in my hands. I needed a new cube, so I bought one: a cheap Chinese cube from a flea market stall. The stickers lasted less than two weeks, and it was less than a month before one of the edges broke in half.

It was then that I decided to take things seriously. I went online and did some research, and discovered the fascinating world of speedcubing. I discovered that the world record at the time was less than six seconds, and that more than a thousand people around the world can solve a Rubik's cube in under fifteen seconds almost all the time! It put my two and a half minutes to shame.

I found out what makes of cube were actually considered good quality, and found a stickerless DaYan GuHong on sale. While waiting for my new cube to arrive (it took two months, thanks to a useless Postal service), I found a Rubik's 2x2 cube in a local toy store. I could solve it by adapting the 3x3 method, but it felt very slow and inefficient. I learnt to solve it using the Ortega method, which is a much faster method specially developed for 2x2 cubes, which is also fairly light on algorithms (you actually only need two of them, but learning up to eleven makes things faster).

Conveniently, my GuHong arrived the day before I left for America to present a paper a conference. A 15 hour plane flight is absolutely perfect for learning a new method. I made a short cheat sheet with the algorithms for the ZZ method, and between the two plane flights, I managed to memorize them.

    4. Speedcubing: attempt #1

Last month, a toy store near my girlfriend's house held a Rubik's cube competition. When I had first looked in 2013, there were only six South Africans ranked by the World cube Association, and speedcubing in the country seemed pretty much non-existent. I was fairly surprised to see an actual competition. I checked the World Cube Association website, only to see that the first official competition had been held a few months before, and more than thirty people had attended, two of whom had managed to set times under fifteen seconds.

It led me to find, a South African online store that stocks a range of the world's leading speed cube brands. I told myself that if I could solve my cube ten times with an average time less than 90 seconds (a minute faster than a year before), then I would allow myself to buy a new cube. I made it, but only just. In ten solves, my best time was 1:22, with an average of 1:29.8.

I ordered my new cube, a DaYan ZhanChi (since my stickerless GuHong is technically not competition legal), as well as a new 2x2 (my Rubik's brand one had a cracked core), and a 4x4 cube. With these new cubes, together with a couple of key rings, I can officially say that I have begun a bit of a collection.

I thoroughly enjoyed my first competition. By some miracle, I actually won the 2x2 category with an average of just over 16 seconds (my five solves took 13, 15, 15, 18 and 32 seconds). In the 3x3 category, I came nowhere near the winning average of 45 seconds. My best time was 53 seconds, and I averaged just over a minute.

    5. Next goal: An official WCA ranking

There's going to be an official WCA ranking event in Johannesburg on 23 November, and one in Cape Town on 30 November. This leaves me four and a half months to practice and get my times down. My goal is to set at least one time less than 30 seconds at that event. I'm improving fairly quickly. As of 30 June, my average time over 100 timed solves was 1:15.62. By 8 July, my average time over 100 solves had dropped to 57.93 seconds, and my current personal best is 42.65 seconds. 30 seconds may seem ambitious, but I'm fairly confident that I will be able to do it.

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .

Thursday, May 1, 2014

On The Fuel-Optimal Ascent Speed in Kerbal Space Program

Kerbal Space Program is a sandbox-style spaceflight simulator game developed by Squad. The player designs and assembles spacecraft by piecing together a wide range of components, and then launches and flies them. The game places an emphasis on the realistic modelling of various physics, including structural failure of components, aerodynamic lift and drag, and accurate orbital mechanics. It should come as no surprise to learn that I absolutely love this game.

It is widely known and claimed that the most fuel efficient ascent speed for a spacecraft in Kerbal Space Program is the terminal velocity. However, not many people can actually explain exactly why this is. The whole thing has given rise to a number of misconceptions about terminal velocities and aerodynamic drag, so I felt I had to clear these up.

I'll also go through the math to calculate the actual fuel optimal ascent speed (which just happens to be equal in magnitude, but opposite in direction to the terminal velocity), because I couldn't find it explained anywhere else. I didn't really believe the claims until I did the math myself, so hopefully this will help those who are not convinced by all the half-baked whishy-washy arguments out there.

    1. What is the terminal velocity?

Many people seem to think that the terminal velocity is the maximum speed a rocket can reach. I don't know where this comes from, but it's absolutely false. The terminal velocity of an object is the speed at which an object will fall through air in the absence of all forces other than gravity and air resistance. That is, the only forces acting on the object are gravity and air resistance, or aerodynamic drag. Finding the terminal velocity is as simple as equating the weight of the object (a constant) to the drag (which varies with the square of the speed), and solving for speed. If an object is falling faster than the terminal velocity, air resistance will cause it to slow down. If it's falling slower than the terminal velocity, gravity will speed it up.

To get an object to fall faster than the terminal velocity, one simply needs needs to apply a downward force in addition to gravity.

Another thing to note is that the terminal velocity is always directed down. That's because at the terminal velocity, gravity and drag are equal in magnitude, but directly opposed.

    2. What does this have to do with going up?

The terminal velocity applies only to falling objects in the absence of other forces, so what is the relevance of the terminal velocity when your rocket is going up? The answer is, not much. It's just a useful reference point. Below the terminal velocity, your engines are doing more work to overcome gravity than drag. Above the terminal velocity, your engines are doing more work against drag than gravity. At the terminal velocity, exactly 50% of the work your engines do goes to overcoming gravity, and exactly 50% goes to overcoming drag. There's no reason why you can't just apply more thrust to ascend faster, or less thrust to ascend slower.

    3. Calculating the terminal velocity

From here on out, we're doing math. Hopefully this doesn't scare you off. As we've already pointed out, the terminal velocity occurs when the weight of the object acting downwards exactly balances the drag acting upwards. The weight is given by

where is the object's mass, and is the gravitational acceleration (which we can assume is constant if we're considering only very small changes in altitude).

The drag depends on several factors: the air density, , the cross-sectional area of our rocket, , the drag coefficient, , and the square of the object's velocity, . The equation is

The terminal velocity occurs when these two forces are equal. That is, when

To find the terminal velocity, we simply solve for to get

    4. Calculating the optimal ascent speed

We're now going to calculate the optimal ascent speed. As far as we're aware (at this stage), that has nothing to do with the terminal velocity, so we're going to start from scratch.

To do this, we're going to try find the mass of fuel that needs to be burnt to increase altitude by a small amount, and then use some basic calculus to find the speed that minimizes that. First, we'll need an expression for the change in altitude at a given speed. That's easy to do if we assume that the speed is constant. This is approximately true, provided we're considering a very small change in altitude:

where is the speed, and is the time taken to change the altitude.

We don't actually know what this change in time is, so we'd like to find another expression for it, preferably one that doesn't involve speed. To do that, we're going to make use of the rocket's impulse:

If we assume that we're looking at a very short period of time, so that the thrust is approximately constant, then this simplifies to

Now we need to calculate this impulse. Fortunately, the impulse, as you might guess, is very closely related to the specific impulse, which is a property of the engine, and is readily available for various engines in KSP. The specific impulse is defined as the impulse delivered per unit weight (at standard gravity, , which is the gravity at sea level on Kerbin) of propellant burned. Therefore, we can calculate the impulse from the weight of fuel burned, and the specific impulse of the engine:

Substituting this into our expression for impulse above, and solving for the time, we get

And so our expression for the change in altitude at a given speed becomes

So, solving for the amount of fuel burned, we get an expression for the fuel required to increase altitude by a certain amount at any given speed:

We don't know how much thrust we need to produce to maintain the optimum velocity. However, we can calculate what this value needs to be based on the two assumptions we've already made. We've assumed that the thrust is constant, and we've assumed that the velocity is constant. This means that thrust will be exactly balanced by the sum of the rocket's weight, and drag, . Therefore, we can write the thrust as

Since we're considering a very short period of time, we can assume that the weight of the rocket is constant. We've already got expressions for weight and drag, but we'll repeat them here. They are


We can substitute these into our equation for thrust to get

Then we can substitute that into our expression for fuel required to get

This can be simplified to give a simple expression for the fuel required to increase altitude by a small amount at any given speed.

We want to find the speed that minimizes the fuel required. This is a standard optimisation problem, and means we need to set the derivative of the objective function to zero.

That derivative is fairly easy to get with basic calculus. It leaves us with the following equation to solve:

This is easy to solve. Move the first term across to the other side, cancel and on each side and then multiply through by . This leaves the following expression:

Does that look familiar? It should. This is the exact same equation we had to solve to calculate the terminal velocity. The term on the left is simply the weight, and the term on the right is the drag. This means that the speed that minimises the fuel required to increase in altitude just happens to be the speed at which weight and drag are equal.

This means that the velocity that gives a fuel optimal ascent is equal in magnitude to the terminal velocity, but in the opposite direction.

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .

Friday, March 14, 2014

On QuickCoords - A tool for quickly capturing coordinates across a series of images.

I needed an easy way to manually track the positions of features across a series of more than 600 photographs. Loading each individual photo and copying the coordinates of each point one at a time gets very tedious very fast, and none of the programs that I tried really seemed to support a rapid workflow.

That's why I wrote my own. QuickCoords v0.1beta is now available, either from Sylvermyst Technologies or from GitHub.

It's still in beta, so if you have any need for a program like this, try it out. The following features are fully functional:
  • Select a folder, and load images from that folder.
  • Quickly switch between images using a range of keyboard shortcuts.
  • Click anywhere in the image to get the coordinates of that point with sub-pixel accuracy.
  • Select and remove points individually, or in groups.
  • Shift points around if your initial click was a handful of pixels off.
  • Copy a list of points for pasting into most spreadsheet programs.
  • Export the points as a CSV file or plain text.

Any feedback is welcome, and if you encounter any major bugs, please report them (if they haven't been reported already).

If you enjoyed this post, then don't forget to like, tweet, +1, or upvote on reddit. If you have any questions, comments or complaints, post them using the form below.
. . . . . . . . . . . . . . . . . . . . . . . .