# “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? – lirtosiast Oct 1 '15 at 19:53
• Just to check, A, B, and N can be negative? – xnor Oct 1 '15 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. – lirtosiast Oct 1 '15 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. – mınxomaτ Oct 2 '15 at 0:15
• @minxomat All your three arguments are very good points :-) – Luis Mendo Oct 2 '15 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.