[QUIZ#4] OnlyFoo (Python)

OnlyFoo

Erfahrenes Mitglied
So, hier meine Python Lösung.
Ich lese die Eingabe Zeile für Zeile ein und addiere zu jedem Feld immer das größere seiner Elternfelder. Wenn ich fertig bin schaue ich das größte Feld in der unteren Zeile (es hat den Wert der Gesammtzeit) an und gehe von dort immer zu dem größeren der beiden Elternelement, und von dort wieder zum größeren, etc... Dadurch highlighte ich den Pfad.
Die Ausgabe erfolgt farbig mittels Ansi Escape Codes.

Python:
#!/usr/bin/python
# -*- encoding: utf-8 -*-

import sys

# Ein Feld enthält Referenzen auf ihre bis zu zwei Elternknoten,
# sowie seinen Originalwert, ob es gehighlighted ist und das
# Ergebnis von seinem Wert plus dem größeren Wert seiner Eltern.
class Field( object ):
    def __init__( self, value, parent_left = None, parent_right = None ):
        self.highlight = False
        
        self.parent_left = parent_left
        self.parent_right = parent_right

        self.original_value = value
        self.value = value + max( \
            self.parent_left.value if self.parent_left else 0,
            self.parent_right.value if self.parent_right else 0 )
    
    # Vergleicht zwei Felder anhand ihrer Werte
    def __cmp__( self, other ):
        return cmp( self.value, other.value )
    
    # Gibt den orignalen Wert zurück
    def __str__( self ):
        return str( self.original_value )
    
    
# Eine Region hält die einzelnen Höhenstufen (in self._rows), sowie
# den Namen der Region
class Region( object ):
    def __init__( self, name ):
        self._rows = []
        self._name = name
    
    # Fügt eine neue untere Höhenstufe hinzu. Erwartet eine Liste mit
    # Integers.
    def add_row( self, row ):
        new_row = []
        for i in range( len( row ) ):
            # Erzeuge ein Feld für jedes Eingabe-Integer und gib ihm, falls
            # vorhanden, seine Eltern mit.
            field = Field( row[i], \
                self._rows[-1][i-1] if i-1 >= 0 else None, \
                self._rows[-1][i]   if i < len( row ) - 1 else None )
            new_row.append( field )

        self._rows.append( new_row )
    
    # Gibt die maximale benötigte Zeit zurück
    def get_max_duration( self ):
        return max( self._rows[-1] ).value
    
    # Vergleicht anhand der maximal benötigten Zeit
    def __cmp__( self, other ):
        return cmp( self.get_max_duration(), other.get_max_duration() )
    
    # Gibt eine String-Repräsentation dieser Region zurück.
    # Der Pfad wird grün markiert.
    def __str__( self ):
        self.highlight()
        
        # ansi Escape Codes... rulz!
        color_green = "\033[32m"
        color_normal = "\033[m"
        
        # Titel ausgeben
        result = [ "%s (%d)" % ( self._name, self.get_max_duration() ) ]
        for row in self._rows:
            # Padden
            line = [" "] * (len(self._rows[-1]) - len(row)) * 2
            
            for field in row:
                line.append( color_green if field.highlight else color_normal )
                line.append( str(field).center(4) )
                
            line.append( color_normal )
            result.append( "".join( line ) )
        
        return "\n".join( result )
    
    # Beginnt beim Ziel und wandert immer über das größere Elternelement weiter.
    def highlight( self ):
        current = max( self._rows[-1] )
        while current:
            current.highlight = True
            if current.parent_left and current.parent_right:
                current = max( current.parent_left, current.parent_right )
            else:
                current = current.parent_left or current.parent_right
        
# Das Hauptprogramm
class Quiz4( object ):
    def __init__( self ):
        self._regions = []
        self.parse( sys.stdin )
    
    # Ließt die Regionen in der Syntax:
    # Name der ersten Region
    # Anzahl der Ebenen
    # Ebene 1
    # ...
    # Ebene n
    # Name der nächsten Region
    # ...
    # Bricht bei der ersten Leerzeile ab und erwartet eine korrekte Eingabe
    def parse( self, inp ):
        name = inp.readline().strip()
        while name:
            region = Region( name )
            depth = int( inp.readline().strip() )
            for i in range( depth ):
                values = [ int(part) for part in \
                    inp.readline().strip().split( " " ) if part.strip() ]
                
                region.add_row( values )
            
            self._regions.append( region )
            name = inp.readline().strip()
        
    # Gibt den Sieger (die Region mit dem längsten Pfad) zurück
    def get_winner( self ):
        return max( self._regions )
        
# Quiz4 erzeugen und einen Sieger ermitteln, dann ausgeben!
print Quiz4().get_winner()



Code:
olli@desktop:/tmp$ cat input2.txt | python quiz4.py 
Vordertux (23)
       3  
     7   5  
   2   4   6  
 8   5   9   3
 

Anhänge

  • quiz4.py.txt
    4,2 KB · Aufrufe: 35
Zuletzt bearbeitet:

OnlyFoo

Erfahrenes Mitglied

Ich weiß. Aber ich finde das so schöner, da man die selbe Syntax für Eingaben hat, ob man nun von Datei ließt, oder z.B. die Eingabe über ein anderes Programm bekommt. Außerdem kann mans leicht gegen gzcat oder ähnliches ersetzten... Nicht zu vergessen, was ind er Wikipedia ja auch steht, wenn man in der Eile versehentlich < und > tauscht... Das wird ärgerlich dann.