Category Archives: code

No Man’s Sky birthday problem

Demo here. Code here.

My birthday is coming up in a couple days, so what better way to celebrate than by implementing a birthday problem calculator in JavaScript?

Don’t answer. I know the answer.

I actually started down this path after reading about how a pair of No Man’s Sky players have already found each other in-game, which was supposed to be nearly impossible. In fact, it’s happened a bunch. I suspect that the developers have underestimated a version of birthday problem. That’s the thing you might have heard about in elementary school, where a surprisingly small group of people will likely have a pair of individuals with the same birthday.

I’m not the only one to come to have this idea, as this comment by reddit user madbadanddangerous shows.

I’ve heard that there are about a billion planets a player can start out on (out of some quintillions of total planets). And the game has sold at least a couple hundred thousand copies, so let’s assume 150,000 players.

Aaaaand my calculator cannot handle those numbers. It just freezes, and I think it might be one of those heat death of the universe length calculations.

UPDATE: I added and approximating calculator. It’ll work for huge numbers.

Aside: factorials shouldn’t be terribly complex calculations, so I think the computer just gets bogged down with trying to handle massive numbers. If you have a fix to this problem, please submit a PR!

Check out this less accurate but actually functional calculator to get a sense of the probability. Going with 1,000,000,000 planets and 150,000 players yields a ~99.998% chance that at least 2 people will start on the same planet. Seems a little high, but that’s the math!

Technical Summary

This was a small project, so there’s not much of a postmortem! It took me maybe 3 or 4 hours to write, which is 2 hours more than I expected. Which sounds about right.

I find the probability with  1 - (d!/((d-n)!) * d^n) , where d is number of days, and n is number of people, from this Wolfram Mathworld article. Wikipedia indicates that there are some ways of approximating the value faster. I might try that.

Much of the time was spent setting up Math.js after realizing that even the standard case with 365 days overflows JS’s integer type. I am surprised to find that Math.js’s factorial function doesn’t cache its calculations, which means repeated calculations aren’t efficient.

Still, factorials shouldn’t have O(n!) time complexity or anything. I think the sluggishness comes from managing the huge numbers involved. A billion factorial is flipping huge.

Another chunk of the time was spent googling how to interact with the DOM without JQuery. Turns out it’s possible, who woulda thought?

Anyways, there you go. The Birthday Problem. No Man’s Sky. Hash collisions.

1 Comment

Filed under code, Uncategorized

Reusable behavior in Ruby objects

Though my Forest project is still in its infancy (a mere 150 commits in), I have spent a great deal of my time wrestling with objects and the bridges between them. The hardest parts of the design are yet to come, like when animals begin interacting with (attacking? eating?) each other. But I’ve made a few major design choices so far.

Note: this article ends up kind of being a recapitulation of David Copeland’s very well-written and informative Re-use in OO, but I come to a different conclusion.

In particular, I’ve come to final (I think!) decision on how objects obtain shared behaviors.

Here’s the problem, in the most general sense: both Wolf and Rabbit should be able to change their location. They should be able to move. The code for movement should be shared.

Module mixins are not the way

My initial solution was to include a Movable module in both Wolf and Rabbit. This is the solution for which Copeland advocates. I walked pretty far down this path, and even found solutions to some of my problems, like that private methods defined in the included module are accessible to every other included module and the parent class. I wrote a blog post about my solution, but I mention at the bottom a remaining qualm: there’s nothing preventing a module from calling another module’s public method, as in this gist. They can do so easily and inexplicitly.

I envisioned a bleak future for my project, with included modules calling each other willy nilly, in all directions, forming intractable dependencies. This problem could be worked around by carefully maintaining unidirectional dependencies, but it would be ad-hoc and easy to break, unensured against by nature of the construct.

So I asked for help. My friends Devon and Forrest, fellow Dev Bootcamp grads (RACCOONS!), helped out. Forrest showed me the Copeland article, and Devon illustrated a technique of sharing behavior through composition.

A few acceptable solutions

Decorating objects to #move! through composition

What I’m going with is Devon’s suggestion. It has the benefit of ensuring that dependencies are explicit and travel in one direction. Additionally, instances only gain these abilities when you want them, rather than having always-on, and thus abusable, abilities.

This is an implementation of the decorator pattern, where Movable is the decorator. I was actually already using decorators in my code to create presenters (with view-specific logic), but I didn’t at first make the connection that it could be used to share behavior.

class Movable < SimpleDelegator
  def move!; ...; end

wolf =
movable_wolf =

Data, Context, Integration (DCI)

Jim Gay discusses DCI in-depth here, and I don’t understand it totally. Anyhow, it relies on modules extending objects as needed, rather than mixed into the class’s definition itself.

Note that usage is very similar to the previous solution.

module Movable
  def move!; ...; end

wolf =

Duck typing your way to movement

Another composition / duck-typing solution is as follows, where the actual moving is delegated to another object or module. This is a partial solution.

I don’t like this path as much; I intuitively think that an object should be in charge of its own movement. I could envisage plenty of cases when it would be preferable, however, like if there was a Map object in charge of collision detection. You’d have to be vigilant in preventing the Map from becoming a God Object, though.

As stated, this is a partial solution. It doesn’t solve the problem of how to ensure a Wolf is a Movable in the first place. One could do that through extension or composition, as in the above two examples. It just changes where the #move! method lives, and implies that movement is the responsibility of a third object.

I like how “movable” makes semantic sense, though. And duck typing is just fun.

module Mover
  def self.move!(movable); ...; end



There’s more than one way to do it.

Module mixin on its own, my naive approach, seems totally untenable. It is multiple inheritance, as demonstrated by the fact that included modules are listed in a class’s .ancestors method. And inheritance can be a mess to begin with, without dependencies being able to go in all directions.

Please let me know if I you’ve got corrections or feedback! For example, I’d love to hear more examples of when the last code example is appropriate. I feel like it’s more useful than I am realizing.

Leave a comment

Filed under code, Uncategorized

RESTful API design and implementation

Recently, while building the forest’s API and finding myself running into problems I’d never imagined would need to be solved, I realized that I know very little API design.

This implies I’ve learned some, and simply have a better view of the field than I did. This article (which concerns both design and implementation) discusses the things I have learned and contended with.

I’ve been reading, and studying a couple different APIs (e.g. GitHub, which is my favorite) to see how it’s done.



APIs need to be versioned so that the developer can easily release new work. The two major schemes to expose different API versions: through request headers, and through the URI.

The header solution is the “most correct”, partially because it keeps URIs as an explicit and clean reference to a particular resource. Properly, the API version doesn’t have any bearing on the resource the client is trying to access, and thus doesn’t belong in the uniform resource identifier. That’s a sound argument.

However, several major players do use “api/v1/resource”, the improper and less technically RESTful method. And I’m doing it, too.

It’s easier for development. I don’t have to use curl or Postman to see what my responses look like. I can just visit localhost in browser. I also believe it’s a less opaque technique, and the only argument against it is an appeal to authority.

Here’s a good StackOverflow answer explaining why I’m wrong.

I agree that URIs should be permalinks, but a major API version change is likely going to introduce breaking changes. API consumers are going to have to change how they request the resource in any case. I’m much happier keeping the version totally in sight.

URIs dependent on params, not IDs

I want clear, beautiful URIs. Locations are best known by their Cartesian coordinates, not their IDs. Any Rails developer already knows that this is somewhat of a pain. Although custom routes are fairly trivial in Rails, these schemes can very quickly and easily get out of hand if not managed properly; such is Rails’ dependence on naming conventions.

I went through a couple thoughts on this, like for example /locations/x/1/y/2, but I eventually settled on a query string: locations?x=1&y=2

I found a couple of people discussing whether query strings are RESTful on StackOverflow. It would seem that there’s no reason for them not to be; REST merely asks that resources have unique endpoints.

Of course, dictating to Rails that I want every location’s URI to use the query string rather than an ID meant clobbering DMM’s opinions.

Here’s some of the weirder stuff I had to do to get this scheme to work:

JSON layouts

That bullshit concerning rails-api and JBuilder that I already wrote about.

It makes no sense that this isn’t built into rails-api. The main draw of Rails is that it’s opinionated, and thus does a bunch of heavy lifting for the developer at the cost of flexibility.

There’s a bunch of stupid rails-api stuff I’ve complained about on Twitter.


This is a large topic that dictates much of the forest’s design. It’s taken a lot of work, and I barely have it in place. HATEOAS is an aspect of REST that most APIs do not bother with; developers (not unreasonably) expect consumers to rely on separate documentation to get around. GitHub is my model API because they actually do implement it, and they implement it well.

I would love some back-end framework that makes this easier, like Rails makes every other common task easier. That’s a niche I would have expected rails-api to fill. Yes I’m bitter.

HATEOAS breaks down into a few sub-issues.

  1. Return relative or absolute URIs?
  2. Where should actions be in the response? All at the top level in one list or object, or some actions per object?
  3. What do action routes look like?

So, 1), I’m going with relative, rather than absolute, URIs. A couple of the reasons for this are, unfortunately, because Rails makes it easier to use relative URIs. URL helpers like url_for and [resource]_url return relative URIs by default. Additionally, RSpec makes it hard to get(absolute_url), so I’d have to add a bunch more boilerplate to the tests.

Here is a good discussion on paths on StackOverflow.

Github uses absolute URIs for action routes. They say it’s so the client doesn’t have to construct the URI themselves. Fair enough; it does take a little work for the client to construct URIs with the scheme I’m using. However, they would probably only need to implement that solution once in that project. I don’t expect it to be too onerous.

2) Right now, actions in the API response are presented like this:

  actions: {...},
  objects: [{
    kind: wolf,
    actions: {...}

Actions are stored in location.actionsand in location.objects[i].actions. They are organized according to what the object the action is on, but as a result are scattered throughout the JSON.

I could also have a big ol’ hash or list at the top level simply labelled actions which would contain every action possible at that moment. It would be very easy to find, and namespacing actions within could help organize them.

My main concern here isn’t whether one thing is more correct that the other. I’m struggling with what solution would be easiest for the API consumer.

In terms of development from the API maintainer’s perspective, the current setup is easiest. So that’s that. If it turns out to be awful from the consumer perspective, I’ll look into changing it.

3) And what should actions look like? Specifically, let’s say hello to a wolf. Is that:

  • /wolves/1/action/say-hello
  • /wolves/1/say-hello
  • /wolves/1?action=say-hello

I’m pretty sure I’m gonna go with the second option, although if the forest ever has nested resources, it could get to be a problem. The solution is to say “no nested resources!”, but that seems pretty limiting. We’ll see!


Designing and building this API has taught me so much that I didn’t know I didn’t know. It’s been so much fun! Because my collaborators (looks like Ryan‘s on board!) and I are basically the only people consuming the API, I have a pretty good idea of what the client’s needs are. Having to deeply consider both sides has given the process a lot of helpful direction.

Leave a comment

Filed under code, Uncategorized

A reintroduction to TDD

So I’ve been writing a forest.

And I’ve been writing tests for it.

It’s been a lot of fun, and I’ve gotten a second wind on the project in the past couple weeks. I’ve written a bunch of code!

However, a lot of features have yet to be implemented. The code I’ve been writing has largely been RSpec, which you can see in this PR. As of right now, most of those tests fail, which isn’t a mistake.

I’ve been TDDing the forest a lot. Not everything, but a lot of things. Professionally, I’ve always regarded TDD like veganism: yes, you can make a lot of great arguments in its favor that I cannot honestly counter, but I just can’t imagine myself actually following through with it. So while I’ve historically written tests, they usually don’t come first.

Good arguments against TDD exist, and I certainly don’t think it’s the be-all and end-all. Some people are really off-puttingly dogmatic about it. But I’ve discovered, personally and for the first time, reasons to do it.

  1. It’s meditative. I’m not going to substantiate this because it’s very subjective, but there. It feels good.
  2. Non-passing tests act as a very difficult-to-ignore to-do list. I have a bunch of to-do lists devoted to the forest, including Trello, post-it notes, and #TODO and #FIXME comments scattered throughout my code (which is great for indelibly affixing a task to a particular line), but nothing encourages me to act more than a yellow or red dot in a sea of green.
  3. I’m not on a timeline. TDD does take longer up front, at least in my experience. Maybe one day I’ll get good enough at it that that won’t take any longer than writing the other way around. Of course, professional projects usually are on a timeline, so this reason might not convince your boss.
  4. It makes my coding intentional. Every time I write a method, it is to get a particular behavior. If I start building a workaround that goes off into some space not covered by the spec, I feel it immediately.
  5. It makes my code prettier. This is also subjective, but I think it does.

I’ve definitely complained about TDD before, because if you are in a time crunch it can feel very, very slow. “What do you mean I have to write code before I can write my code? This is bull!”. But this forest is a nice place. There’s time to do things right here.

Leave a comment

Filed under code, Uncategorized

The forest is better!

Thanks to an unexpected PR from a friend, the forest is in good health. The polymorphism issues I was having in the last blog post are all but solved, and all tests are passing. There need to be *more* tests, for sure, but things are looking much better now.

The Location#objects helper hack method still exists, but that’s okay because all the other ActiveRecord helpers I’m used to are back. Wolf#location and Location#wolves both work out of the box. Trogidu, the writer of the PR, saw to that. He also found a couple pluralization issues! I suspected those would turn up, but I was missing the extra pair of eyes!

I’m not working on this project as frequently as I ought to, but every time I put an hour into it I’m astounded by the amount I learn. Trogidu’s PR introduced me to inverse_of, which I somehow had never heard of before. Plus, it made me feel all warm inside that someone I haven’t spoken to in a while took enough interest to help me write code!

Also, the dev blog seems to be following a pattern of humanistic status update post followed by a more specific post on a particular technical thing. I think it’s a good pattern. I’ll follow this one by a quick post on JBuilder layouts.

Leave a comment

Filed under code, Uncategorized

Reverse polymorphism, aka polymorphic join.

I’ve built and implemented a bunch of stuff I’m excited about with the forest, but this post will focus on one aspect: reverse polymorphism. I don’t have it working perfectly yet (EVEN THOUGH IT SHOULD BE WORKING WHAT THE HECK) but I think it is the solution to the craziness I had been encountering with the ActiveRecord associations I need. The best part about it is that it’s not Single Table Inheritance (STI), another potential “solution”.

I’ll describe the problem that needed solving, and how this solves it, and why it’s awesome. Then I’ll describe what’s not quite working yet, the workarounds I’m using, and plea for help from those more knowledgeable.

First, though, here is the gist which introduced me to RP in Rails. I’ll explain how it works in a bit.

The forest’s fundamental blocks are Location objects. They’re normal AR objects. Locations have_many objects, and objects can be multiple kinds of things. The toy examples in the app right now are Wolves and Trees. Wolves can move around, and Trees can’t, but both have_one location.

Ideally, I’d like to be able to call Location#objects and receive a list (an ActiveRecord::Relation) that looks like [wolf1, wolf2, tree1]. I’d like this to work at the ORM level (i.e. I want ActiveRecord to do it for me) and not have to write that scope or method myself.

Polymorphism to the rescue

This sounds like a job for polymorphism, but it’s not a classic case. The normal case is an object being able to belong_to one of multiple kinds of things. I need an object to be able to have_many of many types of things.

It took me a day to grok this, but the solution is a join table. In my case, a LocationObject.

  • Location has_many LocationObjects
  • LocationObjects (the join table) have a polymorphic have_one association with Wolves, Trees, etc.
  • Wolves and Trees have_one LocationObject as object
  • Location has_many Wolves and Trees through LocationObjects.

So the associations are all set up. Location#location_object AND Wolf#location_object work.

Someone might say “well Vincent, this is totally more complicated than Single Table Inheritance!” and I would say “ugh come on”. Classical inheritance sounds like a great solution until you see what it does to your database. Even though Wolves and Dogs intuitively could both inherit from a hypothetical Canid class, which inherits from a Mammal class, and so on, this means that everything that inherits from the base class shares the same table. Every time a single child needs a new attribute, it gets added as a column to the ancestor table.

Because the forest will hopefully have a widely-branching tree of life, this is not the proper solution for this project. That single table would probably get huge, and track information for everything from number of leaves to most recent meal. Or whatever. It would be painful.

To keep shared behavior manageable, I’m going to be relying on composing with modules. To continue the previous example, I’d have a Mammal module, and a Canid module, both of which would get mixed in to the lowest-level Wolf and Dog classes. I’m keeping these modules in lib/.

Hell yeah. This seems like the perfect solution.

The Problem

The problem I’m having is the join. Location#objects and Wolf#location do not work. I’ve created the following fix, which I really don’t want to be permanent:

# app/models/location.rb
def objects
   self.location_objects.includes(:object).map do |location_object|

While it DOES avoid a potential N+1 issue, I’m pretty sure ActiveRecord is capable of doing this for me. And as long as this is a pet project, I want the code to be beautiful. I’ve even got failing tests demonstrating this behavior.

Another symptom of this is being unable to create the objects as I’d like. Wolf.create(name: "joe", location: some_location) just doesn’t work!

The plea


It may be the ActiveRecord just doesn’t handle those helper methods over polymorphic join tables. But the writing I’ve seen online doesn’t suggest that.

I have a terrible fear that this is a naming or pluralization issue. ActiveRecord’s errors hint at that: Could not find the association :location_objects in model Wolf.

Anyways, here’s the relevant code. I invite feedback!


1 Comment

Filed under code, Uncategorized

It’s just an API for now.

Alright, episode two in the development blog of my little forest project.

Here’s the forest code.

If you look at my Github contribution tracker, you’ll notice a month gap there. There’s a couple reasons for that, but the relevant one is that I was trying to work on the front end. I was learning how to get React + Redux running with Webpack and Babel and all that fun stuff. I was learning about modern JavaScript development and deployment.

I spent a couple weeks following Survive.js’s awesome Webpack and React tutorial. I don’t think I will continue down that road for right now. I’m just doing Ruby for now. I am capable of learning the modern front-end, but it will probably have to be with more time or mentorship. The complex mixture of compilers and languages and package managers is too much for me to handle at the moment.

So that’s that. I’m building an API for now. With Ruby on Rails. Once it’s fleshed out I’ll start looking at a front-end. I’d love for it to imitate the style of text adventures like Zork, except the world is dynamic and alive. Every movement (e.g. north, south) would constitute an API call. Clearly, web technologies are not the best way to build this. I think Z-machine is the way to go for that.

So that’s a status update. I’ll write a follow-up post real soon re: technical issues on the back-end.

Leave a comment

Filed under code, Uncategorized