A Rubik’s cube implementation in Three.js



In 2003, I took the time to put together a page that explains how to solve the Rubik’s cube with a set of formulas that are easy to memorize. The idea was not necessarily to solve the cube quickly (it takes about 50-60 seconds to solve the cube with this approach) but to make it easy for anyone to beat the cube with little effort, as opposed to the hundreds of formulas that speed cubists have to memorize to remain competitive.

Back then, I used a Java applet that represents a cube with formulas and then playing these formulas to explain to the reader how exactly they work. As everybody knows, Java applets have fallen out of favor even more today than they already were ten years ago, so I’ve been wanting to update my page with more modern technologies for a while, especially if these technologies don’t show a scary warning to everyone who reaches my web site.

I finally took the time to update my page and I reimplemented the entire cube animation in Javascript with Three.js. Here is how it looks like today.

While it’s easy to find rapidly implemented Rubik’s cubes in Three.js, I couldn’t find anything that came remotely close to what I needed, namely, being able to configure a cube directly from the HTML page along with the formula, and playing this formula at the click of a button. Three.js turned out to be a great match for this, with the perfect amount of abstraction and power. And with Three.js came a few free bonus tools, such as being able to move the cube around and also effortlessly zooming in and out. Of course, it’s equally trivial to modify the size of the cube, the position of the camera, the field of view, and just as easy to add more fancy stuff such as lighting, shadows and fancy materials.

The implementation is open source but I want to write some proper documentation before publishing it.

Overall, the experience was fairly pleasant. My relationship with Javascript is stormy at times (I’m planning to rewrite this in Dart at some point to compare) but in the end, using both IDEA and Eclipse to write the code (switching between both to compare) and with the Chrome debugger in a separate window, the productivity level is pretty high.

Implementing the cube itself was the most interesting part: there are so many ways you can model a Rubik’s cube that such a problem is a software designer’s dream. I must have had three different iterations of the data model before I settled on the version you see now (and I’m already thinking of ways I could improve it).

Three.js has come a long way since I gave it a try two years ago. The web is still filled with incorrect information referencing an old API that has since then changed, but it’s very intuitive and, most importantly, it allowed me to completely avoid having to deal with the WebGL madness. I don’t know if it’s my brain that’s just not wired for this, but I have tried to read countless OpenGL tutorials over the past years and every time, I give up after an hour, my eyes glazing over the intricate, effect-littered, abstraction empty details of OpenGL. The API is probably too low level for someone like me with just a passing interest for gory graphical details.

My knowledge of computer graphics and animation is abysmal overall, so this was a great opportunity to move myself out of my comfort zone and force myself to confront problems that I usually never encounter, such as finding tricks to counter floating point rounding errors and revising matrix multiplications and other miscellaneous linear algebra and 3D geometry concepts such as quaternions and gimbal locks.

Swift, Apple’s new language

Apple just announced a new language called Swift. I took a look at the language manual, here is a quick overview:

  • Statically typed with type inference.
  • Generics.
  • Closures.
  • No exceptions.
  • Extension methods.
  • Properties (syntax similar to C#), including lazy properties with the "@lazy" annotation.
  • Functions, methods and type (static) methods.
  • Support for observers (with "willSet" and "didSet"). Interesting to see the observer pattern baked in a language although I’m more partial to event buses for this kind of thing.
  • Enums.
  • Classes and structures (structures have restrictions regarding inheritance and other things).
  • For and while loops (statements, not expressions).
  • "mutating" keyword.
  • Named parameters.
  • Deinitializers (finalizers).
  • Protocols (interfaces).
  • Optional chaining with "a?.b?.c" and forced dereference with "!."“.
  • Convenient “assign and test”: "if let person = findPerson() ...".
  • Type casting with "is", down casting with "as?" (combines nicely with the "let" syntax. Ceylon does it right too).

Very interesting overall, and a clear step up from Objective C. From the feature set, I would say the language that Swift has the most overlap with is Kotlin, which is great news for Apple developers.

Update: discussion on reddit.

Coding challenge: partial results semantics

Consider the simple following signature:

  List<Person> searchPeople(String query);

This method takes a search string (e.g. “Bill”) and returns a list of Person that match this search string. This includes people with “Bill” as their first name, or as their last name, or maybe even using nicknames (someone whose name is “William” would match).

However, you have millions of people in your database, which means that this function call can potentially return tens of thousands of people, and it can also be quite time consuming. But your caller cannot wait forever and they want to cap the amount of time you spend doing the search, e.g. five seconds.

The function itself doesn’t know about this limit, it just does as much as it can and then it gets interrupted by its caller after the time has run out. You can imagine that the caller invokes this function in a separate thread and then calls get on the Future with a time out of five seconds.

The nice thing about the signature above is that it’s referentially transparent, which offers a lot of nice properties. However, it’s also binary: either it returns everything that matches the search or it gets interrupted before it can finish and the caller gets zero results.

The challenge is to write this function so that when it gets interrupted by the time out, it still returns whatever it has found so far.

The solution is trivial using mutable structures so bonus points if you can implement this solution with immutable data. Any language welcome, and I suggest you use pastebin or a similar service to share your code, since the comment system is not very good at formatting code.

More about language popularity

Hot on the tail of my previous post about language popularity, the latest numbers from the TIOBE are out.

The top five languages are C, Java, Objective-C, C++ and Visual Basic. Every other language beyond that has less than 4% mind share. The next JVM languages are Scala (#35) and Groovy (#48). Clojure didn’t make it in the top 50.

The pitfalls of Test-Driven Development

A few days ago, David Heinemeier Hansson posted a very negative article on Test-Driven Development (TDD) which generated quite a bit of noise. This prompted Kent Beck to respond with a Facebook post which I found fairly weak because it failed to address most of the points that David made in his blog post.

I have never been convinced by TDD myself and I have expressed my opinions on the subject repeatedly in the past (here and here for example) so I can’t say I’m unhappy to see this false idol finally being questioned seriously.

I actually started voicing my opinion on the subject in my book in 2007, so I thought I’d reproduce the text from this book here for context (with a few changes).

The Pitfalls of Test-Driven Development

I basically have two objections to Test-Driven Development (TDD).

  1. It promotes microdesign over macrodesign.
  2. It’s hard to apply in practice.

Let’s go over these points one by one.

TDD Promotes Microdesign over Macrodesign

Imagine that you ask a famous builder and architect to construct a sky scraper. After a month, that person comes back to you and says

“The first floor is done. It looks gorgeous; all the apartments are in perfect, livable condition. The bathrooms have marble floors and beautiful mirrors, the hallways are carpeted and decorated with the best art.”

“However,” the builder adds, “I just realized that the walls I built won’t be able to support a second floor, so I need to take everything down and rebuild with stronger walls. Once I’m done, I guarantee that the first two floors will look great.”

This is what some premises of Test-Driven Development encourage, especially aggravated by the mantra “Do the simplest thing that could possibly work,” which I often hear from Extreme Programming proponents. It’s a nice thought but one that tends to lead to very myopic designs and, worst of all, to a lot of churn as you constantly revisit and refactor the choices you made initially so they can encompass the next milestone that you purposefully ignored because you were too busy applying another widespread principle known as “You aren’t going to need it” (YAGNI).

Focusing exclusively on Test-Driven Development tends to make programmers disregard the practice of large or medium scale design, just because it no is longer “the simplest thing that could possibly work”. Sometimes it does pay off to start including provisions in your code for future work and extensions, such as empty or lightweight classes, listeners, hooks, or factories, even though at the moment you are, for example, using only one implementation of a certain interface.

Another factor to take into consideration is whether the code you are writing is for a closed application (a client or a Web application) or a library (to be used by developers or included in a framework). Obviously, developers of the latter type of software have a much higher incentive to empower their users as much as possible, or their library will probably never gain any acceptance because it doesn’t give users enough extensibility. Test-Driven Development cripples library development because its principles are at odds with the very concept of designing libraries: think of things that users are going to need.

Software is a very iterative process, and throwing away entire portions of code is not only common but encouraged. When I start working on an idea from scratch, I fully expect to throw out and completely rewrite the first if not the first two versions of my code. With that in mind, why bother writing tests for this temporary code? I much prefer writing the code without any tests while my understanding of the problem evolves and matures, and only when I reach what I consider the first decent implementation of the idea is it time to write tests.

At any rate, test-driven developers and pragmatist testers are trying to achieve the same goal: write the best tests possible. Ideally, whenever you write tests, you want to make sure that these tests will remain valid no matter how the code underneath changes. Identifying such tests is difficult, though, and the ability to do so probably comes only with experience, so
consider this a warning against testing silver bullets.

Yes, Test-Driven Development can lead to more robust software, but it can also lead to needless churn and a tendency to over-refactor that can negatively impact your software, your design, and your deadlines.

TDD Is Hard to Apply

Test-Driven Development reading material that I have seen over the years tends to focus on very simple problems:

  • A scorecard for bowling
  • A simple container (Stack or List)
  • A Money class
  • A templating system

TDD works wonders on these examples, and the articles describing this practice usually do a good job of showing why and how.

What these articles don’t do, though, is help programmers dealing with very complex code bases perform Test-Driven Development. In the real world, programmers deal with code bases comprised of millions of lines of code. They also have to work with source code that not only was never
designed to be tested in the first place but also interacts with legacy systems (often not written in Java), user interfaces, graphics, or code that outputs on all kinds of hardware devices, processes running under very stringent real time, memory, network or performance constraints, faulty hardware, and so on.

Notice that none of the examples from the TDD reading materials fall in any of this category, and because I have yet to see a concrete illustration of how to use Test-Driven Development to test a back-end system interacting with a 20-year-old mainframe validating credit card transactions, I certainly share the perplexity of developers who like the idea of Test-Driven
Development but can’t find any reasonable way to apply it to their day jobs.

TestNG itself is a very good candidate for Test-Driven Development: It doesn’t have any graphics, it provides a rich programmatic API that makes it easy to probe in various ways, and its output is highly deterministic and very easy to query. On top of that, it’s an open source project that is not subject to any deadlines except for the whims of its developers.

Despite all these qualities, I estimate that less than 5% of the tests validating TestNG have been written in a TDD fashion for the simple reason than code written with TDD was not necessarily of higher quality than if it had been delivered “tests last.” It was also not clear at all that code produced with TDD ended up being better designed.

No matter what TDD advocates keep saying, code produced this way is not intrinsically better than traditionally tested code. And looking back, it actually was a little harder to produce, if only because of the friction created by dealing with code that didn’t compile and tests that didn’t pass for quite a while.

Extracting the Good from Test-Driven Development

The goal of any testing practice is to produce tests. Even though I am firmly convinced that code produced with TDD is not necessarily better than code produced the traditional way, it is still much better than code produced without any tests. And this is the number one lesson I’d like everybody to keep in mind: how you create your tests is much less important than writing tests in the first place.

Another good quality of Test-Driven Development is that it forces you to think of the exit criteria that your code has to meet before you even start coding. I certainly applaud this focus on concrete results, and I encourage any professional developer to do the same. I simply argue that there are other ways to phrase these criteria than writing tests first, and sometimes even a simple text file with a list of goals is a very decent way to get started. Just make sure that, by the time you are done with an initial version, you have written tests for every single item on your list.

Don’t test first, test smart.


Update: Discussion on reddit

Language popularity on GitHub

RedMonk just published their latest survey of Github’s most popular languages, and given Github’s continuous growth in popularity, they are worth a look.

Here are the results at a glance:

  • Javascript is seeing a consistent and serious growth.
  • Ruby is in sharp decline.
  • Python is showing a decline as well, although not as severe as Ruby.
  • Java is showing some growth, and it’s also the only JVM language in the top 12 listed by Red Monk.

I’m going to go out on a limb and predict that Python is being replaced by Go. I don’t have a lot of information to back up this prediction except that most of the positive articles I read about Go are written by Python developers, and a lot of them say that they are now actively migrating their code base from Python to Go. I don’t see as much enthusiasm for Go from developers using statically typed languages, probably because of Go’s antiquated type system (which is still a big step up from Python, obviously).

It’s interesting to see Java continue to grow twenty years after its introduction. I think this constant growth is fueled by the language’s remarkable versatility and its ability to adapt to new technologies but also driven by a series of constant popularity boosts such as Android five years ago and Java 8 this year.

I’m surprised not to see Groovy in this top 12 of languages, since it’s usually acknowledged as the second most popular language on the JVM and I expected its popularity grow thanks to Gradle, but this doesn’t seem to be enough to crack the top 12 on Red Monk.

Update: Discussion on reddit

A bit I can’t unsee

This is the binary definition of ET’s sprite, in Atari’s infamous game:


ETWalkSprite_A0
.byte $FE ; |XXXXXXX.|
.byte $FF ; |XXXXXXXX|
.byte $C3 ; |XX....XX|
.byte $0F ; |....XXXX|
.byte $FF ; |XXXXXXXX|
.byte $3F ; |..XXXXXX|
.byte $2B ; |..X.X.XX|
.byte $E7 ; |XXX..XXX|
.byte $00 ; |........|

I am actually less disturbed by the 6502 listing than by this extra bit between ET’s legs (which you can see on the screen shot above).

Coding challenge: fast width/height of an image

I am trying to find out the width and height of an image (a URL) transferring as few bytes as possible. This coding challenge has two separate parts:

  • Finding the cheapest way to retrieve width and height.
  • Verifying that the solution is indeed cheap.

The first part is not that interesting since it’s a fairly well documented problem. A bit too documented, actually, since I found several solutions:

This last solution looks pretty efficient from a network perspective but I’m worried it might leave out a few corner cases in image handling. The first two solutions are probably battle tested and very robust but I have no idea how effective they are from a network standpoint (their Javadoc doesn’t describe the specifics of how they operate).

So… Do you have a better solution? And whether you do or don’t, how would you assess how many bytes these implementations transfer?

Chrome and passwords

An innocent blog post demonstrating that it’s trivial for anyone to see passwords in clear in Chrome is slowly building up into a whole scandal. The Chrome team was quick to respond but unfortunately, that answer simply poured oil on a fire that was already burning quite brightly.

Here are a few predictions:

  • As we speak, the Chrome team is having an emergency meeting to discuss the situation.
  • Within a few days, they will announce that they are going to fix the problem.
  • In a couple of weeks, the next version of Chrome will no longer display passwords in clear without additional action from the user.
  • In the months that follow, the other browsers will fall in line and implement a similar fix (Update: Safari already prompts you for your machine password before showing you its passwords, thanks Fabrizio for pointing this out).

I’m guessing Justin Chuh is probably regretting answering so hastily (you know you’re in hot water when Sir Tim Berners Lee calls your answer “disappointing”) and this might be a good illustration of being immersed into a domain for so many years that you start missing out on obvious things. We’ve all been guilty of this at some point, where our own expertise is reinforcing a flawed premise and that very expertise is preventing us from being critical of that very same premise.

The general idea is that once someone has physical access to a resource you are trying to secure, that resource is pretty much gone, so you shouldn’t spend too much time trying to address that scenario.

A common response to this is that once someone gains access to your computer, they can still log into your favorite web sites without knowing your passwords, but this is a straw man: the exposure of your passwords in clear text can be devastating since this knowledge can then be used to many more web sites. If you give me a password cookie, I can only log to so many web sites in a few minutes. If you give me your clear text password, I can spend hours back home trying to log in various web sites without worries.

The danger with the “physical access is not worth addressing” premise is that it’s tempting to do absolutely nothing to address this case (which is what most browsers do, Chrome is not the only culprit here) instead of doing at least a minimum. For example, maybe you have some cash in your home that you save for emergencies and you are wondering where to hide that money. Just because a burglar inside your house can steal whatever they want at that point doesn’t mean you shouldn’t at least make it a bit harder for them. Surely, hiding that cash inside socks in a drawer is a bit more secure than leaving it in plain sight on the kitchen table.

This added bit of security can be crucial for two reasons:

  • It raises the technical bar on the thief. With the current situation, someone who sits down in front of your unlocked workstation can know your passwords within ten seconds and just a few clicks. Hash and hide these passwords and suddenly, reading them is no longer accessible to a large part of the population.
  • Time is also a factor. When someone gains access to your computer, they might only have a few minutes and anything you can do to delay them (such as installing a hash decrypter) is that much time they don’t have to steal something else.

Whatever happens, I think we will all come out of this situation with more secure browsers.

Email tips

Email tips which I thought were common knowledge.

Avoiding embarrassing forwards

Problem: You receive an email (say from a customer), you pass it along internally with a few comments and… you accidentally copy the author of the email with details they were not meant to read.

Solution: Instead of “Reply to all”, adding your team in Cc and removing the customer (the part a lot of people forget), forward the whole email and then add your comments. It’s much easier to avoid mistakes when you have to populate an empty To: box than when you have to edit an existing list of To's, Cc's and Bcc's.

Don’t send too soon

Problem: writing an email that’s not ready to be sent yet.

You need to write a detailed email which is not supposed to be sent just yet (for example because you are describing something you’re still working on). How do you make sure that you don’t send the email until the time is right?

Solution: Write it and save it as a draft but don’t enter anything in the To: box. Do this last.

Say no to ugly emails

Problem: You want your emails to look nice.

My emails routinely contain code or shell output, and as much I love Gmail, its abilities to format are pathetic, both from a user interaction standpoint (why do I need three clicks to indent text to the right?) and from a theme standpoint. For example:

In order to get this ugly rendition of code, I had to indent the snippet manually and then change its font. And it still looks terrible.

Solution: Use Markdown Here, a Chrome extension which not only allows you to format your code in Markdown but also uses some pretty nice CSS.

You only need a few backticks and, optionally, specify the language:

```java
public class SlidingWindowMap {
  public SlidingWindowMap(Set keys, int maxCount, long periodMs) {
    // ...
  }
 
  /**
   * @return a key that has been used less than `maxCount` times during the
   * past `periodMs` milliseconds or null if no such key exists.
   */
  public String getNextKey() {
    // Your brilliant Solution goes here
  }
 
}
```

Click the Markdown button and voilà:

Your turn now, what email tricks do you use which you think very few people know?