Das deutsche Python-Forum

EyDu hat geschrieben:Willst du damit sagen, dass du optimierst, ohne zu prüfen ob die Optimierung auch schneller ist ?

Das muss man nicht prüfen, das kann man mit der Zeit riechen

Nein, das will ich nicht...

Hallo nochmal,
also vielen Dank, aber ihr habt euch so in eure Optimierung verstrickt dass ihr ganz übersehen habt dass keine der Möglichkeiten mein Problem löst...

Aber ihr habt sicher nichts dagegen wenn's noch ein bisschen komplizierter wird...

wenn mehr (1, 10) tupel auftauchen sollen auch entsprechend mehr Summen rauskommen.

Also damit meine ich, wenn die Liste am Anfang zB so aussieht:

Code: Alles auswählen

a = [(4,4),
       (1,10),
       (7,7),
       (10,10),
       (1,10)]

soll die Lösung so aussehen:

Code: Alles auswählen

[23, 32, 41]

Um das Prinzip nochmal zu verdeutlichen:

Code: Alles auswählen

[(1,10)]		      # ---> [1, 10]
[(1,10),(1,10)]		   # ---> [2, 11, 20]
[(1,10),(1,10),(1,10)]	# ---> [3, 12, 21, 30]
# etc.

Gruss,
Jo

Vielleicht liegt's an der Hitze, aber ich verstehe die Bildungsvorschrift nicht.

jo_hb hat geschrieben: Also damit meine ich, wenn die Liste am Anfang zB so aussieht:
Code: Alles auswählen
a = [(4,4),
       (1,10),
       (7,7),
       (10,10),
       (1,10)]
soll die Lösung so aussehen:
Code: Alles auswählen
[23, 32, 41]
Um das Prinzip nochmal zu verdeutlichen:
Code: Alles auswählen
[(1,10)]		      # ---> [1, 10]
[(1,10),(1,10)]		   # ---> [2, 11, 20]
[(1,10),(1,10),(1,10)]	# ---> [3, 12, 21, 30]
# etc.

Moin,

ich hab die Vorschrift:

Code: Alles auswählen

[(1,10),(1,10)]		   # ---> (1,  10)
Durchgang 1: Erweitern     #  (1,   0, 10)
Durchgang 2: Plus (1, 0)   #   (2,   1, 10)
Durchgang 3: Plus (0, 10) #   (2, 11, 20)

Nur, warum das Tupel erweitert wird, ist mir aus Jos Erklärung nicht erkennbar. Denn wenn man nur einfach die Elemente einzeln addiert, dann ergäbe sich (1+1+10, 10+1+10) = (12, 21). Sieht ein wenig aus wie Binomische Formeln der Addition.

Wie auch immer, mit der obigen Regel sollte Jo das jetzt in einen Pythonausdruck bringen können.

Viel Spaß,
Michael

Im Prinzip soll jedesmal, wenn ein (1,10) tupel auftaucht die Summe, die man durch die addition der bisherigen Tupel erreicht hat aufgeteilt werden, nämlich in einmal bisherige_summe+1 und einmal bisherige_summe+10.
d.h. in diesem Fall

Code: Alles auswählen

a=[(1,10),(1,10)]

würde im ersten Schritt

Code: Alles auswählen

[2,11,11,20]

rauskommen, nur soll das Ergebniss keine doppel enthalten. Ich dachte man könnte das vielleicht auch irgendwie in einem schritt machen, also nicht erst berechnen und dann in einem zweiten Durchgang die doppelten rauskicken?

Und *darauf* hätte man aufgrund Deiner spärlichen Beschreibungen kommen sollen!? Das ist nicht Dein ernst, oder?

Wobei ich jetzt immer noch nicht sicher bin, ob ich's verstanden habe. Wer weiss was für obskure Bedingungen und Vorschriften Du noch nicht verraten hast.

Was ist eigentlich der Sinn dieser Übung?

Hi Jo,

uns Leser scheint das Unverständnis zu einen. Die Vorschrift scheint doch nicht so logisch zu sein, wie ich oben andeutete. Scheinbar hast Du folgende Regel verwendet:
für n gleiche Tupel mit (x, y):

#(x*n, x*(n-1)+y, y*(n-2)+y*2, ..., x+y*(n-1), y*n)
=((n-a)*x + a*y) # für a = 0..n

Im Studium mussten wir so etwas ähnliches auch schon einmal rechnen. Aber nicht in Kombination mit den anderen Tupeln der Liste. Kannst Du uns ein praktisches Anwendungsbeispiel dafür nennen? Wie sieht z.B. die Lösung für folgende Listen aus:
[(1, 10), (4, 4), (4, 4), (1, 10)]
und
[(1, 10), (4, 4), (4, 4), (1, 10), (1, 10)]

Grüße,
Michael

Also ich hab's verstanden oO...

[(1, 10), (4, 4), (4, 4), (1, 10)]
und
[(1, 10), (4, 4), (4, 4), (1, 10), (1, 10)]

Bei dem ersten würde

[10, 19, 28]

und beim zweiten

[11...

Oh Gott, im Kopf dauert das mir zu lang. Auf jedenfall sollen alle möglichen Summen errechnet werden oO Aber keine doppelten Werte!

Also worum es dabei geht: tatsächlich um Blackjack!

Wo man nämlich Karten bekommt, also werte 2 bis 10, das dumme ist nur dass ein Ass wahlweise 1 oder 10 punkte wert ist, je nachdem was grad günstiger ist. Ich möchte allerdings nicht nur den jeweils niedrigsten oder höchsten Wert meiner Hand ausrechnen sondern alle, weil ich das dann wieder zusammenbringen will mit den Karten, die noch im Stapel sind, also noch kommen können.

Ergebnisse für die Beispiele weiter oben wären:

[(1, 10), (4, 4), (4, 4), (1, 10)]
-> [10, 19, 28]

und

[(1, 10), (4, 4), (4, 4), (1, 10), (1, 10)]
-> [11, 20, 29, 38]

Das mit den tupeln für alle Karten, also auch zB (4,4) liegt daran dass ich mir dachte es wäre dann irgendwie einfacher, wenn ass und andere Karten sozusagen im selben format / typ vorliegen, aber vielleicht geht's dann anders doch einfacher?

Danke jedenfalls schonmal für eure Hilfe,
Gruss,
Jo

Blackjack hat geschrieben:Und *darauf* hätte man aufgrund Deiner spärlichen Beschreibungen kommen sollen!? Das ist nicht Dein ernst, oder?

Mal provokant gefragt: Warum hast du einen Lösungsansatz angeboten, ohne die Aufgabenstellung verstanden zu haben?

Hui es geht um mich

Eine einfache, recht geradlinige Umsetzung könnte so aussehen:

Code: Alles auswählen

def add_card(values, card):
    result = [value + card for value in values]
    if card == 1:
        result += [value + 10 for value in values]
    return set(result)

def calculate_hand(cards):
    return sorted(reduce(add_card, cards, set([0])))


def main():
    print calculate_hand([1, 4, 4, 1, 1])
    print calculate_hand([1, 4, 4, 1])

@mawe: Ich dachte ja ich hätte die Aufgabenstellung verstanden und ich war auch nicht der einzige der sie so verstanden hat.

Hi Mawe,

die Frage ist, warum uns Jo ein bei weitem nicht hinreichend beschriebenes Zwischendingsda aus Problem und Lösungsansatz vorsetzt. Denn ich persönlich würde mich nicht auf Paare fixieren, nur weil ein Wert zwei Bedeutungen haben kann. Wie Du siehst kann man sich in einem komplizierten Ansatz verfangen, während man bei Kenntnis des eigentlichen Problems viel weiter außen hätte einfacher ansetzen können.

Und JETZT können wir über Optimierungen reden. Also, die Runde ist eröffnet!

EDIT: jetzt wo ich es nochmal lese, fällt es auch mir wie Schuppen aus den Haaren. Ich dachte es geht allgemein um mehrfach vorhandene Tupel...

Grüße,
der Michael

Naja warum kann ich dir schon sagen: Weil das eben die Stelle war an der ich festgesteckt bin, und dafür dann eine Lösung gesucht habe. Ich würde ja auch nicht kommen und sagen 'Windows ist Mist, ich möchte ein neues Betriebssystem schreiben, wie mach ich das denn', sondern erstmal anfangen und dann, mit einer Teillösung in der Tasche, für Teilprobleme nachfragen.

Gut, wenn dann die Teillösung auch schon krumm ist ist das ne andere Geschichte. Trotzdem würde ich sagen dass eine Beschreibung wie 'wenn tupel (1,10) mehrfach auftauchen sollen auch entsprechend mehr Lösungen rauskommen' soo missverständlich nun auch wieder nicht ist - wenn man den Satz liest, wüsste ich nicht wie man den sonst verstehen sollte, vielleicht dass die Summen die rauskommen dann höher sind? Wohl kaum. Wenn man ihn, den Satz, aber gar nicht versteht, sollte man tatsächlich nachfragen und ihn nicht einfach ignorieren.

Naja, jetzt aber auch gut. Ich werd beim nächsten Mal mehr drauf achten wirklich eindeutig zu schreiben. Und danke euch trotzdem nochmal für eure Hilfe!

Gruss,
Jo

Michael Schneider hat geschrieben:Und JETZT können wir über Optimierungen reden. Also, die Runde ist eröffnet!

Fällt mir nix ein, aber ich hätte einen Einzeiler:

Code: Alles auswählen

calculate_hand=lambda c:sorted(set(reduce(lambda s,c:[v+c for v in s]+(c==1and[v+10for v in s]or[]),c,[0])))

Argh. Doch. Reduce ist unglaublich langsam, das lässt sich sogar mit einer Python only Implementierung schlagen Oo:

Code: Alles auswählen

def calculate_hand(cards):
    tmp = [0]
    for c in cards:
        tmp = [v + c for v in tmp] + (c == 1 and [v + 10 for v in tmp] or [])
    return sorted(set(tmp))

In etwa doppelt so schnell.
(Wenn man den and/or Trick vermeidet muss man eine Kopie von tmp anlegen, das macht die Sache dann langsamer)

//EDIT: wenn man die vielen set instanzierungen rausnimmt nähern sie sich an.

Darum wird es reduce auch bald nicht mehr geben

Moin,

dann war mein Ansatz

=((n-a)*x + a*y) # für jedes a der Menge 0..n

ja doch nicht so falsch.

Was haltet ihr von dieser Variante:

Code: Alles auswählen

def calc_hand(l):
    n = l.count(1)
    return map(sum, zip([sum(l)-n]*(n+1), (9*a+n for a in range(n+1))))

l = [4, 1, 7, 10, 1]
calc_hand(l)
# [23, 32, 41]

Ich habe die normalen Zahlen aufsummiert, dann nach der obigen Vorschrift die Variationen aus den n (1, 10) Tupeln ermittelt und dann diese Tupel summiert.

Wie geht das eigentlich mit der Geschwindigkeitsmessung? Wo liegt die Lösung?

Grüße,
Michael

Hi Jo!

jo_hb hat geschrieben:Also worum es dabei geht: tatsächlich um Blackjack!

Du hast es aber mit Glücksspielen.

jo_hb hat geschrieben:Das mit den tupeln für alle Karten, also auch zB (4,4) liegt daran dass ich mir dachte es wäre dann irgendwie einfacher, wenn ass und andere Karten sozusagen im selben format / typ vorliegen, aber vielleicht geht's dann anders doch einfacher?

Danke jedenfalls schonmal für eure Hilfe,

Ich habe noch einmal versucht, meinen Ansatz hinsichtlich der Berechnungsgeschwindigkeit für den mehrfachen Aufruf zu optimieren - d. h. möglichst viel aus der Funktion auszulagern, was nur einmal berechnet werden muss. Da die Kombinationsmöglichkeiten aufgrund der Austauschbarkeit der Asse in der Zählung doch arg begrenzt sind und es nur 8 Asse = 9 Möglichkeiten (0-8 auf der Hand) gibt, kann man alle Kombinationen schonmal vorher abspeichern. Sowas nennen die Hacker doch "Rainbow-Table", oder?

Hier mal mein Ansatz:

Code: Alles auswählen

#   Mapping Dictionary berechnen, das fuer die Anzahl der Asse die
#   moeglichen Punktzahl-Kombinationen liefert
dMap = {}
for iAces in xrange(9):
    dMap[iAces] = [(9 * i + iAces) for i in xrange(iAces+1)]
print dMap
    
def calc_hand(lCards):
    "Berechnung der Punktzahl-Kombinationen aus Assen und zusammengezogenem Rest"
    iAces = lCards.count(1)
    iStaticValue = sum(lCards)-iAces
    return map(lambda iDynValue: iDynValue + iStaticValue, dMap[iAces])

l = [4, 1, 7, 10, 1]
print calc_hand(l)

Aber da habe ich auch eine Frage: was ist schneller, in calc_hand die Lambda-Funktion zu erzeugen oder doch alternativ mit zip eine Liste von Tupeln, die man per map(sum...) aufsummiert? Dann muss man aber aus iStaticValue auch erst eine Liste oder einen Generator machen...

Grüße,
Michael

Das deutsche Python-Forum

Problem mit summen in tupeln