Zsgn©>‹®L¹˜Kœ0ªε\¹˜0y.;¹gô©O®øO®Å\O®Å/O)˜Ë}à*
Also uses \$0\$ as placeholder. The more \$0\$s (or numbers above \$n^2\$ ) in the input, the slower the program is. Size of the matrix doesn't matter that much (a 10x10 matrix with three \$0\$s runs quite a bit faster than a 3x3 matrix with seven \$0\$s).
Could have been 4 bytes less, but there is currently a bug in the builtin .;
with 2D lists. :
and .:
work as expected, but .;
doesn't do anything on 2D lists right now.. hence the work-around of ˜
and ¹gô
to flatten the matrix; use .;
on the list; and transform it back into a matrix again.
Try it online or verify some more test cases. (NOTE: Last test case of the challenge description is not included, because it has way too many 0s..)
Explanation:
Z # Get the maximum of the (implicit) input-matrix (implicitly flattened)
# (and without popping the matrix)
# i.e. [[8,0,6],[0,5,0],[0,0,2]] → 8
s # Swap to get the input-matrix again
g # Get its length (amount of rows)
# i.e. [[8,0,6],[0,5,0],[0,0,2]] → 3
n # Square it
# i.e. 3 → 9
© # Store it in the register (without popping)
>‹ # Check if the maximum is <= this squared matrix-dimension
# i.e. 8 <= 9 → 1 (truthy)
® # Push the squared matrix-dimension again
L # Create a list in the range [1, squared_matrix_dimension]
# i.e. 9 → [1,2,3,4,5,6,7,8,9]
¹ # Push the input-matrix
˜ # Flatten it
# i.e. [[8,0,6],[0,5,0],[0,0,2]] → [8,0,6,0,5,0,0,0,2]
K # Remove all these numbers from the ranged list
# i.e. [1,2,3,4,5,6,7,8,9] and [8,0,6,0,5,0,0,0,2] → [1,3,4,7,9]
œ # Get all possible permutations of the remaining numbers
# (this part is the main bottleneck of the program;
# the more 0s and too high numbers, the more permutations)
# i.e. [1,3,4,7,9] → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
0ª # Add an item 0 to the list (workaround for inputs without any 0s)
# i.e. [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1]]
# → [[1,3,4,7,9],[1,3,4,9,7],...,[9,7,4,1,3],[9,7,4,3,1],"0"]
ε # Map each permutation `y` to:
\ # Remove the implicit `y` which we don't need yet
¹˜ # Push the flattened input again
0 # Push a 0
y # Push permutation `y`
.; # Replace all 0s with the numbers in the permutation one by one
# i.e. [8,0,6,0,5,0,0,0,2] and [1,3,4,7,9]
# → [8,1,6,3,5,4,7,9,2]
¹g # Push the input-dimension again
ô # And split the flattened list into parts of that size,
# basically transforming it back into a matrix
# i.e. [8,1,6,3,5,4,7,9,2] and 3 → [[8,1,6],[3,5,4],[7,9,2]]
© # Save the matrix with all 0s filled in in the register (without popping)
O # Take the sum of each row
# i.e. [[8,1,6],[3,5,4],[7,9,2]] → [15,12,18]
®øO # Take the sum of each column
# i.e. [[8,1,6],[3,5,4],[7,9,2]] → [18,15,12]
®Å\O # Take the sum of the top-left to bottom-right main diagonal
# i.e. [[8,1,6],[3,5,4],[7,9,2]] → 15
®Å/O # Take the sum of the top-right to bottom-left main diagonal
# i.e. [[8,1,6],[3,5,4],[7,9,2]] → 18
) # Wrap everything on the stack into a list
# → [[15,12,18],[18,15,12],15,18]
˜ # Flatten it
# i.e. [[15,12,18],[18,15,12],15,18] → [15,12,18,18,15,12,15,18]
Ë # Check if all values are equal
# i.e. [15,12,18,18,15,12,15,18] → 0 (falsey)
} # After the map:
# → [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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
à # Check if any are truthy by taking the maximum
# → 1 (truthy)
* # And multiply the two checks to verify both are truthy
# i.e. 1 and 1 → 1 (truthy)
# (and output the result implicitly)
The part ©O®øO®Å\O®Å/O)˜Ë
is also used in my 05AB1E answer for the Verify Magic Square challenge, so see that answer for a more in-depth explanation about that part of the code.
Hmm. I think I've seen a solution somewhere.. – Matthew Roh – 2017-05-06T12:21:26.707
1Suggested test case to make sure that the diagonals are tested correctly:
[ [ 1, 5, 9 ], [ 6, 7, 2 ], [ 8, 3, 4 ] ]
(falsy) – Arnauld – 2017-05-06T13:17:06.023Can we number the placeholders (i.e.
[[8, X1, 6], [X2, 5, X3], [X4, 9, 2]]
)? – Scott Milner – 2017-05-07T00:13:09.737@Scott sure, feel free... – Stewie Griffin – 2017-05-07T08:45:54.813