28 Aug 2016, 8:57

Word Rectangle

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.

26 Aug 2016, 1:04

What's new

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.

29 Dec 2015, 10:06

Raspberry Pi GPIO Projects in Swift

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!

03 Oct 2015, 5:23

It's up

Today my first ever iOS app hit the app store!

Shorthand Icon

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.

18 Sep 2015, 9:28

Debrief

I guess it’s really over now. This summer was really challenging, but I came out of it with a lot more knowledge and experience (working knowledge of three new programming languages, and a fruit fly’s olfactory system).

I think this school year’s going to be really good. Tougher classes, more responsibilities, and a 40” TV in my room for rewatching all of Breaking Bad, because stressful TV is the best stress relief.

22 Jun 2015, 10:11

Janelia

I’ve spent the past week at the Janelia Reseach Campus. It’s pretty nuts. All the labs are privately funded, so scientists here can work here on whatever they want without worrying about writing grants or any of the stupid stuff that’s happening. I’m getting a pretty sweet deal, with housing and food, and I’m on a neat coding project that’s right about at my skill level.

All of the other undergrads here for the summer are extremely cool, and a lot of them are international. Most of them do biology experiments, so they’re bound to the lab for longer hours than me. I’m not sure whether I should have more guilt or pleasure over being the one who sits around the house the most, but there’s only so long I can think in Python.

I want this summer to be a chance for me to correct some of the balances: work to play, watching to reading, reading to writing.

Hopefully by the end I’ll be ready to get back to proving theorems.

04 Mar 2015, 11:21

March Forth

When I was in fifth grade, my teacher introduced a fun history assignment with an example. She got up in front of the class and started talking in a deep voice. “My name is Infante Dom Henrique de Avis, Duke of Viseu, also known as Henry the Navigator. I explored much of the world outside of my native Portugal. I was born on March the Fourth of 1394, and I’ve always thought of my particular birthday as a sign from the heavens, that I ought to ‘March Forth,’ and never stop moving towards my destiny.”


I haven’t had much time lately, between schoolwork, The Office, and that new Robocraft game (now uninstalled). Overall, I can’t complain. I’d love to be able to do more, but right now I’m trying to remember that spending four years on a degree is an extremely valuable use of my time. And it could be much worse - I see a lot of people here who barely sleep during the week.

Yeah, everything’s coming up nicely. I’m getting really into my CS theory class, don’t really know what I’ll do when it’s over, but there’s always more cool classes to take! I just got some advice to take abstract algebra next year…

We’ll see.

21 Feb 2015, 5:39

Treat Day

So today I did some fun stuff.

A few people in my hall went to this really hip place for brunch. I had a Belgian waffle and it made me think about Bruges in Salt Lake. After that, I rode my bike and the train into East Hollywood and found a coffee shop, where I did some of my work for this weekend. I was probably the only one in there without any tattoos, and I was definitely the only one calculating eigenvalues.

After that I hit up The Last Bookstore, and then rode my bike up main street back to Union Station. I ran into what looked like a farmer’s market and Latin culture celebration. There was music and a bunch of kids asking their parents for knickknacks.

When I got up to the platform at Union station, I heard a guy telling someone that the next train to Pasadena would be there in five minutes. I caught a look at this guy’s face, and I saw that he was wearing a contact lens in one eye which, hand to god, had the LA Dodger’s logo on it. I ended up standing next to him on a super crowded train; I had to stand my bike up on one wheel to take up less space. After the train started moving, he took out a disposable razor, felt his cheeks (he was wearing a messy goatee), pressed the razor to his face, and dragged it down, dry. When the train stopped next, a tiny old woman got on, and he stood up, and called her over to take his seat: “Señora!”

15 Feb 2015, 10:40

Night Time

Tonight I went on a run with a few older students. It was later than I usually go out, and kinda dark. We saw three racooons, which is three more than I thought I shared this campus with. It’s cool, the things you can see that you wouldn’t have, if you do something even a tiny bit out of the ordinary and keep your eyes open.

I had an idea last night, which I didn’t write down. After some intense thought this afternoon, I remembered it, so I’ll keep you posted about that if it goes anywhere.

Mostly, routine. Work, sleep, think about things. Routine is good if you like what you’re doing, but I also try to reset every once in a while. Watching movies and old episodes of The Office, playing a couple games.

A guy down the hall gave me a vacuum-sealed package of pesto he made before going on sabbatical this term. I froze it, and for Valentine’s day we made pesto chicken pasta. Delicious! I can’t believe it took me a whole term to realize Trader Joe’s was four blocks away.

13 Feb 2015, 11:55

Reboot

Hello again!

I hope you all are doing splendidly. I think I am. There’s really so much to talk about, so let me hit the highlights.

Rang in the new year in my hometown, and it was a really nice break. Certainly get to miss my roots while I’m out here.

This term has been quite a bit tougher. I’m in what people say is the most difficult required computer science class, because it involves absolute zero coding. 100% proofs. I dig it, but the problem sets are so hard that I basically have to think about them from the moment they come out until the night before they’re due. Not a complaint; that’s what I’m here for.

A week ago I even went into LA for a show: My Brother, My Brother and Me. I took the train, which was nice enough, just took forever (I think the biggest problem with the transit in this region is that it’s such an unbelievable sprawl). There was a girl scout and her dad on the train, so I bought some thin mints. It was a totally great time, and exactly what I needed to get off campus for a night. It’s easy to get stifled here, to forget about the wider world.


I also wanted to show something off: My CS 1 final project. If the professor OKs it, it’ll be up on my github or just here, but regardless I’m going to brag about it, because I spent probably 30 hours on it and I earned this, dammit.

So it’s a game: that one where you take turns making lines in between dots and try to fill in as many boxes as possible. Here are some of the awesome features of my GUI:

  • Demo menu page where computer plays itself
  • Options for size of playing field
  • Randomized colors, not too dark or too close to each other
  • Three levels of computer skill (highest is really tough to beat)
  • Perfected, unbreakable user interface, with mouse and keyboard controls
  • Responsive design?! Sort of?! In the help screen. Against all odds, the graphics module we used isn’t really meant for that
  • Helpful insults for when you give it bad input
  • Hours of amazing gameplay
  • And more!

So that’s about the size of it. Having a good time. Excited about everything.

Until next time

05 Oct 2014, 5:13

Kayaking

So the Caltech Y offered a few trips on Saturday to celebrate the end of rotation and the beginning of the rest of our lives doing sets, and I went on the kayaking trip, which was a blast. It was sea kayaking, which I thought meant being out on open ocean with waves and sharks and everything, but in reality we were at Long Beach, CA, which is this kind of harbor town with a few canals. I guess you might call it a lagoon. Anyway, most everyone there had boats, or jet skis, and probably family money.

There weren’t any waves.

I was paddling along and this giant boat starts to pass me. It’s the kind with three tiers, the driver’s at the top and people can sunbathe on the second level, with, I don’t know, maybe a kitchenette on the lowest bit. The guy who was driving gave me a little wave, which I returned, but I thought about how an actual conversation between me and him would probably have gone…


Him: Hey man.

Me: Hey, so, I don’t know you at all and I don’t have much to go on to make this judgement, but based on the facts that you’re driving a three-tier boat called Rowdy and smoking an e-cigarette, we probably wouldn’t like each other too much, so maybe we should just quit while we’re ahead.

Him: Oh yeah you’re probably right. Bye.

Me: Bye.


Also, my TAs are amazing.

My physics TA is an old man who literally wrote the textbook, so you already know he’s one of the coolest human beings on the planet and also probably the literal most qualified person to teach this physics class. The other day he brought up these squids that propel themselves through the water by pushing water through their bodies, and we talked about that for a little while.

In math, we have this Chinese dude who is so very funny. He gives so much sass to anyone who asks him a question, and he also showed me this ridiculous proof that is like my new favorite thing. I’m putting it in spoiler tags because of how many of you will be so very bored.

Math

So this is an alternate way to prove that the sum of the first n consecutive numbers is (n + 1) choose 2.

First you construct a set called A and fill it with all the numbers up to n + 1. So A = {1, 2, 3, … n + 1}.

Then you make another set, called C. C is a subset of A x A, so it’s made up of ordered pairs (x, y), where x and y are both chosen from A, but there’s another condition: y > x. This means C is made up of all the ways to choose two distinct elements from A, and so the number of elements in C is equal to (n + 1) choose 2.

But we’re not done making sets! Next we need a set called Cj, where j is a member of A. We define Cj to be a subset of C, made of all of the elements of C where y = j. For example, C4 would be = {(1, 4), (2, 4), (3, 4)}. You can see that the number of elements in Cj is just equal to j - 1.

Futher, you can see that all of the Cjs are completely different: none of them could contain any shared elements. This means we can add all of them up to get the entirety of C without any overcounting! So the number of elements in each set Cj from j = 1 all the way up to j = n + 1 add up to be the number of elements in big C! And since the number of elements in each Cj are just the counting numbers 1, 2, 3, all the way up to n, we’ve proved that the sum of all those numbers is just (n + 1) choose 2!

Turns out, you can also generalize this to the sum of n choose k being equal to (n + 1) choose (k + 1), which is also super cool.

But there’s only like three people who might still be reading this because it’s not actually super cool in general.

Anyway, that has been #math.

If you wanted to hear about something else… Leave a comment? I know people think every web page should have comments now, but I think that tends to turn out pretty horribly.

This is not an open forum, not even for people I would want to hear from.

This is my place, and nobody but me should have the right to say whatever they want here.

Plus it’s faster as a static site and comments would be nuts to implement.

If you do want to reach me I suggest Twitter or a telephone.

29 Sep 2014, 8:45

Update

“It’s not a normal place.”


I’ve been settling into Caltech for the past week or so now. It’s insane.

I spent the first couple days at what they call “Frosh Camp” (I’m not super into this phrasing because it sounds awful) which is when they take all of the Caltech incoming freshmen and take us to a hotel on Ventura Beach, where we get shuttled between all kinds of panels and discussions, and we learn about problem sets and how much soul-crushing work this place is. At least there was plenty of time to swim in the ocean.

In the days since we got back, we’ve had rotation dinners every night. At Caltech there are eight on-campus houses, and the process for sorting all of the incoming freshmen into them is pretty absurd. A lot of people have compared it to the houses at Hogwarts, which I think is correct only inasmuch as this place is a ridiculous fantasy land for most people. Basically you have dinner and dessert at all of the houses over the course of two weeks to get a feel for what they’re all like (really it’s only enough time to form a one-word stereotype [ie jocks, freaks]). Each house has also been putting on rotation events, ranging from paint-dodgeball to capture the flag to board games and boba. It’s been a crazy balancing act of meeting as many people as possible and optimizing which names you actually think you’ll need to remember.

There’s also a weird culture of secrecy around rotation. In order for us to get a better idea of what each house is like, the upperclassmen can’t color our opinions, say, by giving a one-word stereotype of each house. Everyone is so afraid of breaking rotation rules that they’ll barely talk about their own experiences with their house.

Everyone says the workload is going to be nuts. I had my first few classes today, and so far it doesn’t seem too bad. The math problems are pretty intense, and the chemistry is taking a really long time. But you probably don’t care about that.


A couple days after I told the people at work that I was going to Caltech, one of them came in trying not to laugh.

“Noah, I’m not sure I should tell you this, but I found out the woman who mucks out my horse stalls is a Caltech graduate.”

She went on to tell me it was a choice this woman had made and she also tutors kids in math. They talked a little bit about the school. The graduate started by saying “It’s not a normal place.” I have to say I completely agree.

16 Sep 2014, 8:54

APIs

Worked with a couple of REST APIs today. Twitter and Trello, more specifically. Pretty cool stuff. The best tutorial I found was in Ruby, so I had to learn a bit of that.

I like Ruby.

I talked to Nathaniel about all this, and he told me why he hates authentication tokens.

Turns out.

Twitter’s API has some very specific terms related to who gets how many API tokens and for what purpose. Basically, they have an “open” API, which means it’s open to anyone who doesn’t want to compete too seriously with Twitter.

applications that attempt to replicate Twitter’s core user experience (as described in Section I.5 below) will need our permission to have more than 100,000 user tokens and are subject to additional terms.

What this means is I can’t use Nat’s favorite third party Twitter client, because they are out of keys.

Scary, unregulated world out there. Social networks kind of breed monopolies because of exponential growth or something.

15 Sep 2014, 9:15

Minecraft

Well, it’s been a good run I guess.

I played Minecraft a little bit right after it was released. It’s quite a game, isn’t it? There’s really nothing I can say about the game itself that hasn’t already been said a thousand times.

I don’t enjoy playing Minecraft as much as everyone else seems to, but I’m truly sorry to see it fall into the hands of a company that will probably move to take it away from the vibrant community of modders and server admins to squeeze more money out of kids who would rather buy skins than paint their own texture pack.

I guess it mostly seems like another way to move us users away from production and towards consumption, a way to reduce our involvement with the things we love as anything other than wallets shaped like people.

Would it be cynical to ask if this is the intention?

14 Sep 2014, 7:59

Limbo

So I’m moving on Friday.

Yes, I’m quite excited.

For now, though, I’m in a weird kind of limbo.

The thing I’ve realized is, life (in the West at least) seems to be based on creating attachments. You become attached to your job, your school, your friends and your hobbies. If you’re like me, you’re attached to a phone, a computer, and a TV show or two. It’s all about getting more and more attached to a specific way of life. That’s why everyone says that moving is one of the most traumatic things a person can go through: because you have all of these uprooted attachments.

It’s okay though.

I can make new attachments.

That’s why I’m not Buddhist.

12 Sep 2014, 10:34

Organizational Tools

I’ve spent the last few weeks of pre-move limbo creating an organizational framework that I’m really, really proud of.

disclaimer: none of this is tested yet with an actual workload. I’ll update when I actually have classes, homework, etc.

The central organizational tool in my new system is a Google Calendar. It lists all of the events in my life, whether that’s a lecture, a meeting, or a party. Now, your standard calendar isn’t exactly great as a to-do list with due dates. That’s where the next tool comes in: Trello. Trello is incredible. It’s super versatile: It can be as complicated or as simple and easy-to-use as you want it to be. I have Trello boards for all of the kinds of stuff in my life. I have one for all the movies and books I hear about, I have one for all of the writing projects I’m working on, I have one for the homework on my plate right now (empty for a couple more weeks). But I should explain exactly what Trello is.

Simply put, it’s a way to organize stuff. Every board has lists, which have cards, which can have anything from a due date to a checklist to a file attachment. It’s really easy to move cards from list to list: Whenever I watch a movie that’s on the to-watch list I move it to the three, four, or five star list. This is a totally pointless exercise but it shows that Trello is just fun to use, and it makes me want to use it for as many things as possible.

So what I’m imagining is this scenario:

I’m sitting in class and the professor lets me know about an upcoming assignment. I pull up Trello on my phone or web browser and immediately add a card to that class’s list on the homework board and add the due date. When I finish that assignment, I move the card over to the done list, because it’s done, you know.

Now here comes the real coolness. Over in the menu, there’re these things called Power-Ups. The calendar Power-Up is basically the best thing ever. What this does is it makes a calendar populated with the due dates of all of your cards. It also generates a webcal URL for this calendar. So what I’ve done is to point the calendar app on my phone and laptop to the Trello calendar of my homework board. This means in addition to seeing all of my obligations on the calendar, I see everything’s due dates.

So now I can see all of my free time in the week, provided of course that I’ve diligently mapped my schedule onto the calendar. The next step is to block out exactly what part of that time is going to be spent on which work, which I also do in the calendar. I can do this with full knowledge of all of my responsibilities and due dates, so I don’t overcommit myself. I expect that eventually I’ll have a good idea of how long everything takes, and I’ll be able to manage my time well enough to get my 8-hour average of sleep every night.

We’ll see how this goes.

11 Sep 2014, 6:12

The First One

So here we are.

A little while ago my dad started rebuilding his website with this thing Hugo. He was super excited about it. He has thousands of posts and it still builds his site in fractions of a second.

Around the same time, Bryan at work pointed out that I needed a place to put a sort of portfolio of the cool stuff I’ve made. (That’ll all be here when I really understand how to make websites.)

So I started checking out Hugo and it sounded really sweet. Not only was it fast, but it relied on Markdown, which I immediately loved. When I got sick of playing around with the Markdown dingus, I decided to build a site.

After an unbelievable amount of repository cloning, a visit to Hover, and a couple passes over the Markdown syntax, this happened.

So here we are.