Lojic Technologies

Archive for October 2007

Solving Anagrams in Ruby

with 4 comments

Someone posted a question on comp.lang.ruby recently asking for help with solving anagrams. The poster originally asked about ways of generating permutations and several people pointed him to the facets library which has some permutation utility functions. As it turns out, I benchmarked the following naive permutation generator as 3 times faster than the facets library code:

def words chars, result='', &b
  if chars.empty?
    yield result
  else
    chars.length.times do |i|
      c = (x = chars.clone).slice!(i)
      words(x, result + c, &b)
    end
  end
end

However, generating all possible combinations of letters in an anagram is a very bad approach which doesn’t take into consideration key knowledge about the problem. Rather than generating all permutations of an anagram, which is infeasible for longer words, we can precompute a hash from our dictionary by using the sorted letters of words as keys. Then to solve an anagram, we simply sort the letters in the anagram and look it up in the hash.

The first program creates the hash and serializes it to disk for future anagram solving:

words = Hash.new([])

File.open("/usr/share/dict/words", "r") do |file|
  while line = file.gets
    word = line.chomp
    words[word.split('').sort!.join('')] += [word]
  end
end

File.open("word_hash", "w") do |file|
  Marshal.dump(words, file)
end

The second program loads the serialized hash from disk to solve anagrams that we type at the console:

words = nil

File.open("word_hash", "r") do |file|
  words = Marshal.load(file)
end

while true
  print "Enter word: "
  anagram = gets.chomp
  sorted_anagram = anagram.split('').sort!.join('')
  p  words[sorted_anagram]
end

This is really fast, but there are probably better methods. If you have one, feel free to add a comment with the code.

Written by Brian Adkins

October 22, 2007 at 7:53 pm

Posted in programming

Tagged with , ,

Functional Features in JavaScript on Firefox

leave a comment »

I was reading an article about adding code to JavaScript to make it more functional, and one of the blog commenters mentioned some built-in features that were added to JavaScript 1.6 & 1.7 on Firefox, so I checked out the links (see below) – very cool stuff.

  • Array methods

    • indexOf
    • lastIndexOf
    • every
    • filter
    • forEach
    • map
    • some
  • Array & String generics
  • Generators & Iterators
  • Array Comprehensions
  • Block Scope w/ let
  • Destructuring Assignment
  • etc.

They won’t help if you have to target IE also, but it should be possible to conditionally include your own code to implement the ones that don’t require syntactic changes for pages loaded from IE. That would reduce network load for customers using Firefox.

New in JavaScript 1.6 (Firefox 1.5)

New in JavaScript 1.7 (Firefox 2.0)

Hopefully IE will catch up someday, but if not, I can see taking advantage of Firefox specific JavaScript enhancements for niche applications. Firefox is so easy to install, that it should be easy to convince customers to use it for certain custom applications.

Written by Brian Adkins

October 7, 2007 at 12:01 am

Inline C Code in Ruby

with 2 comments

Did you know you can write C code directly within a Ruby program? I learned that at the Ruby Hoedown here in Raleigh and thought I’d share it for those who aren’t aware of it.

First install the rubyinline gem.

sudo gem install rubyinline

Then code 🙂

require 'rubygems'
require 'inline'

class MyTest
  inline do |builder|
    builder.c "
      long factorial(int max) {
        long result = 1;
        while (max >= 2) {
          result *= max--;
        }
        return result;
      }"
  end
end
t = MyTest.new
puts t.factorial(10)

The first time you run this it will be slower than subsequent runs because the C code will be compiled and cached. Typically you’ll find the generated C code in ~/.ruby_inline

Enjoy,
Brian

Written by Brian Adkins

October 5, 2007 at 12:37 am

Posted in programming

Tagged with , ,