Maksymalnie skonkatenowany produkt

11

Dajemy listę liczb całkowitych p1, ..., pk (niekoniecznie różne), gdzie każda z nich ma wartość od 1 do 9 włącznie. Używając każdego z p1, ..., pk dokładnie raz, możemy utworzyć konkatenację cyfr, aby uzyskać nową listę liczb; następnie wyprowadzamy produkt z tej nowej listy. Celem jest maksymalizacja tego produktu poprzez wybranie najlepszej kombinacji cyfr.

Na przykład dostajemy listę: 2 3 2 (oddzielone spacjami). Możemy utworzyć następujące konkatenacje:

  • 2 3 2(produktem tych konkatenacji jest 12)
  • 23 2(produkt jest 46)
  • 32 2(produkt jest 64)
  • 22 3(produkt jest 66)

Ponieważ największym produktem, który możemy stworzyć w postaci konkatenacji, jest 66, wytwarzamy to.

Zasady:

  • Musi istnieć co najmniej jedno mnożenie (tzn. Nie można po prostu połączyć wszystkich cyfr i wygenerować tego).
  • Nie możesz używać innych operatorów niż mnożenie, ani wstawiać nawiasów itp.
  • Załóżmy, że podana lista liczb całkowitych jest oddzielona spacjami, a wszystkie liczby całkowite mają wartości od 1 do 9.

Najkrótszy kod (w bajtach) wygrywa!

Przypadki testowe:

Wejście: 1 2 3; Wyjście: 63(tj. 21*3)

Wejście: 2 5 9; Wyjście: 468( 52*9)

Wejście: 1 2 3 4; Wyjście: 1312( 41*32)

Ryan
źródło
Czy powinniśmy napisać cały program lub funkcję, biorąc parametry wejściowe i zwracając wynik, również jest w porządku?
randomra
@randomra Tak, w porządku.
Ryan,
Dla każdej pary liczb a, b iloczyn a * b. Jest mniejszy niż prosta konkatenacja ab (= a * 10 ^ (cyfry b) + b). Tak więc tylko 1 produkt (ponieważ jest to obowiązkowe). Dodaj to: codegolf.stackexchange.com/q/49854/21348
edc65

Odpowiedzi:

8

CJam, 32 28 23 12 bajtów

0le!f{~*}:e>

Wypróbuj online w interpretatorze CJam .

Dzięki @ user23013 za pomoc w uratowaniu 16 całych bajtów!

Pomysł

Dopuszczenie znaków w ciągu wejściowym dzieli go na liczby całkowite (grupy kolejnych cyfr) oddzielone spacjami. Naciskając zero, a następnie oceniając permutowany ciąg wejściowy, wypychamy dwie lub więcej liczb całkowitych. Pomnożenie dwóch najwyższych spowoduje wynik iloczynu wejścia podzielonego na dokładnie dwie liczby całkowite lub pewną nieoptymalną wartość.

Kod

 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
źródło
1
l2%_,,1>\e!m*{~S+m<~*}%$W=.
jimmy23013
2
l2%S+e!{0\~*}%$W=.
jimmy23013
2

CJam, 36 35 bajtów

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

Całkiem prosto. Powtarza wszystkie możliwe kombinacje i sortuje je według produktu. Następnie wypisuje największy. Wszystko to, pamiętając, że powinno być obecne co najmniej 1 mnożenie.

Wkrótce doda wyjaśnienie.

Wypróbuj online tutaj

Optymalizator
źródło
1

JavaScript (ES6) 125

Edytować Myślę, że @oberon ma rację: „każda nowa cyfra musi być powiązana z najmniejszą liczbą”

Nie zmienię tej odpowiedzi, kradnąc jego pomysł. Implementacja w ES6 miałaby 70 bajtów (znak zmieniony w porównaniu do porównania jako liczba, a nie łańcuchy)

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

Moje rozwiązanie

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

Jak powiedziałem w komentarzach, dla każdej pary liczb a, b iloczyn a * b jest mniejszy niż zwykła konkatenacja ab (= a * 10 ^ (cyfry b) + b). Lepiej więc unikać produktów i preferować konkatenację, ale ponieważ wymagany jest co najmniej 1 produkt, musimy zbudować 2 liczby i pomnożyć je.

Próbuję wszystkich możliwych grupowań cyfr, budując parę liczb do pomnożenia. Każda liczba jest oczywiście budowana przy użyciu cyfr w malejącej kolejności.

Na przykład z listą 4 cyfr [1 2 3 4] - spróbuj:

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

Maksymalna z tych wartości to wynik, którego potrzebujemy.

Zgrupowania można wyliczyć zapętlając mapę bitową o 4 bitach, z wartością minimalną 0001 i wartością maksymalną 0111 (czyli 1 << (4 -1) - 1)

Nie tak golfa

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
}

Przetestuj za pomocą poniższego fragmentu w przeglądarce 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
źródło
1

Python 3, 111 bajtów

Prawdopodobnie jest o wiele bardziej golfowy. Lubię jednak jego czas działania (O ( n log n ), prawda?).

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])

Nie obeznany z wyjaśnieniem.

# 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
źródło
0

Pyth, 25 bajtów

eSsmm*ss<dkss>dkr1ld.pcz)

Pętlę nad każdą permutacją wejścia. Ponieważ więc każda optymalna kombinacja składa się z dwóch liczb całkowitych, po prostu dzielę ją w każdej możliwej pozycji i mnożę konkatenowane podziały. Następnie sortuję i otrzymuję ostatni element.

orlp
źródło
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='')))}

Jako metoda nie jestem pewien, czy jest to solidne. W przypadkach, które przetestowałem, wydaje się, że działa za każdym razem. Próbowałem przetestować go pod kątem rozwiązania optymalizującego i wydaje się, że jest to również w porządku. Jestem więcej niż przygotowany na udowodnienie, że się mylę :) Jest miejsce na grę w golfa, ale miałem nadzieję, że najpierw otrzymam opinię na temat tej metody.

Ogólny proces to:

  • Posortuj listę w kolejności malejącej
  • Zamień pierwszą parę parzystą / nieparzystą, która się różni
  • Połącz parzyste i nieparzyste elementy listy
  • Oceń iloczyn dwóch wyników

Rozszerzony o kilka komentarzy

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

I niektóre testy (zaimplementowane jako funkcja o nazwie 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
źródło