Square from Digits with Largest Sum

Question

You should write a program or function which receives a list of digits as input and outputs or returns the largest sum achievable by putting these digits in a square.

Input will always contain a square number of digits. An example square arrangement for the input 9 1 2 3 4 5 6 7 7 could be

677
943
125

The sum is calculated as the sum of all rows and columns. For the above arrangement the sum would be 677 + 943 + 125 + 691 + 742 + 735 = 3913. Note that this is not the maximal sum so this isn't the expected output.

Input

• A list with length n^2 (n>=1) containing non-zero digits (1-9).

Output

• An integer, the largest sum achievable with the input digits put in a square.

Examples

Example format is input => output.

5 => 10

1 2 3 4 => 137

5 8 6 8 => 324

9 1 2 3 4 5 6 7 7 => 4588

2 4 9 7 3 4 2 1 3 => 3823

8 2 9 4 8 1 9 3 4 6 3 8 1 5 7 1 => 68423

5 4 3 6 9 2 6 8 8 1 6 8 5 2 8 4 2 4 5 7 3 7 6 6 7 => 836445

This is code golf so the shortest entry wins.

Answer 1

Pyth, 15 bytes

s*VSsM^^LTUQ2SQ

Demonstration. Test harness.

Note: Input in any python sequence format, such as a,b,c, or [a, b, c]. Fails on a.

This will be an explanation for the example input 5,8,6,8.

^LTUQ: This is a list of powers of 10, out to the length of Q. [1, 10, 100, 1000].

^ ... 2: Then, we take pairs of powers of 10. [[1, 1], [1, 10], ....

sM: Then, we sum those pairs. [2, 11, 101, ... Each number repesents the value of a grid location. The value of the bottom right corner is 2, because the digit placed there is in the ones place of the two numbers it is in. Note that 16 values were generated, even though we only need 4. This will be handled shortly.

S: Sort the value in increasing order. [2, 11, 11, 20, 101, .... Note that the only values which are relevant for this input are the first 4, because this square will not have hundreds or thousands places.

SQ: Sort the input in ascending order. [5, 6, 8, 8]

*V: Vectorized multiplication over the two lists. Pyth's vectorized multiplication truncates the longer input, so this performs [5*2, 6*11, 8*11, 8*20], equivalent to filling in the grid, smallest to largest, bottom right to top left.

s: Sum the results, 324. Printing is implicit.

Answer 2

CJam, 23 bytes

q~$_,mQ,A\f#2m*::+$.*:+

Try it online. Generates the weights for each cell and assigns the highest digits to the highest weights.

An alternative 23:

q~$_,mQ_,A\f#*_$.+$.*:+

Answer 3

CJam, 25 bytes

q~_e!\,mqf/{_z+Afb:+}%$W=

Pretty straight forward approach. Generate all combinations, get the sum, print largest.

Try it online here

Answer 4

Husk, 16 bytes

▲moS(ṁd+)TSCo√LP

Try it online!

Husk, 16 bytes

Σz*O¹OmΣπ2↑:1İ⁰L

Try it online!

same idea as isaacg's answer.

Somehow both of these are still 1 byte more than Pyth.

Answer 5

Japt -x, 13 bytes

Tried a few different approaches with permutations and partitions but, in the end, an adaptation of isaacg's solution ended up being the shortest.

ñ í*¡ApYÃï+ ñ

Try it or run all test cases

ñ í*¡ApYÃï+ ñ     :Implicit input of array U
ñ                 :Sort
  í               :Interleave with
   *              :And reduce each pair my multiplication
    ¡             :  Map each 0-based index Y in U
     A            :    10
      pY          :    Raised to the power of Y
        Ã         :  End map
         ï        :  Cartesian product with itself
          +       :  Reduce each pair by addition
            ñ     :  Sort
                  :Implicit output of sum of resulting array