Triangles (beendet)

Dieses Projekt entstand aus einem Programmierwettbewerb von Al Zimmermann. Dabei geht es um das Lösen folgendes mathematischen Problems:

Ausgehend von einer Folge natürlicher Zahler kann ein "Dreieck" (ein dreieckiges Array natürlicher Zahlen) so konstruiert werden, dass die gegebene Folge die Basis des Dreiecks darstellt und jeder verbleibende Wert des Dreiecks die absolute Differenz der beiden Werte darunter. Zum Beispiel erhält man mit der Folge (89, 78, 12, 13) dieses Dreieck:

      10
    55  65
  11  66  1
89  78  12 13

Eine Folge wird als akzeptabel bezeichnet, wenn in dem dadurch bestimmten Dreieck keine Folge doppelt auftaucht. Die obige Folge ist akzeptabel. Hingegen ist die Folge (19, 80, 51, 77) nicht akzeptabel, da das davon konstruierte Dreieck zweimal die 29 enthält:

      29
    32   3
  61  29  26
19  80  51  77

Für eine akzeptable Folge ist die Spannweite definiert als die Differenz zwischen dem größten und dem kleinsten Wert, der in dem von der Folge konstruierten Dreieck enthalten ist. Die Spannweite von (89, 78, 12, 13) ist 88 (wegen 89 und 1 im Dreieck). Von zwei aktzeptablen Folgen gilt diejenige als besser, die eine kleinere Spannweite hat.

Der ursprüngliche Programmierwettbewerb bestand darin, für Folgen von 2 bis 25 enthaltenen Zahlen jeweils die beste mit einem eigenen Programm gefundene Lösung einzusenden. Das jetzige Projekt verwendet einen DC-Client, um den möglichen Suchraum komplett auszuschöpfen, da bei dem Programmierwettbewerb niemand den Suchraum auch nur annähernd vollständig durchsuchen konnte.

Das Projekt wird deshalb im März 2003 enden, weil es ungefähr dann den nächsten Programmierwettbewerb von Al Zimmermann geben soll und der harte Kern der Teilnehmer sich dann dem neuen Problem widmen möchte.

Projektübersicht

Triangles
Name	Triangles
Kategorie	Mathematik
Ziel	Finden minimaler Spannen in bestimmten Folgen
Kommerziell	nein
Homepage	members.aol.com/bitzenbeitz/Contests/Triangles/Description.html

Es ist uns leider nicht bekannt, wo auf der Welt dieses Projekt zu Hause ist.

Projektstatus

Projektstatus
Status	beendet
Beginn	01.11.2002
Ende	03.03.2003

Projektlinks

• Hintergrundinfos
• Anmelden
• Statistiken
• Mailingliste/Forum

Clientprogramm

Betriebssysteme

	Windows
	Linux
	DOS
	BSD
	Solaris
	Java (betriebssystemunabhängig)

Client-Eigenschaften

Funktioniert auch über Proxy
Normal ausführbares Programm
Als Bildschirmschoner benutzbar
Kommandozeilenversion verfügbar
Personal Proxy für Work units erhältlich
Work units auch per Mail austauschbar
Quellcode verfügbar
Auch offline nutzbar
Checkpoints

Veröffentlichte Versionen

• 30.11.1999: 1.12

Screenshots

• 

  Verbindungs-Einstellungen

• 

  Hauptbildschirm

• 

  Einstellungen

• 

  Priorität

• 

  Status des WU-Puffers

Ergebnisse

Die Spannweite der Folgenlängen 16 bis 21 konnten durch das Projekt verkleinert werden.

Folgenlänge	Spannweite im Programmierwettbewerb	Spannweite im DC Projekt	Differenz
16	286	284	2
17	346	337	9
18	415	411	4
19	495	481	14
20	585	573	12
21	688	663	251)

1) Die Folge der Länge 21 wurde nicht durch das DC Projekt errechnet, wurde aber von einer Person durch Erweiterung der Folge mit Länge 20 des DC Projekts gefunden.

Vier optimale Dreiecke

Hier 4 Beispiele optimaler Dreiecke. Von Hand einzusehen, dass sie optimal sind, da jeweils die Zahlen von 1 bis 3,6,10 usw vorkommen. Weniger geht nicht! Eine Folge der Länge 5, die ein Dreieck mit den Zahlen 1 bis 21 bildet gibt es nicht.

 2      3        3            5
1 3    4 1      4 7          4  9
      2 6 5    5 9  2       7 11  2
              6 1 10 8    8  1  12 10
                         6 14 15  3  13

Meldungen

• 03.02.2003: Die bisher besten bekannten (bis Folge 11 optimalen) Lösungen

• 15.10.2002: Die besten eingeschickten Lösungen des eigentlichen Programmierwettbewerbs