Skip to main content
Code Golf

Return to Answer

use the builtin suggested by @Dennis in the comments
Source Link
ais523
ais523
  • 11
  • 19
  • 35

Jelly, 1010 6 bytes

ZŒ!ŒDḢSƊ€ṀÆṭṀ

Try it online!Try it online!

Wow(4 bytes saved by @Dennis, who pointed out that Jelly had a "sum of main diagonal" builtin. I haven't outgolfed Dennis in monthswas not expecting it to have one of those; the previous solution implemented the operation without using the builtin. TimeThe operation in question, Æṭ, is defined as "trace", but the trace is only defined for square matrices; Jelly implements a generalisation to correct thatrectangular matrices too.)

The improvement over the other answers is mostly from a simpler (thus terser to express) algorithm.

Thisalgorithm; this program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

ZŒ!ŒDḢSƊ€ṀÆṭṀ Z Swap rows and columns Œ! Find all permutations of rows (thus columns of the original) Æṭ Ɗ€ {For each permutation: ŒD Take its diagonals Ḣ Keep only the main diagonal S }, Taketake the sum of thatthe main diagonal Ṁ Ṁ Take the maximum

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

Jelly, 10 bytes

ZŒ!ŒDḢSƊ€Ṁ

Try it online!

Wow, I haven't outgolfed Dennis in months. Time to correct that. The improvement is mostly from a simpler (thus terser to express) algorithm.

This program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

ZŒ!ŒDḢSƊ€Ṁ Z Swap rows and columns Œ! Find all permutations of rows (thus columns of the original) Ɗ€ For each permutation: ŒD Take its diagonals Ḣ Keep only the main diagonal S  Take the sum of that main diagonal Ṁ Take the maximum

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

Jelly, 10 6 bytes

ZŒ!ÆṭṀ

Try it online!

(4 bytes saved by @Dennis, who pointed out that Jelly had a "sum of main diagonal" builtin. I was not expecting it to have one of those; the previous solution implemented the operation without using the builtin. The operation in question, Æṭ, is defined as "trace", but the trace is only defined for square matrices; Jelly implements a generalisation to rectangular matrices too.)

The improvement over the other answers is mostly from a simpler (thus terser to express) algorithm; this program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

ZŒ!ÆṭṀ Z Swap rows and columns Œ! Find all permutations of rows (thus columns of the original) Æṭ {For each permutation}, take the sum of the main diagonal Ṁ Take the maximum

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

Source Link
ais523
ais523
  • 11
  • 19
  • 35

Jelly, 10 bytes

ZŒ!ŒDḢSƊ€Ṁ

Try it online!

Wow, I haven't outgolfed Dennis in months. Time to correct that. The improvement is mostly from a simpler (thus terser to express) algorithm.

This program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

ZŒ!ŒDḢSƊ€Ṁ Z Swap rows and columns Œ! Find all permutations of rows (thus columns of the original) Ɗ€ For each permutation: ŒD Take its diagonals Ḣ Keep only the main diagonal S Take the sum of that main diagonal Ṁ Take the maximum

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

Post Made Community Wiki by ais523