--------------000708060601000400090905 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Here's my solution. It runs in 4 seconds on my 3932 bogomips machine, using /usr/share/dict/american-english (96,273 words). My major optimizations (and I didn't fiddle with minor ones) are limiting the "anagram space" with a standard "anagram" representation, and generating the stems by subtraction from bingos instead of generating all gazillion stems and checking them with all letters. --------------000708060601000400090905 Content-Type: text/plain; name ingo_stems.rb" Content-Transfer-Encoding: base64 Content-Disposition: inline; filename ingo_stems.rb" IyEgL3Vzci9iaW4vcnVieQoKIyBDb3B5cmlnaHQgKEMpIDIwMDQgSGFucyBGdWdhbAojIERp c3RyaWJ1dGVkIHVuZGVyIHRoZSBHUEwKCnJlcXVpcmUgJ3NldCcKCiMgdGhpcyBmdW5jdGlv biBzb3J0cyB0aGUgbGV0dGVycywgc28gZS5nLiAicnVieSIgYmVjb21lcyAiYnJ1eSIuIFRo aXMgd2lsbAojIGdpdmUgdXMgYSBzdGFuZGFyZCByZXByZXNlbnRhdGlvbiBvZiBhbiAiYW5h Z3JhbSIKZGVmIHBhcnNlX2FuYWdyYW0od29yZCkKICB3b3JkLnNwbGl0KCIiKS5zb3J0Lmpv aW4KZW5kCgojIGdldCBuCm4gPSBBUkdWWzBdID8gQVJHVlswXS50b19pIDogMQoKIyBwdWxs IGluIHRoZSB3b3JkbGlzdC4gV2UncmUgb25seSBpbnRlcmVzdGVkIGluIDctbGV0dGVyIHdv cmRzIGFuZCB3ZSdsbAojIGFuYWdyYW0taXplIHRoZW0gc28gd2UgZW5kIHVwIHdpdGggdW5p cXVlIDctbGV0dGVyIGFuYWdyYW1zLgokc3RkZXJyLnByaW50ICJQYXJzaW5nIHdvcmRsaXN0 IG9uIHN0ZGluLi4uIgokc3RkZXJyLmZsdXNoCmFuYWdyYW1zID0gU2V0Lm5ldwokc3RkaW4u ZWFjaF9saW5lIGRvIHx3b3JkfAogIHdvcmQuZG93bmNhc2UhCiAgd29yZC50ciEoIl5hLXoi LCIiKQogIG5leHQgdW5sZXNzIHdvcmQuc2l6ZSA9PSA3CiAgYW5hZ3JhbXMuYWRkKHBhcnNl X2FuYWdyYW0od29yZCkpCmVuZAokc3RkZXJyLnB1dHMgIiAje2FuYWdyYW1zLnNpemV9IHVu aXF1ZSA3LWxldHRlciBhbmFncmFtcyBsb2FkZWQuIgoKCiMgTm93IGZvciB0aGUgcmVhbCBm dW4uIEluaXRpYWxseSBJIGdlbmVyYXRlZCB0aGUgNi1sZXR0ZXIgc3RlbXMsIGFkZGVkCiMg bGV0dGVycywgYW5kIHRlc3RlZCBmb3IgdGhlIHJlc3VsdGluZyBhbmFncmFtIGluIHRoZSBh bmFncmFtIGxpc3QuIFRoYXQgdG9vawojIHdheSB0b28gbG9uZy4gVGhlbiBJIHJlYWxpemVk IGl0IHdvdWxkIGJlIF9tdWNoXyBtb3JlIGVmZmljaWVudCB0byB3b3JrCiMgYmFja3dhcmRz LCBnb2luZyBmcm9tIGtub3duIDctbGV0dGVyIGFuYWdyYW1zIHRvIDYtbGV0dGVyIGFuYWdy YW1zIGJ5CiMgc3VidHJhY3Rpb24uIFZvaWzDoSwgbWFueSBvcmRlcnMgb2YgbWFnbml0dWRl IGZhc3Rlci4KJHN0ZGVyci5wcmludCAiR2VuZXJhdGluZyA2LWxldHRlciBzdGVtcyBmcm9t IGFuYWdyYW1zLi4uIgokc3RkZXJyLmZsdXNoCnN0ZW1zID0gSGFzaC5uZXcge3xoLGt8IGhb a10gPSAiIn0KYW5hZ3JhbXMuZWFjaCBkbyB8YXwKICBhLnNpemUudGltZXMgZG8gfGl8CiAg ICBzdGVtID0gcGFyc2VfYW5hZ3JhbSBhWzAsaV0rYVtpKzEuLi0xXQogICAgbGV0dGVycyA9 IHN0ZW1zW3N0ZW1dCiAgICBsZXR0ZXJzIDw8IGFbaV0gdW5sZXNzIGxldHRlcnMuaW5jbHVk ZT8gYVtpXQogIGVuZAplbmQKJHN0ZGVyci5wdXRzICIgI3tzdGVtcy5zaXplfSBzdGVtcyBn ZW5lcmF0ZWQuIgoKIyBUaGUgYm9yaW5nIHBhcnQuIFByaW50IG91dCB0aGUgYW5zd2VycyBh bmQgYXBwbHkgdGhlIGN1dG9mZiBuLgpzdGVtcy5zb3J0X2J5IHt8a3Z8IGt2WzFdLnNpemV9 LnJldmVyc2UuZWFjaCBkbyB8a3Z8IAogIHNpemUgPSBrdlsxXS5zaXplCiAgcHV0cyAiI3tr dlswXX1cdCN7c2l6ZX0iIGlmIHNpemUgPj0gbgplbmQK --------------000708060601000400090905--