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

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 * City

**maximum**number of traffic controls between any two cities is minimal.

`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?

Oh, a graph problem.

You know the perfect language for that?

Right,

sed.Try it online!

Does not fullfill any of the boni.

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

`$ 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?

Here I go:

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.

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.

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`

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

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.

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

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`

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

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

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 AlgorithmAll graphs here are stored as adjacency lists.

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

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

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 ComplexityPrim'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 codeThe 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!

## Python3

## Results

## Bonus

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

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

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

No special collections, just Python

`dict`

s,`set`

s,`list`

s, and`tuple`

s.