Maximal verkettetes Produkt

11

Wir erhalten eine Liste von ganzen Zahlen p1, ..., pk (nicht unbedingt verschieden), wobei jede einen Wert zwischen 1 und 9 einschließlich hat. Mit jedem der p1, ..., pk genau einmal können wir Verkettungen von Ziffern bilden, um eine neue Liste von Zahlen zu erhalten; Wir geben dann das Produkt dieser neuen Liste aus. Ziel ist es, dieses Produkt zu maximieren, indem die besten Verkettungen von Ziffern ausgewählt werden.

Zum Beispiel erhalten wir die Liste: 2 3 2 (durch Leerzeichen getrennt). Wir können die folgenden Verkettungen bilden:

  • 2 3 2(Produkt dieser Verkettungen ist 12)
  • 23 2(Produkt ist 46)
  • 32 2(Produkt ist 64)
  • 22 3(Produkt ist 66)

Da das größte Produkt, das wir aus Verkettungen bilden können, 66 ist, geben wir das aus.

Regeln:

  • Es muss mindestens eine Multiplikation geben (dh Sie können nicht einfach alle Ziffern verketten und diese ausgeben).
  • Sie können keine anderen Operatoren als die Multiplikation verwenden oder Klammern usw. einfügen.
  • Angenommen, die Liste der angegebenen Ganzzahlen ist durch Leerzeichen getrennt, und alle Ganzzahlen haben Werte zwischen 1 und 9.

Der kürzeste Code (in Bytes) gewinnt!

Testfälle:

Eingabe : 1 2 3; Ausgabe: 63(dh 21*3)

Eingabe : 2 5 9; Ausgabe: 468( 52*9)

Eingabe : 1 2 3 4; Ausgabe: 1312( 41*32)

Ryan
quelle
Sollten wir ein ganzes Programm oder eine Funktion schreiben, die Eingabeparameter übernimmt und das Ergebnis zurückgibt, ist auch in Ordnung?
Randomra
@randomra Ja, das ist in Ordnung.
Ryan
Für jedes Zahlenpaar a, b ist das Produkt a * b kleiner als die einfache Verkettung ab (= a * 10 ^ (Ziffern von b) + b). Also nur 1 Produkt (wie es obligatorisch ist). Fügen Sie dies hinzu: codegolf.stackexchange.com/q/49854/21348
edc65

Antworten:

8

CJam, 32 28 23 12 Bytes

0le!f{~*}:e>

Probieren Sie es online im CJam-Interpreter aus .

Vielen Dank an @ user23013, der mir geholfen hat, 16 ganze Bytes zu sparen!

Idee

Durch Zulassen der Zeichen in der Eingabezeichenfolge wird diese in Ganzzahlen (Gruppen aufeinanderfolgender Ziffern) unterteilt, die durch Leerzeichen getrennt sind. Durch Drücken einer Null und anschließendes Auswerten der permutierten Eingabezeichenfolge werden zwei oder mehr Ganzzahlen verschoben. Das Multiplizieren der obersten zwei ergibt entweder das Produkt der Eingabe, das in genau zwei ganze Zahlen geteilt wird, oder einen suboptimalen Wert.

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.
Dennis
quelle
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=

Ziemlich einfach. Iteriert alle möglichen Kombinationen und sortiert sie nach Produkt. Dann wird die größte ausgegeben. Dies alles unter Berücksichtigung, dass mindestens 1 Multiplikation vorhanden sein sollte.

Wird bald eine Erklärung hinzufügen.

Probieren Sie es hier online aus

Optimierer
quelle
1

JavaScript (ES6) 125

Bearbeiten Ich denke, @oberon hat es richtig gemacht: "Jede neue Ziffer muss mit der kleinsten Zahl verkettet werden."

Ich werde diese Antwort nicht ändern, um seine Idee zu stehlen. Die Implementierung in ES6 würde 70 Bytes betragen (Vorzeichen geändert im Vergleich zum Vergleich als Zahl und nicht als Zeichenfolgen)

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

Meine Lösung

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

Wie ich in den Kommentaren sagte, ist für jedes Zahlenpaar a, b das Produkt a * b kleiner als die einfache Verkettung ab (= a * 10 ^ (Ziffern von b) + b). Es ist also besser, Produkte zu vermeiden und Verkettung zu bevorzugen, aber da mindestens 1 Produkt angefordert wird, müssen wir 2 Zahlen erstellen und diese multiplizieren.

Ich versuche alle möglichen Gruppierungen von Ziffern und baue ein Zahlenpaar, um es zu multiplizieren. Jede Zahl wird offensichtlich in absteigender Reihenfolge mit Ziffern erstellt.

Zum Beispiel mit einer Liste von 4 Zahlen, [1 2 3 4] - versuchen Sie:

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

Das Maximum dieser Werte ist das Ergebnis, das wir brauchen.

Die Gruppierungen können in einer Bitmap von 4 Bits mit dem Minimalwert 0001 und dem Maximalwert 0111 (dh 1 << (4 -1) - 1) in einer Schleife aufgelistet werden.

Nicht so golfen

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
}

Testen Sie mit dem folgenden Snippet 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>

edc65
quelle
1

Python 3, 111 Bytes

Es ist wahrscheinlich viel golffähiger. Ich mag die Laufzeit (O ( n log n ), oder?).

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 mit Erklärung.

# 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
quelle
0

Pyth, 25 Bytes

eSsmm*ss<dkss>dkr1ld.pcz)

Ich durchlaufe jede Permutation der Eingabe. Da dann jede optimale Kombination aus zwei ganzen Zahlen besteht, teile ich sie lediglich an jeder möglichen Position und multipliziere die verketteten Teilungen. Ich sortiere und erhalte dann das letzte Element.

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

Als Methode bin ich mir nicht sicher, ob dies robust ist. Mit den Fällen, die ich getestet habe, scheint es jedes Mal zu funktionieren. Ich habe versucht, es gegen die Optimiererlösung zu testen, und es scheint auch dagegen in Ordnung zu sein. Ich bin mehr als bereit, mich als falsch zu erweisen :) Es gibt Raum zum Golfen, aber ich hatte gehofft, zuerst ein Feedback zur Methode zu bekommen.

Der allgemeine Prozess ist:

  • Sortieren Sie die Liste in absteigender Reihenfolge
  • Tauschen Sie das erste ungerade / gerade Paar aus, das sich unterscheidet
  • Verketten Sie die geraden und ungeraden Elemente der Liste
  • Bewerten Sie das Produkt der beiden Ergebnisse

Mit einigen Kommentaren erweitert

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

Und einige Testläufe (implementiert als Funktion namens 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
quelle