My Brainf Quine

A quine, a program that’s output is it’s own exact input is a rite-of-passage for an engineering afficianado. For those that consider ourselves one level above afficianado we always are looking to up the ante. I took two years off after high school, and remember them fondly. I could read wikipedia all day, program anything I wanted, explore freely.

It’s a magical place to be in, when you any path seems possible and nothing seems mandatory. It’s a time when our world-view is fully open, and interesting possibilities seem everywhere. It’s a time before we get overwhelmed by so many obligatory minutiae (cable bill, health insurance, change my oil, arrange my 401k, excercise more, sleep more, read more, relax more, pickup groceries, return that item, answer those emails to those family members) that we find ourselves overwhelmed and instead of branching out we try to reduce our world. It’s a time before we filter our world into a functional place of checklists and routines to optimize staying afloat, a time when we are so unencumbered that we needn’t even ration our attention or time, and thus can float through the trivial obstacles (traffic, distractions, unforeseen obligations) of life with an interest in these new challenges rather than a resentment at a ceaseless set of obligations.

Anyways, I reminisce. But back in that era, one thing my friends and I would do is make coding challenges for each other. After a friend introduced me to “brainfuck,” a language with only 6 commands all represented as single characters, I challenged him to write a quine in brainfuck. I can see by googling that many other people like us are out there, who, like us, have been to that place where we are hungry for the next challenge to create for ourselves.

Recently I found my quine from back then it brought back memories.




Sopping Wet — Today’s Software Ecosystem Isn’t DRY [and nobody seems to understand or care]

Tl; Dr:

  • Everyone seems to understand DRY is good at the program level, but they don’t seem to understand it at the community level.
  • Examples of useless duplication include many programming languages, libraries, package managers, data-stores, tools
  • This community duplication reduces interoperability and slows productivity across the board

Section 1: Some examples

1. Why is there more than one unix/linux package manager? Do we really need a different package manager with the same commands but renamed for each programming language? Do we really need a distinct package manager for each distro? Rhetorical question — No. We don’t.

2. Nobody seems to admit it, but Php, Ruby, Python, and Javascript are the same language, with a little sugar added here or there and different libraries.  I’m okay if not everybody wants to use curly braces but would rather indent for typing, but I’m not okay with every library for every functionality (date parsing, database connectivity, html parsing, regex, etc) being rewritten as a distinct library for every language when those languages have almost no significant differences.

This leads to a scenario where “learning a language” is more about learning the library than anything else (e.g. “How do timezones work again in PHP?”)

3. MongoDB never should have existedMongoDB should be a storage engine. The concept of a datastore that adapts its schema on-the-fly and drops relations for speed is okay, but there’s no reason the entire data-storage technology has to be reinvented to allow this. There’s no reason the entire query syntax has to be reinvented. There’s no reason the security policy has to be reinvented and all the DB drivers. There’s no reason all the tools to get visibility (sql pro) and backup the database need to be reinvented. Plus, if it were just a storage engine, migrating tables to InnoDB would be easier.

The same point holds for cassandra (which is basically mysql with sharding built in), elastic search, and even kafka (basically just WAL of mysql without columns). For example, a kafka topic could be seen as a table with the columns: offset, value. Remember storage engines can process different variations on SQL to handle any special functionality or performance characteristics as-needed.

4. Overly-specialized technologies should not exist (unless built directly around a general technology). You ever see a fancy dinner-set, where for “convenience” people are offered 5 forks and spoons, each one meant to be used slightly differently for a slightly different task? That’s how I feel about overly-specialized technologies. For example, people seem to love job queues. All job queues should be built on top of a SQL backend so that engineers get the normal benefits

  1. engineers know how to diagnose the system if it fails because it’s a common one (e.g. performance issues, permissions)
  2. engineers can always query the system to see what’s happening because it’s using a standardized query language
  3. engineers can modify the system if necessary because it provides visibility into its workings
  4. engineers can use existing backup, replication, and other technologies to store/distribute the queue (giving interoperability)

Section 2: What’s the result of all this?

  • Senior Engineers are all set back years relative to junior ones (which is bad for senior engineers, good for junior engineers)
  • The ecosystem is set back as a whole (all tools, libraries that interact with the old technology are rebuilt for the new one)
  • The company is placed in a precarious position because it now only has junior engineers in the given technology. Did I tell you that time the place I worked accidentally lost most of their customers phone numbers, because their PHP driver for mongo would convert numeric strings to numbers, and phone numbers would overflow the default integer, resulting in no fatal errors but simply negative phone numbers?
  • The company runs the risk of being saddled with a technology that will be dropped (e.g. couchdb, backbone) and will require a rewrite back to a standard technology or be perceived as behind-the-times.
  • Slow-learning / part-time engineers must keep pace with the changing landscape or face irrelevance. Those that can’t learn 10 technologies a year (a storage technology, a build tool, a package manager, a scripting language, data-monitoring tool, 2 infrastructure tools,  5 libraries, etc) will stumble.
  • Fast paced-engineers will lose half of their learning capacity on trivialities and gotchas of each technology’s idiosyncrasies (e.g. why can’t apache configs and nginx configs bare any resemblance to each other?). Once these technologies are phased out, all of that memorization is for naught. It’s a treadmill effect – engineers have to sprint (keep learning new technologies) to move forward at all, walk just to stay in place, and if you can’t keep pace with the treadmill you get thrown off the machine.


Section 3: The exceptions

There are a few exceptions I can think of when a complete rebuild from scratch was an improvement. One would be Git. In a few months, one of the most prominent software geniuses of our era invented a source-control system so superior to everything else that it has been adopted universally in a few years, despite the intimidating interface.

The times a rebuild is justified seem to be when many of these criteria apply:

  • You’re a known and well-respected name that people trust so much the community might standardize on what you make (e.g. Linus Torvalds, Google)
  • The existing systems are all awful in fundamental ways, not simple in easily-patchable ways. You’ve got the ability, time [and we’re talking at least a decade of support], money to dedicate yourself to this project (git, aws, gmail, jquery in 2006)
  • You can make your system backward compatible (e.g. C++ allows C, C allows assembler, Scala allows Java, many game systems and storage devices can read previous-generation media) and thus can reuse existing knowledge, libraries, and tools
  • You’re so smart and not-average that your system isn’t going to have the myriad of unanticipated flaws that most software systems you want to replace will. For example, angular, backbone, nosql, are all community fails. I theorize Go, Clojure, Haskell, Ruby, and several other high-buzz languages will evaporate.
  • Your system is already built-in-to or easily-integrated-with existing systems (e.g. JSON being interpretable in all browsers automatically, moving your service to the web where it will work cross-platform and be accessible without installation)

Section 4: What can one do?

  1. Learn the technologies that have stood the test of time: linux cli, c++/java, javascript, sql
  2. Wait years before adopting a technology in professional use for a major use-case– let other companies be the guinea pig
  3. Roll your eyes the next time somebody tells you about a new sexy technology. For whatever reason, it’s culturally “cool” to know about the “next big thing,” but professionals need to rise above such fads
  4. Next time you have a brilliant idea, instead of thinking “How great it would be if the entire dev ecosystem adapted itself to use my invention” think “Is there any open-source project out there that can be minimally adapted to accomplish my goal?”

Our obligation as leadership

The talk of importance of values is one irony of the San Francisco scene, if not human nature. The same values are discussed everywhere; so why then is it that these same values seem to be applied nowhere?

Could it simply be that it’s much easier to see the mistakes of others than our own? Perhaps those of us in positions of power often subjected to less scrutiny? Yes, to both of these. And so it becomes our own greatest personal challenge to remain true to our goals when nobody else is checking.

Let’s consider the value of ownership. What does this mean for us? It’s easy to look at the engineers who report to us and think about the times they didn’t take a personal investment in what they were doing, and how that harmed the company.

But for us to be good at our job, we must challenge ourselves to hold ownership, because it’s rare somebody will tell us when we’re not.

So what does ownership actually mean? Well, if an engineer is taking ownership of a project that to me means that she takes personal and emotional accountability for doing the best feasible job she can at it. If it’s broken on production, she is treating the lost revenue like her own.

But what does ownership look like in a manager? To me ownership is no less of an obligation. In fact we have more obligation because we have more influence. We should hold ourselves personally accountable for accurately assessing the merits of our direct reports. If a great manager screws up, he should lay awake at night until he fixes it, just as a great engineer would wake up to fix a production issue. A great manager won’t “good enough” it and wait until the next review cycle to compensate. Us not admitting to an error to save face is no less excusable than an engineer covering up when he breaks the app (which is to say absolutely inexcusable).

Ownership is about caring about the job getting done correctly, at a core level, above-and-beyond what is immediately asked of you. If you see a problem that nobody else sees, ownership is taking it up and ensuring that it gets resolved, regardless of how it reflects on you. Ownership is helping the company and the customer, even if it costs you your job (be that whistle-blowing, disagreeing with an incorrect authority, refusing to do something immoral/illegal).

If you institute an initiative that is clearly ineffective, then you should admit it and withdraw the initiative. Your self-promotion is not a contribution to the company. If you are a great manager, you won’t make it your direct reports’ job to convince you they are great; you will make it your job, your contribution to ensure everyone beneath you is being used to the best of their ability. And if your manager is great, she won’t expect you bring donuts, wear a tie, show up early, or flatter; because it will be her contribution to the company to accurately evaluate your work (and not how much she loves or hates you).

And if, when you hear this, you find it mildly irritating that anybody would ask so much of you… then don’t be surprised when those you lead act as do and not as you say. Your attitude is the irony of the SF tech scene.

Connect 4 – illustration of Matrix rotation in js

Once in an interview, I was asked to determine whether a somewhat filled in connect 4 board has a winner. Here’s an elegant solution using an arbitrary rotation function: Rotate the board 0°, 45°, 90°, 135°, and check for 4 in a row in each of those rotations.

Since I couldn’t find a good rotation solution online I decided to post a solution here (javascript):

var _ = require('underscore');

var rotateArray = function(array, degrees) {
    var radians = degrees * Math.PI / 180;
    var round = (f=>parseFloat(f.toFixed(13)));
    var coordinates = _.flatten(,y) =>,x)=>({value,x,y}))));
    var translatedCoordinates =>({value: spot.value, x: round(spot.x*Math.cos(radians) - spot.y*Math.sin(radians)), y: round(spot.x*Math.sin(radians) + spot.y* Math.cos(radians)) }))
    var rows = _.chain(translatedCoordinates).groupBy(x=>x.y).values().sortBy(x=>parseFloat(x[0].y)).value();

var hasFourInRow = function(array){
    var vectors = [0, 45, 90, 135];
    var matrixToString = (m => (>r.join("")).join("\n")));
    var versions = => rotateArray(array, degrees)).map(matrixToString);
    return _.any(versions,(b=>b.indexOf("****")!==-1));

And to illustrate the use, here’s sample test cases:

var testCases = function(){
    var win1 = [['*','*','*','*'],
                [' ',' ',' ',' '],
                [' ',' ',' ',' '],
                [' ',' ',' ',' ']];
    var win2 = [['*',' ',' ',' '],
                ['*',' ',' ',' '],
                ['*',' ',' ',' '],
                ['*',' ',' ',' ']];
    var win3 = [['*',' ',' ',' '],
                [' ','*',' ',' '],
                [' ',' ','*',' '],
                [' ',' ',' ','*']];
    var win4 = [[' ',' ',' ','*'],
                [' ',' ','*',' '],
                [' ','*',' ',' '],
                ['*',' ',' ',' ']];
    var lose1 = [['*','*','*',' '],
                 ['*',' ','*','*'],
                 [' ','*','*','*'],
                 ['*','*',' ','*']];

    console.log([win1,win2,win3,win4, lose1].map(hasFourInRow));
    //outputs true, true, true, true, false


Stories, and Meaning [at work]

Tl; Dr: All people are motivated by meaning of their work. The ability to shape the “stories” that we tell ourselves gives meaning and thus is an essential motivational tool. This meaning is also key for personal satisfaction.

Let’s consider a standard engineer. There are a lot of “outlooks” this engineer might have. I’ll go over 5 out of thousands of possibilities just to illustrate some variety:

  • I’m the star engineer here, and I’ll turn this place around. Others might not quite see it yet, but it’s only a matter of time.
  • I’m a great engineer but nobody appreciates my work. How come that other engineer got promoted, I don’t think their work is as good as mine. I should run the company, the CEO is only CEO because he has blue-blood 1% investor friends. The world is rigged against me.
  • I’m so excited to be an engineer. I earn multiple times the median household income and I get perks too, while my other friends are still paying off their college debt.
  • Work’s good. It’s just a job though.
  • Why am I always the one under pressure? Nobody ever thanks me no matter how hard I work. Why do I get mistreated? I’m such a victim. It’s not right.

What I’m proposing is that the same engineer having the same experiences could retell that same experience in any of the ways I listed above.

In fact, you’ll find that a lot of people gravitate towards common narratives. I have a friend, let’s call him Fry who always sees the same story: The big guy is mistreating the little guy. One thing I learned quickly was that he liked and actively chooses (if not entirely consciously) to see the world in these terms. And if I want his help, I can motivate him by giving him a rebel story he can play a part in.

For example, if I’m trying to create a new tool, I could tell it in a way that plays up the opposition, especially if it’s an entrenched “senior” group that’s cautious about new ideas, and it’ll make him want to help.

Everybody has a narrative or two that resonates with them. I have another coworker, Bender, who always promotes the story: People are stupid. I know not to try to change his story, because it’s a choice and likely inspired by some very frustrating life experience (I imagine those frustrations are valid, albeit rather long-lived). If I need him on a PR I can ask it in a way that implies I need his expertise. That way he act can out his fantasy of undoing the damage of incompetent/indifferent through the act of improving my code. A win/win.

Sometimes these narratives are just plain counterproductive. I can think of experiences when teammates were annoyed that some “undeserving” party “stole credit.” In these situations you can try to rewrite the narrative, though it takes a certain skill. One way to accomplish this is to bring up an opposing narrative like, “Yeah so his name was mentioned in a meeting big deal… I don’t do great work so some manager can mention my name, I do it because there are literally millions of users who are experiencing what I make and I think I’m lucky to be able to be in a position to help so many people. That’s something I can be proud of.” [And as an aside their is no duplicity in this. It is our choice whether to aim to “do good” or to accrue material. Each philosophy has its upsides.]

And the fact that people are choosing to live these stories is an important fact. For a long time, I would have thought doing this type of thing was “manipulative” or “tricking” people into work when I could instead explain to them why their underlying narrative was too black&white. But knowing that these narratives are choices, with symbolic importance, that give meaning to the individual who holds them, I see now that people choose to live these stories hoping to “play them out.”

And most importantly, we all have narratives. Mastering other peoples narratives is a great tool, but mastering your own is probably more important.


Part 2.

If you’re a leader in an organization, you need to be aware of the stories that occupy the minds you oversee. Do people see themselves as battling each other for recognition? Do they see themselves as allies against a great evil? Do they see themselves as victims of your rule?

People within the company all have their narratives, and those attitudes are contagious. Your actions will have a great role in deciding which attitude wins out.

I’ve seen organizations torn apart by leaders who were out-of-touch with the effects of their actions. The cultural effects you have are of supreme importance. Actions like requiring engineers start an hour earlier, for example, are incredibly dangerous, because they give room for the narrative “We are seen as code monkeys” to thrive.

To win this battle you must understand the narratives that you are battling against. You must truly understand them, you must know and appreciate the day-to-day of your workers. For example, you must know that your Office Manager Lela is frustrated, sleep-deprived, is wondering where her life is going, and is starting to feel like the “manager” in her title is meaningless. When you know the people you work with you’ll know what stories are compelling to them. When you understand, you will be capable of offering the service of arming them with a better story, a brighter story, a more compelling story. Because as bad as Lela’s life is, it’s better for everyone if she feels like her work matters at the end of the day.

This is your value.

The Professional Web Codebase

One of the major advantages of the high career mobility in SF … Cross pollination. Yet each new codebase I comes to seems to lack a few of the following. So I figured I’d list out the essentials that every web codebase should have.

  1. The Obvious: Git, IDE, MV*, relational DB, 3 environments that match production.
  2. Language regularization:Each language has its own idiosyncrasies. Learn your languages weakness and make helper functions to accommodate. In PHP, these weaknesses include single-threaded, bad undefined index default behavior.My preferred solution to PHP’s single-threaded limitations is to make use of a job queue. This will emulate additional threads for heavy tasks (e.g. sending emails to all of your user base) or high-latency tasks that ideally should be asynchronous (e.g. certain API calls). I’ve seen this done well, and I’ve seen it done poorly. From experience, I’d point out the following lessons: don’t use a message queue as a job queue and the DB is a great place to store a home-grown job queue [because it provides great visibility, resilience, can be controlled programatically, can be exported to disk, is atomic, etc].

    In PHP, out-of-bound reads on arrays return null and log a notification to the event log. As this is never the engineer’s intent, I always write two helper functions. One that looks up an key and returns a specific value if the key isn’t found (for cases where you’re using the array as a set). The other function looks up the key and returns an exception if the key is not found (for normal cases where the key should always be present).

    I strongly believe once you handle these edge cases most popular languages are pretty interchangeable (javascript, java, php, python, ruby).

  3. A powerful, generic staging environmentOne of the most impressive and useful technologies I saw was something we called humblebrag. It was a script that caught all requests to *…. It then took the *, checked-out the corresponding git branch, and mapped the request to that particular branch. Thus in effect, we had a zero-effort way to have all branches usable simultaneously on a single server, even by non-engineers.Doing this can be a little harder in more complex environments with versioned services listening on ports, if you don’t plan for it early.
  4. A circuit breaker. Download one from github.
  5. An ability to do cross-server mutexes.
  6. A simple, generic read-through-caching function.
  7. A powerful logging system connected to an alerting system
  8. An A/B test system. Even if you’re not doing A/B tests on user-experience, it can be a great way to rollout to a small portion of users or internal-testers to ensure stability on a new environment.



Understanding engineers by understanding authors

I’ve written before about the challenge it can be for non-engineers to understand engineering work. I’m not the the first to observe that the non-technical need a metaphor to understand invisible and often abstract output an engineer creates. Traditionally, that metaphor has been physical engineering/construction. Others have already, and rightly, criticized the physical labor metaphor.

Instead of ridiculing the wrong metaphor, I offer a substitute. I posit this: To understand engineers, think of them like writers.

to understand engineers, think of them like writers.

Why is this a good analogy? It explains several aspects about engineering that otherwise seem downright unreasonable.

  1. Emotional attachment to work
    Like an author, many engineers see a work project as an opportunity to exercise their creativity and build something the take pride in. Like an author, engineers develop a sense of owning what they create. If the project gets cancelled, handed-off, or drastically changed (especially without notice), compromising their artistic vision, the engineer may experience frustration. But this is natural, how would an author feel in such situations?
  2. Difficulty in measuring progress and estimation.
    If software were physical construction, it might be reasonable to have an easily-predictable timeline. One might confidently answer “how far along are we?” But like writing, and unlike construction, everything one makes in software is new. And like writing, progress can’t merely be measured in the amount typed, refinement and reduction are actually an important and lengthy part of the process.
  3. Ambiguity and subjectivity of excellence
    Every week somebody writes a blog post on how to find out in an interview who’s a good engineer. And every week it gets (rightly) torn to pieces by commentators. The fact of the matter is that there are many independent components that comprise engineering talent and measuring them is very difficult. Even among the very best stylistic difference might mean two greats may not appreciate each others’ virtues, like Faulkner and Hemmingway.
  4. Challenges of collaboration
    And on that note, collaborating can be hard. Like writing, there are an indeterminate number of ways to write software, but each engineer has a style. I can tell you from personal experience that writing software with other people is hardBoth want a sense of ownership and freedom to express their creativity, but must now answer to the confines of the project itself as well as their partner (or team’s) creation. Imagine a group of professional writers trying to work together, of varying cultures, varying talents, varying dispositions, and varying skill-levels. With no objective answer to many issues, engineers reviewing one another’s code is a touchy topic.
  5. A need for freedom
    As a creative endeavor, software’s workflow can be unpredictable. A creative solution may come at any moment, often in the shower or a dream. Sometimes, when all the factors align, answers comes pouring out at a great pace. During such times, the absolute worst thing that could happen would be an interruption (or a required meeting). Compromising on artistic process will compromise the product.
  6. It’s not work
    One of the most persistent and most damaging misunderstandings I have witnessed is the erroneous perception that engineers will avoid work if they can “get away with it.” Perhaps those who feel this way think of engineering as labor, as if it were physical construction. But writing code, like other writing, is a passion that cannot be avoided. When I go on vacation from work I always end up recreationally writing code within a week. I can’t generalize for every engineer, nor every project. Like a writer, if an engineer really doesn’t believe in her work for moral reasons or is so constrained she has no space for creativity then she may lose motivation.
  7. Can we rewrite?
    Another commonality is that due to stylistic differences, every individual prefers their own way of writing things. (And to be clear, in software there is a lot of room for styles, styles that are often so unique that one can often tell who wrote code just by reading it). Each considers her own style clearer, cleaner, or better; often because it aligns so directly with her own thought process. Learning to compromise on this a key skill.
  8. Some produce more than 10 times another
    Is there any number of E.L. James that could produce the Great Gatsby? For specialized work (e.g. advanced problem solving, revolutionary user experiences) there’s just no substitute for a prodigy. On the other hand, if what you’re making is the software equivalent of a gossip magazine, having Shakespeare on your team might actually be a recipe for failure.

I want it to be clear that I’m not saying all engineers automatically deserve to have any project that they work on adapted to conform to their artistic whims. I am advising all to be sensitive to the pride and passion that people put into work.

But most of all I’m trying to help people understand engineers. It can be hard to relate to an engineer who expresses slight negativity about meetings, blows off people who check-in on them, never knows how long their work will take, doesn’t like standard schedules, might prefer to work alone, gets disappointed when their work is shifted, or thinks they’re amazing. So if you care to understand and relate, I’ve given you the tools.

Select vignettes of a tech company

Underneath the “machine” of an engineering company is ultimately emotions. I’ve selected a few vignettes I think most engineers could relate to that highlight common themes of misunderstanding in software engineering.

  • Thinking to motivate people, an executive names a select employee for an award. One employee gets motivated, the rest get demotivated
  • Eager to prove his place a product owner fantasizes about his project that will prove him great like his idol, Steve Jobs. When talking to his team about his product he patiently listens through their objections before ignoring their opinions and making proceeding with his initial plan. The rest of the team no longer feels like this project is a good outlet for personal creativity (since their input gets ignored) and withdraws.
    [This exact same behavior is done just as much by engineers who are equally prone to wanting to take full control of a project]
  • A manager picks an employee who’s already been labeled as a “problem,” and decides to prove they can turn the situation around. The manager gets increasingly involved with day-to-day decisions of the engineer suspecting it will force the engineer to work harder. The engineer, who’s just as likely to be as good as any other engineer, then comes to resent the manager at a personal level, to see treatment as inhumane, and refuses on principal to participate with the tactics. One of the two, and not too unusually both, get fired.
  • Seeking to engage with engineers a manager tries to have a conversation about a project. Bringing up, “firing on all cylinders,” “endzone,” “deliverables,” and “grand slams.” Having no interest in cars, football, or baseball (nor analogies for that matter) engineer gets a sense the person he’s talking to couldn’t ever understand him.
  • Manager wants to present an air of knowing, so pretends to understand things he does not, and honestly could not. His direct reports immediately pick up on this and lose respect for him. Nonetheless they are patient and respectful to his face.
  • Blindly mimicking the culture of management, a manager refers to Sally as a “resource.” With this analogy material resource manager encourages his tendency to think of engineers as fungible. Also, Sally  now hates this manager guy who keeps objectifying her!
  • Seeking to create an objective way to numerically rank candidates and assign bonuses, a 360 review process is put into place. Immediately friends give each other great scores.

All unfortunate situations.

Disclaimer: none of these are inspired by employers past nor present.

Solving rush-hour

For those who’ve been inspired by last programming challenge, I thought I’d give annotations on a programming exercise I’ve created.

The challenge: code an AI to solve Rush Hour, you can play Rush Hour online if you aren’t familiar with how the game works. If you want to follow along, you can find my solution on github.

The game of Rush Hour
The game of Rush Hour(tm) – The objective is to get the red car to the exit. The above picture illustrates one possible board.

Let me start with the high-level thought process.

How to solve it?

The most naive approach is a brute-force solution, trying every move, filtering out backtracking. Some simple math will let us rule this possibility in or out.

The only state in Rush Hour the positions of the cars. Thus the number of possible game states is equal to the number of possible arrangements of cars. We can approximate an upper bound of the latter by multiplying the number of possible spaces each car could move to (this ignores cars being on top of each other, hence upper-bound). In the above board we see 8 vehicles, and each vehicle can only ever occupy 4 or 5 squares [they can’t turn ever] depending if their size). Some boards have more vehicles, so if we estimate 10 vehicles at 5 positions that’s 5^10 < 10 million.  So yes, brute force is in.

The general solution:

Because “brute force” is such a general mechanism, there really is a lot of reusable code in the solution. In my solution I’ve pulled out the reusable logic into genericSearch.js. The idea is that a whole host of puzzles follow the same form: Given an Initial state try to get to End State.

The docblock below is the interface to genericSearch that is used by the solver, but this same search function could be used by any number of puzzles (triangle peg game, sudoku, etc).

Any brute-force can be represented with only these params.

Thus, to write the program (after having written genericSearch.js) all I must do is to make those 5 parameters [and any helpers to go along].

Initial state – Brain Dead Simple

I know a lot of engineers who would be tempted to represent the game of rush hour with at least a half dozen classes (“so we have vehicle base class, which has car or truck subclasses, and we’d need a class for the board and legal moves”).

And that is a valid way to go about it. I went with a minimalist solution– a nested array 36 characters. Brain dead simple.




It seems that perfection is attained, not when there is nothing more to add, but when there is nothing more to take away. — Antoine de Saint Exupéry

Because every car is at least 2 in size, this string notation suffices to convey both the position and bearing of vehicles, everything we need. Since the exit is always in the same spot, that needn’t be represented in state. Adjacent characters of the same value represent the same car.

We have our first parameter, initial state. However, we have skimped in our state, by not defining what a vehicle is or orientation in the state object we’ll have to define that logic later.

Some of the advantages of representing the board state as an array of characters:

  • It’s trivial to serialize. Serialization is key to making sure we don’t backtrack when searching for solutions.
  • It’s very easy to input.
  • It’s very easy to output and debug. At the end to see the solution found I can simply “play” the states and watch the characters move.
  • At any given moment it’s trivial to determine if a space is vacant of any vehicles.
  • Certain impossible board-states are prevented automatically (e.g. a misconfigured initial state could not result in overlapping vehicles).

Some of the disadvantages:

  • We must determine every car on the board and which direction it’s facing. This is non-trivial (let’s call “trivial” something that I code correctly on my first try).
  • Moving a vehicle is kind of “dirty.” By moving vehicles by overwriting the board state it’d be easy make bugs that create weird board states (vehicle with size one).
  • Certain impossible board-states are prevented automatically (e.g. a misconfigured board state could not result in a vehicle with no bearing)
Parameter 2 – Possible moves

Each vehicle may move forward, or backward (assuming its path is unobstructed). To keep things simple, we can say a vehicle can only move 1 square at a time and represent longer travels as multiple moves.

Get all possible moves from this state
Get all possible moves from this state

This definition introduces a few more functions (getVehicles, canGoForward, canGoBackward), which I won’t put into the post. See the full code for that. The reason I exclude them is because I don’t have any particularly elegant solution to those tasks.

Parameter 3 – Apply move

Again I have no magic to work on this one so I won’t show the 15 lines. In fact, it feels like the least dry piece of the code to me, and it makes me want to refactor the most. The number of occurrences of -1 are too numerous (6) and speak to casual coding.

So don’t get me wrong, I don’t want to say anybody should hold this code up as an amazing example of good code. What I hoped to illustrate is how a problem that seems daunting can actually be broken down into 19 functions, the longest being 23 lines.

The Gimmes

I have two functions left. One is how to uniquely represent the state as a string. The other is win condition. The former is easy: JSON.stringify. The latter is easy as well.


And we’re done! Now I’ve left our the genericSearch.js, which honestly was perhaps the most fun, but this post is long enough. If your thirst isn’t quenched try playing around with it yourself.

  • Keep the pure & reusable code in a separate file (or separate function) from your 1-time, implementation-dependent code
  • Maybe 2 classes would have come in handy. Despite being small, the code doesn’t seem as friendly as I’d want. If I had kept state as an object of objects I would never have to define string -> state mapping.
  • Unit tests would have been a good way to allow such a refactoring to be less painful.

Don’t be an Architecture Hipster – A guide

One of my more popular HN comments was a teardown of an all-too-common engineering subculture. The article in question sought to teach “Software Architecture,” but ultimately annoyed me and many other HN readers.

Tl; dr:
Software architecture discussions are so polluted by software-hipsters that the majority of software engineers are disinclined to discuss and study architecture at all.

Know-it-all / hipster

  • Probably studied philosophy, english, film-studies, or engineering.
  • Lurks around discussions, hoping to overhear a mistake, any mistake. 
  • Uses an unnecessarily complex vocabulary
  • Has a self-righteous and loud tone of voice, especially when correcting people.
  • Enjoys correcting people, even on minor/irrelevant points.
  • If asked him a question you can be sure of two things:
    1) he will never admit he doesn’t know
    2) he will answer with so many niche terms that you will end up more confused than when you began
  • He may be likened to Dwight Shrute, or the comic-book guy.

Architecture  Hipster

  • Loves UML making diagrams. Gladly presents them without a legend to people who don’t know how to read UML diagrams.
  • Love creating new unintuitive names for very simple ideas (e.g “Broker topology”). Proceeds to use these niche names in discussions and judges other people for not knowing what a “Broker Topology” is.
  • Gets really into programming fads that are hailed as panaceas but later get tossed out for a new panacea (e.g. microservices, Layered Architecture, REST).
  • Gets very emotionally attached to programming decisions, even if they will have no effect on the user.
  • Loves engineering around unlikely “what ifs…”.
  • Prefers creating abstraction through classes instead of functions, even if no state is needed.
  • Is bored by “practical details” like logging, debugging, convenience, fail-safes, and delivering quickly.
  • Maximizes the number and obscurity of patterns used, leading to classes named things like EventLoopListenerFactory.
  • Only cares about performance if obscure (e.g. tail-call optimization)
  • Isn’t actually very capable creating software (hasn’t won any coding competitions, has trouble with git reset, hasn’t written any software that people enjoy using)


Know-it-all / hipster
 = Architecture  Hipster 
+ software architecture 

I don’t dislike architecture. Architecture is a beautiful study. However, the complexity of the discipline makes an fertile ground for phonies; a space for phonies to use miscommunication as a tool to create an illusion of their own competence.