Programming Challenge - Find path from city A to city B with least traffic controls inbetween.

Oh, a graph problem.

You know the perfect language for that?
Right, sed.

x
z
x
:x
s/$/%;%90123456789/
:y
s/(.)%((%?.)*\1)|;.*/\3\2/
ty
/\n/bz
s/^0*//
N
:z
/\n0+$/!{
        x
        N
        x
        bx
}
s/(.*)\n.*/,\1;/
x
s/^\n//
s/(\n|$)/%&/g
s/(^|\n)/:/g
:a
/[0-9]%/{
        s/ %/ 0%/g
        s/^/0@1@2@3@4@5@6@7@8@9@#/
        :b
        s/([0-9])@([^#]*#.*)(:[^:]*)\1%([^:]*)/\1@\3%\1\4\2/
        tb
        s/.@|#//g
        ba
}       
s/%0*([0-9])/\1/g
/;/be
s/^/:0 0:,0;/
:c
:d
s/(,([0-9]*);.*:)(_?[0-9]* )?\2 ([^:]*)/\1_\2 \3\4/
td
/\n/bf
s/:_[0-9]* _[^:]*//g
s/(^[^;]*)(;[^_]*)(:_[0-9]* ([0-9]*)[^:]*)/\3\1,\4\2/
s/^:_([0-9]*) ([^:,]*)([^;]*)(:\1 [0-9]*)/:_\2%\4%\3/
ba
:e
/^:_/s/^(:_[0-9]* )[^:]*(:[0-9]* ([0-9]*))/\1\3\2/
s/:_(.*;)/:\1/
s/%//g
tc
s/_|,.*//g
x
G
bd
:f
s/.*:_[^ ] ([0-9]*).*/\1/
tg
s/.*//
:g

Try it online!

Does not fullfill any of the boni.

If anyone has interest in an explanation I can give one (but tomorrow).

C++ (all bonuses)

I had a couple of other algorithms that worked (Binary search over graph connectivity), but I ultimately decided to try something that might, with minimal modification, also solve the related ČVUT FIKS challenge (or the version of it that Google Translate spit out).

The Algorithm

All graphs here are stored as adjacency lists.

1. Build a minimum spanning tree using Prim's algorithm (I originally did Kruskal's but wanted to use a heap for the bonus)

2. Find the minimum maximum of traffic controllers by performing a DFS over the minimum spanning tree from the start to the destination

3. Perform a BFS to find the shortest path that conforms to this minimum value

The reason why a minimum spanning tree magically appears and works has lots to do with the minimax path problem, but basically a minimum spanning tree always chooses the lowest edges connecting two pieces of a graph, so to minimize the maximum value going from one point to another, we should travel along the lowest edges too (along the minimum spanning tree).

The algorithm also treats the start and destination as generic variables (src and sk) and only uses them for the DFS and BFS steps. If the graph does not change, the minimum spanning tree can be reused.

Runtime Complexity

Prim's algorithm is O(M log N), the DFS is O(N), and the BFS is O(M), so the final algorithm is O(M log N).

For the related challenge, I didn't see that the paths had to also be minimal in distance, so we could ignore the BFS for an O(M log N + qN) algorithm.

The code

The code takes input formatted as above, and outputs:

One line with the minimum maximum number of traffic controllers encountered to get from 0 to n-1

One line with the shortest path that achieves that minimum

If there is no path, the program outputs -1.

Try it online!

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vii> al;
al g, tr;
int n,m;
priority_queue<ii,vii,greater<ii>> pq;
vi prm,par;
void prim(int u) {
	prm[u] = 1;
	for(int i=0;i<g[u].size();i++) {
		ii pr = g[u][i];
		int v = pr.first,cs = pr.second;
		if(!prm[v]) {pq.push(mp(cs,v));
			par[v] = u;
		}
	}
}
int dfs(int u, int p, int d, int t) {
	if(u == t) {return d;}
	for(int i=0;i<tr[u].size();i++) {
		ii pr = tr[u][i];
		int v = pr.first,cs = pr.second;
		if(v == p) continue;
		int val = dfs(v,u,max(d,cs),t);
		if(val != -1) return val;
	}
	return -1;
}
int main() {
	scanf("%d ",&n);
	scanf("%d ",&m);
	g.assign(n,vii());

	while(m--) {
		int a,b,c;
		scanf("%d %d %d ",&a,&b,&c);
		g[a].push_back(mp(b,c));
		g[b].push_back(mp(a,c));
	}
	prm.assign(n,0);
	par.assign(n,0);
	tr.assign(n,vii());
	for(int i=0;i<n;i++) {
		if(!prm[i]) {
		prim(i);
		}
		while(!pq.empty()) {
			ii pr = pq.top();pq.pop();
			int u = pr.second,cs = pr.first;
			if(!prm[u]) {
				prim(u);
				if(u != 0) {
					int v = par[u];
					tr[u].push_back(mp(v,cs));
					tr[v].push_back(mp(u,cs));
				}
			}
		}
	}
	int src = 0,sk = n-1;
	int dist = dfs(src,-1,0,sk);
	if(dist == -1) {
		printf("-1\n");return 0;
	}
	printf("%d\n",dist);
	queue<int> q;
	vector<int> p(n,-1);
	q.push(src);
	p[src] = src;
	while(p[sk] == -1) {
		int u = q.front();q.pop();
		for(int i=0;i<g[u].size();i++) {
			ii pr = g[u][i];
			int v = pr.first,cs = pr.second;
			if(cs > dist) continue;
			if(p[v] != -1) continue;
			q.push(v);
			p[v] = u;
		}
	}
	int v = sk;
	vector<int> res;
	res.push_back(v);
	while(v != src) {
		v = p[v];
		res.push_back(v);
	}
	for(int i=res.size()-1;i>=0;i--) {
		printf("%d",res[i]);
		if(i > 0) {printf(" ");}
	}
	printf("\n");
}

Python3

#!/usr/bin/env python3

"""Find solutions to a graph traversal problem.  The goal is to find the path from 
a start node to an end node where edges between nodes have a cost associated 
with them.  The best path is that which minimizes the maximum cost of the 
highest cost edge along the path.
"""

def ngrams(iterable, n=1):
    """Generate ngrams from an iterable
    
    l = range(5)
    list(l) -> [0, 1, 2, 3, 4, 5]
    list(ngrams(l, n=1)) -> [(0,), (1,), (2,), (3,), (4,)]
    list(ngrams(l, n=2)) -> [(0, 1), (1, 2), (2, 3), (3, 4)]
    list(ngrams(l, n=3)) -> [(0, 1, 2), (1, 2, 3), (2, 3, 4)]
    
    """
    return zip(*(iterable[i:] for i in range(n)))

def load(data):
    """Load graph and costs of edges from serialized data string"""
    _, _, *lines = data.splitlines()
    graph = {}
    costs = {}
    for line in lines:
        source, dest, cost = map(int, line.split())
        if source not in graph:
            graph[source] = set()
        if dest not in graph:
            graph[dest] = set()
        graph[source].add(dest)
        graph[dest].add(source)
        costs[(source, dest)] = cost
        costs[(dest, source)] = cost
    return graph, costs

def paths(graph, start=None, end=None):
    """From a given graph, generate all possible paths from the start node
    to the end node."""
    if start is None:
        start = min(graph)
    if end is None:
        end = max(graph)
    stack = [(start, [])]
    while stack:
        node, path = stack.pop()
        # normally one would use path.append(node), but we do it this way
        # because it creates a new list, instead of reusing the existing list
        path = path + [node]
        for neighbor in graph[node].difference(set(path)):
            stack.append((neighbor, path))
        if node == end and len(path) > 0:
            yield tuple(path)

def cost(path, costs):
    """Compute the cost of the most costly edge along a given path"""
    most_costly = max(ngrams(path, n=2), key=costs.get)
    return costs[most_costly], len(path)

def main(data, start=None, end=None, verbose=False):
    """Sort each path by cost in ascending order"""
    graph, costs = load(data)
    results = sorted(
        (cost(path, costs), path)
        for path in paths(graph, start=start, end=end)
    )
    if verbose:
        print('cost\tpath')
        for result in results:
            (cost_, length), path = result
            print(cost_, path, sep='\t')
    else:
        ((min_cost, length), path), *_ = results
        print(min_cost)

if __name__ == '__main__':
    import argparse
    parser = argparse.ArgumentParser(
        formatter_class=argparse.ArgumentDefaultsHelpFormatter,
        description=__doc__
    )
    parser.add_argument(
        'input',
        type=argparse.FileType('r'),
        help='input data file (use "-" to read from stdin)'
    )
    parser.add_argument(
        '-s', '--start',
        default=None,
        type=int,
        help='start node in the graph'
    )
    parser.add_argument(
        '-e', '--end',
        default=None,
        type=int,
        help='end node in the graph',
    )
    parser.add_argument(
        '-v', '--verbose',
        default=False,
        action='store_true',
        help='show verbose output'
    )
    args = parser.parse_args()
    main(
        args.input.read(),
        start=args.start,
        end=args.end,
        verbose=args.verbose
    )
    if args.input.name != '<stdin>':
        args.input.close()

Results

$ ./city_paths.py -h
usage: city_paths.py [-h] [-s START] [-e END] [-v] input

Find solutions to a graph traversal problem. The goal is to find the path from
a start node to an end node where edges between nodes have a cost associated
with them. The best path is that which minimizes the maximum cost of the
highest cost edge along the path.

positional arguments:
  input                 input data file (use "-" to read from stdin)

optional arguments:
  -h, --help            show this help message and exit
  -s START, --start START
                        start node in the graph (default: None)
  -e END, --end END     end node in the graph (default: None)
  -v, --verbose         show verbose output (default: False)
$ cat data.txt 
4
5
0 1 3
0 2 2
1 2 1
1 3 4
2 3 5
$ ./city_paths.py data.txt
4
$ ./city_paths.py data.txt -v
cost	path
4	(0, 1, 3)
4	(0, 2, 1, 3)
5	(0, 2, 3)
5	(0, 1, 2, 3)
$ ./city_paths.py data.txt -v -s 1
cost	path
4	(1, 3)
5	(1, 2, 3)
5	(1, 0, 2, 3)
$ ./city_paths.py data.txt -v -s 1 -e 0
cost	path
2	(1, 2, 0)
3	(1, 0)
5	(1, 3, 2, 0)

Bonus

Describe time complexity of your algorithm.

I think the worst case complexity is N * (N - 1) / 2 (when the graph is complete).

If multiple optimal paths exist, find the shortest one.

This was just a matter of adding the length of the paths to sort key.

Does your algorithm work without changing the core logic, if the source city and the target city is not known beforehand (it changes on each input)?

I accounted for this by parameterizing my function that searches for paths in the graph.

Do you use special collection to speed up minimum value search?

No special collections, just Python dicts, sets, lists, and tuples.