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