# "Fill the Grid" Problem

A challenge with simple rules but non-trivial algorithms. :-)

Take input in the form of space-separated integers:

N A B S


Where N is the side length of a 2D square matrix filled with unique numbers (integers) between A and B inclusive. For each row and column in this matrix, the sum is always the same: S. (In other words, the matrix is a semi-magic square).

Note:

All numbers are positive. Exception is A, which can be 0.

### Examples

For

3 1 10000 2015


a valid solution would be For

8 1 300 500


a valid solution would be ### Output

You output should be an ASCII table. Example for the first example above:

 384  159 1472
1174  499  342
457 1357  201


Right-aligned integers padded by spaces. The width of each column is the width of the largest integer in that column.

### Scoring

This is , so shortest code in bytes wins. Standard loopholes apply (especially about built-ins to solve this problem). You don't have to care about wrong or otherwise impossible inputs (including negative numbers). Please provide a sample output in your answer (mandatory) for the second example above.

• Are we allowed to generate random numbers between A and B until they sum correctly and are unique? Oct 1, 2015 at 19:53
• Just to check, A, B, and N can be negative?
– xnor
Oct 1, 2015 at 19:54
• minxomat, I'm not saying it's the best solution I can come up with, I'm saying it may be the shortest possible. Oct 1, 2015 at 20:02
• @LuisMendo You have to generate a sample output according to the task. If you can manage this within your lifetime with a brute-force approach, I'd be impressed. :-). I could rule it out, but it would be too fuzzy, since the most popular solution (which is GA) still involves randomness. Also I don't want to change the rules when someone might work on a solution already.
– user42643
Oct 2, 2015 at 0:15
• @minxomat All your three arguments are very good points :-) Oct 2, 2015 at 0:17

# CJam, 119 91 bytes

q~:M;),>:R;(:L{{R{ML)d/-Y#)mr}$L/L<2{{M1$:+-+}%z}*:U:+__O|=R*-}gU{:s_:,:e>f{Se[}}%zSf*N*}M?


This is a provably correct, non-deterministic approach.

On my desktop, the second test case generally finishes in less than 10 minutes.

The first case finishes instantly. Try it online in the CJam interpreter.

$cjam grid.cjam <<< '8 1 300 500' 77 66 37 47 56 46 86 85 63 102 70 72 49 54 81 9 62 69 58 57 71 17 48 118 64 65 67 87 53 44 80 40 73 60 55 89 51 76 84 12 68 59 28 78 74 38 50 105 61 75 52 43 125 83 42 19 32 4 133 27 21 142 29 112  ### Idea Without time limits, we could just randomly generate squares until finding a valid square. This approach builds on that idea, adding two optimizations: • Instead of pseudo-randomly generating square of side length N, we generate squares of side length N-1, add one column to form a N × (N-1) rectangle whose rows have sum S, then one row to form a square of side length N whose columns have sum S. Since the sum of the elements of all columns will be NS and the sum of the elements of the first N-1 rows is (N-1)S, the last row will also have sum S. However, this process may generate an invalid matrix, since there's no guarantee that all elements of the last row and column will be unique or fall in the range [A ... B]. • Picking a square of unique integers in [A ... B] and side length N-1 uniformly at random would take way too long. We somehow have to prioritize squares that have a higher chance of resulting in a valid square of side length N after applying the process detailed in the previous bullet point. Given that each row and column has to have a sum of S, its elements have an average of S/N. Thus, picking more elements close to that average should increase our chances. For each I in [A ... B], we pseudo-randomly pick a float between 0 and (I - S/N)2 + 1 and sort the elements of [A ... B] by the picked floats. We keep the first N2 numbers and place them in reading order in a square. Assuming a perfectly uniform distribution of all real numbers between 0 and (I - S/N)2 + 1 in each step, all squares have a non-zero probability of being picked, meaning that the process will finish eventually. ### Code q~ e# Read all input from STDIN and evaluate it. :M; e# Save "S" in M and discard it from the stack. ),>:R; e# Transform "A B" into [A ... B], save in R and discard. (:L e# Save "N - 1" in L and keep it on the stack. { e# If L is non-zero: { e# Do: R{ e# For each I in R: ML)d/ e# Compute M/Double(L+1). -Y# e# Subtract the result from I and square the difference. )mr e# Add 1 and pick a non-negative Double below the result. }$      e#     Sort the values of I according to the picks.
L/      e#     Split the shuffled R into chunks of length L.
L<      e#     Keep only the first L chunks.
2{      e#     Do twice:
{     e#       For each row of the  L x L array.
M1\$ e#       Push M and a copy of the row.
:+- e#       Add the integers of the row and subtract their sum from M.
+   e#       Append the difference to the row.
}%    e#
z     e#       Transpose rows and columns.
}*      e#
:U:+    e#     Save the result in U and concatenate its rows.
__O|    e#     Push two copies. Deduplicate the second copy.
=R*     e#     Push R if all elements are unique, an empty array otherwise.
-       e#     Remove the result's elements from U's elements.
}g        e#   If the resulting array is non-empty, repeat the loop.
U{        e#   For each row in U:
:s      e#     Convert its integers into strings.
_:,     e#     Copy and replace each string with its length.
:e>     e#     Compute the maximum length.
f{      e#     For each integer, push the maximum length; then
Se[   e#       Left-pad the integer with spaces to that length.
}       e#
}%        e#
z         e#   Transpose rows with columns.
Sf*N*     e#   Join columns by spaces, rows by linefeeds.
}M?         e# Else, push M.


# Jelly, 19 18 bytes

S;§f⁵
r/œ!²}s€ÇÞṪG


Try it online!

Takes input via the command-line in the form A, B N S. Outputs the lexicographic ally first grid that fits

-1 byte thanks to Jonathan Allan!

On the one hand, it's short. On the other hand, it's incredibly inefficient. This generates

$$\frac {(B-A+1)!} {(B-A-N^2+1)!}$$

$$\N\times N\$$ squares to check. For example, if $$\A = 1, B = 9, N = 3\$$ (the example in TIO), this generates $$\362880\$$ $$\3\times3\$$ matrices to check are semi-magic. For the second test case, it generates 243427020732724848691170301000009788596908895057539171134817782742659530443034291592046861179091424965386457564096330026488754281163364761600000000000000000 $$\8\times8\$$ matrices.

Given enough time and memory, this would work on any input. However, on my computer, it runs out of memory for the second test case after 5 minutes

## How it works

S;§f⁵ - Helper link. Takes a matrix M and outputs if it's semi-magic to S
S     - Column sums of M
§   - Row sums of M
;    - Concatenate
f⁵ - Keep only S

r/œ!²}s€ÇÞṪG - Main link. Takes [A, B] on the left and N on the right
r/           - Reduce [A, B] by range, yielding [A, A+1, ..., B-1, B]
}       - To N:
²        -   Square
œ!         - Generate all permutations of range(A, B) of length N²
€     - Over each:
s      -   Slice into NxN matrices
ÇÞ   - Sort the matrices by the helper link
ṪG - Take the last and format as a grid

• Impossible inputs do not need to be handled so save two using filter-keep and sort to save one, which then allows a four-link dyad, which saves one more TIO. (The spec does say we must take space-separated integers, so that might cost a little unless we're just allowed to ignore that nowadays?) Apr 4, 2021 at 23:15
• @JonathanAllan Thanks, that's really clever! For older challenges, I typically ignore the "space separated" inputs rule if they have them, unless the OP complains, because it just seems unnecessary and outdated. But I suppose you could argue that they are space separated on the command line when provided locally rather than on TIO, if someone really insisted on space separated input Apr 4, 2021 at 23:25
• I don't think the 17-byter solves the challenge, as 9 8 7 / 6 5 4 / 3 2 1 is pretty far from semi-magic. Apr 5, 2021 at 0:01
• @Bubbler Good point, I've reverted the edit. Can't believe I didn't noticed that Apr 5, 2021 at 0:03
• @Bubbler oh, yeah the four cannot be combined with a hyper, so 18 it is. Apr 5, 2021 at 0:50