Calculer la matrice de densité de périmètre

introduction

La matrice de densité périmétrique est une matrice binaire infinie M définie comme suit. Considérons un indice ( basé sur 1) (x, y) et notons M [x, y] la sous-matrice rectangulaire recouverte par le coin (1, 1) et (x, y) . Supposons que toutes les valeurs de M [x, y] à l' exception de M _{x, y} , la valeur à l'indice (x, y) , ont déjà été déterminées. La valeur M _{x, y} est alors celle de 0 ou 1 qui rapproche la valeur moyenne de M [x, y] de 1 / (x + y) . En cas d'égalité, choisissez M_{x, y} = 1 .

Il s'agit de la sous-matrice M [20, 20] avec des zéros remplacés par des points pour plus de clarté:

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

Par exemple, nous avons M _{1, 1} = 1 dans le coin supérieur gauche, car 1 / (1 + 1) = ½ , et la moyenne de la sous-matrice 1 × 1 M [1, 1] est soit 0 soit 1 ; c'est une cravate, nous choisissons donc 1 .

Considérez alors la position (3, 4) . Nous avons 1 / (3 + 4) = 1/7 , et la moyenne de la sous-matrice M [3, 4] est 1/6 si nous choisissons 0 et 3/12 si nous choisissons 1 . Le premier est plus proche de 1/7 , nous choisissons donc M _{3, 4} = 0 .

Voici la sous-matrice M [800, 800] sous forme d'image, montrant une partie de sa structure complexe.

La tâche

Étant donné un entier positif N <1000 , sortez la sous-matrice N × N M [N, N] , dans n'importe quel format raisonnable. Le nombre d'octets le plus bas gagne.

code-golf matrix Zgarb
la source

Réponses:

R, 158 154 141 octets

Edit: Parce que le seul 1dans la 2x2sous-matrice supérieure est en haut à gauche, M[1,1]nous pouvons commencer la recherche 1squand {x,y}>1donc pas besoin de l' ifinstruction.

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 solution est très inefficace car la matrice est dupliquée deux fois pour chaque itération. n=1000a pris un peu moins de deux heures et demie pour fonctionner et produit une matrice de 7.6Mb.

Non golfé et expliqué

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

Sortie pour 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
la source

Python 2, 189 octets

Il n'y a pas de trucs fous ici, c'est juste du calcul comme décrit dans l'introduction. Ce n'est pas particulièrement rapide, mais je n'ai pas besoin de créer de nouvelles matrices pour ce faire.

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

Explication:

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

Pour les curieux, voici quelques 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.

Sortie "jolie" pour 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
la source

Raquette 294 octets

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

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

Essai:

(f 8 8)

Production:

rnso
la source

Perl, 151 + 1 = 152 octets

Courez avec le -ndrapeau. Le code ne fonctionnera correctement que toutes les autres itérations dans la même instance du programme. Pour le faire fonctionner correctement à chaque fois, ajoutez 5 octets en ajoutant my%m;au code.

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

Lisible:

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

Sortie pour entrée 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
la source