Calcule la matriz de densidad perimetral

Introducción

La matriz de densidad perimetral es una matriz binaria infinita M definida como sigue. Considere un índice ( basado en 1) (x, y) , y denote por M [x, y] la submatriz rectangular que abarca la esquina (1, 1) y (x, y) . Suponga que todos los valores de M [x, y] excepto M _{x, y} , el valor en el índice (x, y) , ya se han determinado. Entonces el valor M _{x, y} es cualquiera de 0 o 1 que coloque el valor promedio de M [x, y] más cerca de 1 / (x + y) . En caso de empate, elija M_{x, y} = 1 .

Esta es la submatriz M [20, 20] con ceros reemplazados por puntos para mayor claridad:

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

Por ejemplo, tenemos M _{1, 1} = 1 en la esquina superior izquierda, puesto que 1 / (1 + 1) = ½ , y la media de la 1 × 1 sub-matriz M [1, 1] es o bien 0 o 1 ; eso es un empate, así que elegimos 1 .

Considere entonces la posición (3, 4) . Tenemos 1 / (3 + 4) = 1/7 , y el promedio de la submatriz M [3, 4] es 1/6 si elegimos 0 , y 3/12 si elegimos 1 . El primero está más cerca de 1/7 , entonces elegimos M _{3, 4} = 0 .

Aquí está la submatriz M [800, 800] como una imagen, que muestra parte de su intrincada estructura.

La tarea

Dado un número entero positivo N <1000 , salida de la N × N sub-matriz M [N, N] , en cualquier formato razonable. El conteo de bytes más bajo gana.

code-golf matrix Zgarb
fuente

Respuestas:

R, 158154141 bytes

Editar: debido a que el único 1en la 2x2submatriz superior es la parte superior izquierda M[1,1], podemos comenzar la búsqueda 1scuando {x,y}>1no sea necesario el ifenunciado.

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

La solución es altamente ineficiente ya que la matriz se duplica dos veces para cada iteración. n=1000tardó menos de dos horas y media en ejecutarse y produce una matriz de 7.6Mb.

Desengañado y explicado

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

Salida para 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
fuente

Python 2, 189 bytes

No hay trucos locos aquí, solo se calcula como se describe en la introducción. No es particularmente rápido, pero no necesito crear matrices nuevas para hacer esto.

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

Explicación:

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

Para aquellos curiosos, aquí hay algunos horarios:

 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.

Salida "bonita" para 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
fuente

Raqueta 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""))

Sin golf:

(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 ""))
  )

Pruebas:

(f 8 8)

Salida:

rnso
fuente

Perl, 151 + 1 = 152 bytes

Corre con la -nbandera. El código solo funcionará correctamente cada dos iteraciones dentro de la misma instancia del programa. Para que funcione correctamente cada vez, agregue 5 bytes al anteponer my%m;el código.

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""}''

Legible:

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""
}

Salida para entrada de 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
fuente