graph.db

AB5,BC4,CD8,DC8,DE6,AD5,CE2,EB3,AE7

Question.txt

The local commuter railroad services a number of towns in Kiwiland.  Because of monetary concerns, all of the tracks are 'one-way’. That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!

The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.

Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.

Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops.  In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops.  In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30.  In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

Test Input:
For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

Expected Output:
Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7

 - There must be a way to supply the application with the input data via text file.
 - The application must run and you should provide sufficient evidence that your solution is complete by, as a minimum, indicating that it works correctly against the supplied test data.
 - The submission should be production quality and it can be done in any language (using JavaScript, CoffeeScript or Ruby would be a bonus).
 - You may not use any external libraries to solve this problem, but you may use external libraries or tools for building or testing purposes. Specifically, you may use unit testing libraries or build tools available for your chosen language.

trains.go

package main

import (
	"bufio"
	"encoding/csv"
	"errors"
	"fmt"
	"io"
	"os"
	"strconv"
)

// Edge struct holds node links
type Edge struct {
	weight int
	end    Node
}

// Node struct holds edges and the hash maps key for convinence
type Node struct {
	ID     byte
	weight int
	edges  []Edge
}

// Graph type
type Graph struct {
	nodes map[byte]Node
}

// NewGraph creates a graph object and inits some stuff
func NewGraph() *Graph {
	g := Graph{nodes: make(map[byte]Node)}
	return &g
}

// LoadFromFile graph def from CSV formated file, treats rows and cols as a single 1D map
func (g *Graph) LoadFromFile(fname string) error {
	f, err := os.Open(fname)
	if err != nil {
		return err
	}
	r := csv.NewReader(bufio.NewReader(f))
	for {
		record, err := r.Read()
		if err == io.EOF {
			break
		}
		for _, value := range record {
			// Sanity
			if len(value) != 3 {
				return errors.New("Input file invalid")
			}

			// Grab node ids
			a := []byte(value)[0]
			b := []byte(value)[1]

			// Grab distance weight
			w, err := strconv.Atoi(string(value[len(value)-1]))
			if err != nil {
				return err
			}

			// If nodes don't exist make sure they do
			aNode, ok := g.nodes[a]
			if !ok {
				g.nodes[a] = Node{ID: a, weight: w}
			}
			_, ok = g.nodes[b]
			if !ok {
				g.nodes[b] = Node{ID: b, weight: w}
			}

			// Populate edges
			aNode.edges = append(g.nodes[a].edges, Edge{end: g.nodes[b], weight: w})

			// Push back changes
			g.nodes[a] = aNode
		}
	}
	return nil
}

// ABDistance test
func (g *Graph) ABDistance(a, b byte) int {
	// Check for nil map(runtime errors are bad)
	if aNode, ok := g.nodes[a]; ok {
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// On match return distance
			if edge.end.ID == b {
				return edge.weight
			}
		}
	}
	return -1
}

// Distance result
func (g *Graph) Distance(stops ...byte) string {
	// Distance result
	var res int

	// Loop over variadic node list
	for i, stop := range stops[:len(stops)-1] {
		// Check if route is possible, then accumulate distance
		if t := g.ABDistance(stop, stops[i+1]); t != -1 {
			res += t
		} else {
			fmt.Println("NO SUCH ROUTE")
			return "NO SUCH ROUTE"
		}
	}

	fmt.Println(res)
	return strconv.Itoa(res)
}

// TripsCheck test
func (g *Graph) TripsCheck(a, b byte, maxhops int) (bool, int) {
	// Check for nil map(runtime errors are bad)
	if aNode, ok := g.nodes[a]; ok && maxhops > 0 {
		// Do a quick edge check
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Every populated edge is a possible path
			if a == b {
				return true, maxhops - 1
			}
		}

		// Recursive check
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			return g.TripsCheck(edge.end.ID, b, maxhops-1)
		}
	}
	return false, 0
}

// Trips result
func (g *Graph) Trips(a, b byte, minhops, maxhops int) string {
	// Number of trips
	res := 0

	// Check for nil map(runtime errors are bad)
	if aNode, ok := g.nodes[a]; ok {
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Check if path was resolved and remaining hops fits within
			// the requested paramaters
			if ok, remHops := g.TripsCheck(edge.end.ID, b, maxhops); ok {
				if minhops > 0 && remHops < (maxhops-minhops) {
					continue
				}
				res++
			}
		}
	}

	fmt.Println(res)
	return strconv.Itoa(res)
}

// RouteLengthCheck test
func (g *Graph) RouteLengthCheck(a, b byte, maxhops int) int {
	// Don't traverse ourself, just return the distance of last the node
	if a == b {
		return g.nodes[b].weight
	}

	// Check for nil map(runtime errors are bad)
	// Make sure we haven't exceeded maxhops
	if aNode, ok := g.nodes[a]; ok && maxhops > 0 {
		//fmt.Print("->", string(a), "->", string(b))
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Recursively resolve path accumulating distance
			r := g.RouteLengthCheck(edge.end.ID, b, maxhops-1)

			// A negitive value means the path could not be resolved
			if r == -1 {
				continue
			}

			return r
		}
	}
	return -1
}

// ShortestRouteLength result
func (g *Graph) ShortestRouteLength(a, b byte, maxhops int) string {
	// Route paths
	res := []int{}

	// Check for nil map(runtime errors are bad)
	if aNode, ok := g.nodes[a]; ok {
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Recursively resolve path accumulating distance
			r := g.RouteLengthCheck(edge.end.ID, b, maxhops-1)
			if r == -1 {
				continue
			}

			// Append path distance
			res = append(res, r+edge.weight)
		}
	}

	// Get smallest value
	// (could be done with search built-in but this makes less sense)
	min := 1000
	for _, v := range res {
		if v < min {
			min = v
		}
	}

	fmt.Println(min)
	return strconv.Itoa(min)
}

// PossibleRoutesCheck test
func (g *Graph) PossibleRoutesCheck(a, b byte, maxhops int, start byte, route *int) {
	// Increment previous
	if start == b {
		*route++
	}
	if aNode, ok := g.nodes[a]; ok && maxhops > 0 {
		// Traverse edges
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Increment routes if not at end of chain
			*route++

			// Continue search
			g.RouteLengthCheck(edge.end.ID, b, maxhops-1)
		}
	}
}

// PossibleRoutes result
func (g *Graph) PossibleRoutes(a, b byte, maxhops int) string {
	res := 0
	if aNode, ok := g.nodes[a]; ok && maxhops > 0 {
		// Traverse edges
		for _, edge := range aNode.edges {
			// Detect nil end
			if edge.end.ID == 0 {
				continue
			}

			// Every non-nil path, thats a route
			if a == b {
				res++
			}

			// Begin recursive search up to maxhops
			g.PossibleRoutesCheck(edge.end.ID, b, maxhops-1, a, &res)
		}
	}

	fmt.Println(res)
	return strconv.Itoa(res)
}

func main() {

}

trains_test.go

package main

import "testing"

type test struct {
	res      string
	function func(...byte) string
}

var ans = []string{"9", "5", "13", "22", "NO SUCH ROUTE", "2", "3", "9", "9", "7"}

func TestTrains(t *testing.T) {
	// Init our node graph
	g := NewGraph()

	// Populate from file
	g.LoadFromFile("graph.db")

	if r := g.Distance('A', 'B', 'C'); r != ans[0] {
		t.Error("Expected", ans[0], "got", r)
	}
	if r := g.Distance('A', 'D'); r != ans[1] {
		t.Error("Expected", ans[1], "got", r)
	}
	if r := g.Distance('A', 'D', 'C'); r != ans[2] {
		t.Error("Expected", ans[2], "got", r)
	}
	if r := g.Distance('A', 'E', 'B', 'C', 'D'); r != ans[3] {
		t.Error("Expected", ans[3], "got", r)
	}
	if r := g.Distance('A', 'E', 'D'); r != ans[4] {
		t.Error("Expected", ans[4], "got", r)
	}
	if r := g.Trips('C', 'C', 0, 3); r != ans[5] {
		t.Error("Expected", ans[5], "got", r)
	}
	if r := g.Trips('A', 'C', 4, 4); r != ans[6] {
		t.Error("Expected", ans[6], "got", r)
	}
	if r := g.ShortestRouteLength('A', 'C', 10); r != ans[7] {
		t.Error("Expected", ans[7], "got", r)
	}
	if r := g.ShortestRouteLength('B', 'B', 10); r != ans[8] {
		t.Error("Expected", ans[8], "got", r)
	}
	if r := g.PossibleRoutes('C', 'C', 30); r != ans[9] {
		t.Error("Expected", ans[9], "got", r)
	}
}