What data structure might this game use? This question is not about game development or about actual implementation details.

I was playing Little Alchemy yesterday.  (Warning: Productivity hazard.)  You start with the four classical Elements of earth, air, fire, and water.  You can combine them to produce other "Elements" (wood, humanity, time, cities, etc.), combine those to produce even more, etc.  All of the relationships are predefined, so the game is less about crafting and more about lateral thinking.

I got curious about how exactly the game could store and query the various combinations optimally.  Whether the developer actually does so under the hood is a different story, and not what I'm asking about.

Consider the following game mechanics:


There is no limit to the number of Elements, but it's decided in advance by the game's designer and thus does not change at runtime.
All Elements are made by combining exactly two other Elements, possibly of the same kind (Fire + Water = Steam).
Even the four base Elements can be created (Fire + Ice = Water).
Some Elements can be created through more than one combination. (Fire + Water = Energy + Water = Steam)
Some combinations produce more than one Element (Human + Cow = Minotaur and Milk)
Some Elements are "final" and cannot be combined to produce any other, though they may in future updates.  (Jedi + Swamp = Yoda)
Order of combination does not matter (e.g. Water + Fire = Fire + Water).


The game presumably needs fast lookup and low memory usage.  More specifically:


Given exactly two elements, look up the result of their combination, if any.  This should be fast.
There is no insertion or removal except by the game's designer in advance.  This can safely be slow.


Given these, what data structure might Little Alchemy use to store the various combinations that can be used to produce elements?



Initial Thoughts

Back-of-the-envelope guess?  A big ass-hash-table that maps (Element, Element) pairs to Element lists. For $n$ Elements, this results in amortized $O(1)$ lookup and $O(n^2)$ memory, because theoretically any combination can produce every other Element at once.  Can we do better?
A hashtable is asymptotically optimal.  Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces).  Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space.  You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal.  Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors.  But speaking pragmatically: I expect a hashtable will be fine.  The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.