# Lojic Technologies

## Solving Anagrams in Ruby

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

October 22, 2007 at 7:53 pm

Posted in programming

Tagged with , ,

## Telogis Puzzle

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.

September 19, 2007 at 11:23 am

Posted in programming

Tagged with , ,

## 8 Queens in Ruby

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

September 14, 2007 at 3:04 am

Posted in programming

Tagged with , , ,

## Escape from Zurg

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 }
```