Hot Pad

Das „Hot Pad“-Problem von HP Codewars für 9 Punkte besteht eigentlich aus 2 Problemen. Im Rahmen des Problems erhalte ich von einem Keypad die Temperaturen je Taste und muss eine Liste der möglichen Kombinationen ausgegeben, die ein Anwender getippt haben könnte.

Problem

Die beiden Probleme sind folglich:

1. Lies die Temperaturwerte ein und stelle fest, welche Taste einmal und welche ggf. zweimal gedrückt wurde. Es gibt eine durchschnittliche Temperatur und die Taste # muss zwingend zum Absenden gedrückt sein.
2. Für die ermittelten Tasten muss ich anschließend alle möglichen Kombinationen ausgeben. Das ist ein Problem der Kombinatorik, wenn ich mich nicht irre.

Erste Annäherung

Beachten muss ich, dass die eingegebenen Codes eine Länge von 4 Ziffern haben und mit einem # abgeschlossen werden. Das Keypad sieht so aus:

1	2	3
4	5	6
7	8	9
*	0	#

Die Temperaturwerte für das Pad sehen u. a. so aus:

Datensatz 1

72.1	75.0	75.1
72.0	72.1	72.2
72.0	72.2	77.9
72.1	72.2	75.2

Datensatz 2

77.2	77.1	76.9
77.0	83.5	77.0
77.1	77.3	77.1
77.0	79.4	79.1

Die Temperaturen können schwanken, was beachtet werden muss! Denke daran, dass eine Taste einmal, zweimal, dreimal oder auch viermal gedrückt werden könnte; die Raute wird einmal gedrückt worden sein. Das Sternchen sollte eigentlich nicht gedrückt worden sein.

Peter’s Peppers

Bei HP Codewars war 2012 als Aufgabe 5 eine Lösung für folgendes Problem zu entwickeln:

Ein Geschäft verkauft Paprika in Paketen zu 6, 11 oder 13 Paprikas. Der Preis pro Verpackung ist gleich, nur die Größen sind verschieden. Ein Skript soll nun eine Zahl n (n < 1000) erhalten und die kleinste Kombination von Paketen für den Versand finden. 13er-Pakete sollen bevorzugt werden.

Als Beispiele werden Bestellungen von 42, 55, 27 und 88 Paprikas gegeben. Das Skript soll seine Ausgabe in einer bestimmten Form erledigen:

42 peppers can be packed most economically in:
1 package of 13
1 package of 11
3 packages of 6
5 total packages.

bzw.

27 peppers cannot be packed.

Das Problem sieht stark nach einem Graphentheorie-Problem aus, was ich aber noch nicht beherrsche. Folgendes Skript arbeitet korrekt, ist aber bei einem größeren n nicht mehr sehr performant:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben

    '''
    ergebnisliste = []
    
    for a in range(0,n // 13 + 1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    ergebnisliste.append(ergebnis)

    ergebnisliste.sort()     
    if len(ergebnisliste) == 0:
        return 0,0,0
    else:
        return ergebnisliste.pop()


bestellungen = [6,31,42,55,27,88,79,802,999,964]

for bestellung in bestellungen:
    a,b,c = packen(bestellung)

    packages_gesamtzahl = a + b + c

    if a == 0 and b == 0 and c == 0:
        print("{} peppers cannot be packed.\n".format(bestellung))
    else:
        print("{} peppers can be packed most economically in:".format(bestellung))

        for package, value in zip([a,b,c], [13,11,6]):
            if package > 1:
                print("{} packages of {}".format(package,value))
            elif package == 1:
                print("{} package of {}".format(package,value))
                
        print("{} total packages.\n".format(packages_gesamtzahl))

Ich denke, dass das Problem besser zu lösen sein müsste. In einem ersten Schritt ist mir jedenfalls für die Funktion eine Vereinfachung eingefallen:

def packen(n):
    ''' Algorithmus, der die beste Kombination
    von 13er-, 11er- und 6er-Paketen Paprika ermitteln
    und zurueckgeben soll. Kann keine Loesung gefunden
    werden, dann wird 0,0,0 zurueckgegeben
 
    '''    
    for a in range(n // 13,-1,-1):
        for b in range(0,n // 11 + 1):
            for c in range(0,n // 6 + 1):
                if a * 13 + b * 11 + c * 6 == n:
                    # print(a,b,c)
                    ergebnis = a,b,c
                    return ergebnis
    return 0,0,0

Ich kann die Funktion eindampfen, weil ich nicht mehr alle möglichen Kombinationen erfassen will, sondern jetzt vom größtmöglichen Faktor von 13 starte und gegen 0 runterzähle. Der erste "Treffer" kann direkt zurückgegeben werden, weil hier die Bedingung - größtmögliche Anzahl der 13er-Pakete - erfüllt ist. Für die Anzahl der 11er- und 6er-Pakete gibt es in der Aufgabenstellung keine Bedingung.