Sie erhalten einen Satz willkürlicher, eindeutiger, 2d ganzzahliger kartesischer Koordinaten: zB [(0,0), (0,1), (1,0)]

Finden Sie aus diesem Satz von Koordinaten den längsten möglichen Pfad, mit der Einschränkung, dass eine Koordinate nur einmal "besucht" werden kann. (Und Sie "kommen" nicht zu der Koordinate zurück, bei der Sie angefangen haben).

Wichtig:

Sie können eine Koordinate oder deren Umgebung nicht "überfahren". Zum Beispiel können Sie im letzten Notenbeispiel (Rechteck) nicht von D nach A wechseln, ohne C zu besuchen (was ein erneuter Besuch sein kann und die so gefundene Länge ungültig macht). Dies wurde von @FryAmTheEggman darauf hingewiesen.

Funktionseingabe: Array von 2d kartesischen Koordinaten.
Funktionseingabe: Nur maximale Länge.
Gewinner: Kürzester Code gewinnt, kein Halten ausgeschlossen (nicht der platzsparendste).

Beispiele

1 : In diesem oben gezeigten Fall ist der längste Pfad ohne zweimal "besuchte" Koordinate A -> B -> O (oder OBA oder BAO) und die Pfadlänge ist sqrt (2) + 1 = 2,414

2 : In diesem oben gezeigten Fall ist der längste Pfad ohne zweimal "besuchte" Koordinate ABOC (und offensichtlich COBA, OCAB usw.), und für das gezeigte Einheitsquadrat wird zu sqrt (2) + sqrt (2) + gerechnet 1 = 3,828.

Hinweis: Hier ist ein zusätzlicher Testfall, der nicht so einfach ist wie die beiden vorherigen Beispiele. Dies ist ein Rechteck aus 6 Koordinaten:

Hier ist der längste Pfad: A -> E -> C -> O -> D -> B, der 8.7147 beträgt
(maximal mögliche Diagonalen und keine überquerten Kanten)

Pyth, 105 103 100 92 86 Bytes

V.pQK0FktlNJ.a[@Nk@Nhk)FdlNI&!qdk&!qdhkq+.a[@Nk@Nd).a[@Nd@Nhk)J=K.n5B)=K+KJ)IgKZ=ZK))Z

              Z = 0 - value of longest path
              Q = eval(input())

V.pQ         for N in permutations(Q):
  K0           K = 0 - value of current path
  FktlN        for k in len(N) - 1:
    J.a          set J = distance of
    [@Nk                 Q[k] and Q[k+1]
    @Nhk)    
    FdlN         for d in len(N):
I&                 if d != k && d != (k + 1)
!qdk
&!qdhk
q+                and if sum of
.a                   distance Q[k] and Q[d]
 [@Nk                
 @Nd)                
.a                   distance Q[d] and Q[k+1]
 [@Nd
 @Nhk)
J                    are equal to J then
  =K.n5              set K to -Infinity
  B                  and break loop
                     ( it means that we passed over point )
  )                   end of two if statements
=K+KJ                  K+=J add distance to our length
)                      end of for
IgKZ                   if K >= Z - if we found same or better path
  =ZK                  Z = K       set it to out max variable
))                     end of two for statements
Z                      output value of longest path 

Probieren Sie es hier aus!

Mathematica, 139 Bytes

Max[Tr@BlockMap[If[1##&@@(Im[#/#2]&@@@Outer[#/Abs@#&[#-#2]&,l~Complement~#,#])==0,-∞,Abs[{1,-1}.#]]&,#,2,1]&/@Permutations[l=#+I#2&@@@#]]&

Testfall

%[{{0,0},{0,1},{1,0},{1,1},{2,0},{2,1}}]
(* 3 Sqrt[2]+2 Sqrt[5] *)

%//N
(* 8.71478 *)

Perl, 341 322 318 Bytes

sub f{@g=map{$_<10?"0$_":$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/../g}glob"{@g}"x(@i=@_);map{@c=/../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)and$v=0 for 0..$#c}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)}

Der Code unterstützt bis zu 100 Punkte. Da alle möglichen Punktpermutationen erzeugt werden, benötigen 100 Punkte mindestens 3,7 × 10 ¹³⁴ Yottabyte Speicher (12 Punkte benötigen 1,8 GB).

Kommentiert:

sub f {
    @g = map { $_<10 ? "0$_" : $_ } 0..$#_; # generate fixed-width path indices
    $" = ',';                               # set $LIST_SEPARATOR to comma for glob
    @l = grep {                             # only iterate paths with unique points
        "@g" eq join $", sort /../g         # compare sorted indices with unique indices
    } glob "{@g}" x (@i=@_);                # produce all permutations of path indices
                                            # and save @_ in @i for sub d
    map {
        @c = /../g;                         # unpack the path indices
        $s=0;                               # total path length
        $v=1;                               # validity flag
        for $k (1..$#c) {                   # iterate path
            $s +=                           # sum path length
                $D = d( $k-1, $k );         # line distance 

              $_!=$k && $_!=$k-1            # except for the current line,
              && $D == d( $_, $k )          # if the point is on the line,
                     + d( $_, $k-1 )
              and $v = 0                    # then reset it's validity
            for 0 .. $#c                    # iterate path again to check all points
        }
        $m=$s if $m<$s && $v                # update maximum path length
    } @l;
    $m                                      # return the max
}

sub d {                                     
    @a = @{ $i[$c[$_[0]]] };                # resolve the index $_[0] to the first coord
    @b = @{ $i[$c[$_[1]]] };                # idem for $_[1]
    sqrt( ($a[0] - $b[0])**2       
        + ($a[1] - $b[1])**2 )      
}

Testfälle:

print f( [0,1], [0,0], [1,0] ), $/;        $m=0; # reset max for next call
print f( [0,0], [0,1], [1,0], [1,1] ), $/; $m=0;
print f( [0,0], [0,1], [0,2] ), $/;        $m=0;
print f( [0,0], [0,1], [0,2], 
         [1,0], [1,1], [1,2]),$/;          $m=0;

• 322 Bytes: Sparen Sie 19 Bytes , indem Sie nicht zurücksetzen $", und einige Inlinings
• 318 Bytes: Sparen Sie 4, indem Sie die maximale Anzahl der Koordinaten auf 100 reduzieren.