Starting with this email on @lrug mailing list:
http://lists.lrug.org/pipermail/chat-lrug.org/2013-October/009583.html
Eventually, 11 different implementations where proposed (code below). I adapted them to a Rspec spec and ran correctness and (naive) performance tests on them.
➜ spec git:(master) ✗ ls -lrt *.rb