Foo meets Bar and the wizardly trio

Will Foo and Bar meet?

Once upon a time, Foo and Bar went on holiday, separately, to the same city. We know the day each of them arrived and left, and are asked how many days they had fun together.

When I was a lad, the IBM System/360 series computers were the latest thing. Amazingly, they were the first machines I used that had access to the current date and time, and equally amazingly, that data wasn't accessible to Fortran code, though I think it could be retrieved in Cobol. 

I prevailed on someone to write a Fortran-accessible subroutine in assembler, and annoyed the computer staff having it on binary coded punched cards which only their newest card reader could cope with.

But I digress. The date on these machines was held as a 5 digit number such as 65365, which meant the 365th day of 1965, ie 31 December 1965. And annoying though that was at the time, it comes in useful this week. We're told that our pair's holidays both started and ended in the same year, so let's convert their start and end dates to days since the start of the year numbers, ie 1 (1 January) to 365 (31 December).

Now we can easily see that the overlap is the later of their start dates to the earlier of their end dates, and its duration is simply the difference between these two day numbers, plus 1 - and if that is less than zero then - bad luck, Foo and Bar.

Magical triplets

In task 2, we are asked to write a script to find the triplet (a, b, c) from a given list that satisfies the following rules.

1. a + b > c
2. b + c > a
3. a + c > b
4. a + b + c is maximum.
5. If we end up with more than one triplet having the maximum then we pick the triplet where a >= b >= c.

My first approach to this was to use Algorithm::Combinatorics to get all the possible triplets, filter out the ones that satisfy rules 1, 2 and 3, and find which of these maximises a + b + c.  In my submission that is Method 1 and it certainly works.

However, there is an easier way - my Method 2:

1. Sort the supplied list into reverse order
2. Suppose the first three items are now m, n and o.
3. If o is greater than m - n, then we have the solution - output it and stop
4. If not, discard the first item in the list and if there are still at least 3 items in the list go back to step 2.
5. If you get here, there is no solution.

Why does this work?

In a reverse sorted list, the first three numbers are the three largest in the list, and clearly their sum is the largest possible triplet sum, so that's rule 5 taken care of.

For any three reverse sorted numbers m, n and o, rules 1 and 3 will always be satisfied because any sum involving m is already larger than o, so we only need to do test 2. If that succeeds, we have the solution, because no subsequently found triplet will have a larger sum.

If it fails, then no solution can contain m, because if n + o doesn't exceed m then no other pair will. So we can discard m and work on the next triplet (n, o and p) in the same way.