[QUIZ#4] Pistenjodler e.V.

Matthias Reitinger

Matthias Reitinger

ɐɯıǝɹ
Quiz #4
Pistenjodler e.V.

Regeln
Die Regeln und der Ablauf der Quizrunde können in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält. Lösungsansätze können und dürfen auch schon vorab untereinander ausgetauscht und diskutiert werden, allerdings nicht öffentlich im Forum. Verwendet stattdessen bitte private Nachrichten oder schaut im Chat vorbei.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Sonntag, der 12. Oktober 2008 um ca. 21 Uhr.

Das Problem
Der Skisportverein "Pistenjodler e.V." plant einen Ausflug in die Alpen. Die Mitglieder haben sich schon auf einige Skigebiete geeinigt, die in die engere Auswahl kommen. Um das endgültige Ziel zu bestimmen, soll nun das Skigebiet ermittelt werden, das die längste Abfahrtszeit (von der Bergstation in's Tal) bietet.

Für jedes Skigebiet steht steht ein Plan bereit, der sich aus einzelnen Feldern zusammensetzt, die in Dreiecksform angeordnet sind. Jedes Feld ist mit einer Ganzzahl beschriftet. Als Beispiel:
Code: 
   3
  7 5
 2 4 6
8 5 9 3
Die Spitze des Dreiecks steht für den Gipfel, die letzte Zeile für das Tal. Die Zahl in jedem Feld gibt an, wieviel Zeit für die Abfahrt durch dieses Feld benötigt wird. Von jedem Feld aus kann man die zwei angrenzenden Felder in der Zeile darunter erreichen. Die längste Abfahrt wäre im Beispiel also:
Code: 
   3
  7 5
 2 4 6
8 5 9 3
Die längste Abfahrtszeit beträgt somit 3+7+4+9=23.

Ziel ist nun, für jedes so spezifizierte Skigebiet die längste Abfahrtszeit zu bestimmen und das Skigebiet mit der längsten Zeit zu benennen.

Die Eingabe besteht aus beliebig vielen Skigebieten. Jedes Skigebiet setzt sich zusammen aus aus:
  • Name des Skigebietes
  • Höhenunterschied, also die Anzahl der Zeilen im Plan
  • Abfahrtsplan wie oben beschrieben
Das Ende der Eingabe wird mit einer Leerzeile markiert.

Erweiterung
Zusätzlich soll die längste Abfahrt mit ausgegeben werden. In welcher Form (ASCII, Grafik, Animation) ist euch überlassen.

Beispiele
Eingabe:
Code: 
Vordertux
4
3
7 5
2 4 6
8 5 9 3
Zugstumpf
5
1
2 4
7 4 5
2 3 1 2
3 5 4 9 2
Ausgabe (einfach):
Code: 
Längste Abfahrtszeit: Vordertux (23)
Ausgabe(vorschlag) (erweitert):
Code: 
Längste Abfahrtszeit: Vordertux (23)
   3
  7 5
 2 4 6
8 5 9 3
Hinweis: die längste Abfahrtszeit für "Zugstumpf" beträgt 21.


Eingabe:
Code: 
Hindelang-Oberjoch
8
11
11 14
14 14 3
7 7 3 12
8 3 9 8 10
7 12 8 6 2 11
10 4 13 4 8 6 3
13 8 7 5 5 5 12 5
Jungholz
7
12
5 3
14 3 8
6 3 13 11
13 11 4 9 13
13 9 10 3 6 14
11 8 7 11 12 11 13
Wertach
7
6
3 3
3 14 4
10 9 13 11
11 4 14 12 7
9 5 2 3 10 10
11 5 14 4 11 13 12
Oy-Mittelberg
7
12
3 12
7 9 4
3 9 6 5
10 6 2 2 12
2 4 8 7 8 6
2 13 8 13 5 3 7
Bolsterlang
9
14
14 9
12 5 6
13 6 6 11
2 12 14 4 4
6 4 10 4 7 12
4 3 7 7 5 9 5
14 14 4 5 10 6 2 5
7 7 5 2 7 4 8 9 6
Ofterschwang
8
13
3 7
8 7 9
2 5 6 5
4 5 5 10 10
8 13 9 3 14 13
11 8 5 2 3 5 5
3 8 12 5 6 9 10 7
Obermaiselstein
7
3
14 9
9 11 3
10 14 2 12
5 5 8 11 13
5 7 10 5 6 2
6 12 5 2 12 4 8
Balderschwang
8
4
2 7
5 2 4
6 8 12 14
11 8 12 7 11
5 10 7 11 2 4
7 11 10 13 10 8 2
3 10 4 6 4 2 5 8
Immenstadt
8
4
9 10
11 2 11
7 7 8 13
5 14 11 11 13
5 8 10 10 5 14
11 9 7 8 3 4 7
9 12 3 2 13 13 11 9
Ausgabe (einfach):
Code: 
Längste Abfahrtszeit: Bolsterlang (99)
Hinweis: die längsten Abfahrtszeiten für die restlichen Pisten betragen: 83 (Hindelang-Oberjoch), 74 (Jungholz), 71 (Wertach), 69 (Oy-Mittelberg), 74 (Ofterschwang), 67 (Obermaiselstein), 69 (Balderschwang), 83 (Immenstadt)


Eingabe: Siehe Textdatei im Anhang!
Ausgabe (einfach):
Code: 
Längste Abfahrtszeit: Oy-Mittelberg (1060)
 

Anhänge

Zuletzt bearbeitet:
Hier ein kleines Script zum generieren von zufälligen Plänen, die man als zufällige Eingabe nutzen kann
Python: 
#!/usr/bin/python
import random

for name in ( "Hindelang-Oberjoch", "Jungholz", "Wertach", "Oy-Mittelberg",
        "Bolsterlang", "Ofterschwang", "Obermaiselstein", "Balderschwang",
        "Immenstadt" ):
    
    depth = random.randint( 3, 10 )
    print name
    print depth
    for i in range( 0, depth ):
        print " ".join([str(random.randint(2,15)) for j in range( 0, i+1 )])
 
Zuletzt bearbeitet:
Diesmal bin ich auch mit dabei.

Meine PHP-Loesung ist schon mehr oder weniger im Kasten.
Und wenn ich Zeit und Lust habe probier ich auch noch etwas ausgefalleneres.

Bin ja mal gespannt was andere so abliefern.

Wir sollten auf jeden Fall noch mehr Beispiele haben.
Denn wenn jeder nur zufaellig erstellte nutzt ist der Vergleich schwer.

Ich hab bei einer durch das Python-Script erstellten Piste noch ein Problem entdeckt. Also nicht mit der Piste, sondern mit der Auswertung ebendieser.
Werd mal noch was schrauben, ist ja noch Zeit.
 
Hallo,

wie versprochen habe ich noch zwei weitere Beispiele hinzugefügt. Das letzte Beispiel ist eine Art Härtetest, ob euer Algorithmus einigermaßen effizient ist. Danke an OnlyFoo für die Bereitstellung des Python-Skripts! Ich hab es aber vorher in Ruby umgeschrieben ;-) Wen es interessiert:
Ruby: 
#!/usr/bin/env ruby
%w{
  Hindelang-Oberjoch
  Jungholz
  Wertach
  Oy-Mittelberg
  Bolsterlang
  Ofterschwang
  Obermaiselstein
  Balderschwang
  Immenstadt
}.each do |name|
  depth = rand(3) + 7
  puts name, depth
  depth.times do |n|
    puts Array.new(n+1){rand(13)+2}.join(" ")
  end
end

Grüße,
Matthias
 
Zuletzt bearbeitet:
Auf Performance-Probleme bin ich bislang nicht gestossen. Ich brauche aber zur Zeit eine "kosmologische Konstante" um der Laenge des naechsten Abschnittes etwas mehr Gewicht einzuraeumen.
Als ich aber grad zum Einkaufen bin hatte ich eine Idee die mich von dieser "Eselei" erloesen koennte.
 
Performance Probleme hab ich auch nicht. Auf 800MHZ laufen beide Versionen in < 0.5sek für die obrige pisten.txt... Und eine Kosmische Konstante habe ich auch nicht =)
Mal gucken ob ich heute mir noch ne dritte Lösung ausdenke.
 
Und Du bist die Pisten auch mal von "zu Fuss abgelaufen" und hast gecheckt ob alles stimmt?

Meine Werte sehen soweit ganz gut aus, aber bei ein paar wenigen Ausnahmen kommen bei mir falsche Angaben zustande.
 
Meine Werte stimmen mit den zu erwartenden Werten überein, selbst die hervorgehobenen Pfäde, und ich bin mir relativ sicher, dass mein Verfahren korrekt ist =)
 
Bei den beiden ersten Strecken hatte ich auch die richtigen Werte, auch gleich mit der ersten Version (auch wenn bei der Siegerstrecke dort ein etwas anderer, aber gleich langer, Weg eingeschlagen wurde), nur als ich dann mal ein paar Strecken mit Deinem Script erstellt habe und dann alle Strecken inklusive Highlighting und Gewichtung ausgegeben habe hab ich festgestellt dass es, bei laengeren Strecken, zu Fehlern kommen kann.

Ich gebe bei mir, zur Zeit noch, alle Strecken aus um eben meine Gewichtung zu pruefen.

Ich hab jetzt aber noch was angepasst und jetzt scheint alles zu passen. Und es war doch so einfach. Ist jetzt im Grunde nur eine Abwandlung der ersten Version...
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück