Producto máximo concatenado

11

Se nos da una lista de enteros p1, ..., pk (no necesariamente distintos) donde cada uno tiene un valor entre 1 y 9, inclusive. Usando cada uno de los p1, ..., pk exactamente una vez, podemos formar concatenaciones de dígitos, para lograr una nueva lista de números; Luego sacamos el producto de esta nueva lista. El objetivo es maximizar este producto eligiendo las mejores concatenaciones de dígitos.

Por ejemplo, se nos da la lista: 2 3 2 (separados por espacios). Podemos formar las siguientes concatenaciones:

  • 2 3 2(producto de estas concatenaciones es 12)
  • 23 2(producto es 46)
  • 32 2(producto es 64)
  • 22 3(producto es 66)

Dado que el producto más grande que podemos formar de concatenaciones es 66, lo sacamos.

Reglas:

  • Debe haber al menos una multiplicación (es decir, no puede concatenar todos los dígitos y generarlos).
  • No puede usar ningún otro operador que no sea la multiplicación, o insertar paréntesis, etc.
  • Suponga que la lista de enteros dada está separada por espacios, y todos los enteros tienen valores entre 1 y 9.

¡El código más corto (en bytes) gana!

Casos de prueba:

Entrada 1 2 3:; Salida: 63(es decir, 21*3)

Entrada 2 5 9:; Salida: 468( 52*9)

Entrada 1 2 3 4:; Salida: 1312( 41*32)

Ryan
fuente
¿Deberíamos escribir un programa completo o una función tomando parámetros de entrada y devolviendo el resultado también está bien?
randomra
@randomra Sí, está bien.
Ryan
Para cada par de números a, b, el producto a * b. Es menor que la concatenación simple ab (= a * 10 ^ (dígitos de b) + b). Entonces solo 1 producto (como es obligatorio). Agregue esto: codegolf.stackexchange.com/q/49854/21348
edc65

Respuestas:

8

CJam, 32 28 23 12 bytes

0le!f{~*}:e>

Pruébelo en línea en el intérprete de CJam .

¡Gracias a @ user23013 por ayudarme a guardar 16 bytes completos!

Idea

Permutar los caracteres en la cadena de entrada lo divide en enteros (grupos de dígitos consecutivos) separados por espacios. Al presionar un cero y luego evaluar la cadena de entrada permutada, empujamos dos o más enteros. Multiplicar los dos más altos dará como resultado el producto de la entrada dividido en exactamente dos enteros o algún valor subóptimo.

Código

 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.
Dennis
fuente
1
l2%_,,1>\e!m*{~S+m<~*}%$W=.
jimmy23013
2
l2%S+e!{0\~*}%$W=.
jimmy23013
2

CJam, 36 35 bytes

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

Muy claro. Repite todas las combinaciones posibles y las ordena por producto. Luego sale el más grande. Todo esto, teniendo en cuenta que al menos 1 multiplicación debe estar presente.

Agregará una explicación pronto.

Pruébalo en línea aquí

Optimizador
fuente
1

JavaScript (ES6) 125

Editar Creo que @oberon lo hizo bien: "cada nuevo dígito debe concatenarse al número más pequeño"

No cambiaré esta respuesta robando su idea. La implementación en ES6 sería de 70 bytes (el signo cambió en comparación para comparar como número y no cadenas)

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

Mi solución

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

Como dije en los comentarios, para cada par de números a, b, el producto a * b es menor que la concatenación simple ab (= a * 10 ^ (dígitos de b) + b). Por lo tanto, es mejor evitar productos y preferir la concatenación, pero como se solicita al menos 1 producto, tenemos que construir 2 números y multiplicarlos.

Intento todos los grupos posibles de dígitos, construyendo un par de números para multiplicar. Cada número se construye obviamente tomando dígitos en orden decreciente.

Por ejemplo, con una lista de 4 números, [1 2 3 4] - intente:

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

El máximo de estos valores es el resultado que necesitamos.

Las agrupaciones se pueden enumerar en bucle en un mapa de bits de 4 bits, con un valor mínimo 0001 y un valor máximo 0111 (es decir, 1 << (4 -1) - 1)

No tan golfizado

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
}

Prueba usando el fragmento de abajo en 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>

edc65
fuente
1

Python 3, 111 bytes

Probablemente sea mucho más golfable. Sin embargo, me gusta su tiempo de ejecución (O ( n log n ), ¿verdad?).

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 con explicación.

# 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])
Oberon
fuente
0

Pyth, 25 bytes

eSsmm*ss<dkss>dkr1ld.pcz)

Doy vueltas sobre cada permutación de la entrada. Entonces, como cada combinación óptima consta de dos enteros, simplemente la dividí en cada posición posible y multipliqué las divisiones concatenadas. Luego ordeno y obtengo el último elemento.

orlp
fuente
0

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='')))}

Como método, no estoy seguro de si esto es robusto. Con los casos que he probado, parece funcionar cada vez. Intenté probarlo con la solución de optimizadores y parece estar bien también con eso. Estoy más que preparado para demostrar que estoy equivocado :) Hay espacio para jugar al golf, pero esperaba obtener algunos comentarios sobre el método primero.

El proceso general es:

  • Ordenar la lista en orden descendente
  • Cambia el primer par impar / par que difiere
  • Concatenar los elementos pares e impares de la lista
  • Evaluar el producto de los dos resultados.

Ampliado con algunos comentarios

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=''))) 
}

Y algunas ejecuciones de prueba (implementadas como una función llamada 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
MickyT
fuente