14
1
You are provided a set of arbitary, unique, 2d, integer Cartesian coordinates: e.g. [(0,0), (0,1), (1,0)]
Find the longest path possible from this set of coordinates, with the restriction that a coordinate can be "visited" only once. (And you don't "come back" to the coordinate you started at).
Important:
You cannot "pass over" a coordinate or around it. For instance, in the last note example (Rectangle), you cannot move from D to A without visiting C (which may be a revisit, invalidating the length thus found). This was pointed out by @FryAmTheEggman.
Function Input: Array of 2d Cartesian Coordinates
Function Output: Maximum length only
Winner: Shortest code wins, no holds barred (Not the most space-time efficient)
Examples
1: In this case shown above, the longest path with no coordinate "visited" twice is A -> B -> O (or O-B-A, or B-A-O), and the path length is sqrt(2) + 1 = 2.414
2: In this case shown above, the longest path with no coordinate "visited" twice is A-B-O-C (and obviously C-O-B-A, O-C-A-B etc.), and for the unit square shown, it calculates to sqrt(2) + sqrt(2) + 1 = 3.828.
Note: Here's an additional test case which isn't as trivial as the two previous examples. This is a rectangle formed from 6 coordinates:
Here, the longest path is: A -> E -> C -> O -> D -> B, which is 8.7147
(max possible diagonals walked and no edges traversed)
Here's a very similar question, albeit with different scoring.
– Geobits – 2016-02-19T14:40:33.903@Geobits Agreed, but I'd not say "very", having gone through the problem description there. And for that matter, any min/max path problem is essentially some flavor of your usual graph suspects. I'm interested in a byte saving solution here. – BluePill – 2016-02-19T14:43:50.570
@Fatalize Done. It's 8.7147. – BluePill – 2016-02-19T15:13:42.057
By the way: Welcome to PPCG! – Fatalize – 2016-02-19T15:14:50.040
@Fatalize Thank you! (Actually I've been an observer here for a while, just got active and into the whole thing starting today). :) – BluePill – 2016-02-19T15:15:49.507