Silhuettproblemet - lösning

Strategi

• Gå igenom kursens algoritmer. Finns det något liknande?

  Max-beräkning - vilken av byggnaderna är högst på denna x-koordinat? Måste göras upprepade gånger.

• Gå igenom kursens datastrukturer. Finns någon lämplig?

  En max-heap kan användas för att hitta högsta byggnaden.

• Hur hålla reda på vilka byggnader som är aktuella för en viss position?

  En min-heap kan användas för att hålla reda på vilka hus som är aktuella.

Datastrukturer: Det här knepiga problemet kan vi lösa med hjälp av två heapar.

• Den ena är en min-heap, som ser till att vi får ut husväggarnas koordinater i ordning från minsta (vänstraste) till största (högraste) x-värde. Där är prioriteten husets x-koordinat.
• Den andra är en max-heap som hjälper oss att hitta det just nu högsta huset. Där är prioriteten husets höjd.

Algoritm:

1. Lägg in alla hus, med vänstervägg som nyckel, i en min-heap som vi kallar xheap.
2. Skapa också en tom max-heap, som vi kallar för yheap, där vi (så småningom) ska sortera husen efter höjd.
3. Låt x och y vara aktuell x-koordinat resp y-koordinat. Båda är noll från början.
4. Så länge det finns hus kvar i xheap,
   1. Ta ut första huset ur xheap (vi får det hus som har den vänstraste vänsterväggen).
   2. Om vänsterväggen ligger efter aktuell x-koordinat...
      • ...så blir den ny x-koordinat.
      • Om dessutom huset höjd är högre än aktuell y-koordinat skriver vi ut x och y.
      • Stoppa in huset i xheap igen, men nu med högerväggen som nyckel.
      • Stoppa in samma hus i yheap med höjden som nyckel.
   3. men om vänsterväggen inte ligger efter aktuell x-koordinat har vi fått ut ett hus med högervägg som nyckel, och då...
      • ...letar vi igenom yheap efter det högsta huset vars högervägg inte ligger efter aktuell x-koordinat.
      • Om yheap tar slut medan vi letar är höjden noll.
      • Sen skriver vi ut x och y.

Programkod (ej krav på tentan - finns med här för att du lättare ska förstå algoritmen)

from maxheap import MaxHeap
from minheap import MinHeap

class House:
    left = None
    height = None
    right = None

    def __init__(self, left, height, right):
        self.left = left
        self.height = height
        self.right = right

def readHousesTo(xheap):
    ins = raw_input("Vilka hus finns? ").split()
    for h in ins:
        h = h.strip("()")
        hs = h.split(",")
        house = House(int(hs[0]), int(hs[1]), int(hs[2]))
        print house
        xheap.put(house, house.left)

xheap = MinHeap(20)
yheap = MaxHeap(20)

readHousesTo(xheap) # Läs in husen

x = 0
y = 0
while not xheap.isempty():
    house = xheap.get()
    if house.left > x:  # Hus med vänstervägg utplockat
        x = house.left
        if house.height > y:
            y = house.height
            print "x=", x, "y=", y
        xheap.put(House(house.left, house.height, house.right), house.right)
        yheap.put(House(house.left, house.height, house.right), house.height)

    else: # Hus med högervägg utplockat
        if house.height == y: # Det var det just nu högsta huset
            # Sök efter det hus som blir högst nu
            x = house.right
            while not yheap.isempty() and yheap.top().right <= x:
                yheap.get()     # Ta bort hus som ligger...
                                # ...till vänster om x
            if yheap.isempty():
                y = 0
            else:
                y = yheap.top().height
            print "x=", x, "y=", y