Maintain diagonal symmetry when placing N items on a square grid

Question

Write a program that takes in two non-negative integers S and N in that order. S represents the side length of a square grid of . characters. N represents the number of those .'s that need to be changed to x's. You may assume N is no greater than S squared.

Your program needs to output this S×S square of .'s and N x's but the requirement is that the square must always have a diagonal line of symmetry from its top left to its bottom right. Any grid arrangement is valid output as long as it has this symmetry.

For example, if S is 3 and N is 4 here are several grids that have this diagonal symmetry and would be valid output:

x.x
...
x.x

x..
.xx
.x.

...
.xx
.xx

The following grids however would not be valid:

.x.
xxx
...
(lacks diagonal symmetry)

..x
xx.
.x.
(has diagonal symmetry but not from the top left to the bottom right)

x.x
.x.
x.x
(incorrect number of x's)

This is code golf so the shortest program in bytes wins!

Details:

• A trailing newline after the grid is fine.

• You may use any two distinct printable-ASCII characters in place of . and x if you prefer.

• If you prefer you may even output a binary-matrix instead of a string.

• When N is 0 the output will be a pure S×S square of .'s with no x's.

• When S is 0 the output will be an empty string (or single trailing newline).

• The output does not need to be deterministic, as long as it is always guaranteed to be valid.

More Examples:

Not all valid arrangements are listed for each example input. Your output might look different yet still be valid.

S = 0, N = 0
[empty string]

S = 1, N = 0
.

S = 1, N = 1
x

S = 2, N = 0
..
..

S = 2, N = 1
x.
..

..
.x

S = 2, N = 2
x.
.x

.x
x.

S = 2, N = 3
xx
x.

.x
xx

S = 2, N = 4
xx
xx

S = 3, N = 2
x..
.x.
...

..x
...
x..

S = 4, N = 1
....
.x..
....
....

S = 4, N = 5
x..x
.x..
..x.
x...

xxx.
x...
x...
....

S = 5, N = 23
xxxxx
xxxxx
xxxxx
xxx.x
xxxx.

xxxxx
xxxxx
xxxxx
xxxx.
xxx.x

S = 7, N = 13
...x...
...x...
...x...
xxxxxxx
...x...
...x...
...x...

xxxxxxx
x......
x......
x......
x......
x......
x......

Answer 1

Python 2, 116 113 112 101 bytes

lambda s,n:[[[n>i<s-(s+n&1),[i*~-i+2*j,j*~-j+2*i][i<j]<n-s][j!=i]for j in range(s)]for i in range(s)]

Try it online!

Input: 2 integers s and n
Output: A 2D list of True and False, representing x and . respectively.

Explanation

The strategy is to put as many xs on the diagonal as possible.

• If \$s\$ and \$n\$ has the same parity, then we can fill \$min(s,n)\$ diagonal squares.
• If \$s\$ and \$n\$ has different parity, then we can fill \$min(s-1,n)\$ diagonal squares.

The remaining xs can be split symmetrically between the 2 triangular half of the grid. For the bottom triangle, we fill from top to bottom, where each row is filled left to right. The upper triangle mirrors the bottom triangle (fill left to right, each column from top to bottom)

Thus, we can determine if a square is filled just based on its indices \$(i,j)\$:

• If \$i=j\$ (the square is on the diagonal), then that square is filled if \$i<n\$ and \$i<s-t\$, where \$t\$ is 0 or 1 depending on whether \$s\$ and \$n\$ have the same or different parity.
  The following snippet evaluates to True or False if the diagonal square should be filled or not.

[n>i<s-(s+n&1), ...case when square is not diagonal... ][j!=i]

• If \$i>j\$ (the square is in lower triangle), then the number of squares in the lower triangle before this square (in fill order) is \$m = \frac{i(i-1)}{2} + j\$. Thus if this square is filled, then the number of squares filled before it is \$2m = i(i-1)+2j\$. We need to make sure that \$2m<n-s\$, otherwise the diagonal cannot be filled to the maximum.
  Similarly, if \$i>j\$, then we fill if \$j(j-1)+2i<n-s\$.
  The following snippet evaluates to True or False if the non-diagonal square is filled or not:

[i*~-i+2*j,j*~-j+2*i][i<j]<n-s

Combined together, this big expression evaluates to whether a square \$(i,j)\$ should be filled:

[n>i<s-(s+n&1),[i*~-i+2*j,j*~-j+2*i][i<j]<n-s][j!=i]

Thanks @ovs for saving 4 bytes in a previous solution!

Answer 2

MATL, 21 20 bytes

U:<~Zc`tnZ@)[]ett!-z

Try it online!

Characters are # and . The output is random, that is, it may be different every time the program is run. Running time is also random, but the program is guaranteed to finish in finite time.

How it works

General idea

The code first generates a numeric vector with N ones and S^2-N zeros (U:<~), and transforms it into a string replacing 1 and 0 by the two mentioned characters (Zc). Then, a random permutation is applied (tnZ@)) , the result is reshaped into a square matrix of characters ([]e), and this is repeated (`) until the matrix equals its transpose (t!-z), while leaving a copy (t) for the next iteration or as final result.

Detailed steps

U        % Input (implicit): S. Push S^2
:        % Range [1 2 ... S^2]
<~       % Input (implicit): N. Greater-or-equal, element-wise. Gives
         % [1 1 ... 1 0 0 ... 0] with N ones and S^2-N zeros
Zc       % String where 1 becomes '#'  and 0 becomes space
`        % Do...while
  tn     %   Duplicate. Number of elements. Gives S^2
  Z@     %   Random permutation of the integers 1, 2, ..., S^2
  )      %   Apply as an index. This shuffles the previous string
         %   or char matrix, and gives a string as result
  []e    %   Reshape as a square matrix of chars
  tt!    %   Duplicate twice, and transpose the second copy
  -      %   Subtract element-wise
  z      %   Number of nonzeros. This is the loop condition. The loop
         %   is exited when the result is 0, meaning that the matrix
         %   and its transpose are equal
         % End (implicit)
         % Display (implicit). The stack contains a copy of the latest
         % matrix of chars, which is the first that was found to
         % satisfy the symmetry condition

Answer 3

JavaScript (ES6),  116 114  110 bytes

Takes input as (s)(n). Returns a matrix of Boolean values.

s=>n=>[...Array(s)].map((_,y,a)=>a.map((_,x)=>(p=Math.min(n&~1,s*s-s),x-y?(x<y?y*y-y+2*x:x*x-x+2*y)<p:x<n-p)))

Try it online!

How?

The output matrix is divided into 2 parts:

• the cells located on the main diagonal (type A)
• all other cells (type B)

Whenever a type-B cell is set, its symmetrical counterpart must be set as well. We want to set as many type-B cells as possible and this number is given by:

$$p_{n,s}=\min\left(2\left\lfloor\frac{n}{2}\right\rfloor,s(s-1)\right)$$

The number of type-A cells is therefore given by:

$$q_{n,s}=n-p_{n,s}$$

We define \$T(k)\$ as the \$k\$-th triangular number:

$$T(k)=\frac{k(k+1)}{2}$$

To figure out whether the type-B cell at \$(x,y)\$ must be set or not, we assign it the following ID and compare it with \$\dfrac{p_{n,s}}{2}\$:

$$\begin{cases} T(y-1)+x,&\text{if $x<y$}\\ T(x-1)+y,&\text{if $x>y$}\\ \end{cases}$$

Example for \$s=5\$:

$$\begin{pmatrix} -&0&1&3&6\\ 0&-&2&4&7\\ 1&2&-&5&8\\ 3&4&5&-&9\\ 6&7&8&9&- \end{pmatrix}$$

To figure out whether the type-A cell at \$(x,x)\$ must be set or not, we simply use \$x\$ as its ID and compare it with \$q_{n,s}\$.

Example for \$s=5\$:

$$\begin{pmatrix} 0&-&-&-&-\\ -&1&-&-&-\\ -&-&2&-&-\\ -&-&-&3&-\\ -&-&-&-&4 \end{pmatrix}$$

Answer 4

Wolfram Language (Mathematica), 113 bytes

Searches random matrices [S,N] until matrix g is equal to Transpose(g)
Outputs a binary matrix

If[#<1,"",g=(P=Partition)[k=Join@@{1~Table~#2,Table[0,#^2-#2]},#];While[g!=Transpose@g,g=P[RandomSample@k,#]];g]&

Try it online!

Wolfram Language (Mathematica), 75 bytes

Here is also a deterministic version that searches all possible matrices
(it works only up to 4x4 due to memory limitations)

If[#<1,"",x=#2;Select[{0,1}~Tuples~{#,#},#==Transpose@#&&Tr[Tr/@#]==x&,1]]&

Try it online!

-2 bytes by @my pronoun is monicareinstate

Answer 5

Bash + Unix utilities, 152 bytes

a=`dc<<<4dk$2*1+v1-2/0k1/p`
for((q=$2-a*a-a,b=++a<$1?q/2:0;i<$1;++j>=$1?j=0,i++:0)){ printf $[i-j?i<a&j<a?1:i==a&j<b|j==a&i<b?1:0:i<q-2*b?1:0]\ ;}|rs $1

Try the test suite online!

\$S\$ and \$N\$ are read from stdin, and the output is printed to stdout. The characters used are 0 and 1 (for (for . and x, respectively).

This program prints a space between successive characters, which I think looks better (the grids are more squarish and easier to read), and it saves me a byte. If that's not acceptable, use fold instead of rs as follows (for 153 bytes):

a=`dc<<<4dk$2*1+v1-2/0k1/p`
for((q=$2-a*a-a,b=++a<$1?q/2:0;i<$1;++j>=$1?j=0,i++:0)){ printf $[i-j?i<a&j<a?1:i==a&j<b|j==a&i<b?1:0:i<q-2*b?1:0];}|fold -$1

How it works:

First we use dc to compute $$a=\left\lfloor\frac{\sqrt{4N+1}-1}{2}\right\rfloor.$$

You can check that \$a\$ is the greatest integer such that \$a(a+1) \leq N.\$ The reason this is useful is that $$a(a+1)=2(1+2+\dots+a).$$

The for loop that comes next runs through each position \$(i, j)\$ where each of the variables goes from \$0\$ to \$S-1.\$ It prints a 0 or a 1 for each \$(i,j)\$.

For convenience, \$a\$ is incremented during the for loop initialization, so it's actually \$1\$ higher than the above value during the body of the loop.

The following entries are filled in with 1s (the others are all 0s):

(1) Fill in each \$(i,j)\$ where \$0 \le i \lt a\$ and \$0 \le j \lt a.\$

(2) If \$a<S\$ (so that there's at least one row and one column left untouched still), fill in the entries at positions \$(a,i)\$ and \$(i,a)\$ (starting from \$i=0\$ and keeping \$i\$ below \$a-1\$), up to the number of additional entries that are still needed after step 1. These are always entered in pairs.

(3) If we still haven't marked enough entries (which can happen because we ran out of room off the main diagonal, or simply because we needed to mark an odd number of entries, but everything so far has been in pairs), then fill in entries \$(i,i)\$ on the main diagonal, starting at \$i=0,\$ until we've filled in the right number of 1s.

Finally, the rs (or fold) at the end formats it all as a square array.

Answer 6

Perl 5, 139 bytes

sub f{($s,$n)=@_;$_='-'x$s x$s;$i=-1;while($n){$j=++$i%$s*$s+int$i/$s;$n<2&&$i-$j&&next;for$o($i,$j){$n-=s,^(.{$o})-,$1x,}}s/.{$s}/$&\n/gr}

Try it online!

sub fungolfed {
  ($s,$n) = @_;                     # input params s and n
  $_ = '-' x $s x $s;               # $_ is the string of - and x
  $i=-1;                            # start at position i=0, due to ++ below
  while($n){                        # while more x's to place (n>0)
    $j = ++$i % $s * $s + int$i/$s; # j is the symmetrical position of i
    $n<2 && $i-$j && next;          # place x only in diagonal if one x left (n=1)
    for $o ($i,$j){                 # place x at positions i and j
      $n -= s/^(.{$o})-/$1x/        # ...and decrease n if - was replaced by x
                                    # ...that is if the position was not aleady x
    }
  }
  s/.{$s}/$&\n/gr                   # put \n after each s'th char and return that
}

Test:

for my $s (0..7){
  for my $n (0..$s*$s){
    print "\n__________________ s=$s n=$n\n";
    print f($s,$n) =~ s/./$& /gr;                 }  }

Part of the output:

__________________ s=3 n=0
- - - 
- - - 
- - - 
__________________ s=3 n=1
x - - 
- - - 
- - - 
__________________ s=3 n=2
x - - 
- x - 
- - - 
__________________ s=3 n=3
x x - 
x - - 
- - - 
__________________ s=3 n=4
x x - 
x x - 
- - - 
__________________ s=3 n=5
x x x 
x - - 
x - - 
__________________ s=3 n=6
x x x 
x x - 
x - - 
__________________ s=3 n=7
x x x 
x x - 
x - x 
__________________ s=3 n=8
x x x 
x x x 
x x - 
__________________ s=3 n=9
x x x 
x x x 
x x x

Answer 7

PowerShell, 153 140 136 bytes

param($l,$n)if($l--){0..$l|%{$y=$_
-join(0..$l|%{$n-=$a=($_-eq$y-and$n)+2*($_-gt$y-and$n-gt1)
'.x'["$y;$_"-in($c+=,"$_;$y"*$a)-or$a]})}}

Try it online!

Unrolled:

param($length,$n)
if($length--){
    0..$length|%{
        $y=$_
        -join(0..$length|%{
            $draw = 1*($_ -eq $y -and $n) +         # draw 1 element on the diagonal
                    2*($_ -gt $y -and $n -gt 1)     # draw 2 elements in the corners
                                                    # or draw 0 elements (draw field char '.')
            $n-=$draw                               # reduce the number of drawing elements
            $coordCache += ,"$_;$y" * $draw         # add one element or two identical elements
            '.x'[$draw -or "$y;$_" -in $coordCache] # draw element directly or draw from cache
        })
    }
}

Answer 8

Charcoal, 39 bytes

ＮθＮηＧ←↑⊖θ.ＵＭ✂ＫＡ⁰⊘η¹x↑‖Ｍ↗Ｐ↘⭆θ§.x›η⁺ι№ＫＡx

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input S and N.

Ｇ←↑⊖θ.

Fill a triangle of size S-1 with .s.

ＵＭ✂ＫＡ⁰⊘η¹x

Change up to N/2 of those .s to xs.

↑‖Ｍ↗

Reflect to create the diagonal symmetry, but leaving the diagonal empty.

Ｐ↘⭆θ§.x›η⁺ι№ＫＡx

Count the number of xs and complete the diagonal using xs and .s as necessary to end up with N xs.

Answer 9

Ruby, 97 bytes

->s,n{t=(?.*s+$/)*s
i=1
(t[i*-~s/s]=t[i/s-i%s*~s]=?X;i+=1)until 2>m=n-t.count(?X)
m>0&&t[0]=?X
t}

Try it online!

Llamda function. Returns a newline separated string with X and . can be shorter if a single line string is acceptable.

Very simple:

• Make a newline separated string of s lines of s .

• Set i=1 and scan through all indexes of i interpreting this as both [row-then-column] and [column-then-row] and change the relevant . to X . The total number of X added per iteration will be 1 if it is the cell is on the diagonal, and either 2 or 0 if it is not, depending on whether the cells already contain X.

• End the loop when less than 2 more X need to be added.

• If there is still one X to be added, put it at top left (index 0)

• Return the string