Commit 6551862

@@ -0,0 +1,158 @@
+#!/usr/bin/env ruby
+
+require 'set'
+
+def assert_equal(expected, actual)
+  raise [expected, actual].inspect unless expected == actual
+end
+
+def assert_includes(expected, actual)
+  puts [expected, 'not found in', actual].inspect unless actual.include?(expected)
+end
+
+=begin
+  A<->B: 5
+  A<->D: 6
+  A<->F: 3
+  B<->C: 4
+  B<->E: 2
+  C<->D: 3
+  C<->E: 1
+  C<->G: 2
+  D<->E: 1
+  F<->G: 8
+=end
+
+# class Edge
+#   attr_reader :source, :destination, :distance
+
+#   def initialize(source, destination, distance)
+#     @source = source
+#     @destination = destination
+#     @distance = distance
+#   end
+
+#   def to_s
+#     "#{source.title}->#{destination.title}: #{distance}"
+#   end
+
+# end
+
+# class Node
+#   attr_reader :title, :edges
+
+#   def initialize(title:)
+#     @title = title
+#     @edges = []
+#   end
+
+#   def to(node, distance)
+#     @edges.push(Edge.new(self, node, distance))
+#   end
+
+#   def each
+#     @edges.each do |edge|
+#       yield edge
+#     end
+#   end
+
+#   def to_s
+#     title
+#   end
+
+#   def inspect
+#     to_s
+#   end
+# end
+
+class Graph
+  def initialize
+    @nodes = Hash.new { |h, k| h[k] = Set.new }
+  end
+
+  def connect(source, destination, weight)
+    @nodes[source] << destination
+    @nodes[destination] << source
+  end
+
+  def simple_paths(source, destination)
+    return [source] if source == destination
+
+    @nodes[source].each do |other|
+      puts other
+      items = simple_paths(other, destination)
+      # if items.any?
+      #   return [source, items]
+      # end
+    end
+
+    []
+  end
+
+  def inspect
+    @nodes.inspect
+  end
+end
+
+# a = Node.new(title: "A")
+# b = Node.new(title: "B")
+# c = Node.new(title: "C")
+# d = Node.new(title: "D")
+# e = Node.new(title: "E")
+# f = Node.new(title: "F")
+# g = Node.new(title: "G")
+
+
+# a.to(b, 5)
+# a.to(d, 6)
+# a.to(f, 3)
+# b.to(c, 4)
+# b.to(e, 2)
+# c.to(d, 3)
+# c.to(e, 1)
+# c.to(g, 2)
+# d.to(e, 1)
+# f.to(g, 8)
+
+# [a,b,c,d,e,f,g].each do |node|
+#   node.each do |edge|
+#     puts edge.to_s
+#   end
+# end
+
+# puts ""
+# puts "Paths from A to G"
+# assert_includes([a,b,c,g], results)
+# assert_includes([a,b,e,c,g], results)
+# assert_includes([a,d,c,g], results)
+# assert_includes([a,d,e,b,c,g], results)
+# assert_includes([a,d,e,c,g], results)
+# assert_includes([a,f,g], results)
+# assert_equal([
+#   [a,b,c,g],
+#   [a,b,e,c,g],
+#   [a,d,c,g],
+#   [a,d,e,b,c,g],
+#   [a,d,e,c,g],
+#   [a,f,g]
+# ], results)
+
+
+graph = Graph.new
+graph.connect(:a, :b, 5)
+graph.connect(:a, :d, 6)
+graph.connect(:a, :f, 3)
+graph.connect(:b, :c, 4)
+graph.connect(:b, :e, 2)
+graph.connect(:c, :d, 3)
+graph.connect(:c, :e, 1)
+graph.connect(:c, :g, 2)
+graph.connect(:d, :e, 1)
+graph.connect(:f, :g, 8)
+
+puts graph.inspect
+
+puts ""
+puts "Paths from A to G"
+
+graph.simple_paths(:a, :g)

@@ -20,13 +20,70 @@ main.s
 
 Chapter 7:
 
-> 16.	Given the following diagram, where the numbers represent the time delays across a link:
+> 16. Given the following diagram, where the numbers represent the time delays across a link:
+
 >  a. How many simple paths (those that do not repeat a node) are there from node A to G?
+  ```plaintext
+    A<->B: 5
+    A<->D: 6
+    A<->F: 3
+    B<->C: 4
+    B<->E: 2
+    C<->D: 3
+    C<->E: 1
+    C<->G: 2
+    D<->E: 1
+    F<->G: 8
+  ```
+
+  There are 6 simple paths
+
+  ```plaintext
+  | Path        |
+  | ----        |
+  | a,b,c,g     |
+  | a,b,e,c,g   |
+  | a,d,c,g     |
+  | a,d,e,b,c,g |
+  | a,d,e,c,g   |
+  | a,f,g       |
+  ```
+
 >  b. What is the shortest path from node A to node G? What is the overall delay?
+
+  The shortest path has a distance of 10. The overall delay is 11.
+
+  ```plaintext
+  | Path        | Total Distance |
+  | ----        | -------------- |
+  | a,b,c,g     | 5+4+2 = 11     |
+  | a,b,e,c,g   | 5+2+1+2 = 10   |
+  | a,d,c,g     | 6+3+2 = 11     |
+  | a,d,e,b,c,g | 6+1+2+4+2 = 15 |
+  | a,d,e,c,g   | 6+1+1+2 = 10   |
+  | a,f,g       | 3+8 = 11       |
+  ```
+
 >  c. If node E fails, does that change the shortest path? If so, what is the new shortest path?
 
+  Yes, if node E fails then there are 3 simple paths remaining with the shortest path having a distance of 11.
 
-> 18.	What are some of the specific responsibilities performed by the device called a gateway (diagrammed in Figure 7.21) that is placed between two different types of networks to allow them to communicate?
+  ```plaintext
+    A<->B: 5
+    A<->D: 6
+    A<->F: 3
+    B<->C: 4
+    C<->D: 3
+    C<->G: 2
+    F<->G: 8
+  ```
 
-Chapter 8:
+  ```plaintext
+  | Path        | Total Distance |
+  | ----        | -------------- |
+  | a,b,c,g     | 5+4+2 = 11     |
+  | a,d,c,g     | 6+3+2 = 11     |
+  | a,f,g       | 3+8 = 11       |
+  ```
 
+Chapter 8: