Category Archives: Uncategorized

Cellular Chronometer Part 1: Reversing the Game of Life

I’m designing an LED matrix clock that plays Conway’s Game of Life to evolve a representation of the current time. See the whole series of blog posts about the project here.

The very first step of making the Cellular Chronometer is figuring out how I’m going to make the clock display the time. As a quick refresher, Conway’s Game of Life is what’s called a “cellular automaton“, which is a set of simple rules that’s played over a grid of cells, each of which are alive or dead. You process the grid with the rules and get a new grid with a different set of cells. Cellular automata are interesting because simple starting configurations can lead to really wild phenomena like self-replicating patterns and apparent movement.

But what I want to do is be able to get the game to display specific states. I want to populate the grid with a state that I know will evolve into a digital display of the current minute. The only reasonable way I could think to do this is to craft my desired state in advance and then do a search backwards – that is, in the reverse direction of the regular Game of Life – to find prior states. This happens to be a nontrivial problem. Played forwards, the Game of Life has very simple deterministic rules, but played backwards, there are an immense number of possible configurations to examine. In computer science terms, this problem is bounded by 2^n, where n is the number of cells in the grid. 2^n gets really big really fast. Not good.

Luckily, like so many other aspects of the Game of Life, work has been done trying to efficiently search for prior game states. I figured this out after two weeks of fruitless genetic algorithms experiments when a desperate Google search led me here. While the code didn’t prove useful to me, I managed to suss out that there are several existing algorithms that do what I need. The one that I best understood is called Duparc’s Method. The key win is that instead of being 2^n in the size of the pattern, Duparc’s method is only 2^n in the height of the grid! Since my grid is only five cells tall, this makes the search into a tractable problem, even if it does turn my MacBook into a proper lap-roaster.

duparc_illustrationIt’s hard to be 100% sure if I took the same approach as Duparc, since his original research paper is written in French. The way my algorithm works is to divide the grid in half vertically again and again until I’m working with single columns, at which point I essentially rotate the column into a row apply the same subdivision algorithm again until I reach a single cell. Single cells – both alive and dead – have a nice, cacheable method for determining all their prior states. Once I have the partial answers for a single cell, I intersect them with the answers from the neighboring cell by checking the overlap between the two. If the cells shared by the two possible solutions match, then the combined solution is also viable. Partial solutions that don’t match neighbors are discarded. This same process of merging based on overlapping cells continues back up the search tree until we reach the root, at which point we have a set of possible prior generations.

Something that took me a long time to grasp fully is that the algorithm naturally has to search in a grid bigger than the one you’re starting with. The reason for this is that while true “gardens of eden” are extremely rare, if you constrain the grid to a finite number of cells, it’s not at all hard to come up with a pattern that isn’t produceable. I ultimately came up with this sort-of logical proof to convince myself on this one:

  • In a grid of N cells, there are 2^N unique configurations
  • Some of these 2^N configurations will lead to non-unique next generations (ie, all cells dead is pretty common)
  • Therefore, it cannot be possible to generate each of the 2^N initial configurations from one of the other initial configurations.

In practice, this just means that you have to allow a “gutter” of arbitrary-valued cells around your desired image. If it’s really important to trim the excess, you just select ultimate solutions that have the extra cells as dead, since that’s the same as the border on a finite grid. The risk is that you’ll filter all the possible solutions by doing so.

As I developed this algorithm, I found that the line between “ever finishes” and “never finishes” was very fine. Most of the problems stemmed from running out of memory on my 16GB MacBook. A given target grid can have millions of intermediate states, and they need to be cached to make the algorithm run in a reasonable amount of time. The tweak that I credit with getting me all the way over the line was to discard many of the intermediate answers that, while actually unique, had the same border regions as other answers. Since the merging algorithm examines only the region of overlap between two sets of sub-solutions, any non-overlapping sections don’t actually increase your chance of finding some solution, and as such they can be discarded. This does mean that not all prior states are found, but for my purposes, I only need one.

Screen Shot 2013-09-01 at 8.57.39 PM

Along with improving the algorithm, I found that I had to tweak my font. Early on I guessed that different fonts and digit spacings would have an effect on whether a given configuration was reversible. I was surprised by how many of the configurations I wanted to generate were impossible with the grid dimensions I was enforcing. I had the algorithm report a bunch of statistics while searching so that I could see (at an aggregate level) when all possible solutions were being eliminated. I learned that particular characters were difficult to reverse, like 4s, 5s, and 0s. But the one that most surprised me was the colon I added between the hours and minutes. That guy turned out to be stubborn in some of the worst cases. In the end, I had to compromise and hand-edit certain minutes so that they would reach a prior generation.

The end result of all this hard work is 720 unique start states that will each evolve into one of the minutes of the 12-hour day. I’ll embed these states directly into the firmware for the clock so that my tiny microcontroller won’t have to do any “real” work, just run the Game of Life from each start state and advance the pointer every minute.

You can find the Ruby code for this crazy search in my GitHub repo.

Advertisements

The Cellular Chronometer

Making a clock seems to be a rite of passage for hobby electronics folks. The appeal is pretty obvious: straightforward functionality built with common components, and when you’re done, you have something that you can actually use in your daily life.

A little over a month ago, I had the idea for a clock project. But my clock is going to be a bit unusual. I’m designing an LED matrix clock that shows the current time by playing a different instance of Conway’s Game of Life every minute that evolves into the digital representation of the current minute. I’m going to call it the Cellular Chronometer.

This project concept hits the sweet spot for me in a number of ways. First and foremost, the challenge of making the Game of Life do my bidding is exactly the kind of deep, interesting algorithmic problem I love to tackle. I get to use all of my optimization and analysis skills to get a pretty cool result. Second, I am a sucker for designs that make use of cleverness to get a lot out of a little, so naturally I’ve been dying for a reason to build a Charlieplex, and this is the perfect opportunity. Finally, since this is something I want to actually put on display somewhere in my home or office, there’s a nice industrial design aspect to it. I want it to look well-made and polished when it’s finished.

Making an LED matrix should be pretty straightforward, as should be the “clock” behavior. I’m most familiar with Atmel microntrollers and the Arduino environment, so I’m going to use that for all the coding. Playing the Game of Life on a microcontroller is nothing new, but it’s probably impossible to search for prior game states on something with so little memory, so I’m planning to use my laptop to pre-compute all of the starting states that lead to my desired end states. And finally, I’m thinking that I’ll do the enclosure out of wood (either laser-cut or CNC-milled) so that I can finish it handsomely.

There are a lot of individual steps to this project, and I’m going to try to document them individually as I work through the project. Stay tuned for updates!

Form letter response for engineering recruiters

Like every other breathing engineer in the Bay Area, I get a lot of cold emails from random recruiters. While I haven’t yet replied to one of those messages with the below, I sure am tempted at times. Feel free to modify this template for your own purposes!

Corollary: if you are a recruiter, and you find that your reach-out emails would tick some of these checkboxes, maybe it’s time to reconsider your script.

Hello,

Thank you for your note. I am not interested for the following reason(s):

[ ] You do not include the specific name of the company you represent, which a) leads me to believe you are just canvassing and b) limits my ability to filter based on companies I don’t care for

[ ] You do not call out the specific skills I have that make me a “perfect fit”

[ ] You refer to skills or interests a) substantially in my past and/or b) clearly not part of my current role or expertise

[ ] If your CEO/CTO/VP Eng/Director of ____________ thought my background sounded good, he/she should have emailed me personally

Additionally:

[ ] I will not send you any leads because I am already personally recruiting all the good people I know

[ ] Your request that we start with a “quick call” shows a clear disregard for the work style of engineers

[ ] You appear to have misspelled my name despite having my email address to use as starting point

Lasercut Dual Vertical Cinema Display Stand

front
Front view
back
Back view

Last week was HackWeek at Square, and as usual I took the opportunity to stretch my maker legs. This time I decided to tackle a practical problem that’s on my horizon – or perhaps more accurately, in my peripheral vision.

My current workstation has two Apple Thunderbolt Displays. This is, as you might imagine, awesome. There’s tons of desktop real estate to lay out browsers and code and terminals. However, this setup does have a dark side: it’s 50″ wide! Not only does this require me to pan my head to see the far edges of the most distant windows, but it’s actually wider than the desk space allotted to me. As soon as someone moves into the vacant spot next to me, one of these bad boys will have to go.

Faced with the prospect of giving up one of my beloved monitors, I hatched a plan to rotate them both from landscape to portrait. The traditional way to achieve this sort of thing is through the magic of the VESA mount. A lot of monitors have this built in, but not Apple displays. (After all, who wants to see a bunch of extra screw holes on the back of their perfectly sculpted monitor?) Apple sells an add-on VESA mounting kit, which is apparently an enormous pain in the butt to install. (You know it’s a bad sign when a how-to includes fast motion.) Luckily, the Square IT team had a pair of the older Cinema displays with the

VESA mount already attached so I could experiment.

Once your monitors are ready to be mounted, you need a stand. There are commercially available stands of all sorts, but that’s no fun, so instead I designed a custom stand using my favorite tool of choice, OpenSCAD. I wanted something that would be cheap to fabricate and easy to assemble that would still turn out handsome and sturdy. This led me to choose laser-cut birch plywood and the standard T-slot style screw-together construction.

By far the hardest part of this project was getting all the geometry correct. I wanted the monitors to come together very precisely, so I had to lay out the mounting points by carefully computing a bunch of different angles. There were more than a few head-scratcher moments spent hunched over a notepad. (Lesson learned here: start your sketches much bigger than you expect if you’re planning to add a lot of little annotations for angles and segments.)

This version seems to work pretty well, though I’m still planning to to a nice sanding, staining, and clear-coating pass to make it extra presentable. I also set my personal best for time from conception to realized prototype – I started sketching on Tuesday afternoon and had the stand built by noon on Friday.

As usual, all the project files are available on my GitHub page. If you’re thinking of making one, let me know!

Custom standalone programming fixture

I spent my evenings over Memorial Day weekend working on a customized fixture designed to make programming and testing the electronics of our Question Block Lamp really easy. As part of our plan to bring the lamps back into production, we decided that a custom programming fixture would go a long way towards helping our outsourcing partner get exactly what we want quickly and without the difficulty of communication. (Emailing back and forth to China is actually pretty expensive – a simple back-and-forth exchange can take days, thanks to the time difference.)

Once we decided to build this device, I jumped in and started designing. I had a few clear design criteria:

  • It should be durable. It will be used to program thousands of units. (Hopefully, tens of thousands!)
  • One part or another will ultimately break down, so it has to be modular and easily repaired,  particularly by someone other than me.
  • It should be incredibly intuitive to use. After all, it’s not even clear that the people using it will speak English!

Here’s what I ended up building:

2013-05-24 23.21.00

The interface

The interface is very simple. The strip of LEDs down the right hand side indicate the state of the programmer. The top one is just power, so you know it’s on. The next is the “contact” indicator, which lights up when a target board is properly connected. After that is “working”, for when the programmer is programming, and then “success” and “failure”. I etched the descriptions next to the LEDs, but used different colors so that it’s clear even if you don’t read the text. You start the programmer by pressing the only button on the faceplate, marked “Go”.

The enclosure

The exterior of the device is laser-cut 3/16″ acrylic. We just happened to have clear laying around, but I think that a more opaque color might work out better. I used standard T-slot style construction to put it together, with the exception that I used long screws from the top to the bottom to make a sort of sandwich. All the fasteners are #4-40, which I’ve found to be a great size for these small-scale enclosures.

A big part of the combined electronic and enclosure design process was rendering the whole thing in OpenSCAD, my 3D design tool of choice. I personally find it really crucial to be able to visualize how all the parts will go together before I settle on details of a design. Here’s the final render I ended up with:

standaloader_render

The hardware

On the inside, the components are simple by design. The brain of the whole operation is just a plain old Arduino Uno. I chose to use an Arduino as the driver for the programmer for a few reasons: I’ve used the ArduinoISP sketch a lot in the past very successfully; there was already existing code to convert an Arduino into a standalone programmer; the USB port and barrel jack were the only connectors I needed; and Arduinos are completely ubiquitous and easily replaced.

In addition to the Arduino, there are a few custom components. First, there’s a shield I designed that mates with the Arduino and provides all the connection adapters to the two other peripherals. It also has a handful of resistors for lighting the LEDs and a capacitor to suppress the auto-reset that occurs when a computer connects to the USB port – a must-have when operating as an ArduinoISP. Next is the interface board, which is basically just an LED array and the Go button – not much to see there.

The most interesting and challenging to fabricate component is the pogo pin array. I took inspiration on how to make this thing from a number of other pogo pin projects I’ve seen across the web. I made a point of breaking this out into a separate module so that I could isolate “fragile” electronics like the Arduino from any sort of mechanical stress. I found that setting the pin height was a little fidgety, and I’m going to experiment with alternative techniques for that the next time around.

The code

I based my programmer code very heavily on the existing AdaLoader project. However, there were a number of tricky issues I had to chase down to get it to work in my application. The original version was designed for flashing bootloaders onto ATMega168 chips, and there are some assumptions baked in to match that choice of target. Since I am flashing ATTiny44 chips instead, I needed to figure out the mismatches and update accordingly.

The first step was spending some time with the ATTiny24/44/84 datasheet to get some information like the chip signature. Next, I had to capture the hex file of my compiled code. The Arduino UI creates this file already, but it puts it in a random location every time. Finding it is pretty easy if you turn on the debug logging feature. (Basically, just set upload.verbose=true in your preferences.txt file.) After that, the path to the hex file is displayed in the window at the bottom every time you build/verify.

With the hex file in hand, I ran into my first real issue. For some reason, even though my program was actually laid out in contiguous memory, the hex dump produced by the Arduino IDE broke it up a bit towards the end. The AdaLoader code didn’t like this – it expected every hunk of data in the hex dump to be full and got confused when it wasn’t. I ended up writing a short Ruby script to transform the hex file into a clean, contiguous dump. I couldn’t quite figure out what I was doing wrong when trying to calculate the line-ending checksums, but I wasn’t really worried about data integrity between my laptop and the Arduino, so I ended up disabling that feature.

At this point I ran into my second issue – really, a pair of issues. What I was seeing is that the flashing would complete, but when the programmer read the bytes back to verify them, it failed, saying that the values were wrong. Uh oh. This was a real head scratcher for a while, so I spent some more time reading the datasheet. The first issue I found was that while the ATMega168 has a 128-byte flash page size, the ATTiny44’s was only 64. That was concerning, so I changed the settings, but the problem persisted. After reading the code very carefully for a while, I managed to debug it to point where it looked like it was flashing two different chunks of data to the same memory address. In fact, there was an odd pattern of alternating correct addresses and incorrect addresses aligned on 128-byte boundaries. (0x0 -> 0x0, 0x40 -> 0x0, 0x80 -> 0x80, 0xC0 -> 0x80…) This turned out to be because the target address was being masked with a pattern that aligned on 128-byte boundaries – clearly a relic of the code’s prior purpose. I just removed the mask altogether and all of the sudden everything started working!

What I have now is a device that can be powered by a simple wall wart and will program an un-flashed board in about 5 seconds, much faster than if we were doing it with the computer attached. Woo hoo!

There are a few next steps for this project before I’m considering it done. The programming part of the device is important, but so is the testing part. I’d like to figure out how to make the programmer put each newly-programmed board through it’s paces briefly so that we can identify defective boards early, before they are glued inside finished lamps. Also, there are a handful of places where the part tolerances of the laser-cut parts aren’t perfect, and making another copy gives me the opportunity to correct those mistakes. The version that I end up sending to China should be a bit more polished and feature-packed.

How to impress me in a coding interview

At Square, candidates are expected to actually write code during the interview process – on a computer, not on a whiteboard. As a competent software developer, this kind of interview should feel like a gift. Your skills are going to be measured more or less directly by doing the very thing you’ve been doing all these years!

So how do you impress me – or any interviewer – in a coding interview? Here are a few things I consider when pairing with a candidate.

It’s about the process

First off, let’s deal with a myth: the interview is not about the answer to my question. Sure, I’d prefer that you get it right, but I’m far more interested in seeing how you work to get there. I want to see how you decompose problems, conceive solutions, and debug issues as they arise. Make sure you take the time to show me how you’re getting to the answer.

It’s about communication

A big part of the development process on a healthy team is communication. Ideally I’d like to leave the interview feeling like you’re someone who asks good questions and is receptive to feedback and external insights. A great way to blow this portion of the interview is to hunch over a notepad and scribble quietly while I wait. If you must do something like this, be prepared to explain your thoughts thoroughly when you’re done.

Don’t go it alone

My interview exercise is hard. I fully expect that you might need a hint at some point. I even enjoy working with you to debug the problems you hit as you work. But if you never ask, you’re not going to come out ahead. Coding on a real team often involves working on something that you don’t understand, but that the person sitting two seats down knows in detail. You should be self-sufficient only insofar as it makes you productive; spinning your wheels trying to go it alone is just indulgence.

You should run the interview

Don’t make me march you through all the steps. Once I’ve explained the exercise and you’ve started coding, it’s best if you drive. If you need help, ask. If you think you’re done, propose more test cases or ask for my thoughts. The best interviews I’ve had are more like working with the candidate than interviewing them. If you can do this in an interview setting, then I can believe you’ll work the same way when you’re on my team.

Use the tools

I am consistently impressed when a candidate is able to drop into a debugger or quickly access documentation in the IDE of their choice. It’s an aspect of professional mastery that will be extremely important to your day to day productivity. The inverse is also true – if you choose to write C++ in vim and don’t know how to save the file, it’s going to cost you.

No bonus points for doing things the hard way

One of the key attributes I select for in coworkers is pragmatism. Sometimes this means choosing an ugly but expedient solution instead of an elegant but expensive alternative. If you know when to make these tradeoffs, you’re someone I want to work with. A lot of candidates feel pressure to give me “perfect” solutions right away, but I’d rather see an answer than an incomplete, perfect one. Plus, I love it when we can iterate on the “quick and dirty” solution to build a refined version. This is how software works in the real world, and I love when candidates aren’t too self-aware to just go about it casually.

Moving on

In a turn that few will have seen coming, this coming Friday will be my last day at Rapleaf. After five years, I’ve decided that it’s time to move on and seek new challenges. To that end, after much consideration, I will be joining Square to help them scale up their analytics efforts. I’m incredibly excited to get to work with a new team on a totally new problem domain, and I believe I have a ton of value to add to the company.

This decision is exquisitely bittersweet, though. It’s difficult to even begin to describe how spectacular my time at Rapleaf has been. I found it telling that when I tried to sit down and write a summary of my experience for my resume, it seemed impossible to summarize all that I had learned and done. This is still totally insufficient, but I’ll boil it down to this: I was given the opportunity to make many amazing software systems; I was allowed to grow into a member of the broader engineering and open source community; I learned the meaning of scale; I got to be a real owner of the business’s direction and purpose; and I played a role in building a world-class team.
It is this last point in particular, the team, that puts the tears in my eyes. I have never before had the opportunity to work with so many brilliant, hard-working, interesting, and just generally nice people, and I am humbled and honored to have been counted among their number. My greatest worry – one which I consider not wholly irrational – is that the team I’m leaving behind is in fact of the rarest kind, and I’ll spend the rest of my career hoping to rebuild something as great.
To everyone I have worked with over these last five years, thank you for everything you have taught me. You are what has – and will continue to – make Rapleaf great. 
Let’s do this again some time.