Berechnen Sie die Perimeterdichtematrix

Einführung

Die Perimeterdichtematrix ist eine unendliche binäre Matrix M, die wie folgt definiert ist. Betrachten Sie einen (1-basierten) Index (x, y) und bezeichnen Sie mit M [x, y] die rechteckige Untermatrix, die von der Ecke (1, 1) und (x, y) überspannt wird . Angenommen, alle Werte von M [x, y] mit Ausnahme von M _{x, y} , dem Wert am Index (x, y) , wurden bereits bestimmt. Dann ist der Wert M _{x, y} derjenige von 0 oder 1 , der den Durchschnittswert von M [x, y] näher an 1 / (x + y) bringt . Bei Gleichstand wählen Sie M._{x, y} = 1 .

Dies ist die Untermatrix M [20, 20], bei der aus Gründen der Klarheit Nullen durch Punkte ersetzt sind:

1 . . . . . . . . . . . . . . . . . . .
. . . . . 1 . . . . . . . . . . . . . .
. . 1 . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . 1 . . . . . . . . . . . . . . .
. 1 . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 1 . .
. . . . . . . . . . . . . . 1 . . . . .
. . . . . . . . . . . . 1 . . . . . . .
. . . . . . . . . . 1 . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 1 . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . 1 . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . 1 . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .

Zum Beispiel haben wir M _{1, 1} = 1 in der oberen linken Ecke, da 1 / (1 + 1) = ½ , und der Durchschnitt der 1 × 1 -Untermatrix M [1, 1] ist entweder 0 oder 1 ;; Das ist ein Unentschieden, also wählen wir 1 .

Betrachten Sie dann die Position (3, 4) . Wir haben 1 / (3 + 4) = 1/7 und der Durchschnitt der Untermatrix M [3, 4] ist 1/6, wenn wir 0 wählen , und 3/12, wenn wir 1 wählen . Ersteres ist näher an 1/7 , also wählen wir M _{3, 4} = 0 .

Hier ist die Submatrix M [800, 800] als Bild, die einige ihrer komplizierten Strukturen zeigt.

Die Aufgabe

Bei einer positiven ganzen Zahl N <1000 wird die N × N -Untermatrix M [N, N] in einem beliebigen vernünftigen Format ausgegeben. Die niedrigste Byteanzahl gewinnt.

code-golf matrix Zgarb
quelle

Antworten:

R, 158 154 141 Bytes

Bearbeiten: Da die einzige 1in der oberen 2x2Submatrix oben links ist M[1,1], können wir die Suche starten, 1swenn {x,y}>1die ifAnweisung nicht benötigt wird .

M=matrix(0,n<-scan(),n);M[1]=1;for(i in 2:n)for(j in 2:n){y=x=M[1:i,1:j];x[i,j]=0;y[i,j]=1;d=1/(i+j);M[i,j]=abs(d-mean(x))>=abs(d-mean(y))};M

Die Lösung ist sehr ineffizient, da die Matrix für jede Iteration zweimal dupliziert wird. n=1000Der Betrieb dauerte knapp zweieinhalb Stunden und ergab eine Matrix von 7.6Mb.

Ungolfed und erklärt

M=matrix(0,n<-scan(),n);                        # Read input from stdin and initialize matrix with 0s
M[1]=1;                                         # Set top left element to 1
for(i in 2:n){                                  # For each row    
    for(j in 2:n){                              # For each column
        y=x=M[1:i,1:j];                         # Generate two copies of M with i rows and j columns
        x[i,j]=0;                               # Set bottom right element to 0
        y[i,j]=1;                               # Set bottom right element to 1
        d=1/(i+j);                              # Calculate inverse of sum of indices
        M[i,j]=abs(d-mean(x))>=abs(d-mean(y))   # Returns FALSE if mean(x) is closer to d and TRUE if mean(y) is
    }
};
M                                               # Print to stdout

Ausgabe für n=20

      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16] [,17] [,18] [,19] [,20]
[1,]     1    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[2,]     0    0    0    0    0    1    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[3,]     0    0    1    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[4,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[5,]     0    0    0    0    1    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[6,]     0    1    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[7,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[8,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     1     0     0
[9,]     0    0    0    0    0    0    0    0    0     0     0     0     0     0     1     0     0     0     0     0
[10,]    0    0    0    0    0    0    0    0    0     0     0     0     1     0     0     0     0     0     0     0
[11,]    0    0    0    0    0    0    0    0    0     0     1     0     0     0     0     0     0     0     0     0
[12,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[13,]    0    0    0    0    0    0    0    0    0     1     0     0     0     0     0     0     0     0     0     0
[14,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[15,]    0    0    0    0    0    0    0    0    1     0     0     0     0     0     0     0     0     0     0     0
[16,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[17,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[18,]    0    0    0    0    0    0    0    1    0     0     0     0     0     0     0     0     0     0     0     0
[19,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0
[20,]    0    0    0    0    0    0    0    0    0     0     0     0     0     0     0     0     0     0     0     0

Billywob
quelle

Python 2, 189 Bytes

Hier gibt es keine verrückten Tricks, es wird nur wie in der Einleitung beschrieben berechnet. Es ist nicht besonders schnell, aber ich muss keine neuen Matrizen erstellen, um dies zu tun.

n=input()
k=[n*[0]for x in range(n)]
for i in range(1,-~n):
 for j in range(1,-~n):p=1.*i*j;f=sum(sum(k[l][:j])for l in range(i));d=1./(i+j);k[i-1][j-1]=0**(abs(f/p-d)<abs(-~f/p-d))
print k

Erläuterung:

n=input()                                     # obtain size of matrix  
k=[n*[0]for x in range(n)]                    # create the n x n 0-filled matrix
for i in range(1,-~n):                        # for every row:
  for j in range(1,-~n):                      # and every column:
    p=1.*i*j                                  # the number of elements 'converted' to float
    f=sum(sum(k[l][:j])for l in range(i))     # calculate the current sum of the submatrix
    d=1./(i+j)                                # calculate the goal average
    k[i-1][j-1]=0**(abs(f/p-d)<abs(-~f/p-d))  # decide whether cell should be 0 or 1
print k                                       # print the final matrix

Für diejenigen, die neugierig sind, hier einige Timings:

 20 x  20 took 3 ms.
 50 x  50 took 47 ms.
100 x 100 took 506 ms.
250 x 250 took 15033 ms.
999 x 999 took 3382162 ms.

"Hübsche" Ausgabe für n = 20:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Kade
quelle

Schläger 294 Bytes

(define(g x y)(if(= 1 x y)1(let*((s(for*/sum((i(range 1(add1 x)))(j(range 1(add1 y)))#:unless(and(= i x)(= j y)))
(g i j)))(a(/ s(* x y)))(b(/(add1 s)(* x y)))(c(/ 1(+ x y))))(if(<(abs(- a c))(abs(- b c)))0 1))))
(for((i(range 1(add1 a))))(for((j(range 1(add1 b))))(print(g i j)))(displayln""))

Ungolfed:

(define(f a b)  
  (define (g x y)
    (if (= 1 x y) 1
        (let* ((s (for*/sum ((i (range 1 (add1 x)))
                             (j (range 1 (add1 y)))
                             #:unless (and (= i x) (= j y)))
                    (g i j)))
               (a (/ s (* x y)))
               (b (/ (add1 s) (* x y)))
               (c (/ 1 (+ x y))))
          (if (< (abs(- a c))
                 (abs(- b c)))
              0 1))))
  (for ((i (range 1 (add1 a))))
    (for ((j (range 1 (add1 b))))
      (print (g i j)))
    (displayln ""))
  )

Testen:

(f 8 8)

Ausgabe:

rnso
quelle

Perl, 151 + 1 = 152 Bytes

Lauf mit der -nFlagge. Der Code funktioniert nur bei jeder zweiten Iteration innerhalb derselben Instanz des Programms korrekt . Fügen Sie my%m;dem Code 5 Bytes hinzu , damit es jedes Mal ordnungsgemäß funktioniert .

for$b(1..$_){for$c(1..$_){$f=0;for$d(1..$b){$f+=$m{"$d,$_"}/($b*$c)for 1..$c}$g=1/($b+$c);print($m{"$b,$c"}=abs$f-$g>=abs$f+1/($b*$c)-$g?1:_).$"}say""}''

Lesbar:

for$b(1..$_){
    for$c(1..$_){
        $f=0;
        for$d(1..$b){
            $f+=$m{"$d,$_"}/($b*$c)for 1..$c
        }
        $g=1/($b+$c);
        print($m{"$b,$c"}=abs$f-$g>=abs$f+1/($b*$c)-$g?1:_).$"
    }
    say""
}

Ausgabe für Eingabe von 100:

1___________________________________________________________________________________________________
_____1______________________________________________________________________________________________
__1_________________________________________________________________________________________________
___________________________1________________________________________________________________________
____1_______________________________________________________________________________________________
_1__________________________________________________________________________________________________
_________________________1__________________________________________________________________________
_________________1__________________________________________________________________________________
______________1_____________________________________________________________________________________
____________1_______________________________________________________________________________________
__________1_________________________________________________________________________________________
____________________________________________________________________________________________________
_________1__________________________________________________________________________________________
____________________________________________________________________________________________________
________1___________________________________________________________________________________________
______________________________________________________________________________________1_____________
_________________________________________________________________1__________________________________
_______1____________________________________________________________________________________________
_____________________________________________________________1______________________________________
____________________________________________________1_______________________________________________
______________________________________________1_____________________________________________________
__________________________________________1_________________________________________________________
_______________________________________1____________________________________________________________
____________________________________1_______________________________________________________________
__________________________________1_________________________________________________________________
______1_____________________________________________________________________________________________
____________________________________________________________________________________________________
___1________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
________________________________1___________________________________________________________________
____________________________________________________________________________________________________
________________________1___________________________________________________________________________
____________________________________________________________________________________________________
_______________________1____________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
______________________1_____________________________________________________________________________
____________________________________________________________________________________________________
___________________________________________________________________________________________________1
_____________________1______________________________________________________________________________
____________________________________________________________________________________________________
_____________________________________________________________________________________1______________
__________________________________________________________________________________1_________________
____________________1_______________________________________________________________________________
____________________________________________________________________________________________________
________________________________________________________________________________1___________________
______________________________________________________________________________1_____________________
___________________________________________________________________________1________________________
_________________________________________________________________________1__________________________
___________________1________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_______________________________________________________________________1____________________________
______________________________________________________________________1_____________________________
____________________________________________________________1_______________________________________
___________________________________________________________1________________________________________
__________________________________________________________1_________________________________________
_________________________________________________________1__________________________________________
__________________1_________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
________________1___________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
________________________________________________________1___________________________________________
_______________________________________________________1____________________________________________
____________________________________________________________________________________________________
___________________________________________________1________________________________________________
____________________________________________________________________________________________________
__________________________________________________1_________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________________________________1__________________________________________________
____________________________________________________________________________________________________
________________________________________________1___________________________________________________
____________________________________________________________________________________________________
_____________________________________________1______________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________1_______________________________________________________
_______________1____________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
____________________________________________________________________________________________________
_________________________________________1__________________________________________________________

Gabriel Benamy
quelle