anagram_finder.ik

AnagramFinder = Origin mimic do(
  Multimap = Origin mimic do(
     initialize = method(self content = {})
     cell("[]=") = method(key, value,
      if(content key?(key),
        content[key] << value,
        content[key] = DefaultBehavior[value]))
     [] = method(key,
      content[key])
     keys = method(
      content keys)
     key? = method(key,
      content key?(key))
     
     initialize
  )
  
  words = method(text, 
    #/[a-z]+/ allMatches(text lower))
  
  index = method(words,
    words each(x, Multimap[encode(x)] = x))
   
  encode = method(word, 
    word chars reduce(1, code, x, code * asPrime(x)))
  
  asPrime = method(char,
    primes[char])
   
  primes = {
    "a" => 2,  "b" => 3,  "c" => 5,  "d" => 7,  "e" => 11,
    "f" => 13, "g" => 17, "h" => 19, "i" => 23, "j" => 29,
    "k" => 31, "l" => 37, "m" => 41, "n" => 43, "o" => 47,
    "p" => 53, "q" => 59, "r" => 61, "s" => 67, "t" => 71,
    "u" => 73, "v" => 79, "w" => 83, "x" => 89, "y" => 97,
    "z" => 101} withDefault(1)
  
  anagram = method(word,
    anagrams = set()
    code = encode(word)
    Multimap keys each(x, 
      if(code % x == 0,
        y = code / x
        if(Multimap key?(y), 
         anagrams << set(Multimap[x],Multimap[y]))))
         
    return anagrams)
    
)

anagram_finder_spec.ik

use("ispec")
use("../lib/multimap") ; point this to the right place :-)

describe(AnagramFinder,
  describe("words",
    it("should convert a string of words separated by linebreaks into an array",
      Finder = AnagramFinder mimic
      Finder words("sam\nbob\njohn") should == ["sam", "bob", "john"]
    )
    
    it("should lowercase any input",
      Finder = AnagramFinder mimic
      Finder words("SAM\nBOB\nJOHN") should == ["sam", "bob", "john"]
    )
    
    it("should treat any non-[a-z] char as a wordbreak",
      Finder = AnagramFinder mimic
      Finder words("sam0bob-john") should == ["sam", "bob", "john"]
    )
  )
  
  describe("encode",
    it("should encode single chars to their primes",
      Finder = AnagramFinder mimic
      Finder encode("a") should == 2
      Finder encode("t") should == 71
      Finder encode("z") should == 101 
    )
    
    it("should multiply the encoding values of the individual chars",
      Finder = AnagramFinder mimic
      Finder encode("ab")  should == 2 * 3
      Finder encode("cd")  should == 5 * 7
      Finder encode("sam") should == 67 * 2 * 41
    )
  )
  
  describe("Multimap#intialize",
    it("should reset the contents of the Multimap",
      Finder = AnagramFinder mimic
      
      Finder Multimap initialize
      Finder Multimap keys should == set()
      Finder Multimap[:red] = :case
      Finder Multimap keys should == set(:red)
      Finder Multimap initialize
      Finder Multimap keys should == set()
    )
  )
  
  describe("index",
    it("given an array of words should store a dictionary of word encodings to lists of words",
      Finder = AnagramFinder mimic
      Finder Multimap initialize
      Finder index(["sam", "bob", "john"])
      Finder Multimap keys should == set(5494, 1113571, 423)
      Finder Multimap[5494] should == ["sam"]
      Finder Multimap[1113571] should == ["john"]
      Finder Multimap[423] should = ["bob"]
    )
  )
  
  describe("anagram",
    it("should find all two word anagrams",
      Finder = AnagramFinder mimic
      
      Finder Multimap initialize
      input = "sam\nbob\njohn\npete"
      Finder index(Finder words(input))
      Finder anagram("sambob") should == set(set(["bob"], ["sam"]), set(["sam"], ["bob"]))
    )
  
  )
)