Bestimmen der Drehung des Quadrats anhand einer Liste von Punkten

19

Bei dieser Herausforderung erhalten Sie eine Liste mit Punkten. Diese Punkte liegen auf dem Umfang eines imaginären Quadrats . Ihr Ziel ist es:

  1. Wenn möglich, drucken Sie die Drehung des Quadrats aus. Dies ist ein Wert von [0, 90], wobei 0 ein Quadrat mit vertikalen und horizontalen Linien darstellt. Die Drehung ist in Grad gegen den Uhrzeigersinn anzugeben.
  2. Wenn die Drehung des Quadrats mehrdeutig ist (z. B. nur 2 Punkte erhalten), drucken Sie "Unbekannt" aus.
  3. Wenn das Erstellen eines Quadrats aufgrund der Punkte nicht möglich ist, drucken Sie "Impossible" aus.

Die Punkte, die Sie erhalten, sind garantiert einzigartig und in keiner bestimmten Reihenfolge. Sie können jedes Format verwenden, in das Sie die Liste eingeben möchten, aber für meine Beispiele haben meine Punkte das Formatx,y und durch Leerzeichen getrennt sein. Die Zahlen sind Gleitkommazahlen, und Sie können davon ausgehen, dass sie in einem Bereich liegen, den Ihre Sprache verarbeiten kann. Ihre Ausgabe sollte auf mindestens 3 Dezimalstellen genau sein und davon ausgehen, dass Ihre Sprache Gleitkommazahlen mit perfekter Genauigkeit verarbeitet.

Hier sind einige Testfälle (ich habe die meisten davon zur einfachen Visualisierung mit ganzen Zahlen erstellt, aber Ihr Programm sollte mit Gleitkommawerten umgehen können):

Unbekannte:

0,0                      
0,0 1,0        
0,0 1,0 0,1              
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

Unmöglich:

0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

Möglich (falls nicht angegeben, sollte 0 zurückgegeben werden):

0,0 1,0 2,0
0,0 0.3,0.3 0.6,0.6  (should return 45)
0,0 0.1,0.2 0.2,0.4  (should return appx 63.435 (the real value is arctan(2)))
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

Möglicherweise habe ich einige interessante Testfälle verpasst. Wenn ja, kommentieren Sie bitte, um sie hinzuzufügen.

Das ist Code-Golf, also gewinnt der kürzeste Code!

code-golf geometry Nathan Merrill
quelle
Gibt es eine Mindestgenauigkeit? Wie weit von der richtigen Antwort entfernt kann die Ausgabe sein, bevor sie als falsch gilt?
Trichoplax
@trichoplax Seien Sie so genau, wie es die Implementierung von Gleitkommazahlen in Ihrer Sprache zulässt.
Nathan Merrill
Bedeutet dies, dass bei zwei möglichen Ansätzen und einem etwas genaueren Ergebnis in Ihrer Sprache der genaueste Ansatz verwendet werden muss?
Trichoplax
@ Trichoplax ja.
Nathan Merrill
2
@ NathanMerrill Woher weiß ich (oder jemand), ob es einen genaueren Ansatz gibt? Ich denke, es wäre sinnvoller, nur eine feste Mindestgenauigkeit wie 4 oder 6 Dezimalstellen zu fordern. Obwohl ich nicht einmal sicher bin, ob die Ungenauigkeiten der Gleitkommadarstellung der Eingabe viele Beispiele unmöglich machen. Vielleicht wäre dafür eine rationale oder ganzzahlige Eingabe besser gewesen.
Martin Ender

Antworten:

6

Rev 1: Ruby, 354 Bytes

weiter golfen dank blutorange.

->a{t=s=Math::PI/18E4
d=r=c=0
a=a.map{|e|e-a[0]}
0.upto(36E4){|i|b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m,n=b
if n.min>=f=0
l=[m.max-x=m.min,n.max].max
a.each_index{|j|f+=((l-w=n[j])*(x+l-v=m[j])*(x-v)*w)**2}
(1E-9>q=f/l**8)&&(c>0&&(i-d)%9E4%89E3>1E3?c=9E9:0;c+=1;d=i)
q<t&&(r=i)&&t=q;end}
c<101&&a[1]?c<1?'impossible':r%9E4/1.0E3:'unknown'}

Ruby, 392 Bytes

->(a){
s=Math::PI/18E4
t=1
d=r=c=0
a=a.map{|e|e-a[0]}
(0..36E4).each{|i|
b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose
m=b[0]
n=b[1]
x=m.min
if n.min>=0
l=[m.max-x,n.max].max
f=0
a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
q=f/l**8
if q<1E-9
c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0
c+=1
d=i
end
if q<t
r=i
t=q
end
end
}
c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3
}

Der Algorithmus lautet wie folgt:

-Wählen Sie einen beliebigen Punkt (den ersten) und verschieben Sie diesen zum Ursprung (subtrahieren Sie die Koordinaten dieses Punktes von allen Punkten in der Liste.)

-Versuchen Sie alle Umdrehungen des Quadrats um den Ursprung in Schritten von 0,001 Grad um 360 Grad.

- Wenn bei einer bestimmten Drehung alle Punkte über der y-Achse liegen, zeichnen Sie das kleinstmögliche Quadrat um alle Punkte, einschließlich des niedrigsten und des am weitesten links liegenden Punkts.

-Überprüfen Sie, ob alle Punkte am Rand liegen. Dies geschieht mit einer weichen Berechnung, die jeden Punkt nimmt, die quadratischen Abstände von allen Kanten findet und sie miteinander multipliziert. Dies ergibt eher eine gute Übereinstimmung als eine Ja / Nein-Antwort. Es wird interpretiert, dass eine Lösung gefunden wird, wenn dieses Produkt dividiert durch die Seitenlänge ^ 8 kleiner als 1E-9 ist. In der Praxis ist dies weniger als ein Toleranzgrad.

-Die beste Anpassung wird um 90 Grad vorgenommen und als korrekter Winkel angegeben.

Derzeit gibt der Code den Wert mehrdeutig zurück, wenn mehr als 100 Lösungen gefunden werden (bei einer Auflösung von 0,001 Grad. Das sind 0,1 Grad Toleranz.)

erste voll funktionsfähige Funktion im Testprogramm

Ich habe die Auflösung auf 1/10 der erforderlichen Auflösung belassen, um die Geschwindigkeit angemessen zu machen. Im letzten Testfall ist ein Fehler von 0,01 Grad aufgetreten.

g=->(a){
 s=Math::PI/18000
 t=1
 d=r=-1
 c=0
 a=a.map{|e| e-a[0]} 

 (0..36000).each{|i| 
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose

    m=b[0]
    n=b[1]
    x=m.min

    if n.min>=0

       l=[m.max-x,n.max].max
       f=0
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}
       q=f/l**8

       if q<1E-9

         j=(i-d)%9000
         c>0&&j>100&&j<8900?(c=9E9):0 
         c+=1
         d=i
       end  

       if q<t
         r=i
         t=q
       end

     end    
  }

 print "t=",t,"   r=",r,"     c=",c,"    d=",d,"\n"
 p c>100||a.size<2?'unknown':c<1? 'impossible':r%9000/100.0   
}


#ambiguous
#g.call([Complex(0,0)])
#g.call([Complex(0,0),Complex(1,0)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
#g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
#g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
#g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
#g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
#g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

Golf-Version, Auflösung gemäß Spezifikation, dauert etwa eine Minute pro Anruf im Testprogramm.

Es gibt immer noch einen lästigen Fehler von 0,001 Grad im letzten Testfall. Eine weitere Erhöhung der Auflösung würde diese wahrscheinlich beseitigen.

g=->(a){                                                            #take an array of complex numbers as input
  s=Math::PI/18E4                                                   #step size PI/180000
  t=1                                                               #best fit found so far
  d=r=c=0                                                           #angles of (d) last valid result, (r) best fit; c= hit counter
  a=a.map{|e|e-a[0]}                                                #move shape so that first point coincides with origin
  (0..36E4).each{|i|                                                #0..360000
    b=a.map{|e|(e/Complex.polar(1,i*s)).rect}.transpose             #rotate each element by dividing by unit vector of angle i*s, convert to array... 
    m=b[0]                                                          #...transpose array [[x1,y1]..[xn,yn]] to [[x1..xn],[y1..yn]]...
    n=b[1]                                                          #...and assign to variables m and n 
    x=m.min                                                         #find leftmost point
    if n.min>=0                                                     #if all points are above x axis
       l=[m.max-x,n.max].max                                        #find the sidelength of smallest square in which they will fit
       f=0                                                          #f= accumulator for errors. For each point
       a.each_index{|j|f+=((l-n[j])*(x+l-m[j])*(x-m[j])*n[j])**2}   #...add to f the product of the squared distances from each side of the smallest square containing all points
       q=f/l**8                                                     #q= f normalized with respect to the sidelength.
       if q<1E-9                                                    #consider a hit if <1E-9
         c>0&&(i-d)%9E4%89E3>1E3?(c=9E9):0                          #if at least one point is already found, and the difference between this hit and the last exceeds+/-1 deg (mod 90), set c to a high value
         c+=1                                                       #increment hit count by 1 (this catches infinitely varible cases)
         d=i                                                        #store the current hit in d
       end  
       if q<t                                                       #if current fit is better than previous one
        r=i                                                         #store the new angle
        t=q                                                         #and revise t to the new best fit.
       end             
    end
  }
  c>100||a.size<2?'unknown':c<1? 'impossible':r%9E4/1.0E3           #calculate and return value, taking special care of case where single point given.
}
#ambiguous
puts g.call([Complex(0,0)])
puts g.call([Complex(0,0),Complex(1,0)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1)])
puts g.call([Complex(0,0),Complex(1,0),Complex(0,1),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2)])

#impossible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(3,1),Complex(4,2)])
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0),Complex(1,1)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,3),Complex(2,0),Complex(2,3),Complex(3,1),Complex(3,2),Complex(2,2)])
puts g.call([Complex(2,0),Complex(0,1),Complex(2,2),Complex(0,3)])
puts g.call([Complex(0,0),Complex(2,1),Complex(0,2),Complex(2,2),Complex(-1,1)])

#possible
puts g.call([Complex(0,0),Complex(1,0),Complex(2,0)])
puts g.call([Complex(0,0),Complex(0.3,0.3),Complex(0.6,0.6)]) #(should return 45)
puts g.call([Complex(0,0),Complex(0.1,0.2),Complex(0.2,0.4)]) #(should return appx 63.435 (the real value is arctan(2)))
puts g.call([Complex(0,0),Complex(0,1),Complex(2,1),Complex(2,2)])
puts g.call([Complex(0,1),Complex(0,2),Complex(1,0),Complex(1,4),Complex(2,0),Complex(2,4),Complex(4,1),Complex(4,3)])

Beachten Sie, dass dieser Algorithmus für etwa 30% mehr Code schnell angepasst werden könnte: Es ist offensichtlich, dass in Fällen mit einer begrenzten Anzahl von Lösungen eine der Kanten flach entlang eines Würfels liegt, sodass wir wirklich nur diese Winkel ausprobieren müssen das entspricht jedem Paar von Eckpunkten. Es wäre auch notwendig, ein bisschen zu wackeln, um zu überprüfen, ob es nicht unendlich viele Lösungen gibt.

Level River St
quelle
Ich habe den zweiten Testfall behoben, danke
Nathan Merrill
@ NathanMerrill der überarbeitete Fall 0,0 1,0 2,0 1,2ist noch möglich für ein Quadrat der Diagonale 0,0 ... 2,2. Ich habe das ausprobiert und auch 0,0 1,0 2,0 1,1(letzteres ist in der Tat unmöglich). Ein weiterer Punkt: Halten Sie es für akzeptabel oder inakzeptabel, dass mein Code nicht unbekannt, sondern unmöglich zurückgegeben wird, wenn nur ein einziger Punkt angegeben wird? Ich würde mich über eine Antwort freuen, bevor ich mit dem Golfen beginne.
Level River St
Ich wollte es tun 1,1. Ich bin mir nicht sicher, wie 1,2ich dahin gekommen bin. Es ist nicht akzeptabel.
Nathan Merrill
Sie sollten in der Lage sein, es auf mindestens 354 Bytes wie folgt zu bringen
blutorange
@blutorange danke für die tipps! Ich bin neu bei Ruby und habe einige Schwierigkeiten beim Golfen. Ich habe viele if..ends verlassen, weil ich schreckliche Probleme mit verschachtelten ternären Operatoren in Ruby habe. Ich sehe, dass Sie das umgehen, indem Sie &&.
Level River St
6

Perl

Hallo, hier ist meine bescheidene Rede. Testfälle werden im DATA- Stream am Ende der Datei abgelegt. Der Algorithmus ist durch einen Try-Error-Ansatz gewachsen.
Ich gebe zu, dass es ein allgemein heuristischer Ansatz ist, aber er ist sehr schnell: Er löst alle Fälle sofort .
Ich bin mir bewusst, dass es einige Fehler geben wird, aber bis jetzt werden alle Testfälle korrekt beantwortet.
Mir ist auch bewusst, dass der kürzeste Code gewinnt, aber ich bin mir sicher, dass dieser zu den kürzesten im Internet gehört schnellsten gehört Sinne des Begriffs gehört.

Hier ist der Algorithmus

  1. Punkte untersuchen und für jedes Segment zwischen zwei Punkten Steigung, Länge, x-Achsenabschnitt, y-Achsenabschnitt aufzeichnen

  2. Finde gerade Linien (dh drei Punkte oder zwei benachbarte Segmente) und unterscheide mögliche Steigungen (sprich Rotationen). Verfolgen Sie das längste verfügbare Segment in jeder Zeile.

  3. finden Sie alle Abstände zwischen einem Segment und einem dritten Punkt (dies sollte verwendet werden, um Punkt 4). Verfolgen Sie den Mindestabstand ungleich Null.

  4. für vier beliebige Punkte (ein raues Rechteck) finden Sie innere Punkte

Lösungen anzeigen:

A. Sagen Sie "Unmöglich", wenn es einen oder mehrere innere Punkte gibt.

B. Eine Zeile:

  • Bei den meisten Punkten in einer einzelnen Zeile ohne innere Punkte sagen Sie "Möglich".

  • Bei Punkten, die zu nahe an der Linie liegen, sagen Sie "Unmöglich".

    C. Zwei Zeilen:

  • Sagen Sie "Möglich", wenn es nur eine mögliche Drehung gibt

  • Sagen Sie "Unmöglich", wenn es mehr als eine Umdrehung gibt

    D. Keine Linien: Finden Sie eine Drehung, die zu dem um 90 ° gedrehten Segment passt

  • Sagen Sie "Möglich", wenn nur einer passt oder so viele Punkte passen.

  • Sagen Sie "Unmöglich", wenn mehr als einer passt und nicht so viele wie Punkte

  • Sagen Sie "Unbekannt", wenn so viele wie Rotation passen.

Hier ist der Code (alle bekannten Fehler sind behoben) 

#!/usr/bin/perl
use strict ;
use warnings ;
my $PI = 4*atan2( 1, 1 ) ;
my $EPS = 0.000001 ;
while ( <DATA> ) {
    if ( /^\s*#/ ) { print ; next } # print comments
    chomp ;
    my @dot = split /\s+/ ;
    my $n = scalar @dot || next ; # skip empty lines

    # too few dots
    if ( $n < 3 ) {
        print "@dot : Unknown.\n" ;
        next
    }

    my %slop = () ; # segment --> its slope
    my %leng = () ; # segment --> its length
    my %x0   = () ; # segment --> its line's x-intercept
    my %y0   = () ; # segment --> its line's y-intercept
    my %side = () ; # slope   --> list of segments (with duplicates)

    # 1. examine dots
    for my $p (@dot) {
        my ($px,$py) = split /,/, $p ;
        for my $q (@dot) {
            next if $p eq $q ;
            next if defined ( $slop{ "$q $p" } ) ;
            my $segment_name = "$p $q" ;
            my ($qx,$qy) = split /,/, $q ;
            my $dx = $px - $qx ;
            my $dy = $py - $qy ;
            my $slope = "inf" ; $slope = $dy / $dx if abs($dx) > 0 ;
            my $sd = $dx*$dx+$dy*$dy ;
            my $x0 = ( $slope eq 'inf' ? $px : "nan" ) ;
            my $y0 = ( abs($slope) > 0 ? $px : "nan" ) ;
            $x0 = $qx - $qy / $slope if abs($slope) > 0 ;
            $y0 = $qy - $qx * $slope if $slope ne "inf" ;
            push @{ $side{ $slope } }, $segment_name ;
            $slop{ $segment_name } = $slope ;
            $leng{ $segment_name } = sqrt( $sd ) ;
            $x0{ $segment_name } = $x0 ;
            $y0{ $segment_name } = $y0 ;
        }
    }

    # 2. find straight lines and distinct possible slopes (rotation)
    my %line = () ;     # slope --> segment name
    my %rotation = () ; # slope --> slope itself
    my $a_rotation ;
    for my $slope ( keys %side ) {
        my %distinct = () ;
        for my $segment_name ( @{ $side{ $slope } } ) {
            $distinct{ $segment_name } = $slope ; 
            my $rot = $slope eq 'inf' ? '0' : abs( $slope < 0 ? 1/$slope : $slope ) ;
            $rotation{ $rot } = $rot ;
            $a_rotation = $rot ;
        }
        for my $a_segm ( keys %distinct ) {
            for my $b_segm ( keys %distinct ) {
                next if $a_segm eq $b_segm ;
                # the two segment has to be adjacent
                my ($a1,$a2) = split / /, $a_segm;
                my ($b1,$b2) = split / /, $b_segm;
                next unless $a1 eq $b1 || $a1 eq $b2 || $a2 eq $b1 || $a2 eq $b2 ;
                # the two segment has to have same intercepts
                my $x0a = $x0{ $a_segm } ;
                my $x0b = $x0{ $b_segm } ;
                my $y0a = $y0{ $a_segm } ;
                my $y0b = $y0{ $b_segm } ;
                next unless $x0a eq $x0b && $y0a eq $y0b ;
                # keep the longest segment
                my $a_len = 0 ;
                $a_len = $leng{ $line{ $slope } } if defined( $line{ $slope } ) && defined( $leng{ $line{ $slope } } ) ;
                for my $segm ("$a1 $b1", "$a1 $b2", "$a2 $b1", "$a2 $b2",
                              "$b1 $a1", "$b2 $a1", "$b1 $a2", "$b2 $a2" ) {
                    next unless defined ( $leng{ $segm } ) ;
                    if ( $a_len < $leng{ $segm } ) {
                        $a_len = $leng{ $segm } ;
                        $line{ $slope } = $segm ;
                    }
                }
            }
        }
    }

    # 3. find distance between a segment and a third point
    my %distance = () ;            # segment-point --> distance
    my %distance_mani = () ;       # distance --> array of segment-point
    my %min_distance = () ;        # segment --> min distance to other dots
    for my $segment_name ( keys %slop ) {
        my $a = $slop{ $segment_name } ;
        my $b = -1 ;
        my $c = $y0{ $segment_name } ;
        my $z = $x0{ $segment_name } ;
        for my $p (@dot) {
            next if $segment_name =~ /$p/ ; # skip dots that are in the segment
            my ($px,$py) = split /,/, $p ;
            my $d = 0 ;
            if ( $a ne 'inf' ) {
                my $num = ($b * $py) + ($a * $px) + $c ;
                my $den = sqrt( $a*$a + $b*$b ) ;
                $d = abs( $num ) / $den ;
            }
            else {
                $d = abs( $px - $z );
            }
            $distance{ "$segment_name $p" } = $d ;
            push @{ $distance_mani{ $d } }, "$segment_name $p" ;
            if ( $d > 0 ) {
                $min_distance{ $segment_name } = $d if !defined ( $min_distance{ $segment_name } ) or $d < $min_distance{ $segment_name }
            }
        }
    }

    # 4. find inner dots: pick 4 dots to form a well shaped pseudo-rectangle
    #    and check for any other dot that is too close to all the 4 sides.
    my $fail = 0 ;
    RECTANGLE:
    for my $a ( @dot ) {
        for my $b ( @dot ) {
            next if $a eq $b ;
            my ($ax,$ay) = split /,/, $a ;
            my ($bx,$by) = split /,/, $b ;
            next if $ax > $bx || $ay > $by ;
            for my $c ( @dot ) {
                next if $c eq $a or $c eq $b ;
                my ($cx,$cy) = split /,/, $c ;
                next if $bx < $cx || $by > $cy ;
                for my $d ( @dot ) {
                    next if $d eq $a or $d eq $b or $d eq $c ;
                    my ($dx,$dy) = split /,/, $d ;
                    next if $cx < $dx || $cy < $dy  ;
                    next if $dx > $ax || $dy < $ay  ;
                    for my $e ( @dot ) {
                        next if $e eq $a or $e eq $b or $e eq $c or $e eq $d ;

                        my $abe = $distance{ "$a $b $e" } || $distance{ "$b $a $e" } || next ;
                        my $bce = $distance{ "$b $c $e" } || $distance{ "$c $b $e" } || next ;
                        my $cde = $distance{ "$c $d $e" } || $distance{ "$d $c $e" } || next ;
                        my $dae = $distance{ "$d $a $e" } || $distance{ "$a $d $e" } || next ;

                        my $abd = $distance{ "$a $b $d" } || $distance{ "$b $a $d" } || next ;
                        my $abc = $distance{ "$a $b $c" } || $distance{ "$b $a $c" } || next ;
                        my $bca = $distance{ "$b $c $a" } || $distance{ "$c $b $a" } || next ;
                        my $bcd = $distance{ "$b $c $d" } || $distance{ "$c $b $d" } || next ;
                        my $cdb = $distance{ "$c $d $b" } || $distance{ "$d $c $b" } || next ;
                        my $cda = $distance{ "$c $d $a" } || $distance{ "$d $c $a" } || next ;
                        my $dac = $distance{ "$d $a $c" } || $distance{ "$a $d $c" } || next ; 
                        my $dab = $distance{ "$d $a $b" } || $distance{ "$a $d $b" } || next ; 

                        if ( $abd > $abe && $abc > $abe && 
                             $bca > $bce && $bcd > $bce &&
                             $cdb > $cde && $cda > $cde &&
                             $dac > $dae && $dab > $dae) {
                            ## print "     $a $b $c $d --> $e\n";
                            $fail ++ ;
                            last RECTANGLE ;
                        }
                    }
                }
            }
        }
    }
    if ( $fail ) {
        print "@dot : Impossible.\n" ;
        next # DATA 
    }

    my $m = scalar keys %rotation ; # how many distinct slopes
    my $r = scalar keys %line ; # how many lines i.e. >3 dots in a straight line

    print "@dot : " ;
    # most of dots lie in single line without inner dots
    if ( $r == 1 ) {
        $a_rotation = (keys %line)[0] ;
        my $a_segment = $line{ $a_rotation } ;
        my $a_dist = $min_distance{ $a_segment } || 0 ;
        if ( $a_dist && $a_dist < $leng{ $a_segment } ) {
            print "Impossible.\n"  ;
        }
        else {
            print "Possible. --> " . sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" ;
        }
        next # DATA
    }
    # two lines
    if ( $r == 2 ) {
        print "Impossible.\n" if $m > 1 ;
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $m == 1 ;  # never?
        next ; # DATA
    }
    # no lines
    if ( $r == 0 ) {
        # match between segment rotation and other side
        my $count = 0 ;
        my $numeros = 0 ;
        for my $slope ( keys %rotation ) {
            my $rot = $slope eq '0' ? 'inf' : -1/$slope ;
            if ( exists $side{ $rot } ) {
                $count++ ;
                my $u = scalar @{ $side{ $rot } } ;
                if ( $numeros < $u ) {
                    $numeros = $u ;
                    $a_rotation = $slope ;
                }
            }
        }
        print "Possible. --> " .
            sprintf("%.3f deg", 180 / $PI * atan2( $a_rotation, 1 ) ) . "\n" if $count < 2 or $count == $n ;
        print "Unknown.\n"    if $count == $m ;
        print "Impossible.\n"    if $count > 2 && $count != $n && $count != $m;
        next # DATA
    }
    # there are lines
    print "lines $r " ;
    my $shorter = 0 ;
    my $longer = 0 ;
    for my $slope ( keys %line ) {
        for my $dis ( keys %distance_mani ) {
            $shorter++ ;
            $longer++ ;
        }
    }
    print "ACK! WHAT IS THIS CASE! n=$n, m=$m, r=$r\n" ;
    1 ;
}

1;

__DATA__
# Unknown:

0,0
0,0 1,0
0,0 1,0 0,1
0,0 1,0 0,1 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2

# Impossible:

0,0 1,0 2,0 3,1 4,2
0,0 1,0 2,0 1,1
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2
2,0 0,1 2,2 0,3
0,0 2,1 0,2 2,2 -1,1

# Possible (if not designated, should return 0):

0,0 1,0 2,0 1,2
0,0 1,0 2,0 0.5,2.1

0,0 1,0 2,0
0,0 1,0 2,0 1,2
0,0 0.3,0.3 0.6,0.6
0,0 0.1,0.2 0.2,0.4
0,0 0,1 2,1 2,2
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3

Und hier ist seine Ausgabe

# Unknown:
0,0 : Unknown.
0,0 1,0 : Unknown.
0,0 1,0 0,1 : Unknown.
0,0 1,0 0,1 1,1 : Unknown.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 : Unknown.
# Impossible:
0,0 1,0 2,0 3,1 4,2 : Impossible.
0,0 1,0 2,0 1,1 : Impossible.
0,1 0,2 1,0 1,3 2,0 2,3 3,1 3,2 2,2 : Impossible.
2,0 0,1 2,2 0,3 : Impossible.
0,0 2,1 0,2 2,2 -1,1 : Impossible.
# Possible (if not designated, should return 0):
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 1,0 2,0 0.5,2.1 : Possible. --> 0.000 deg
0,0 1,0 2,0 : Possible. --> 0.000 deg
0,0 1,0 2,0 1,2 : Possible. --> 0.000 deg
0,0 0.3,0.3 0.6,0.6 : Possible. --> 45.000 deg
0,0 0.1,0.2 0.2,0.4 : Possible. --> 63.435 deg
0,0 0,1 2,1 2,2 : Possible. --> 0.000 deg
0,1 0,2 1,0 1,4 2,0 2,4 4,1 4,3 : Possible. --> 0.000 deg

Grüße.

Matteo.

Mattstahl
quelle
Hier ist der erste Fehler: Ihr Fall 0,0 1,0 2,0 1,1 (Unmöglich) wird von meinem Skript als "Möglich. -> 0,000 Grad" bezeichnet. Ich muss reparieren
Mattsteel
Ich mag diese Lösung wirklich. Machen Sie sich keine allzu großen Sorgen um den Code Golf, darum geht es bei der Herausforderung nicht wirklich, und es ist nicht unbedingt die Person, die das Kopfgeld bekommt.
Nathan Merrill
Vielen Dank, Nathan. Die Ausgabe zeigt viel mehr Informationen: Diese sind für Debug-Zwecke und ich habe sie absichtlich verlassen, um in der Lage zu sein, zu beheben
Mattsteel
Zweiter Fehler: Ein falsches "Unmöglich. (Keine Zeilen) n = 8, m = 6, r = 0 c = 6" wird direkt nach der richtigen Antwort "0,1 0,2 1,0 1,3 2,0" geschrieben 2,3 3,1 3,2: Unbekannt (keine Linien) n = 8, m = 6, r = 0 c = 6 ".
Mattsteel
Zwei Fehler behoben: Alle Fälle funktionieren jetzt einwandfrei.
Mattsteel