Maximum Concatenated Product

Question

We are given a list of integers p1, ..., pk (not necessarily distinct) where each has a value between 1 and 9, inclusive. Using each of the p1, ..., pk exactly once, we can form concatenations of digits, to achieve a new list of numbers; we then output the product of this new list. The goal is to maximize this product by choosing the best concatenations of digits.

For example, we are given the list: 2 3 2 (separated by spaces). We can form the following concatenations:

• 2 3 2 (product of these concatenations is 12)
• 23 2 (product is 46)
• 32 2 (product is 64)
• 22 3 (product is 66)

Since the largest product that we can form of concatenations is 66, we output that.

Rules:

• There must be at least one multiplication (i.e., you cannot just concatenate all of the digits and output that).
• You cannot use any other operators other than multiplication, or insert parentheses, etc.
• Assume that the list of integers given is separated by spaces, and all integers have values between 1 and 9.

Shortest code (in bytes) wins!

Test cases:

Input: 1 2 3; Output: 63 (i.e., 21*3)

Input: 2 5 9; Output: 468 (52*9)

Input: 1 2 3 4; Output: 1312 (41*32)

Answer 1

CJam, 32 28 23 12 bytes

0le!f{~*}:e>

Try it online in the CJam interpreter.

Thanks to @user23013 for helping me save 16 whole bytes!

Idea

Permuting the characters in the input string divides it into integers (groups of consecutive digits) separated by spaces. By pushing a zero and then evaluating the permuted input string, we push two or more integers. Multiplying the topmost two will result either in the product of the input divided into exactly two integers or some suboptimal value.

Code

 le!         e# Push all possible character permutations of the input.
0   f{  }    e# For each permutation:
             e#   Push 0, then the permuted string.
      ~      e#   Evaluate the string. Pushes one or more integers.
       *     e#   Multiply the two topmost integers.
         :e> e# Retrieve the greatest integer in the array.

Answer 2

CJam, 36 35 bytes

q~]_,([SL]m*{s},\e!\m*{z[s~]:*}%$W=

Pretty straight forward. Iterates over all possible combinations and sorts them by product. Then outputs the largest. All this, keeping in mind that at least 1 multiplication should be present.

Will add explanation soon.

Try it online here

Answer 3

JavaScript (ES6) 125

Edit I think @oberon got it right : "each new digit must be concatenated to the smallest number"

I'll not change this answer stealing his idea. Implementation in ES6 would be 70 bytes (sign changed in comparison to compare as number and not strings)

f=l=>l.split(' ').sort().reverse().map(d=>-a>-b?a+=d:b+=d,a=b='')||a*b

My solution

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

As I said in comments, for each pair of numbers a,b, the product a*b is less than the simple concatenation ab (=a*10^(digits of b)+b). So it's better to avoid products and prefer concatenation, but as at least 1 product is requested, we have to build 2 numbers and multiply them.

I try all possible grouping of digits, building a pair of numbers to multiply. Each number is obviosuly built taking digits in decreasing order.

For instance, with a list of 4 numbers, [1 2 3 4] - try:

• 4 * 321
• 43 * 21
• 42 * 31
• 41 * 32
• 432 * 1
• 431 * 2
• 421 * 3

The max of these value is the result we need.

The groupings can be enumerated looping on a bitmap of 4 bits, with min value 0001 and max value 0111 (that is 1<<(4 -1) - 1)

Not so golfed

f=l=>{
  l = l.split(' '); // string to array
  l.sort().reverse(); // decreasing order 
  m = 1 << (l.length-1); starting value fro loop
  r = 0 
  // loop from m-1 down to 1
  for(i=m; --i; )
  {
    a = b = '';
    k = i;
    for(v of l) // divide the digits base on bits of i
    {
      k & 1 ? a+=v : b+=v;
      k /= 2;
    }
    if (r < a*b) r = a*b; // remember max value in r
  }
  return r
}

Test using the snippet below in Firefox.

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

t=l=>(i=>{for(x=r='';a=b='',k=--i;r<a*b?(r=a*b,x=' = '+a+'x'+b):0)for(v of l)k&1?a+=v:b+=v,k/=2})
(1<<~-(l=l.split(' ').sort().reverse()).length)|| x

function go()
{
  R.value = f(I.value) // TEST AS IS
   + t(I.value) // Some more info
}

test=['1 2 3 4','1 2 3','2 5 9','8 9 8']

test.forEach(t => O.innerHTML = O.innerHTML + (t + ' -> ' + f(t)) + '\n')

Type your list: <input id=I><button onclick='go()'>-></button><input readonly id=R><br>
<pre id=O></pre>

Answer 4

Python 3, 111 bytes

It's probably much more golfable. I like its running time, though (O(n log n), is it?).

l=sorted(map(int,input().split()),reverse=1);m=[0,0]
for x in l:i=m[0]>m[1];m[i]=m[i]*10+x
print(m[0]*m[1])

Ungolfed with explanation.

# edc65 has already explained that the optimal solution can be found applying a single
# multiplication. thus, given that
#     (10x + d)y > (10y + d)x
# where x, y are the two numbers and d is the next digit to insert, it follows that
#     y > x
# and thus each new digit must be concatenated to the smallest number. obviously, digits
# should be added in descending order.
l = sorted(map(int, input().split()), reverse=1)
m = [0,0]
for x in l:
    i = m[0] > m[1]
    m[i] = m[i]*10 + x
print(m[0] * m[1])

Answer 5

R, 164

function(n){l=length(n);a=sort(n,T);i=1;while(a[i]==a[i+1]&&i<l-2)i=i+2;a[c(i,i+1)]=a[c(i+1,i)];eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse='')))}

As a method I'm unsure if this is robust. With the cases that I have tested it appears to work each time. I tried testing it against optimizers solution and it appears to be OK against that as well. I'm more than prepared to be proven wrong :) There's room for golfing, but I was hoping to get some feedback on the method first.

The general process is :

• Sort the list in descending order
• Swap the first odd/even pair that differ
• Concatenate the even and odd items of the list
• Evaluate the product of the two results

Expanded out with some comments

function(n){
    l=length(n);
    a=sort(n,T);    # sort descending order
    # Determine which pair to swap
    i=1;
    while(a[i]==a[i+1]&&i<l-2)i=i+2;
    a[c(i,i+1)]=a[c(i+1,i)];  # swap pair   
    # concatenate the even and odd indices items around a * and evaluate    
    eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse=''))) 
}

And some test runs (implemented as a function called g)

> g(c(1,2,3))
[1] 63
> g(c(2,5,9))
[1] 468
> g(c(1,2,3,4))
[1] 1312
> g(c(1,2,3,5,5,5))
[1] 293132
> g(c(1,5,7,7,9,9))
[1] 946725
> g(c(1,7,8,9,9,9))
[1] 978117
> g(c(7,8,9,9,9))  #Test case provided edc65 to randomra
[1] 97713

Answer 6

Pyth, 25 bytes

eSsmm*ss<dkss>dkr1ld.pcz)

I loop over every permutation of the input. Then because every optimal combination consists of two integers I merely split it at every possible position, and multiply the concatenated splits. I then sort and get the last element.