daily programming logs down the river

Dec 27, 2014  

Found this problem from about a month ago. I did a sloppy job on this one – it’s correct, but mostly straight-line “C - style” code. I’ll come up with a better way to do this later, promise. Meanwhile, here’s the code.

package main

import "bufio"
import "fmt"
import "os"

type nodelabel uint8

type link struct {
	next      *node
	available int
}

type node struct {
	label    nodelabel
	links    []link
	hops     int
	capacity int
	isFinal  bool
}

type nodeset map[nodelabel]*node

func main() {
	nodes := make(nodeset)
	scanner := bufio.NewScanner(os.Stdin)
	var numNodes int
	for scanner.Scan() {
		line := scanner.Text()
		if line[0] == '#' {
			continue
		}
		if numNodes == 0 {
			fmt.Sscanln(line, &numNodes)
		} else {
			var startNode, endNode nodelabel
			var capacity int
			fmt.Sscanf(line, "%c %c %d", &startNode, &endNode, &capacity)
			n := nodes.getNode(startNode)
			next := nodes.getNode(endNode)
			l := link{next: next, available: capacity}
			n.links = append(n.links, l)
		}
	}
	finalNodeLabel := nodelabel('A') + nodelabel(numNodes-1)

	startNode := nodes.getNode('A')
	numLogs := 0
	for {
		nodes.updateHopsAndCapacities(finalNodeLabel)

		if startNode.capacity == 0 {
			break
		}
		path := startNode.sendOneLog()
		numLogs++

		// Print out path (in reverse)
		fmt.Printf("Log #%d takes ", numLogs)
		for i := len(path) - 1; i > 0; i-- {
			fmt.Printf("%c -> ", path[i])
		}
		fmt.Printf("%c -- path of %d\n", path[0], len(path))
	}
	fmt.Printf("River is now full. We could send %d logs\n", numLogs)
}

func (nodes nodeset) updateHopsAndCapacities(finalNodeLabel nodelabel) {
	for _, n := range nodes {
		n.hops = -1
	}
	for _, n := range nodes {
		n.computeHops(finalNodeLabel)
		n.capacity = 0
		for _, l := range n.links {
			n.capacity += l.available
		}
	}
}

func (n *node) sendOneLog() []nodelabel {
	if n.isFinal {
		singlePath := make([]nodelabel, 1)
		singlePath[0] = n.label
		return singlePath
	}

	// Pick shortest path
	minHops := -1
	var nextLink *link
	for i := 0; i < len(n.links); i++ {
		l := &n.links[i]
		if !l.next.isFinal && l.next.capacity == 0 {
			continue
		}
		if minHops < 0 || (l.available > 0 && l.next.hops < minHops) {
			minHops = l.next.hops
			nextLink = l
		}
	}

	path := nextLink.next.sendOneLog()

	// Update current node and link
	n.capacity--
	nextLink.available--

	// TODO: avoid making a copy here (!)
	newPath := make([]nodelabel, len(path)+1)
	copy(newPath, path)
	newPath[len(path)] = n.label
	return newPath
}

func (nodes nodeset) getNode(r nodelabel) *node {
	n, ok := nodes[r]
	if !ok {
		n = &node{label: r, isFinal: false}
		nodes[r] = n
	}
	return n
}

func (n *node) computeHops(finish nodelabel) {
	if n.hops >= 0 {
		return
	}
	if n.label == finish {
		n.hops = 0
		n.isFinal = true
		return
	}
	minHops := -1
	for _, l := range n.links {
		l.next.computeHops(finish)
		if l.available == 0 {
			continue
		}
		if minHops < 0 ||
			l.next.hops < minHops {
			minHops = l.next.hops
		}
	}
	n.hops = minHops + 1
}

It was easy to read in a formatted text file, so I did that instead of storing the specified routes and weights as a data literal. Here is the input:

# Format:
# Number of nodes on the first line
# Each subsequent line contains
# <start node> <end node> capacity
# Nodes are labelled starting with 'A'
9
A B 6
A C 2
B E 3
B D 3
D C 2
D F 1
C G 5
E H 1
E I 2
F H 1
G H 2
G I 2
H I 4

And here is how the program runs:

$ cat /tmp/logroutes  | go run src/reddit-prog/log-routes.go

Log #1 takes A -> B -> E -> I -- path of 4
Log #2 takes A -> B -> E -> I -- path of 4
Log #3 takes A -> C -> G -> I -- path of 4
Log #4 takes A -> C -> G -> I -- path of 4
Log #5 takes A -> B -> E -> H -> I -- path of 5
Log #6 takes A -> B -> D -> F -> H -> I -- path of 6
Log #7 takes A -> B -> D -> C -> G -> H -> I -- path of 7
Log #8 takes A -> B -> D -> C -> G -> H -> I -- path of 7
River is now full. We could send 8 logs.