Posts Tagged ‘puzzle’
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|
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.
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:
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/” + 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.
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
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 }
