It is not especially difficult, but you need to take into account memory access time and structure your data accordingly. Smart iteration over a graph-like structure does the job well. FYI, for the sample tests, my code run in about 700ms, and around 10s for the complete test suite, so I guess you need to aim at 850ms top for the samples

Is this Kata especially hard in Ruby because Ruby is slow? I have optimized and optimized and my code still isn't fast enough.

short solution using core lib only

Performance Version

This method only checks whether there already is a memo the first time it is called. Then the method redifines itself, and further calls retrieve the (instance variable) memo directly, without perfoming the check. Since the check doesn't need to happen every time the method is called, it should have better performance (and performance is the point of doing memoization in the first place)