Überlappender Kreis

16

Sie sollten ein Programm oder eine Funktion schreiben, die bei einem Quadrat Nmit Ngleichem Abstand und einem Vollkreis die Anzahl der Gitterquadrate ausgibt oder zurückgibt, die teilweise oder vollständig vom Vollkreis überlappt werden.

Überlappungen der Größe 0 (dh wenn der Kreis nur eine Linie berührt) werden nicht gezählt. (Diese Überlappungen treten zB auf N = 10.)

Beispiel

N = 8 (64 squares), Slices = 60

[Imgur] (http://i.imgur.com/3M1ekwY.png)

Eingang

  • Eine ganze Zahl N > 0. (Das Gitter wird N * NQuadrate haben.)

Ausgabe

  • Eine Ganzzahl, die Anzahl der durchgezogenen Kreisscheiben.

Beispiele

(Eingabe-Ausgabe-Paare)

Inputs:  1 2 3  4  5  6  7  8  9 10  11  12  13  14  15
Outputs: 1 4 9 16 25 36 45 60 77 88 109 132 149 172 201

Dies ist Code-Golf, also gewinnt der kürzeste Einstieg.

randomra
quelle
Liegt es nur an mir oder fehlt allen hier die naheliegende Lösung? Edit: Macht nichts. Das sah zunächst einfach aus N^2.
nyuszika7h

Antworten:

5

Pyth, 27 26

-*QQ*4lfgsm^d2T*QQ^%2_UtQ2

Probieren Sie es online aus: Pyth Compiler / Executor

Ich benutze ein 2Nx2NGitter und zähle überlappende 2x2Quadrate. Das ist etwas kürzer, da ich den Radius schon kenne N.

Und eigentlich zähle ich die überlappenden Quadrate nicht. Ich zähle die nicht überlappenden Quadrate des zweiten Quadranten, multipliziere die Zahl mit 4 und subtrahiere das Ergebnis von N*N.

Erklärung zur 27-Lösung:

-*QQ*4lfgsm^-Qd2T*QQ^t%2UQ2   implicit: Q = input()
                     t%2UQ    generates the list [2, 4, 6, ..., Q]
                    ^     2   Cartesian product: [(2, 2), (2, 4), ..., (Q, Q)]
                              These are the coordinates of the right-down corners
                              of the 2x2 squares in the 2nd quadrant. 
       f                      Filter the coordinates T, for which:
        gsm^-Qd2T*QQ             dist-to-center >= Q
                                 more detailed: 
          m     T                   map each coordinate d of T to:
           ^-Qd2                       (Q - d)^2
         s                          add these values
        g        *QQ                 ... >= Q*Q
    *4l                       take the length and multiply by 4
-*QQ                          Q*Q - ...

Erklärung für die 26 Lösung:

Mir ist aufgefallen, dass ich die Koordinaten nur einmal benutze und die Koordinaten sofort von subtrahiere Q. Warum nicht einfach die Werte Q - coordsdirekt generieren ?

Das passiert in %2_UtQ. Nur ein Zeichen größer als in der vorherigen Lösung und spart 2 Zeichen, weil ich nicht subtrahieren muss -Q.

Jakube
quelle
6

Python 2, 72

lambda n:sum(n>abs(z%-~n*2-n+(z/-~n*2-n)*1j)for z in range(~n*~n))+n+n-1

Ungolfed:

def f(n):
    s=0
    for x in range(n+1):
        for y in range(n+1):
            s+=(x-n/2)**2+(y-n/2)**2<(n/2)**2
    return s+n+n-1

Das Gitter zeigt auf ein (n+1)*(n+1)Quadrat. Eine Zelle überlappt den Kreis, wenn der dem Mittelpunkt am nächsten liegende Gitterpunkt innerhalb des Kreises liegt. Wir können also Gitterpunkte zählen, außer dass 2*n+1Gitterpunkte an den Achsen fehlen (sowohl für gerade als auch für ungerade n). Deshalb korrigieren wir dies manuell.

Der Code speichert Zeichen, indem komplexe Abstände zur Berechnung des Abstands zur Mitte verwendet und eine Schleife geschlossen wird , um über einen einzelnen Index zu iterieren.

xnor
quelle
6

CJam, 36 35 34 27 Bytes

Es stellte sich heraus, dass dies der gleiche Algorithmus ist wie der von xnor, aber ich frage mich, ob es einen besseren gibt.

rd:R,_m*{{2*R(-_g-}/mhR<},,

Code Erklärung :

rd:R                                "Read the input as double and store it in R";
    ,_                              "Get 0 to input - 1 array and take its copy";
      m*                            "Get Cartesian products";
                                    "Now we have coordinates of top left point of each";
                                    "of the square in the N by N grid";
        {               },,         "Filter the squares which are overlapped by the";
                                    "circle and count the number";
         {        }/                "Iterate over the x and y coordinate of the top left";
                                    "point of the square and unwrap them";
          2*                        "Scale the points to reflect a 2N grid square";
            R(-                     "Reduce radius - 1 to get center of the square";
               _g-                  "Here we are reducing or increasing the coordinate";
                                    "by 1 in order to get the coordinates of the vertex";
                                    "of the square closer to the center of the grid";
                    mhR<            "Get the distance of the point from center and check";
                                    "if its less than the radius of the circle";

UPDATE : Verwenden Sie den 2N-Trick von Jakube zusammen mit einigen anderen Techniken, um 7 Bytes zu sparen!

Probieren Sie es hier online aus

Optimierer
quelle
2

Pyth,  44  36

JcQ2L^-+b<bJJ2sm+>*JJ+y/dQy%dQqQ1*QQ

Ich versuche es ein bisschen zu säubern, falls ich ein paar Bytes rasieren könnte.

Erläuterung

                           Q = eval(input())    (implicit)
JcQ2                       calculate half of Q and store in J
L                          define function y(b) that returns
 ^-+b<bJJ2                 (b - J + (1 if b < J else 0)) ^ 2
s                          output sum of
 m                 *QQ      map d over integers 0..(Q*Q-1)
  +
   >*JJ                      J*J is greater than
       +y/dQy%dQ              sum of y(d / Q) and y(d % Q)
                qQ1          or Q is 1; see below

Ich muss explizit nachsehen n = 1, da mein Algorithmus nur die Ecke des Quadrats prüft, die der Mitte am nächsten liegt (und keine abgedeckt ist n = 1).

PurkkaKoodari
quelle
2

Oktave (74) (66) (64)

Hier die Oktavfassung. Grundsätzlich alle Eckpunkte innerhalb des Kreises finden und dann alle Quadrate mit einem oder mehreren gültigen Eckpunkten durch Faltung finden. 64 Bytes:

x=ndgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

66 Bytes:

x=meshgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

74 Bytes:

n=input('');x=ones(n+1,1)*(-1:2/n:1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)
fehlerhaft
quelle
1

R - 64

function(n)sum(rowSums(expand.grid(i<-0:n-n/2,i)^2)<n^2/4)+2*n-1
Flodel
quelle