Lojic Technologies

Posts Tagged ‘puzzle

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 , ,

Telogis Puzzle

with 6 comments

I came across a web site that required job candidates to solve a puzzle to be able to access a job application page. I’m a sucker for puzzles. The original puzzle is at the following site:

http://www.telogis.co.nz/

But in case, they take it down at some point, here is the plain text version nicely formatted:

z = 4254145 * 0x18712495;
b = (z & 1) << 4;
a = b--;
o = [];
c = a - b;
x = b - a;
while (z) {
  x = a & x ? a & b : c + x;
  {
    o[z & b^x] = (x + 6 * a + b / 5 - c).chr;
    z = z / a / a;
  } if (!(z / a & b^x))
}

To apply go to “http://www.telogis.co.nz/&#8221; + o + “.html”

I don’t think this will parse correctly in any language, but I decided to solve the puzzle using Ruby since it wasn’t that far from it and Ruby is my main programming language currently. I had a couple false starts due to a subtlety in Ruby compared to other languages.

I’ll come back in a while and post the Ruby solution, but I don’t want to post a spoiler too soon.

Written by Brian Adkins

September 19, 2007 at 11:23 am

Posted in programming

Tagged with , ,

8 Queens in Ruby

leave a comment »

I came across a puzzle article that mentioned the 8 Queens problem. It’s been a long time since I encountered it, but I can’t recall if I ever took the time to code it up, so I took a few minutes to code up a couple versions in Ruby. I was impressed with how easy it was in Ruby. If Ruby had the macros and efficiency of Lisp, I’d be pleased.

In a nutshell, the idea is to determine all possible ways to arrange 8 queens on a chessboard so that none are attacking another.

I’m sure my solution is naive since it was pretty much the first approach I thought of, but it cranks out all solutions in a quarter of a second, so it’ll do 🙂

require 'pp'

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank)
      queens(stack, n+1) if valid?(stack)
      stack.pop
    end
  end
end

queens [], 0

I then became curious about abstracting away the concept of:
1) push something onto a stack
2) do something with the stack
3) pop something off the stack

So, I opened up the Array class and modified push to accept a block.

require 'pp'

class Array
  alias_method :orig_push, :push
  def push obj
    orig_push(obj)
    if block_given?
      yield self
      pop
    end
  end
end

def valid? stack
  q2 = stack.length - 1
  (0..stack.length-2).each do |q1|
    return false if stack[q1] == stack[q2] || (q1-q2).abs == (stack[q1]-stack[q2]).abs
  end
end

def queens stack, n
  if n == 8
    pp stack
  else
    (1..8).each do |rank|
      stack.push(rank) {|s| queens(s, n+1) if valid?(s) }
    end
  end
end

queens [], 0

It makes the code 15% slower, and I don’t like modifying the existing push method in this way, but it does show the convenience of Ruby blocks and how you can extend existing classes. I think a better approach would be to introduce a new function – either standalone as below, or in the Array class.

def push_with_block stack, obj
  stack.push(obj)
  yield stack
  stack.pop
end

Written by Brian Adkins

September 14, 2007 at 3:04 am

Posted in programming

Tagged with , , ,

Escape from Zurg

with 3 comments

I came across a little programming puzzle on comp.lang.ruby.

The author blogged about it here – nice solution. He refers to the original paper that got things started, but I haven’t had time to read it in depth yet.

I thought I’d try something a little different. I was going for simple and came up with a 3 function solution using just hashes and arrays. It’s not very general except for the handy combinations(array, n) function I wrote, and it certainly doesn’t feel Rubyish, but it was fun.

Something tells me that Lisp can handle this nicely, so I’ll probably write a Lisp version later.

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n - 1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result << x}
    end
  end
  return result
end

def generate_states state
  forward = state[:position] == :forward
  args = forward ? [state[:source], 2] : [state[:destination], 1]
  combinations(*args).inject([]) do |states, movers|
    states < state[:minutes] - TOYS[movers.max {|a,b| TOYS[a]  TOYS[b] }],
      :source => forward ? state[:source] - movers : state[:source] + movers,
      :destination => forward ? state[:destination] + movers : state[:destination] - movers,
      :position => forward ? :backward : :forward,
      :history => state[:history] + [[ state[:position], movers ]] }
    states
  end
end

def play_game state
  if state[:source].empty?
    pp(state[:history]) unless state[:minutes]  60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] })

UPDATE: Something didn’t quite feel right about my first solution, so I took a second look at the op’s solution and decided I liked his use of Ruby blocks. They add some flexibility and efficiency in this case. Instead of computing a full array of possible states at each level of recursion (not as bad as precomputing the entire tree, but still not good), the new solution does a depth first search via block yields. I also removed the hardcoded print statement in play_game and yield the solution to the caller’s block to do with as they please.

require 'pp'
TOYS = { :buzz => 5, :woody => 10, :rex => 20, :hamm => 25 }

def combinations array, n
  result = []
  if n > 0
    (0 .. array.length - n).each do |i|
      combs = [[]] if (combs = combinations(array[i + 1 .. -1], n - 1)).empty?
      combs.collect {|comb| [array[i]] + comb}.each {|x| result < state[:minutes] - TOYS[movers.max {|a,b| TOYS[a]  TOYS[b] }],
    :source => forward ? state[:source] - movers : state[:source] + movers,
    :destination => forward ? state[:destination] + movers : state[:destination] - movers,
    :position => forward ? :backward : :forward,
    :history => state[:history] + [[ state[:position], movers ]] }
end

def each_state state
  combinations(*(
    forward = state[:position] == :forward) ?
    [state[:source], 2] :
    [state[:destination], 1]).each {|movers| yield execute_move(state, forward, movers) }
end

def play_game state, &b
  if state[:source].empty?
    yield(state[:history]) unless state[:minutes]  60,
  :source => [ :buzz, :woody, :rex, :hamm ],
  :destination => [],
  :position => :forward,
  :history => [] }) {|history| pp history }

Written by Brian Adkins

September 10, 2007 at 3:38 pm

Posted in programming

Tagged with , ,