Stay Frosty

I thought I’d share a little trick I learnt the other day regarding swapping variables.

A common coding/computer science task is to swap the values of two variables. In some languages, such as Java, one may start by creating a new temporary variable. For example (assuming we already have two ints, x and y):

int temp = x;
x = y;
y = temp;

This creation of a new variable uses more memory, and whilst in most circumstances would be fine, it could become an issue if we’re swapping many times, for example in a sorting algorithm.

Some languages allow us to do a nice swap without extra variables, using multiple assignment and tuple packing and unpacking:

x, y = y, x

This is pretty neat, although is apparently slower than using a temporary variable.

Anyway, yesterday I discovered a third method: XOR swapping. Again, this doesn’t require the use of an extra variable, and I thought it was pretty clever (here ^ represents XOR, as in Python):

x = x ^ y
y = x ^ y
x = x ^ y

Neat, huh? It’s fairly simple to see how it works if you simply walk through the steps. Let’s swap x = 7, y = 9:

x = 0111
y = 1001
x = x ^ y = 1110
y = x ^ y = 0111
x = x ^ y = 1001

Apparently this method is quite commonly used in embedded assembly code, however you won’t find it appearing much in code on a desktop computer. It usually is slower to compute than using temporary variables, as most processors attempt to execute commands in parallel – and of course, each of these instructions depends upon the previous result, so they must be executed sequentially. Still, it’s a nice thing to know.

The short version: it seems that if you’re trying to save memory then XOR swap or use multiple assignment, otherwise if efficiency is an issue, use a temporary variable.

I thought I’d post a follow-up to yesterday’s FizzBuzz post with some sample solutions, as a bunch of you seemed to find it fun to solve. Feel free to add your own solutions in the comments of this post!

My own first solution was Python-based, and a fairly simple one:

for i in range(1,101):
    if i % 3 == 0 and i % 5 == 0:
        print "FizzBuzz"
    elif i % 3 == 0:
        print "Fizz"
    elif i % 5 == 0:
        print "Buzz"
    else:
        print i

Obviously it’s not in a function or anything, but I just wanted to do it as fast as possible. Shortly afterwards, I realised that line 2 could be simplified by changing it to:

if i % 15 == 0:

Because of course, if a number is a multiple of 3 and 5, then it must be a multiple of 15.

Here are a couple of nice alternatives (ideas courtesy of Dave, although re-written by me because we didn’t save them). First, writing FizzBuzz as a iterator:

def fizzbuzz_generator(n):
    for i in range(1, n+1):
        if i % 15 == 0:
            yield "FizzBuzz"
        elif i % 3 == 0:
            yield "Fizz"
        elif i % 5 == 0:
            yield "Buzz"
        else:
            yield str(i)

for result in fizzbuzz_generator(100): print result

Then, a simple function to calculate the correct fizz/buzz, combined with a list comprehension to create the result (man, I love list comprehensions):

def fizzbuzz(i):
    if i % 15 == 0:
        return "FizzBuzz"
    elif i % 3 == 0:
        return "Fizz"
    elif i % 5 == 0:
        return "Buzz"
    else:
        return str(i)

print "\n".join([fizzbuzz(i) for i in range(1,101)])

Finally, here are two neat little Ruby one-liners, taken from the comments of the original FizzBuzz article. I hope the authors (Brendan, and Brian respectively) don’t mind me reproducing them here:

puts (1..100).map{|i|(s=(i%3==0?'Fizz':'')+(i%5==0?'Buzz':''))==''?i:s}

puts (1..100).map{|i|i%15==0?'FizzBuzz':i%5==0?'Buzz':i%3==0?'Fizz':i}

How neat is that? Anyway, as I said, feel free to leave your own solutions below.

Update: Check out the follow-up post for some sample solutions!

I love to code. Since a young age (I think I was about 7 when we first got our BBC B, and I would patiently tap BASIC code into the blinking prompt from childrens’ books about programming), I’ve loved to write programs. I read somewhere recently (unfortunately, I forget where) that it’s not the act of coding itself we love, but rather it’s solving problems that we love. I think that’s one reason I like learning new programming languages, as it allows me to solve problems in different ways.

A while back, I came upon the FizzBuzz idea. In short, it’s a simple exercise for employers to give to potential employees at interviews; a very simple exercise, yet one that someone will only be able to answer quickly if they ‘get’ programming. A suggested FizzBuzz problem is the following:

Write a program that prints the numbers from 1 to 100. But for multiples of three print ‘Fizz’ instead of the number and for the multiples of five print ‘Buzz’. For numbers which are multiples of both three and five print ‘FizzBuzz’.

I invite everyone reading this to have a go now – time yourself, and see how quickly you can do it. Unfortunately, I only timed myself by looking at the clock, but I was glad to have completed it in under a minute. Apparently this shows I can code:

Most good programmers should be able to write out on paper a program which does this in a under a couple of minutes.

Want to know something scary? – the majority of comp-sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

That is a scary thought, but I expect it’s almost certainly true.

So, this sort of simple problem excites me – I can work out a solution, and then try and improve that, perhaps. Myself and Dave spent a fair while earlier today trying to come up with more and more sophisticated solutions. And y’know what? It was fun!

On a similar note, I thought I’d mention a website that I found a while back (thanks to Matt Gwynne) that might be of interest to anybody else who enjoys these kind of problems. Project Euler is “a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve”. It contains a list of (at the time of writing) 195 mathematical problems, and the aim is to write code to solve them. You can then put in your answers, the website will tell you if you’re correct, and check them off the list. Great fun, and it’s neat to see some of the interesting solutions that people come up with (and the range of languages they use!). Hooray for being a geek! \o/