Nine Algorithms that Changed the Future -Random surfer trick algorithm-

graph.txt

0 1
1 4
2 0
3 0
4 0

random_surfer_trick.rb

class RandomSurfer
  attr_reader :graph, :start_point, :counts

  def initialize(filename)
    if (!filename || !File.exists?(filename))
      abort "Invalid filename"
    end
    @graph = []
    @counts = []
    File.open(filename) do |file|
      while line = file.gets
        start_and_end = line.scan(/\w+/)
        start_point = Integer(start_and_end[0])
        @counts[start_point] = 0
        @graph[start_point] = Integer(start_and_end[1])
      end
    end
  end

  def select_start
    @start_point = rand(self.graph.size)
    counts[@start_point] += 1
    return self
  end

  def step_forward(given_point = nil)
    next_point = @graph[given_point || @start_point]
    @counts[next_point] += 1
    next_point
  end
end

surfer.rb

require File.expand_path('../random_surfer_trick', __FILE__)

TRIAL = 10000
result = {}

surfer = RandomSurfer.new('graph.txt').select_start
TRIAL.times do
  if rand(20) < 3 then
    surfer.select_start
  end
  surfer.step_forward
end

p "Trial count: #{TRIAL}"
new_a = surfer.counts.map do |count|
  "#{count * 100 / TRIAL}%"
end

new_a.zip(("A".."Z").to_a) do |num, alpha|
  result[alpha] = num
end
p result

test_rspec.rb

require File.expand_path('../random_surfer_trick', __FILE__)

describe RandomSurfer do
  describe :initialize do
    it 'should read file' do
      surfer = RandomSurfer.new('graph.txt')
      surfer.should_not be nil
      surfer.graph[0].should eq 1
    end

    it 'should initialize counts' do
      surfer = RandomSurfer.new('graph.txt')
      surfer.counts.each do |count|
        count.should eq 0
      end
    end

    it 'should raise error when filename is nil' do
      lambda {
        surfer = RandomSurfer.new()
      }.should raise_error
    end

    it 'should raise error when wrong filename' do
      lambda {
        surfer = RandomSurfer.new('foobar.txt')
      }.should raise_error
    end
  end

  describe :select_start do
    let(:surfer) { RandomSurfer.new('graph.txt') }

    it 'should return self' do
      surfer.select_start.should equal surfer
    end

    it 'should select start point' do
      surfer.select_start.start_point.should be_between(0, surfer.graph.size)
    end

    it 'should increment start_point\'s count' do
      surfer.select_start
      surfer.counts[surfer.start_point].should eq 1
    end
  end

  describe :step_forward do
    it 'should go to given point\'s target' do
      surfer = RandomSurfer.new('graph.txt')
      surfer.step_forward(0).should eq 1
      surfer.counts[1].should eq 1
    end

    it 'should go to its target' do
      surfer = RandomSurfer.new('graph.txt')
      surfer.select_start.step_forward.should_not be nil
    end
  end
end