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.
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
Zuletzt bearbeitet:
