A few different things led me to this contest over winter break. I’ve been feeling sort of unfulfilled creatively for a few years now - engineering school will do that to you, I think. Around Halloween, I saw Stella Parks’ haunted gingerbread house and thought for a second that it’d be a good thing to do before a Halloween party we were throwing, but there just wasn’t time.

A few weeks later, I saw the McMansion Hell contest - it seemed totally perfect, a creative project that I might actually be able to finish. I started thinking of ideas, and ways of keeping myself from burning out halfway through. I’ve left a lot of half-finished projects lying around after losing interest. When I flew home for Christmas, I found a self-help book at the airport called Finish (which I could not be mature about). I brought myself back from the brink of actually buying a self-help book at Hudson News, and started reading Amazon reviews to find the two bits of useful advice in it. I had already been thinking along these lines, so I really latched onto those ideas of cutting my goal in half and trying to reduce perfectionism.

I made a couple of test houses to practice the gingerbread/icing recipes (Stella’s), and they really helped me adjust my expectations of the scale of this project. It turns out even making the style of house that a 5-year-old might draw is super hard. I canned a lot of my original ideas, like having interior rooms or dormers on every roof.

Stella points out a huge advantage to a haunted gingerbread house - any mistakes you make are consistent with the theme. So a broken piece of the facade, hastily glued together with icing, is just one more aspect of a spooky old house. A similar thing happens with a gingerbread McMansion: If it’s lopsided, or shoddily decorated, or the design is just plain ugly, that’s because it’s a cheap house designed by committee and built to be big instead of tasteful.

The project took place over three days, not including the design process, learning about architecture from reading the McMansion Hell blog, or my two practice houses.

Day 1: Cutting templates and baking pieces

I started the morning by making 6 batches of Stella’s construction gingerbread recipe and putting them in the fridge. I ended up doing this in two batches, since I didn’t really think my mom’s old KitchenAid would fit all of the dough.

Once this was done, I turned my attention to the template. I drew an excellent model in SketchUp, and planned the measurements. I drew every piece on a big cardboard box, then cut them out (I found a T-square in the basement, which was lifesaving). To make sure all of the measurements were right, I tried putting it all together with packing tape. Pieces that were on the inside of joints got about ¹⁄₈” cut off of them to account for the thickness of the pieces. The thing seemed to stand up on its own ok, so I was ready to make the gingerbread pieces.

I took a break at that point to finally see Free Solo (so good) and get lunch and a coffee. I always love sitting in diners with some food and coffee, not doing anything besides looking around and listening to people. Even better when there’s a bar to sit at. Eating alone is very underrated.

I had a loose plan for which cardboard pieces would go on which sheet, and mostly stuck to it. This part was pretty mind-numbing. Roll out a sheet, put it on my parents’ one sheet pan (my sister had taken the other one to her apartment), lay out some cardboard pieces on it, cut around them, bake the sheet, cut around the pieces one more time just after taking the sheet out of the oven, then punch them out after it cools. I got through 4 out of 6 before I needed to go to sleep - only a little bit behind schedule.

Day 2: Assembly

In the morning, I finished baking the rest of the pieces. I was going to see some cousins at a mall, so I popped into one of those fancy-looking mall candy stores to find materials for decorating. Everything was very expensive, and nothing was really right for a gingerbread house, but I grabbed some rock candy to try to melt into windows.

The whole window thing didn’t work out at all. As part of my anti-perfectionist Zen, I decided it would be better to finish it with mostly empty windows than to burn out.

After that, I mixed up a batch of this royal icing (I do not have many recipe sources in my life), and started putting it all together. I had made a cardboard support piece for the middle of the large hipped roof on the left, to put under it while the icing dried, but I realized as soon as I took it out that I’d need to bake a gingerbread piece or the roof would go down when I tried to decorate it. Other than that, it came together pretty easily: when the pieces didn’t line up quite right, I just slathered on more icing.

This day also ended a little behind schedule, with two roof pieces and a dormer not attached.

Day 3: Decoration

I glued on the remaining pieces, then got to work on the turret. I made a mold out of foil, but ended up mostly shaping it by hand. Rice Krispee treats are a totally gross invention. I had a couple of friends who were interested in decorating, so I mixed up some more icing but then sat back until they came over. Since I didn’t have a plan ready for decorating the thing, I just let my friends do whatever they thought would look good. The result was a little slapdash, but it made me really happy to be with people working on something like this.

Lessons Learned

• Nobody should ever try to make a gingerbread house in one day. Spread it out over at least two.
• Gingerbread can either taste good or be a good building material, but not both.
• Candy windows are extremely hard to do, and Ralph’s does not carry sheet gelatin. Order some online next time.
• It’s important to plan ahead with a big project, and lower your expectations. Things will happen that you didn’t plan for, so allow plenty of time.
• Finishing a creative project feels amazing, even if the result isn’t perfect.

This is a post about a question from Cracking the Coding Interview. It’s boring, so probably go watch Stranger Things instead.

“Given a list of millions of words, design an algorithm to create the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). The words need not be chosen consecutively from the list, but all rows must be the same length and all columns must be the same height.”

Example:

spears
planet
easily
animal
relate
styles

Occasionally I’ll try a practice problem like this on a whiteboard. Usually I learn something cool or at least feel a little less like I’m going to curl up into a ball the next time I have a programming interview, but this one got super weird and interesting.

Try to come up with one of these rectangles with just the words you know, it’s like a crossword puzzle with no clues or boxes and it’s horrible. I muddled along though, and with just a couple hints from the book, I came up with something, question mark? Let’s go through it.

When you’re building up a rectangle row by row, you tend to get stuck pretty quickly with something like

noticable
potential
classroom

because npc isn’t the start of any word I can think of. If the words are stored in something called a prefix tree (these are also called Tries but I don’t know how to say that and it isn’t very descriptive), you can easily check this for any partial rectangle you’ve built up, and cry because basically nothing works. But if you’re a computer, you wouldn’t cry because that’s ridiculous, and because it means you don’t have to try quite so many rectangles, and you can move on to rectangles that still have potential.

So, let’s just assume we knew all about prefix trees and we just have some object that tells us if something is a prefix for a word in the list.

tree.isPrefix('spe')
True
tree.isPrefix('npc')
False

Now, instead of doing a search on all possible 10 x 10 word rectangles (conservatively, if you had 10 10-letter words in your language that’s already ten billion rectangles), we can “prune off” some of the rectangles before they’re even fully formed, and go right from

spears
planet
planet   # spp? I don't think so

to

spears
planet
easily

skipping right past

spears
planet
planet
planet   # a person would have stopped trying by now

After this, it’s basically brute force. I took the book’s advice and tried areas in decreasing order until finding a size that was possible, so the main loop does that and calls a function sort of like this at each step (I changed a few things to make it clearer what’s going on):

def makeRectangle(length, width, words, rect):
    if rect.width == width:
        if isFullRect(rect):
            return rect
        else:
            return None

    for word in words:
        rect.addWord(word)
        if not isPartialRect(rect):
            # Prune this one! Don't try any of its descendants.
            rect.removeWord()
            continue
        else:
            fullRect = makeRectangle(length, width, words, rect)
            if fullRect:
                # The recursive call got it!
                return fullRect
            # Or it didn't, and we remove the failed word to try the next one.
            rect.removeWord()

    # If all those fail, it's impossible.
    return None

You might recognize this as a depth-first search - it goes deep and tries everything it can with a given first word before trying with the next first word.

There’s a few elements of the solution I’m glossing over - walking down potential areas to see if any of them are possible, splitting the list of words up into the different lengths - check out my full solution here.

Once I debugged it on this very small test set

['dog',
 'emu',
 'fog',
 'def',
 'omo',
 'gug']

(I’m not good at crossword puzzles so I cheated), I put it to work on /usr/share/dict/words, a file with about 230000 words in it, which has words almost as obscure as ‘gug’ but is a good, smallish example of the type of data the question asks about.

My program chugged away for a few minutes without coming up with anything, so I ran a profiler on it to see what was taking the most time. Over the next day, I tried everything I could think of (short of rewriting the damn thing in C) to get this program to run faster (including but not limited to storing rectangles as byte arrays, storing rectangles as columns instead of rows, replacing the prefix tree with a huge hash table of strings that were valid prefixes), but it couldn’t finish the search for words much shorter than 16 letters (it’s easier the more letters you’re trying to use per word, because of how few words there are with 16+ letters).

Finally, frustrated, I turned to the solution in the book. Just reading the code, I couldn’t figure out why it would be much faster than mine, so I thought I’d clone it and try to run it myself. The solution is written in Java, which I know barely anything about, and the author recommends using Eclipse, which I know nothing about. I halfheartedly tried to bully it into running the code for a few minutes, but then I actually looked at the test that was going to run, and saw that the list of words it was going to use was just a couple thousand words long. 🤔 I ran my program on this test case, and it spat out the answer in 1.5 seconds.

Unsatisfied. I grabbed this list of 10000 most common english words, and just under two hours later I had

spears
planet
easily
animal
relate
styles

to show for it.

So, anybody else think about or solve this one? Can any Java person try it and tell me if the book solution can handle the Unix words file? I believe that the question as originally posed isn’t possible, and not just because I couldn’t do it.

Been working on a couple projects this summer. The big one is a research fellowship in theoretical computer science - really interesting experience. Theory research is straight-up math - seeing if you can prove statements about how fast different things can be computed, coming up with algorithms, reading complicated papers. It’s hard to tell if I’m doing a good job, but the work is interesting for sure.

This other small project is a shot-for-shot remake of Shazam or SoundHound. Not an original idea at all, but I’m learning tons. Loosely following this post, but I’m rolling everything from scratch - wrote the FFT and everything. Check it out if you’re interested in that kind of thing - I’ll probably write a technical post about it once it works.

Moved into an apartment at the beginning of the summer, so I’m balancing all the tech stuff with cooking and cleaning, and watching tons of movies. Pretty nice quiet time.

Warning - this is a technical post

It’s been a super good break for me here in Salt Lake.

I got a Raspberry Pi for Christmas, and I’ve been constantly working on it. Since my other recent projects are in Swift, I felt like using it for a bigger GPIO project: a morse decoder/encoder.

Installing Swift on the RPi

This was, to be honest, the most difficult part of the project. At first when I looked into this, it wasn’t possible, because the Pi has an ARM processor instead of x86. But then I this tweet popped up on my timeline, and I got back to it. The next snag was related to Raspbian. I couldn’t get the package to work on the standard Raspberry Pi linux flavor, so I started over and installed a fresh Ubuntu image. Then the installation went smoothly.

Wrapping wiringPi in Swift

The Raspberry Pi has 40 GPIO pins that can be used for interacting with the outside world - people plug in things like temperature sensors or servo motors. My brother gave me the idea of writing a morse code system with an LED and a push-button. There’s a Python library for interacting with these pins programmatically, but writing Python doesn’t feel like gaining experience anymore. wiringPi is a C library with functions for getting input and output from the pins, which is perfect for wrapping in Swift. Figuring out which .o files I needed to link against was just a matter of adding until I didn’t get anymore compiler errors, and I ended up with this simple Makefile.

Writing the code

The encoder is easy: Just write a dictionary literal of morse code characters, run the input through that, and flash the LED for the right lengths of time. The decoder is tricky, and I still haven’t finished it because of some problems with my pushbutton. I’ve settled on the basic design of writing two functions that get the length of a press or a release, and passing control back and forth from them in a main update loop until a letter or word is finished. My buttons are a little unreliable right now, so I can’t really test this part until I do a little bit more hardware work to get the input right. I’m pretty sure the code will work as soon as the button does, so for now, I’m putting the project up on Github!

Today my first ever iOS app hit the app store!

Shorthand - Teachable Gesture Keyboard

Shorthand is a keyboard that lets you draw your most common phrases. You enter a phrase, then draw whatever symbol you want to represent those words, and the keyboard learns to tell your drawings apart.

For the curious, Shorthand uses an artificial neural network to “learn” the difference between the different gestures you give it. As such, it can be a little finnicky about when it does and doesn’t work. For best results, use gestures that are very different from each other: lower versus uppercase K would be really difficult for it the way it currently works, for example.

I’m excited to keep improving this and to take feedback from anyone who tries it out, this was a really fun project.