knight-random-walk.rb

#!/usr/bin/env ruby

class Knight
  attr_accessor :x, :y, :count

  def initialize(x, y)
    @x, @y, @count = x, y, 0
  end

  def position
    [@x, @y]
  end

  def move
    @count += 1
    old_x, old_y = @x, @y
    if rand(2) == 0
      if rand(2) == 0
        @x += 2
      else
        @x -= 2
      end
      if rand(2) == 0
        @y += 1
      else
        @y -= 1
      end
    else
      if rand(2) == 0
        @x += 1
      else
        @x -= 1
      end
      if rand(2) == 0
        @y += 2
      else
        @y -= 2
      end
    end

    if @x < 0 or @x > 7 or @y < 0 or @y > 7
      @count -= 1
      @x, @y = old_x, old_y
      move
    end
  end
end

t1 = Time.now

knight = Knight.new(0, 0)
memo = Array.new
1.upto(100000) do |x|
  knight.move
  knight.move until knight.position == [0, 0]
  puts x if x % 100 == 0
  memo << knight.count
  knight.count = 0
end

t2 = Time.now

puts
puts memo.inject(:+).to_f / memo.length
puts t2 - t1