geben Sie einige kleine und große Zahlen, gewünschte Nummer - ohne Schleifen

Question

Ich lösen die Codierung Probleme auf codingbat in Python. Das make_bricks Problem ist wie folgt definiert:

Wir haben eine Reihe von Ziegeln machen wollen, das Ziel Zoll lang ist. Wir haben eine Nummer von kleinen Ziegeln (1 Zoll) und große Ziegelsteine ​​(jeweils 5 Zoll). Return True, wenn es möglich ist, das Ziel von aus den gegebenen Ziegeln zu wählen. Diese ist etwas härter als es aussieht und kann ohne Schleifen gemacht werden.

make_bricks(3, 1, 8) → True 
make_bricks(3, 1, 9) → False 
make_bricks(3, 2, 10) → True 

Die erste Lösung kam ich mit war:

from itertools import permutations 

def make_bricks(small, big, goal): 
    l = small*[1]+big*[5] 
    return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \ 
    for i in range(2,len(l)+1)])]) 

Was ist richtig, aber wurde durch die Beurteilungs Software abgelehnt, da die Einfuhren nicht erlaubt. Also meine nächste Lösung war:

def make_bricks(small, big, goal): 
    bricks = small*[1]+big*[5] 
    for step in range(len(bricks)+1,1,-1): 
     for start in range(len(bricks)): 
      if len(bricks[start:start+step])==step: 
       if sum(bricks[start:start+step])==goal: 
        return True 
    return False 

Welche auch richtig ist, aber mit einem Time-out bei der Eingabe wie make_bricks(1000000, 1000, 1000100) erstickt.

Also, wie würden Sie dieses Problem in Python lösen, ohne Importe zu verwenden, ohne Schleifen und im Zeitlimit zu verwenden?

Answer 1

Dies ist ein mathematisches Problem. Angenommen, Sie haben S kleine Steine ​​und B große Steine ​​und Sie wollen eine Länge L Block.

Sie können K = min(B, L div 5) große Steine ​​und L - 5K kleine Steine ​​verwenden, also müssen Sie nur überprüfen, ob Sie genügend kleine Steine ​​haben.

div ist Integer Division (Boden).

EDIT geändert L-K zu L-5K. Tippfehler.

Answer 2

Beachten Sie, dass Sie nur die endgültige Größe erreichen müssen. Daher ist es egal, in welcher Reihenfolge Sie die Steine ​​platzieren.

Die nächste wichtige Idee ist dann, wenn möglich 5-Zoll-Steine ​​zu verwenden. Sie decken 5 Zoll, wenn Sie eine davon verwenden, sowie wenn Sie 5 der 1-Zoll-Steine ​​verwenden. Daher ist es sinnvoll, nur einen Baustein zu verwenden.

Jetzt sind Sie schon wirklich fertig: Überprüfen Sie die maximale Länge, die Sie mit Ihren gegebenen 5-Zoll-Ziegeln erstellen können, bis Sie entweder 5-Zoll-Steine ​​oder Sie haben weniger als 5-Zoll für Ihre Ziellänge fehlt . In jedem Fall fehlt eine Entfernung, die Sie mit den restlichen 1-Zoll-Steinen füllen müssen.

Ich werde hier keinen Code geben, weil es wirklich ein sehr einfaches Problem ist und von dem, was Sie oben geschrieben haben, sollten Sie leicht in der Lage sein, es zu lösen, sobald Sie verstehen, wie.

Answer 3

Nicht so schwierig, wenn Sie Einzelteile haben und nur eine größere Größe, da Sie immer so viele wie Sie können mit den größeren füllen können.

Schwieriger, wenn Sie Viertel und Groschen haben und versuchen, eine Menge genau mit ihnen zu machen, zB wenn Sie 55c machen müssen, scheitern Sie, wenn Sie mit 2 Vierteln beginnen, obwohl es kleiner als das Ziel ist.

Es gibt natürlich noch andere Kombinationen, die das Problem noch komplexer machen werden als "gehe nicht näher als die Menge - die kleinste Einheit, die du hast".

Wenn Sie die kongruente Gleichung (Ax + By)% AB = C lösen, können Sie immer mehr Gleichungen mit A (x + B) + B (yA) erhalten, die auch gleich C sind begrenzte Menge, die du von deinen Steinen/Münzen oder was auch immer hast.

Ein Beispiel für eine kongruente Gleichung ist etwa (7x + 9y)% 63 = 47 und Sie können eine Funktion schreiben, um diese zu lösen. Wir gehen zu den niedrigsten Termen über, nehmen also an, dass A und B Co-Prime sind oder reduzieren sie durch die HCF.

Es gibt eine eindeutige Lösung mit x = 0. In diesem Fall werden wir tatsächlich mit x = 8, y = 6 enden, jede mit ihrem maximalen Wert 56 + 54 = 110 was kongruent zu 47 mod 63 ist Wenn das Ziel tatsächlich 47 ist, ist es mit keiner Anzahl von 7s und 9s lösbar.

Wenn das Ziel 110 ist, kann es gelöst werden, wenn wir 8 Steine ​​von 7 und 6 von 9 haben. Andernfalls gibt es keine Lösung.

Wenn das Ziel höher ist, gibt es mehrere Lösungen mit unbegrenzten Steinen, aber die Anzahl von 9 Steinen, die wir benötigen, wird immer 8 Mod 9 sein, also 8, 17, 26 usw. Wir nehmen die höchste Anzahl das passt zu dieser Kategorie und versuche den Rest mit 7 Steinen zu füllen. Wenn wir sie haben, können wir unser Ziel machen. Wenn wir 33 Steine ​​von 9 haben, müssen wir 26 von ihnen verwenden.

Das ist Ihr Algorithmus, sobald Sie die Kongruenz gelöst haben.

Answer 4

Sie können ein Loch der Größe 5 mit 1s oder 5s füllen, aber Sie können nur ein Loch mit weniger als fünf Löchern mit 1s füllen. Zum Beispiel: um 19 zu machen, musst du mindestens 4 1s haben - es spielt keine Rolle, ob du 100 5s hast, wenn du nur 3 1s hast, hast du kein Glück.

Also der Trick ist zu sehen, ob Sie genug 1s haben, um den Rest-von-5 zu füllen, dann genug 5s und 1s übrig, um den Rest zu machen.

def make_bricks(small, big, goal): 
    # minimum number of 1s needed 
    rem = goal % 5 # ex: 19 % 5 == 4 

    if rem > small: 
    # too few 1s 
    return false 
    else: 
    # we have enough 1s; deduct what we just used 
    small -= rem 
    goal -= rem 

    # now see if what's left will fill the rest of the hole 
    return small + 5*big >= goal 

Hoffe, dass für Sie Sinn macht!

Answer 5

def make_bricks(small, big, goal): 
    if goal > small + big * 5: 
    return False 
    else: 
    return goal % 5 <= small 

Answer 6

def make_bricks(s,b,g): 
    return not(g>b*5+s or g%5>s) 

s = small | b = groß | g = Ziel

Answer 7

n = int (Ziel/5)

wenn das Tor> small + big * 5: Falsch elif (Ziel < = small + big * 5) zurück: wenn Ziel> n * 5 + klein:
return false
sonst: return true

Answer 8

Hier ist die Lösung kam ich mit - nicht wie bei dieser kondensiert bekommen können, aber durch leicht genug logic'd:

def make_bricks(small, big, goal): 
    if int(goal/5) < big: 
    big -= big - int(goal/5) 
    return big*5 + small >= goal