Skip to content

Instantly share code, notes, and snippets.

@yasuoza
Created August 6, 2012 07:22
Show Gist options
  • Save yasuoza/3271898 to your computer and use it in GitHub Desktop.
Save yasuoza/3271898 to your computer and use it in GitHub Desktop.
Nine Algorithms that Changed the Future -Random surfer trick algorithm-
0 1
1 4
2 0
3 0
4 0
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
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment