Optimizing Facebook's "Hoppity" Puzzle

I found Facebook's puzzle page the other day. While it has some very meaty challenges, it also has a couple of trivial ones. These easy puzzles are there to allow you to make sure you can submit solutions (I'm not consistently getting mine to run but I'm hopeful that turning off "Always send Windows-friendly attachments" in OSX Mail will do the trick).

One easy puzzle is called Hoppity. Essential you count up from 1 to a specified number and follow these rules
  • For integers that are evenly divisible by three, output the exact string Hoppity, followed by a newline.
  • For integers that are evenly divisible by five, output the exact string Hophop, followed by a newline.
  • For integers that are evenly divisble by both three and five, do not do any of the above, but instead output the exact string Hop, followed by a newline.
This very simple program is typically written with a few if then else's, though you could also simulate a bitmask and use a case statement:

As soon as I'd written it I started wondering: can I optimize this? I mean, this is Facebook we're talking about. Endless scale. So if they offered a Hoppity function on the main page, you bet they'd have to make it run fast! :-)

Looking at this program it's clear that the output should repeat every 15 counts. Here's a Mathematica plot to illustrate this where I've replaced Hoppity, Hophop, and Hop with 1, 2, and 3 respectively.

So if you're ever interviewing at Facebook and you're given this problem (which would be surprising, I agree), you can offer this optimization to make sure the Hoppity feature doesn't take down their servers when they release it to all their members :-)

Pre-computing is always useful!

The Beautiful Atherton Tablelands

The Tablelands are a fertile set of plateaus to the West of Cairns in the North Eastern tip of Australia. It's a lush, verdant land with red red earth, rain forests, plains, hills, and much beauty. We spent a couple weeks in and around Atherton, the Tablelands' capital, and had a wonderful time (thanks to some great recommendations by friends).

Things to do:
  • The waterfalls! We visited in the "wet" (aka summer) and, thanks to recent rains, the waterfalls were in full bloom. Two are pictured below. The largest is Millaa Millaa falls, the smaller Malanda Falls. You can swim in both and it's a wonderfully refreshing experience...
  • ... As is swimming in crater lakes such as Eacham and Barrine (below). A remnant of the region's volcanic past the water is clean and free of crocs
  • Mount Hypipamee's crater is more impressive still but you can't swim in it
  • The Barron River cuts through the Tablelands, literally, giving rise to the Barron Falls which are over 200m high in places
  • There are unique fig trees in the area. Pictured below is the Curtain Fig tree. There's also a Cathedral Fig tree but we didn't have time to visit it
  • Yungaburra and Tolga both have large fruit bat colonies. Yungaburra also has a monthly arts and craft market
  • Keen on Aussie wildlife, Aborigine customs, and the rain forest? Take a day trip to Rainforestation, our boys had a blast there and, considering all you get to do, it was great value for money (more than Steve Irwin's Australia Zoo IMO). We took all three "tours" they offer and highly recommend a visit. BTW that's a cassowary, a dingo, and a saltwater croc below
  • If you're a World War II buff there's a decent museum on the road between Atherton and Mareeba, though a little pricey
  • The Crystal Caves is a shop / museum in Atherton. If you're really into rocks I'd take the self guided tour, otherwise just check out all that's on display in the shop
  • This list is far from comprehensive!

Mathematica, Pi, Mandelbrot, OpenCL, and More

As usual I was looking for something completely different (pages devoted to the game Hex, but that's another story) and came across this intriguing finding by Dave Brol.

Dave was investigating whether the "neck" of the Mandelbrot set was infinitely thin, and in the process realized that pi was showing up in the number of iterations he was performing. What the?!

Curious, I whipped up a quick Mathematica function to test his observation (and as another excuse to play with Mathematica :-)

First I define Mandelbrot's function, here called mandelIter. Nice, I can actually use complex numbers in Mathematica. This function is usually written to include a stopping condition based on a max number of iterations. I chose to omit it here since the points we're investigating are supposed to eventually escape the set.

The point in question is (-0.75 + x i) where x -> 0. The table shows what occurs for ever more "precise" (i.e. closer to 0) values of x. The right hand column lists pairs of numbers. The left one is the time it took to execute mandelIter in seconds. The right one is the number of iterations before escaping the set.

Notice anything special regarding those iteration counts? Yup, we're re-discovering pi.

The other thing you may have noticed is that it's going to take a long long time to calculate pi this way. Each subsequent finding takes 10 times longer to compute.

Naturally, I wondered how to make mandelIter faster.

Mathematica includes a Compile[] function, which basically turns a function into an optimized version, though it's still in pcode, not machine code.

My first attempt was just to compile the Abs[] and z = z^2 + c functions, but this resulted in trivial speed improvements. The solution was to let Mathematica compile the whole function.

Much faster! Unfortunately, it runs into problems and never returns when I go to 10^-8:

My assumption is that compilation uses machine-level precision instead of the arbitrary precision that's Mathematica's default. Since we're squaring very small numbers, we're rapidly exceeding this precision. It's pretty cool that Mathematica realizes this and switches back.

Still, I was hoping for more.

One of the features new to Mathematica 8 is the ability to leverage your computer's GPU, i.e. your graphics processor. Modern graphics chips actually have a massive amount of computing power and are highly parallelized. You typically program these chips with either CUDA (which is NVidia specific) or OpenCL (an industry standard). As of Snow Leopard, Apple includes OpenCL drivers with its Macs.

Re-implementing the algorithm was pretty easy: you're writing C code with an OpenCL flavor. Previous versions calculated each row sequentially. This version calculates them in parallel. After all, there are 48 (!) cores on my laptop's GPU :-)

mandelCLsrc takes 5 arguments: two input vectors, one output vector, the length of the vectors, and the max iterations we want to compute. Then I compile it with OpenCLFunctionLoad[]. Notice the "8" parameter: that means we want to leverage 8 cores to process this function.

If you're doing any OpenCL programming, definitely use OpenCLFunctionLoad[]'s ShellOutputFunction -> Print option, it'll help you find errors. While I'm on the subject: if Mathematica stops compiling OpenCL functions or behaves strangely, just restart it. OpenCL gives you very low level memory access, it's not hard to corrupt things.

So how did this solution fare? Disappointingly :-(

I define my two input vectors, xt and yt, and one output vector nt. Sadly, while the first few iterations are promising, it appears that we quickly run out of precision here too. With one thousandth as input, the function should return in roughly 31,420 iterations. Clearly it does not.

I tried switching from floats to double, even though my chip apparently doesn't support them, this was no help.

Where to go from here? Mathematica's ParallelEvaluation[] function, which splits jobs across multiple Mathematica kernel, won't really help. Another option could be to switch to integer arithmetic for Mandelbrot's function though I'm not convinced this would improve Mathematica's speed. There's always a chance that I may have done something wrong in my OpenCL code, or that further optimizations are possible in the Mathematica code. A final option that I couldn't get to work was running the OpenCL code on my CPU instead of my GPU. This is theoretically possible and would leverage the CPU's ability to handle higher precision doubles.

Implementation in a different language may be the ultimate solution. C, C++, or Java make most sense to me given they have excellent optimizing compilers but, just for kicks, I picked one of my favorite programming languages: ruby.

Here are the results running on ruby 1.9.2 (ruby 1.8.7 is about 1/2 as fast):

1,          3,        2.0e-05
1/10,       33,       4.4e-05
1/100,      315,      0.000312
1/1000,     3143,     0.003746
1/10000,    31417,    0.031083
1/100000,   314160,   0.300709
1/1000000,  3141593,  3.02154
1/10000000, 31415927, 30.608127

To my surprise modern ruby is significantly slower than compiled Mathematica at this task. I would have expected ruby to fare better.

Interestingly, both ruby and Mathematica bog down significantly when computing 10^-8. They don't return in a meaningful timeframe, i.e. I killed both calculations after 30 minutes. Presumably this is the point where both switch to arbitrary length floating point routines in software.

The Beautiful Chillagoe Caves

Chillagoe is an outback town about 3-4 hrs west of Cairns in Northern Queensland, Australia. Formerly a mining and smelting town, it's now famous for its spectacular limestone caves. There are apparently hundreds of caves in the area, many quite small. 

Three caves have guided tours and we visited all of them. We not only enjoyed seeing and learning about the beautiful stalactites, stalagmites, shrouds, pools, false floors and more, but it was also cool to see the caves' fauna such as different species of bats, huntsman spiders, and even a spotted python. 

Well worth a visit if you're in the area, our boys loved it.

Travel tips:
  • The caves' aspect will depend significantly on the time of year: during the dry you'll have full access but the walls won't sparkle, during the wet you will see calcite crystals sparkle, you may see waterfalls... and you may not be able to enter at all due to flooding
  • Given the last point it definitely makes sense to call the Chillagoe Tourist Office ((07) 4094 7163) esp. if you're traveling there between Feb and April
  • Don't know if it ever gets cold in the caves but we were quite comfortable in shorts and t-shirst when we visited in December
  • After a visit, climb up to the top of the rocks to admire the view and check out some of the caves "from above" (be careful!)
  • The aboriginal paintings are few in number, really faded and not worth bothering with
  • More information on the caves at the state park site
  • We stayed overnight at the Chillagoe Eco-Lodge and Observatory. The new managers were super nice and the rooms decent. Chatting with other guests and locals was an added bonus.

You have 100 feet of fencing, what shape will give you the biggest field?

That's the question I asked my sons today. It's an interesting problem but to make it a little more interesting and apropos given we're in Australia, I asked them: "If you were a crocodile farmer and only had a 100 foot long fence, what shape would you arrange it in to have the most space for your reptiles?"

I got many different answers: Square! Pentagon! Circle! Oval! Most people assumed square was the right answer but didn't all want to pick the same shape.

So we decided to start with a more general square: a rectangle. Thanks to a length of rope (representing our 100 foot fence) we were able to prototype various areas. A square seemed best. Was that so?

We turned to Mathematica (I just bought the newly released version 8, love it) for confirmation:

The maximum area is achieved when a side is equal to 25 feet. In other words: a square gives us the max area of 625 ft^2.

What about other shapes? Mathematica to the rescue!

A triangle makes poor use of fencing, the square is an improvement but clearly the more sides our fence has, the greater the area... The optimal shape must be a circle!

Though they saw that the circular field's area was greater than the square field's, this still didn't hit home until I plotted both.

Circles rock!

Saving a Flying Fox and Pup

Australia isn't only home to many beautiful birds, it's also home to many species of bat. An everyday occurrence for many Australians, seeing flying foxes in the skies at dusk, was a magical moment for our family. This just doesn't happen in California!

A few days later we were visiting friends who live next door to a bat colony. Walking under the canopy we spotted something all too common these days: a fruit bat struggling on the ground. She wasn't alone either: a pup was desperately clinging to its mother.

Mum was slowly dying from a paralysis tick bite: most Australian animals have built up immunity to its venom but not bats. Since the introduction of the tobacco plant twenty (?) odd years ago, the bats now come into contact with these ticks. Why? Because the flying foxes like the fruit of the tobacco plants, which are much shorter than the other fruit trees they frequent. Since they're shorter, ticks jump from forest animals like wallabies onto the plants, along comes a fruit bat, and...

The bat we found had a single tick on it. Our friend removed it but the damage was done: she didn't think the mother would make it, nor would the pup if we didn't do something about it.

Wrapped in a blanket we rushed both of them to the local bat hospital: a group of very dedicated individuals working hard to rehabilitate sick, injured, and orphaned bats.

The good news? They gave mum an antidote and she recovered! Both mother and daughter are now doing well and when we returned a few days later, the pup had been moved to an external cage.

Sadly, unless bats build up immunity to the ticks, I don't see their future very bright. A shame as they're beautiful creatures.

Here's a short video of the bats we saved...

So this is one of those Infamous Cane Toads?

Australia has an unfortunate history of introduced species running rampant and devastating native flora and fauna. Years ago it was rabbits. These days it's the cane toad (bufo marinus). Originally from Central and South America, the Australian toads were introduced in 1935 from Hawaii to eat beetles attacking sugar canes. Only two problems: one, the toads apparently don't like living in the cane fields; two, they're toxic and have no known predators in Australia. Indeed indigenous fauna such as lizards have declined from eating the toads. 

The toads are all over Queensland and rapidly moving into all Australian states. More proof that we humans are pretty poor at playing God.

That's one grumpy-looking toad.

More Diving in the Great Barrier Reef

Our three day live aboard adventure is over and we had a wonderful time. Snorkeling turned out to be just as fun as diving: we could be with our children and close to the surface colors just pop out. The boys had a blast, seeing fish, small sharks, and even swimming with and petting a turtle.

If you're looking for a diving adventure, we recommend Pro Dive Cairns: the crew were friendly, enthusiastic, and professional, the accommodations good, and the dive sites excellent.

For an affordable stay in Cairns, we really liked Tropic Days Inn. It has great atmosphere with hammocks, a swimming pool, musical instruments, pool table, etc. The owner, Gabriel, was incredibly helpful and made us feel at home. He also owns a sister hotel in Cairns, the Travellers Oasis.