13 votes

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

Previous challenges

Hi, it's been very long time from last Programming Challenge, and I'd like to revive the tradition.

The point of programming challenge is to create your own solution, and if you're bored, even program it in your favourite programming language. Today's challenge isn't mine. It was created by ČVUT FIKS (year 5, season 2, challenge #4).

You need to transport plans for your quantum computer through Totalitatia. The problem is, that Totalitatia's government would love to have the plans. And they know you're going to transport the computer through the country. You'll receive number N, which denotes number of cities on the map. Then, you'll get M paths, each going from one city to another. Each path has k traffic controls. They're not that much effective, but the less of them you have to pass, the better. Find path from city A to city B, so the maximum number of traffic controls between any two cities is minimal. City A is always the first one (0) and city B is always the last one (N-1).

Input format:

N
M
A1 B1 K1
A2 B2 K2
...

On the first two lines, you'll get numbers N (number of cities) and M (number of paths). Than, on next M lines, you'll get definition of a path. The definition looks like 1 2 6, where 1 is id of first city and 2 is id of second city (delimited by a space). You can go from city 1 to city 2, or from city 2 to city 1. The third number (6) is number of traffic controls.

Output format:

Single number, which denotes maximum number of traffic controls encountered on one path.

Hint: This means, that path that goes via roads with numbers of traffic controls 4 4 4 is better than path via roads with numbers of traffic controls 1 5 1. First example would have output 4, the second one would have output 5.

Example:

IN:

4
5
0 1 3
0 2 2
1 2 1
1 3 4
2 3 5

OUT:

4

Solution: The optimal path is either 0 2 1 3 or 0 1 3.

Bonus

  • Describe time complexity of your algorithm.
  • If multiple optimal paths exist, find the shortest one.
  • 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)?
  • Do you use special collection to speed up minimum value search?

Hints

Special collection to speed up algorithm

5 comments

  1. [3]
    mironimous Link
    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...

    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).

    11 votes
    1. [2]
      Soptik Link Parent
      $ man sed O_o You spent too much time asking "can I", instead of "should I". That's pretty impressive! I can't imagine how it could be done. Would you mind describing how it works?

      Oh, a graph problem.

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

      $ man sed

      sed - stream editor for filtering and transforming text

      O_o

      You spent too much time asking "can I", instead of "should I".

      That's pretty impressive! I can't imagine how it could be done. Would you mind describing how it works?

      6 votes
      1. mironimous Link Parent
        Here I go: x z x Basically, sed has two buffers, the main pattern buffer and a hold buffer. The pattern buffer is cleared each new cycle, but the hold buffer not, so I exchange those, clear the...
        • Exemplary x2

        Here I go:

        x
        z
        x
        

        Basically, sed has two buffers, the main pattern buffer and a hold buffer.
        The pattern buffer is cleared each new cycle, but the hold buffer not, so I exchange those, clear the buffer and exchange them again.

        :x
        s/$/%;%90123456789/
        :y
        s/(.)%((%?.)*\1)|;.*/\3\2/
        ty
        

        This puts a % at the end and decrements any decimal number with a % after it - sed doesn't have any concept of numbers, so I have to do it manually.
        For example, 5531% gets turned into 5530 and 30% would get turned into 3%9, which gets turned into 29.
        Since the first line is the number of cities, we get the name of the last city.

        /\n/bz
        s/^0*//
        N
        :z
        /\n0+$/!{
                x
                N
                x
                bx
        }
        

        sed doesn't have any more control flow than "branch to label", "branch to label if previous substitution successful" and running a code of block if a pattern matches.
        But I would like to reuse the decrement routine for the second line to repeat getting a line as long as it isn't zero.

        So we look if we have a newline in the buffer (/\n/bz branches to :z if we do see a newline) - if we don't, we know we are still on the first line, so we remove the zeros in front of the first number to normalize it (s/^0*//) and get a newline (N).
        In any case, we have now a second number in our buffer, so we check if it is zero, and if not we get a new line into our hold buffer (x;N;x;) and decrement the second number (bx - branching to :x).

        s/(.*)\n.*/,\1;/
        x
        s/^\n//
        s/(\n|$)/%&/g
        s/(^|\n)/:/g
        

        This prepares everything for the actual algorithmic phase.
        First, we don't need the second number anymore, so we remove it and format the first number so it is of the form ,n; - it is needed later.

        Then we switch to the other buffer with the edges, which now becomes our main buffer.
        We remove the newline at the very beginning, which we don't need, and put a % after every number of traffic controls.
        Finally, we change every record to be of the form :id1 id2 weight, which removes the need for newlines that are annoying to handle.

        Our pattern space now looks like :0 1 3%:0 2 2%:1 2 1%:1 3 4%:2 3 5%

        :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
        }
        

        This is a sorting routine that sorts every record beginning with : that has a % behind a number.
        Again, sed doesn't understand numbers, so we have to implement the sorting ourselves.
        Comparison is pretty hard in sed, but pattern matching is easy, so we use radix sort.
        Each loop, it moves each of the records with a n% (with n being a single digit) to the corresponing n@ at the beginning and moves the % one to the left and pad 0 as needed.
        We are finished if there are no % signs with numbers in front of it left.

        In the context of the control flow, we have now sorted the edges in ascending order of traffic controls.

        s/%0*([0-9])/\1/g
        /;/be
        s/^/:0 0:,0;/
        

        We remove the leftover % signs and remove the superfluous 0s in front of the numbers we just sorted (s/%0*([0-9])/\1/g).
        If we find a ;, we jump to :e - we do not have a ; in pattern space right now, but it is needed later, as we also use the sorting routine for finding the minimum of two numbers.
        Finally, we put :0 0:,0; at the beginning.
        The :0 0 is the value for getting from 0 to 0 (first of the tuple) - 0 (second of the tuple).

        Next, we use prim's algorithm to use the minimum spanning tree for finding the minimum.
        The ,0; is a list of the vertices included in our spanning tree - right now, only 0.

        :d
        s/(,([0-9]*);.*:)(_?[0-9]* )?\2 ([^:]*)/\1_\2 \3\4/
        td
        /\n/bf
        s/:_[0-9]* _[^:]*//g
        

        This marks all edges that contain the number immediately in front of the semicolon (0 for the first run) with a _ in front of the id and - if it is the second id of the pair - swaps the ids.
        If there's a newline, we branch to :f (we use it again later for finding the record with the last city).
        If there is a edge with two marks, we all ready have both vertices in our tree so we delete it.

        s/(^[^;]*)(;[^_]*)(:_[0-9]* ([0-9]*)[^:]*)/\3\1,\4\2/
        s/^:_([0-9]*) ([^:,]*)([^;]*)(:\1 [0-9]*)/:_\2%\4%\3/
        ba
        :e
        

        The first line searches for the first edge with a record that is marked - so the one with the lowest weight that already has a vertex in the spanning tree (this is how Prim's algorithm works)
        It also moves the edge to the front and adds the unmarked vertex to the end of the vertex list so that edges containing it are marked next.

        The second line takes the edge of the form :_n m w and turns it into :_m w%:n v%, where we get the v from the list of getting from 0 to n that we have at the front (remember the :0 0 record).

        We then jump to :a to sort those and continue at :e.

        /^:_/s/^(:_[0-9]* )[^:]*(:[0-9]* ([0-9]*))/\1\3\2/
        s/:_(.*;)/:\1/
        s/%//g
        tc
        

        If the marked record is at the front, we know that the edge going from n to m has a lower weight than getting from 0 to n, so going from 0 to m has the same weight as going from 0 to n, so we substitute in that case :_m w% to :_m v%.
        We then unmark it and remove the percents and, if any of the substitutions have been successful, we repeat everything from :c.

        s/_|,.*//g
        x
        G
        bd
        :f
        s/.*:_[^ ] ([0-9]*).*/\1/
        tg
        s/.*//
        :g
        

        This is the end to output the record containing the last city.
        First, we remove everything after the first comma - so the vertices and leftover edges.
        We then get the last city name from the hold buffer and search for it using the marking substitution (remember that we formatted it to ,n;)
        If it is not present, we output nothing, else we output the weight for it.

        13 votes
  2. Hvv Link
    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...

    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");
    }
    
    8 votes
  3. onyxleopard (edited ) Link
    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...

    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.

    6 votes