[Ruby] Ich sitze auf dem Baum fest und komme nicht runter

Mat

Well-Known Member
c-b Experte
#1
Sprache ist Ruby, aber die Frage betrifft algorithmische Sportgymnastik im Allgemeinen (hab die Ruby-Kurzschreibweise nach Möglichkeit in leichter lesbaren Code umgewandelt, für Nicht-Ruby-Leute.. sonst einfach fragen, wenn etwas noch zu exotisch aussieht):

Ich bin ein bisschen am Ruby üben für eine Klausur und bin dabei auf eine Hirnblockade gestoßen. Habe als Datenstruktur einen Möchtegern-Baum (ist so vorgegeben), man könnte ihn eigentlich sogar eher als gerichteten Graphen abarbeiten. Der Baum besteht aus Knoten mit einem Wert (dient in diesem Fall nur als ID) und einem optionalen Array von Subknoten.

Bild:
Baum.png

Problem:
Ich möchte die maximale Tiefe bzw. den längsten Pfad beginnend ab dem ausgewählten Knoten finden. Ich sitze oben in der Baumspitze fest und will wissen, wie weit ich gleich runter fallen werde. Eigentlich ein Selbstläufer..aber ich hab eine Denkblockade.

Knoten.rb (Methode get_max_tiefe() macht Probleme)
Rubin:
class Knoten
  def initialize(wert, unterknoten = [])
    @wert = wert
    @unterknoten = unterknoten
  end

  def get_anz_unterknoten()
    return @unterknoten.size()
  end

  def add_unterknoten(knoten)
    @unterknoten << knoten
  end

 def get_max_tiefe()
    return 1 if get_anz_unterknoten() < 1

    max = 0
    tmp = 0
    for knoten in @unterknoten
      tmp += knoten.get_max_tiefe()
      max = [tmp,max].max()
    end

    return max + 1
  end

  def to_s
    return "n#{@wert}"
  end

end

KnotenTest.rb (Test schlägt fehl)
Rubin:
require_relative 'Knoten'
require 'test/unit'

class KnotenTest < Test::Unit::TestCase
  def setup()
    # n1(n11(n111),n12(n121,n122,n123,n123(n1241)),n13)
    @n1 =  Knoten.new(1)

    @n11 =  Knoten.new(11)
    @n12 =  Knoten.new(12)
    @n13 = Knoten.new(13)

    @n111 =  Knoten.new(111)
    @n121 =  Knoten.new(121)
    @n122 =  Knoten.new(122)
    @n123 =  Knoten.new(123)
    @n124 =  Knoten.new(124)

    @n1241 = Knoten.new(1241)

    @n1.add_unterknoten(@n11)
    @n1.add_unterknoten(@n12)
    @n1.add_unterknoten(@n13)

    @n11.add_unterknoten(@n111)

    @n12.add_unterknoten(@n121)
    @n12.add_unterknoten(@n122)
    @n12.add_unterknoten(@n123)
    @n12.add_unterknoten(@n124)

    @n124.add_unterknoten(@n1241)
  end

  def test_get_anz_unterknoten()
    assert_equal(@n1.get_anz_unterknoten(), 3, "Falsche Anzahl Subknoten bei #{@n1}")
    assert_equal(@n11.get_anz_unterknoten(), 1, "Falsche Anzahl Subknoten bei #{@n11}")
    assert_equal(@n12.get_anz_unterknoten(), 4, "Falsche Anzahl Subknoten bei #{@n12}")
    assert_equal(@n13.get_anz_unterknoten(), 0, "Falsche Anzahl Subknoten bei #{@n13}")

    nTemp = Knoten.new(0)
    assert_equal(nTemp.get_anz_unterknoten(), 0, "Falsche Anzahl Subknoten bei #{nTemp}")
  end

  def test_add_unterknoten()
    numUnterknotenVorher = @n1.get_anz_unterknoten()
    @n1.add_unterknoten(Knoten.new(0))

    assert_equal(@n1.get_anz_unterknoten(), numUnterknotenVorher + 1, "Falsche Anzahl Subknoten nach Add")
  end

  # Hier schlägt's fehl: 
  # => Falsche maximale Tiefe bei n12 festgestellt. 
  # <3> expected but was <6> in `test_get_max_tiefe'
  def test_get_max_tiefe()
    assert_equal(1, @n1241.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n1241} festgestellt")
    assert_equal(2, @n11.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n11} festgestellt")
    assert_equal(3, @n12.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n12} festgestellt")
    assert_equal(4, @n1.get_max_tiefe(), "Falsche maximale Tiefe bei #{@n1} festgestellt")
  end
end

Knoten als Objekt (sieht richtig aus):

Rubin:
#<Knoten:0x00000002b68530 @wert=1,
    @unterknoten=[
        #<Knoten:0x00000002b684b8 @wert=11,
            @unterknoten=[#<Knoten:0x00000002b68300 @wert=111,
                @unterknoten=[]>
            ]>,
        #<Knoten:0x00000002b68418 @wert=12,
            @unterknoten=[#<Knoten:0x00000002b682b0 @wert=121,
                @unterknoten=[]>,
            #<Knoten:0x00000002b68238 @wert=122,
                @unterknoten=[]>,
            #<Knoten:0x00000002b68198 @wert=123,
                @unterknoten=[]>,
            #<Knoten:0x00000002b68058 @wert=124,
                @unterknoten=[
                    #<Knoten:0x00000002b68008 @wert=1241,
                        @unterknoten=[]>
                ]>
            ]>,
        #<Knoten:0x00000002b683a0 @wert=13,
            @unterknoten=[]>
    ]>
 

Mat

Well-Known Member
c-b Experte
#2
Ja toll.. grad abgeschickt.. Beitrag überflogen.. Fehler gefunden....

Zeile 20 in Knoten.rb.. richtig wäre:
Rubin:
for knoten in @unterknoten
      tmp = knoten.get_max_tiefe()
      max = [tmp,max].max()
end
Anstelle von:
Rubin:
for knoten in @unterknoten
      tmp += knoten.get_max_tiefe()
      max = [tmp,max].max()
end
Das nochmal in längerer Schreibweise zu lesen hat geholfen :mauer:

Hat sich erledigt.. kann weg oder als Mahnmal so stehen bleiben :D
 
Oben