# Prune connections

John is writing a program that finds the best route from A to B using public transport. For a given pair of origin and destination the program calculates a set of routes with departure time and arrival time, such as this:

10:12 11:45
10:15 11:50
10:22 12:05
10:25 12:00


As you see, the output may include a few routes that are superfluous in the sense that there is another route that starts later and ends earlier. Such routes are certainly never wanted by the user since he cat get out later to arrive sooner.

Your task, if you choose to accept it, is to write a program that prunes a set of routes such that all superfluous rules are eliminated.

## Input

The input is a list of newline separated pairs of whitespace separated departure and arrival time in military format (hh:mm). Such a pair is called a route.

You may assume that all times are in the same day and that the arrival time is always later than the departure time. You may also assume that the list is orderer by departure times.

## Output

The output is the same list as the input without redundant routes. A redundant route is a route for which another route exists in the list that has a later departure and an earlier arrival time. There must exist an order to remove all redundant routes such that in each step you can show the route that makes the removed route redundant. You don't have to output that order.

## Extra credit

Prove or disprove that for each list of input routes there exists exactly one set of output routes.

## Restriction

• Usual codegolf rules apply

## Scoring

To score, apply the function that gives an upper bound to your solutions complexity with your solution's total number of characters. Normalize your bounding function such that a solution length of two character yields a score of two.

For example, if your solution has 24 characters and a complexity of O(2n), your score is 4194304. If your solution has 123 characters and a complexity of O(n2) your score is 7564. If your solution has 200 characters and a complexity of O(n*logn), your score is 734.

I use this scoring method in order to encourage people to implement efficient solutions.

• The proof of uniqueness is trivial: this is a special case of identifying maximal elements in a poset. – Peter Taylor Dec 11 '12 at 13:06
• that starts later and ends earlier - Surely you mean starts earlier and ends later? – Leigh Dec 11 '12 at 14:44
• @Leigh I hope I fixed the confusion. – FUZxxl Dec 11 '12 at 14:46
• @FUZxxl Not sure if it's just me who was confused then :) - I'm of the opinion that a route that starts later and ends earlier gives a wholly shorter journey time overall, and is therefore more desirable to the traveller. Your wording indicates (possibly just to me...) that these shorter routes are the superfluous ones. Possibly a bit of ambiguity around the "Such routes", perhaps. – Leigh Dec 11 '12 at 14:51
• How about: " As you see, the train schedule may include superfluous departure-arrival options. A departure-arrival Option A is superfluous if there exists another option, B, that departs after A yet arrives before A. Your task is to identify and remove superfluous options from the train schedule." – DavidC Dec 11 '12 at 15:30

### GolfScript, 26 characters, 26 score

n%-1%{6>[0$m]$0=:m=},-1%n*


The solution assumes a list sorted on departure time on input (as noted in the problem description) and also prints a sorted list (if this restriction can be dropped we may save 3 chars).

The code traverses the list backwards and removes any connection where the arrival time is larger than the minimum arrival time processed so far.

n%            # split input at newlines
-1%           # reverse list
{             # filter list...
6>         # take arrival time of current item
[0$m] # make an array consisting of that arrival time and the minimum # up to now, contained in variable m. Note since m is not initialized # the array will consist of a single item in the first iteration$          # sort that array (consisting of one or two items)
0=         # take first item, i.e. minimum arrival time
:m         # save to variable m
=          # compare current item to m and select if both are equal
},            # ... end of filter list
-1%           # reverse list again
n*            # join items with newline


The code can be tested online.

• Elegant and functional. – primo Dec 13 '12 at 16:14

## Perl 47 (+1) bytes • O(n) ⇒ 48 score

$#a-=2until$a[-/ \K/]lt$';push@a,$,$'}{print@a  Adding one byte for the -n option, as per the OP's instructions. Sample input: 10:30 11:00 10:33 11:18 10:42 11:10 10:47 11:18 10:49 11:26 10:50 11:09 11:00 11:20 11:01 11:28 11:11 11:31 11:21 11:49 11:23 11:53 11:29 12:09 11:36 12:08 11:41 12:15 11:46 12:06 11:53 12:23 11:56 12:32 12:01 12:30 12:04 12:47 12:05 12:25  Sample output: $ perl -n prune-connections.pl < in.dat
10:30 11:00
10:50 11:09
11:00 11:20
11:01 11:28
11:11 11:31
11:21 11:49
11:23 11:53
11:46 12:06
11:53 12:23
12:05 12:25


Input generator (PHP):

<?php
for($t = strtotime('10:30'); 20 >$i; $i++) {$r = rand(15, 45)*60;
echo date('H:i', $t), ' ', date('H:i',$t+$r), PHP_EOL;$t += rand(0, 10)*60;
}
?>


Lemma:
If a route is invalidated by some other route where , and no other route between and invalidates , then invalidates all routes from to .

Because the routes are sorted by departure time, and , must necessarily have a later departure time than . Then, in order to invalidate , needs only to have an earlier arrival time. If there were a route between and which was not invalidated by , it would have an earlier arival time than , and hence, would have already invalidated .

Therefore, a linear time algorithm, which only checks if the current route invalidates the previous route is sufficient to solve the problem. When an invalidation is found, the route before the invalidated route must also be checked, until a route is not invalidated (or no valid routes remain). Because a route can only be invalidated once, no more than routes will be invalidated in this manner.

Note that it is important that the invalid routes actually be removed from the list. If they are simply marked invalid (or set to null, etc.), this will result in complexity, in the case that each new route invalidates all previous routes.

Proof that only one solution exists follows directly from the law of transitivity. If a route is invalidated by , and is invalidated by , is also invalidated by . In order for multiple solutions to exist, it must be possible to invalidate without invalidating , but any route that invalidates will also invalidate , and will lead to the same solution.

## Python 82 • O(n) = 82

New to code golfing. Dunno if I am breaking any rules.

i=-1
while len(a)>-i:
if a[i][6:]<a[i-1][6:]:a.pop(i-1)
else:i-=1
print ''.join(a)


The algorithm is to iterate from the back of the list, removing the previous line if it has a later arrival time or moving the pointer to the previous line otherwise.

Note: The definition of redundant routes given by the OP is taken to the word, so neither of the two routes which have the same arrival times but different departure times are removed.

• In Python list.pop() is O(n) operation. So this program is O(n^2) in worst case. – AMK Dec 14 '12 at 12:32

## APL 10757 52 . O(n) = 52

T m
r←m
m←⍎(,0 5↓m)~':'
l:m←(n←(2≤/m),1)/m
r←n⌿r
→(~×/n)/l
r


The input m variable could be simply typed in as follows for the first example below:

m←4 11⍴'10:12 11:4510:15 11:5010:22 12:0510:25 12:00'


or it could be read in programatically from a number of sources eg text file.

The line before the start of the loop converts the character input (m) of arrival times to 4 digit numbers. The loop is then using sequential ≤ on those times to do the pruning. Tested on the following:

10:12 11:45  10:12 11:45  10:12 11:45  10:12 11:45
10:15 11:50  10:15 11:50  10:15 11:50  10:15 11:50
10:22 12:05  10:22 12:05  10:22 12:05  10:22 12:05
10:25 12:00  10:25 12:00  10:25 12:00  10:25 12:00
===========  10:30 11:55  10:30 11:55  10:30 11:55
10:12 11:45  ===========  10:35 12:10  10:35 12:10
10:15 11:50  10:12 11:45  ===========  10:40 11:40
10:25 12:00  10:15 11:50  10:12 11:45  ===========
10:30 11:55  10:15 11:50  10:40 11:40
10:30 11:55
10:35 12:10

• I don't speak APL, but judging by the English that's O(n squared), giving a score of 11449. – histocrat Dec 11 '12 at 17:28
• @histocrat If you accept primo's explanation of the solution then it is O(n). – Graham Dec 11 '12 at 18:27
• I'm curious how to test this solution. I've tried running this code (assuming that m is the variable that needs to be assigned to the input?), but running it on this online apl interpreter produces the runtime error Symbol 'T' referenced before assignment. Have I missed something? – primo Dec 13 '12 at 7:31
• @primo That interpreter does not implement the full set of APL functions. It is failing on the third line of code with error: Function ⍎ Execute is not implemented. In your example the result of that line is effectively m←1145 1150 1205 1200` – Graham Dec 13 '12 at 10:33
• @Graham what would be your recommendation for testing this solution (or any other APL solution, for that matter)? – primo Dec 13 '12 at 10:42