Lojic Technologies

Archive for September 2007

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

Lojic Technologies is Expanding

leave a comment »

Lojic Technologies is gearing up for new business projects. I finally got around to putting up a portfolio page with a few past projects.

http://www.lojic.com/portfolio/

We’re currently offering a 10% referral fee, so if you become aware of businesses or individuals in need of web sites or web applications, let me know. Once my referral advertising system is completed (in the next few weeks), we’ll integrate it with the corporate site to track referrals automatically.

Brian

Written by Brian Adkins

September 18, 2007 at 11:00 pm

Posted in business

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

Web Hosting Bandwidth Constant

with one comment

  • 365.25 days per year
  • 12 months per year
  • 24 hours per day
  • 60 minutes per hour
  • 60 seconds per minute
  • 1,024 MB per GB
  • 1,024 KB per MB
  • 8 kilobits (kb) per kilobyte (KB)

Put that all together and you get the following:

3.19 (month kb) / (sec GB)

So when you see a web hosting company stating a bandwidth per month (in GB), you can multiply that by 3.19 to get a kilobits per second figure. In other words, 18 GB/month of bandwidth is the amount of bandwidth that a 56Kb modem would consume at full capacity, and 480 GB/month is roughly the same as a 1.5Mb T1 line.

Written by Brian Adkins

September 3, 2007 at 1:42 am

Posted in internet

Tagged with , ,