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/” + 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.

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