add social graph.

8 files changed, 205 insertions, 0 deletions

diff --git a/lib/social_graph.rb b/lib/social_graph.rb
new file mode 100644
index 0000000..6dc27bc
--- /dev/null
+++ b/lib/social_graph.rb
@@ -0,0 +1,129 @@
+require 'set'
+
+class SocialGraph
+  attr_reader :reader, :writer
+
+  def initialize(reader, writer)
+    @reader, @writer = reader, writer
+    @members = Hash.new { |hash, key| hash[key] = Member.new(key) }
+  end
+
+  def run(traversal = Traversal.new(writer))
+    (reader.readline.to_i - 1).times do
+      add_to_graph(reader.readline.strip)
+    end
+
+    member_for(reader.readline).tap do |root|
+      traversal.traverse(root)
+    end
+  end
+
+  private
+
+  def add_to_graph(line)
+    key, friend_keys = line.split(':')
+    friend_keys.split(',').each do |friend|
+      member_for(key).add_friend(member_for(friend))
+    end unless friend_keys.nil?
+  end
+
+  def member_for(key)
+    @members[key.strip]
+  end
+end
+
+class Member
+  include Enumerable
+
+  attr_reader :name
+
+  def initialize(name)
+    @name = name
+    @friends = []
+  end
+
+  def add_friend(friend)
+    @friends << friend
+  end
+
+  def each
+    @friends.each do |friend|
+      yield friend
+    end
+  end
+
+  def to_s
+    name
+  end
+
+  def inspect
+    name
+  end
+
+  def ==(other)
+    name == other.name
+  end
+end
+
+class Traversal
+  attr_reader :writer
+
+  def initialize(writer)
+    @writer = writer
+    @visited = { }
+    @queue = []
+  end
+
+  def traverse(member)
+    @queue = []
+    @root = member
+    @queue.push(member)
+    until @queue.empty? do
+      member = @queue.shift
+      write(newline) if member.nil? && @queue.first
+      next if member.nil?
+
+      visit(member)
+      added = false
+      member.each do |friend|
+        @queue.push(friend) if eligible?(friend)
+        added = true
+      end
+
+      @queue.push(nil) if added
+    end
+  end
+
+  private
+
+  def eligible?(member)
+    !visited?(member) && !root?(member) && !queued?(member)
+  end
+
+  def newline
+    "\n"
+  end
+
+  def queued?(friend)
+    @queue.find { |x| x == friend }
+  end
+
+  def visit(member)
+    return if visited?(member) || root?(member)
+    write(member.name) unless root?(member)
+    write(",") unless @queue.first.nil?
+    @visited[member.name] = true
+  end
+
+  def visited?(member)
+    @visited.key?(member.name)
+  end
+
+  def root?(member)
+    @root.name == member.name
+  end
+
+  def write(value)
+    writer.write(value)
+  end
+end
diff --git a/spec/fixtures/input000.txt b/spec/fixtures/input000.txt
new file mode 100755
index 0000000..1cd1a31
--- /dev/null
+++ b/spec/fixtures/input000.txt
@@ -0,0 +1,8 @@
+7
+A:B,C,D
+B:A,D,E
+C:A,B
+D:E,A,B
+E:A,F,G
+F
+A
\ No newline at end of file
diff --git a/spec/fixtures/input001.txt b/spec/fixtures/input001.txt
new file mode 100755
index 0000000..88803ed
--- /dev/null
+++ b/spec/fixtures/input001.txt
@@ -0,0 +1,3 @@
+2
+A:B,C,D
+A
\ No newline at end of file
diff --git a/spec/fixtures/input002.txt b/spec/fixtures/input002.txt
new file mode 100755
index 0000000..6d47d45
--- /dev/null
+++ b/spec/fixtures/input002.txt
@@ -0,0 +1,5 @@
+4
+A:B,C,D
+B:A,D,E
+C:E,B
+A
\ No newline at end of file
diff --git a/spec/fixtures/output000.txt b/spec/fixtures/output000.txt
new file mode 100755
index 0000000..45877a4
--- /dev/null
+++ b/spec/fixtures/output000.txt
@@ -0,0 +1,3 @@
+B,C,D
+E
+F,G
\ No newline at end of file
diff --git a/spec/fixtures/output001.txt b/spec/fixtures/output001.txt
new file mode 100755
index 0000000..8c1939d
--- /dev/null
+++ b/spec/fixtures/output001.txt
@@ -0,0 +1 @@
+B,C,D
\ No newline at end of file
diff --git a/spec/fixtures/output002.txt b/spec/fixtures/output002.txt
new file mode 100755
index 0000000..6f68804
--- /dev/null
+++ b/spec/fixtures/output002.txt
@@ -0,0 +1,2 @@
+B,C,D
+E
\ No newline at end of file
diff --git a/spec/practice/social_graph_spec.rb b/spec/practice/social_graph_spec.rb
new file mode 100644
index 0000000..02ee5f7
--- /dev/null
+++ b/spec/practice/social_graph_spec.rb
@@ -0,0 +1,54 @@
+#given a graph, output each level of friends.
+#each friend should only be output once, at the first level they are encountered.
+
+=begin
+INPUT
+2 # number of lines to follow
+A:B,C,D # member a has friends b,c,d
+A # the member to start the traversal from.
+
+OUTPUT
+=end
+
+require 'social_graph'
+
+describe "problem" do
+  subject { SocialGraph.new(input, output) }
+  let(:output) { StringIO.new }
+
+  context "when 2 lines given" do 
+    let(:fixtures_dir) { File.join(Dir.pwd, 'spec', 'fixtures') }
+    let(:input) { StringIO.new(IO.read(File.join(fixtures_dir, "input001.txt"))) }
+    let(:expected) { IO.read(File.join(fixtures_dir, "output001.txt")) }
+
+    it 'writes the correct result' do
+      subject.run
+      output.rewind
+      expect(output.read).to eql(expected)
+    end
+  end
+
+  context "when 4 lines given" do
+    let(:fixtures_dir) { File.join(Dir.pwd, 'spec', 'fixtures') }
+    let(:input) { StringIO.new(IO.read(File.join(fixtures_dir, "input002.txt"))) }
+    let(:expected) { IO.read(File.join(fixtures_dir, "output002.txt")) }
+
+    it 'writes the correct result' do
+      subject.run
+      output.rewind
+      expect(output.read).to eql(expected)
+    end
+  end
+
+  context "when 7 lines given" do
+    let(:fixtures_dir) { File.join(Dir.pwd, 'spec', 'fixtures') }
+    let(:input) { StringIO.new(IO.read(File.join(fixtures_dir, "input000.txt"))) }
+    let(:expected) { IO.read(File.join(fixtures_dir, "output000.txt")) }
+
+    it 'writes the correct result' do
+      subject.run
+      output.rewind
+      expect(output.read).to eql(expected)
+    end
+  end
+end