Problem mit summen in tupeln

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
jo_hb
User
Beiträge: 72
Registriert: Donnerstag 26. April 2007, 09:21

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?
BlackJack

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

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?
Benutzeravatar
Michael Schneider
User
Beiträge: 569
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Brandenburg

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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

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!
jo_hb
User
Beiträge: 72
Registriert: Donnerstag 26. April 2007, 09:21

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
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

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? ;)
BlackJack

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.
Benutzeravatar
Michael Schneider
User
Beiträge: 569
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Brandenburg

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! :lol:

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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
jo_hb
User
Beiträge: 72
Registriert: Donnerstag 26. April 2007, 09:21

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
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Michael Schneider hat geschrieben:Und JETZT können wir über Optimierungen reden. Also, die Runde ist eröffnet! :lol:
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])))
:D
TUFKAB – the user formerly known as blackbird
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

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.
TUFKAB – the user formerly known as blackbird
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Darum wird es reduce auch bald nicht mehr geben :)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
Michael Schneider
User
Beiträge: 569
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Brandenburg

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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
Benutzeravatar
Michael Schneider
User
Beiträge: 569
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Brandenburg

Hi Jo!
jo_hb hat geschrieben:Also worum es dabei geht: tatsächlich um Blackjack! :)
Du hast es aber mit Glücksspielen. :lol:
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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
Antworten