Angepinnt [Sammelthread] Knobel-Aufgaben, knifflige Algorithmen, elegante Lösungen

    • VB.NET

    Es gibt 178 Antworten in diesem Thema. Der letzte Beitrag () ist von Thunderbolt.

      Ich habe den Beitrag zur Verständnis des ersten Punktes bearbeitet.

      Angrenzende Flächen: Flächen, die eine unterschiedliche Nummer haben. Da field[x] = 0 gilt, sind die Flächen mit 1, 2, 3 in der potentiellen Auswahl.
      Es sollen diejenigen Punkte pro Zahl zurückgegeben werden, die am Nächsten sind.
      Beispielsweise müsste für 2 der Punkt rechts unterhalb von x zurückgegeben werden.

      Jetzt muss ich aber noch mal fragen.
      1. Was passiert, wenn ich zwei voneinander getrennte Flächen mit der selben Zahl habe?
      2. Sind nur die Zahlen der Flächen gesucht, die direkt an die Fläche, in der sich der Startpunkt befindet, angrenzen (im Beispiel bedeutet das: ist auch 1 gesucht)?
      3. Wie werden die Abstände gemessen? Luftlinie oder in Schritten, und wenn Schritte, was sind Schritte, nur horizontal und vertikal oder auch diagonal?

      1. Wird als eine Fläche behandelt.
      2. Ja, nur die angrenzenden Flächen in der Fläche des Startpunktes
      3. Die Länge ist nur zur Bestimmung der nächsten Fläche. Quadratwurzel((Startpunkt.X - Ziel.X)² + (Startpunkt.Y - Ziel.Y)²).

      AliveDevil schrieb:


      Es soll nun eine Funktion geschrieben werden, die ausgehend von dem Startpunkt, alle angrenzenden Flächen (Zahlen) bestimmt, und zu jeder Zahl den nächsten Punkt zurückgibt.
      Das scheint mir bisserl überkompliziert.
      Zunächst mal muss doch v.a. ein "RandFinder" geschrieben werden, der alle Randpunkte der Fläche ermittelt.
      Von diesen Randpunkten aus dann die dem Startpunkt nächsten Punkte der angrenzenden Flächen zu finden sollte einfach sein.

      btw: Hat die Aufgabe ieinen praktischen Bezug?

      Jap, es hat einen praktischen Nutzen - in einem Mapgenerator, der durch Farbflächen Funktionen aufruft, die wiederum auf anderen Funktionen basieren.
      Der RandFinder ist die einfachste Variante, die mir auch eingefallen ist, nur habe ich es nicht geschafft, eine Variante davon zu entwickeln, die irgendwie funktioniert.
      Ein Anfang könnte Floodfill sein - das Problem: der Algorithmus ist unendlich, wenn am Quellarray nichts geändert wird, was nicht passieren kann, da das Arrays mehrere hunderttausend Elemente beinhalten kann.
      Ich habe mir auch die Arbeit gemacht, dass ganze umzuwandeln, nur wie gesagt: das Teil ist derzeit unendlich.
      Spoiler anzeigen

      C-Quellcode

      1. public static void Main()
      2. {
      3. Queue<Point> q = new Queue<Point>();
      4. q.Enqueue(Point.Empty);
      5. while (q.Count > 0)
      6. {
      7. Point p = q.Dequeue();
      8. if (isValid(p))
      9. {
      10. Console.WriteLine("{0}", p);
      11. Point w = p, e = p, n = p, s = p;
      12. n.Y += 1;
      13. s.Y -= 1;
      15. while (isValid(w)) { w.X += 1; }
      16. while (isValid(e)) { e.X -= 1; }
      18. for (int x = e.X; x <= w.X; x++)
      19. {
      20. if (p.X != x)
      21. {
      22. n.X = s.X = x;
      23. //Console.WriteLine("\t{0}", p);
      24. if (isValid(n)) { q.Enqueue(n); }
      25. if (isValid(s)) { q.Enqueue(s); }
      26. }
      28. //System.Threading.Thread.Sleep(125);
      29. }
      30. }
      31. }
      32. }
      34. static bool isValid(Point location) { return Math.Sqrt(location.X * location.X + location.Y * location.Y) < 5; }

      Ich wollts erst versuchen, nur exakt am Rand entlang zu gehen, aber dann ist mir aufgefallen, dass "Inseln" auf die Art verschluckt werden. Floodfill scheint mir hier auch die einzig gescheite Lösung, auch wenns warscheinlich vergleichsweise Langsam und viel Speicher belegt. Meine Implementation sollte nicht unendlich sein, zumindest falls ich nichts falsch gemacht hab.
      Ist noch nicht ganz fertig, kommt später noch. ;)

      Ob es lange dauert oder nicht, spielt keine Rolle. Die Anwendung darf für die Erzeugung gerne die ein oder andere Minute länger brauchen. Wie gesagt: es ist "nur" ein MapGenerator der intern verwendet wird. Effizienz ist dabei ebenfalls vollkommen unbedeutend.
      Sobald ein fertiger Algorithmus steht, sollte es einfacher sein, den zu verbessern.

      Hier:
      Spoiler anzeigen

      C#-Quellcode

      1. ​ public static class AreaMagic
      2. {
      3. /// <summary>
      4. /// Gets the surrounding points of a point.
      5. /// </summary>
      6. public static Point[] GetSurroundingPoints(Point point)
      7. {
      8. var result = new Point[8];
      9. result[0] = new Point(point.X + 1, point.Y);
      10. result[1] = new Point(point.X + 1, point.Y + 1);
      11. result[2] = new Point(point.X, point.Y + 1);
      12. result[3] = new Point(point.X - 1, point.Y + 1);
      13. result[4] = new Point(point.X - 1, point.Y);
      14. result[5] = new Point(point.X - 1, point.Y - 1);
      15. result[6] = new Point(point.X, point.Y - 1);
      16. result[7] = new Point(point.X + 1, point.Y - 1);
      17. return result;
      18. }
      20. /// <summary>
      21. /// Finds the border of the shape the specified point belongs to.
      22. /// </summary>
      23. public static Point[] FindBorder(int[,] area, Point point, out Point[] interior)
      24. {
      25. if (area == null)
      26. throw new ArgumentNullException("area");
      27. if (point.X < area.GetLowerBound(0) || point.X > area.GetUpperBound(0)
      28. || point.Y < area.GetLowerBound(1) || point.Y > area.GetUpperBound(1))
      29. throw new ArgumentOutOfRangeException("startPoint");
      31. int shapeKey = area[point.X, point.Y];
      32. var inactivePoints = new List<Point>();
      33. var activePoints = new List<Point>(new[] { point });
      34. var borderPoints = new List<Point>();
      36. while (activePoints.Count > 0)
      37. {
      38. var newActivePoints = new List<Point>();
      39. foreach (Point p in activePoints)
      40. {
      41. bool isBorderPoint = false;
      43. Point[] surroundingPoints = GetSurroundingPoints(p);
      44. foreach (Point p1 in surroundingPoints)
      45. {
      46. if (p1.X < area.GetLowerBound(0) || p1.X > area.GetUpperBound(0)
      47. || p1.Y < area.GetLowerBound(1) || p1.Y > area.GetUpperBound(1)
      48. || area[p1.X, p1.Y] != shapeKey)
      49. {
      50. isBorderPoint = true;
      51. continue;
      52. }
      54. if (inactivePoints.Contains(p1))
      55. continue;
      57. if (!newActivePoints.Contains(p1))
      58. newActivePoints.Add(p1);
      59. }
      61. if (isBorderPoint)
      62. borderPoints.Add(p);
      63. }
      65. inactivePoints.AddRange(activePoints);
      66. activePoints = newActivePoints;
      67. }
      69. interior = inactivePoints.ToArray();
      70. return borderPoints.ToArray();
      71. }
      73. /// <summary>
      74. /// Finds the border of the shape the specified point belongs to.
      75. /// </summary>
      76. public static Point[] FindBorder(int[,] area, Point point)
      77. {
      78. Point[] interior;
      79. return FindBorder(area, point, out interior);
      80. }
      82. /// <summary>
      83. /// Finds the nearest points of the shapes adjacent to the specified point's shape.
      84. /// </summary>
      85. public static Dictionary<int, Point> FindAdjacentShapes(int[,] area, Point point)
      86. {
      87. Point[] borderPoints = FindBorder(area, point);
      88. int shapeKey = area[point.X, point.Y];
      90. var pointsToCheck = new List<Point>();
      91. foreach (Point p in borderPoints)
      92. {
      93. Point[] surroundingPoints = GetSurroundingPoints(p);
      94. foreach (Point p1 in surroundingPoints)
      95. {
      96. if (p1.X < area.GetLowerBound(0) && p1.X > area.GetUpperBound(0)
      97. && p1.Y < area.GetLowerBound(1) && p1.Y > area.GetUpperBound(1)
      98. && area[p1.X, p1.Y] != shapeKey && !pointsToCheck.Contains(p1))
      99. {
      100. pointsToCheck.Add(p1);
      101. }
      102. }
      103. }
      105. var distances = new Dictionary<int, double>();
      106. var points = new Dictionary<int, Point>();
      107. foreach (Point p in pointsToCheck)
      108. {
      109. int key = area[p.X, p.Y];
      111. int dX = p.X - point.X;
      112. int dY = p.Y - point.Y;
      113. double distance = dX * dX + dY * dY;
      115. if (!distances.ContainsKey(key) || distances[key] > distance)
      116. {
      117. distances[key] = distance;
      118. points[key] = p;
      119. }
      120. }
      122. return points;
      123. }
      124. }
      Kannst du es ausprobieren? Ich kanns gerade nicht, muss demnächst leider schlafen gehen und ne Testanwendung würde hier glaube ich großzügiger ausfallen.

      AliveDevil schrieb:

      Zudem darf keine Rekursion angewandt werden.

      AliveDevil schrieb:

      Sobald ein fertiger Algorithmus steht, sollte es einfacher sein, den zu verbessern.
      Diese beiden Aussagen widersprechen sich deutlich.
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      Für Flächen ohne Inseln ist ein Randfinder am effizientesten. Bei mit Inseln muss halt ein Floodfill mit Rand-Detection her.

      Nur die Randpunkte einer Fläche zu merken ist eh bisserl speicherschonender.

      so ich hab mal ein Werk von mir umgebastelt als Basis einer TestSolution. Die Daten werden als 1-dimensionales Array in der LedDesignDts.DesignRow gespeichert, aber ich hab Konverter beiliegen, mit denen man von 1D <-> 2D konvertieren kann:

      VB.NET-Quellcode

      1. Imports System.Runtime.CompilerServices
      3. <Microsoft.VisualBasic.HideModuleName()> _
      4. Public Module ArrayConverter
      5. <Extension()> _
      6. Public Function ToSquare2D(Of T)(arr As T()) As T(,)
      7. Dim sqrt = Math.Sqrt(arr.Length)
      8. Dim size = CInt(sqrt)
      9. If size <> sqrt Then Throw New Exception("das eindimensionale array kann nicht in ein quadratisches 2-dimensionales Array umgewandelt werden")
      10. Dim result(size - 1, size - 1) As T
      11. Using enrt = arr.GetEnumeratorX
      12. For y = 0 To size - 1
      13. For x = 0 To size - 1
      14. enrt.MoveNext()
      15. result(y, x) = enrt.Current
      16. Next
      17. Next
      18. End Using
      19. Return result
      20. End Function
      22. <Extension()> _
      23. Public Function ToArray(Of T)(arr2D As T(,)) As T()
      24. Dim size = arr2D.GetLength(0)
      25. Dim result(size * size - 1) As T
      26. Dim i = 0
      27. For Each n In arr2D
      28. result(i) = n
      29. i += 1
      30. Next
      31. Return result
      32. End Function
      33. End Module

      Dateien

      ErfinderDesRades schrieb:

      Für Flächen ohne Inseln ist ein Randfinder am effizientesten. Bei mit Inseln muss halt ein Floodfill mit Rand-Detection her.
      Bildverarbeitung:
      1. Laplace-Operator.
      2. Diskriminierung am Histogramm-Minimum, Laplace-Operator.
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      @Artentus
      mit einige Änderungen konnte ich die Lösung dazu bewegen, zu funktionieren.
      Eine Bedingung, die ich nicht nannte: es darf nicht diagonal gegangen werden, was am Ende keine Probleme darstellt.
      Die Funktion public static Point[] FindBorder(int[,] area, Point point, out Point[] interior) liefert die Punkte zurück, die gerade nicht außerhalb des Bereiches liegen. Die Definition war Punkte, die auf der Außenfläche liegen. Die Funktion public static Dictionary<int, Point> FindAdjacentShapes(int[,] area, Point point) liefert mir kein Ergebnis, was für mich nicht weiter schlimm ist, da ich auch anderweitig die Dinge testen kann.
      Ein weiterer Punkt: field[area.X, area.Y] geht davon aus, dass das Array so aufgebaut ist:

      Quellcode

      1. Y1 Y2 Y3 Y4
      2. X1 11 12 13 14
      3. X2 21 22 23 24
      4. X3 31 32 33 34
      5. X4 41 42 43 44

      Ich habe mich vermutlich falsch ausgedrückt, als ich sagte, dass das Feld mit X;Y definiert wird.


      So .. da dieser Beitrag jetzt über eine Stunde geschrieben wurde, habe ich keine Ahnung mehr, wovon ich eigentlich am Anfang geschrieben habe.
      Die veränderte, funktionierende Variante ist im Expander zu finden:
      Spoiler anzeigen

      C#-Quellcode

      1. using System;
      2. using System.Collections.Generic;
      3. using System.Drawing;
      4. using System.Linq;
      5. using System.Text;
      6. using System.Threading.Tasks;
      8. namespace ConsoleApplication1
      9. {
      10. class Program
      11. {
      12. static void Main(string[] args)
      13. {
      14. int[,] field = {
      15. {1,1,1,1,1,1,1},
      16. {1,0,0,0,0,0,1},
      17. {1,0,1,0,1,0,1},
      18. {1,0,0,0,0,0,1},
      19. {1,0,1,0,1,0,1},
      20. {1,0,0,2,0,0,1},
      21. {1,1,1,1,1,1,1}
      22. };
      23. var t = AreaMagic.FindBorder(field, new Point(3, 3));
      24. var s = AreaMagic.FindAdjacentShapes(field, new Point(3, 3));
      25. }
      26. }
      27. public static class AreaMagic
      28. {
      29. /// <summary>
      30. /// Gets the surrounding points of a point.
      31. /// </summary>
      32. public static Point[] GetSurroundingPoints(Point point, bool diagonal = false)
      33. {
      34. Point[] result;
      35. if (diagonal)
      36. {
      37. result = new Point[8];
      38. result[0] = new Point(point.X + 1, point.Y);
      39. result[1] = new Point(point.X + 1, point.Y + 1);
      40. result[2] = new Point(point.X, point.Y + 1);
      41. result[3] = new Point(point.X - 1, point.Y + 1);
      42. result[4] = new Point(point.X - 1, point.Y);
      43. result[5] = new Point(point.X - 1, point.Y - 1);
      44. result[6] = new Point(point.X, point.Y - 1);
      45. result[7] = new Point(point.X + 1, point.Y - 1);
      46. }
      47. else
      48. {
      49. result = new Point[4];
      50. result[0] = new Point(point.X + 1, point.Y);
      51. result[1] = new Point(point.X, point.Y + 1);
      52. result[2] = new Point(point.X - 1, point.Y);
      53. result[3] = new Point(point.X, point.Y - 1);
      54. }
      55. return result;
      56. }
      58. /// <summary>
      59. /// Finds the border of the shape the specified point belongs to.
      60. /// </summary>
      61. public static Point[] FindBorder(int[,] area, Point point, out Point[] interior)
      62. {
      63. if (area == null)
      64. throw new ArgumentNullException("area");
      65. if (point.X < area.GetLowerBound(0) || point.X > area.GetUpperBound(0)
      66. || point.Y < area.GetLowerBound(1) || point.Y > area.GetUpperBound(1))
      67. throw new ArgumentOutOfRangeException("startPoint");
      69. int shapeKey = area[point.X, point.Y];
      70. var inactivePoints = new List<Point>();
      71. var activePoints = new List<Point>(new[] { point });
      72. var borderPoints = new List<Point>();
      74. while (activePoints.Count > 0)
      75. {
      76. var newActivePoints = new List<Point>();
      77. foreach (Point p in activePoints)
      78. {
      79. Point[] surroundingPoints = GetSurroundingPoints(p);
      80. foreach (Point p1 in surroundingPoints)
      81. {
      82. if (p1.X < area.GetLowerBound(0) || p1.X > area.GetUpperBound(0)
      83. || p1.Y < area.GetLowerBound(1) || p1.Y > area.GetUpperBound(1)
      84. || area[p1.X, p1.Y] != shapeKey)
      85. {
      86. if (!borderPoints.Contains(p1))
      87. borderPoints.Add(p1);
      88. continue;
      89. }
      91. if (inactivePoints.Contains(p1))
      92. continue;
      94. if (!newActivePoints.Contains(p1))
      95. newActivePoints.Add(p1);
      96. }
      97. }
      99. inactivePoints.AddRange(activePoints);
      100. activePoints = newActivePoints;
      101. }
      103. interior = inactivePoints.ToArray();
      104. return borderPoints.ToArray();
      105. }
      107. /// <summary>
      108. /// Finds the border of the shape the specified point belongs to.
      109. /// </summary>
      110. public static Point[] FindBorder(int[,] area, Point point)
      111. {
      112. Point[] interior;
      113. return FindBorder(area, point, out interior);
      114. }
      116. /// <summary>
      117. /// Finds the nearest points of the shapes adjacent to the specified point's shape.
      118. /// </summary>
      119. public static Dictionary<int, Point> FindAdjacentShapes(int[,] area, Point point)
      120. {
      121. // Änderung in einen LINQ Ausdruck, weil es mir einfacher erschien.
      122. //Point[] borderPoints = FindBorder(area, point);
      123. //int shapeKey = area[point.X, point.Y];
      125. //var l = borderPoints.ToLookup(item => area[item.X, item.Y], item => item);
      126. //var d = l.ToDictionary(item => item.Key, item => item.OrderBy(checkPoint =>
      127. //{
      128. // int dX = checkPoint.X - point.X;
      129. // int dY = checkPoint.Y - point.Y;
      130. // return dX * dX + dY * dY;
      131. //}).First());
      133. //return d;
      136. // Einzeiler. Obiges in "kurz"
      137. // area[item.X, item.Y] muss genutzt werden, da andernfalls die Dictionary-Konvertierung nicht funktioniert.
      138. return FindBorder(area, point).ToLookup(item => area[item.X, item.Y], item => item).ToDictionary(item => item.Key, item => item.OrderBy(checkPoint =>
      139. {
      140. int dX = checkPoint.X - point.X;
      141. int dY = checkPoint.Y - point.Y;
      142. return dX * dX + dY * dY;
      143. }).First());
      144. }
      145. }
      146. }


      @RodFromGermany
      Die zwei Aussagen schließen sich nicht aus, da ein Zwischenergebnis durchaus eine rekursive Funktion sein kann, das Endergebnis aber iterativ sein muss (Crowdthinking, mir fällt der deutsche Begriff dazu nicht ein).

      @ErfinderDesRades
      Wenn du mir sagen könntest, wie man die Anwendung verwendet, wäre das sehr nett. Auf Anhieb steige ich da nämlich gerade nicht durch.

      Ich danke jedem, der mir hier bei der Findung der Lösung beigetragen hat.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „AliveDevil“ ()

      AliveDevil schrieb:

      Die Funktion public static Point[] FindBorder(int[,] area, Point point, out Point[] interior) liefert die Punkte zurück, die gerade nicht außerhalb des Bereiches liegen. Die Definition war Punkte, die auf der Außenfläche liegen.
      Ja, ich weiß, war auch so beabsichtigt. Ich weiß, dass eigentlich das andere gesucht ist, aber die Funktion ist nur ein Zwischenschritt und nur so semantisch sinnvoll. Der Border sind nunmal nur diese Punkte, hätte ich es anders gemacht, dann wäre das zwar in diesem Fall richtig, aber nicht allgemein.

      AliveDevil schrieb:

      ​Die Funktion public static Dictionary<int, Point> FindAdjacentShapes(int[,] area, Point point) liefert mir kein Ergebnis
      Das ist schade. Darf ich fragen, was der Fehler ist?
      Eigentlich war es so geplant:
      Schritt 1: die Randpunkte mit FindBorder holen.
      Schritt 2: die an diese Punkte angrenzenden Punkte, die eine andere zahl haben, sind die äußeren Punkte.
      Schritt 3: von diesen Punkten wiederum alle durchgehen und den nächsten finden - und zwar für jede vorkommende Zahl einen.

      AliveDevil schrieb:

      Ich habe mich vermutlich falsch ausgedrückt, als ich sagte, dass das Feld mit X;Y definiert wird.
      Was meintest du denn eigentlich, wenn nicht ein solches Array? Das würde mich jetzt doch mal interessieren.

      Nach meiner Definition wäre das Array mit Y;X definiert worden.

      Jap, genau das, was du eigentlich wolltest, funktionierte nicht. Ich hatte mich auch nicht weiter mit der Nicht-Funktionalität beschäftigt, sondern eher damit, die Funktion FindBorders() anzupassen.
      Es soll zudem nur der nächste Partner gesucht werden, nicht alle möglichen Flächen, die eventuell beteiligt sein könnten. Das es dann nicht allgemein gilt, ist dann klar.
      Hast du selbst deinen Code mit meinem Sample-Array getestet? Es werden entweder zuviele oder zuwenige Punkte angegeben (FindAdjacentShapes lieferte mir jedesmal {} zurück).

      Die Funktion kann ja trotzdem so bestehen bleiben, denn ansich funktioniert sie - würde sie nicht {} zurückgeben.

      AliveDevil schrieb:

      Nach meiner Definition wäre das Array mit Y;X definiert worden.
      Wirklich? Kann man das so sagen? Imo hätte es ja auch sein können, das die Y-Dimension die erste im Array ist. Da ein Array keinerlei räumliche Anhaltspunkte liefert, hätte das Bild auch einfach an der Vertikalen gespiegelt sein können und an der Indizierung des Arrays hätte sich nichts geändert. Es hängt eben nur davon ab, wie man die Koordinaten bei der Darstellung wählt, geht man von der allgemeinen Konvention aus, dann wäre das Bild von dir ein Y-X-System, kein X-Y-System, also genau das, was du wolltest.

      AliveDevil schrieb:

      Es soll zudem nur der nächste Partner gesucht werden, nicht alle möglichen Flächen, die eventuell beteiligt sein könnten.
      Hä, warum kommt dann ein Dictionary raus? Ich bin gerade verwirrt.

      ich hab jetzt einen Randfinder gebastelt. Nach Art der Turtle-Programmierung. Also ein Objekt kann in 4 Richtungen voranschreiten, und bei Kollision musses halt die Richtung ändern.
      Dafür hab ich mir eine extra Richtung-Klasse ausgedacht:

      VB.NET-Quellcode

      1. Imports System.Diagnostics
      3. <DebuggerDisplay("{Value}")> _
      4. Public Structure Direction
      5. Private Shared _Directions As Integer = 4
      6. Public Value As Integer
      7. Private Shared Function cyclicAddition(left As Integer, right As Integer) As Integer
      8. cyclicAddition = (left + right) Mod _Directions
      9. If cyclicAddition < 0 Then cyclicAddition += _Directions
      10. End Function
      11. Public Shared Operator +(ByVal left As Direction, ByVal right As Integer) As Direction
      12. Return New Direction With {.Value = cyclicAddition(left.Value, right)}
      13. End Operator
      14. Public Shared Operator -(ByVal left As Direction, ByVal right As Integer) As Direction
      15. Return New Direction With {.Value = cyclicAddition(left.Value, -right)}
      16. End Operator
      17. Public Shared Widening Operator CType(ByVal initialData As Integer) As Direction
      18. Return New Direction With {.Value = initialData}
      19. End Operator
      20. Public Function Move(pt As Point) As Point
      21. If (Value And 1) = 1 Then 'horizontal
      22. pt.X += 2 - Value
      23. Else 'vertical
      24. pt.Y += Value - 1
      25. End If
      26. Return pt
      27. End Function
      28. End Structure
      Also nix besonderes, nur dass man unendlich in-/de-crementieren kann ohne Zahlen-Überlauf.
      Achja, und dann kann eine Direction einen Point um einen Schritt moven.

      und die Turtle ist auch überraschend übersichtlich:

      VB.NET-Quellcode

      1. Imports System.ComponentModel
      3. Public Class Turtle : Implements INotifyPropertyChanged, INotifyPropertyChanging
      5. Public Event PropertyChanged As PropertyChangedEventHandler Implements INotifyPropertyChanged.PropertyChanged
      6. Public Event PropertyChanging As PropertyChangingEventHandler Implements INotifyPropertyChanging.PropertyChanging
      8. Public Direction As New Direction
      10. ''' <summary> this validator is meant to be set from outside </summary>
      11. Public Canstep As Func(Of Point, Boolean)
      13. Private _Location As Point = Nothing
      14. Public Property Location() As Point
      15. Get
      16. Return _Location
      17. End Get
      18. Set(value As Point)
      19. If _Location = value Then Return
      20. RaiseEvent PropertyChanging(Me, New PropertyChangingEventArgs("Location"))
      21. _Location = value
      22. RaiseEvent PropertyChanged(Me, New PropertyChangedEventArgs("Location"))
      23. End Set
      24. End Property
      26. ''' <summary> try move in its Direction </summary>
      27. Public Function TryStep() As Boolean
      28. Dim pt = Direction.Move(_Location)
      29. If Not Canstep(pt) Then Return False
      30. Location = pt
      31. Return True
      32. End Function
      34. ''' <summary> move along the Border - Border on left hand </summary>
      35. Public Sub StepAgainstBorder()
      36. 'suche rechtsrum eine freie Richtung. Wenn gefunden, 1 Schritt, dann Richtung decrementieren damit wieder gegen die Grenze gerichtet.
      37. For i = 0 To 3
      38. If TryStep() Then
      39. Direction -= 1
      40. Return
      41. End If
      42. Direction += 1
      43. Next
      44. End Sub
      46. End Class
      die muss halt 2 Step-Modi haben, weil die Art, wie sie an einer Grenze entlanggeht ist ganz anders, als wenn sie von ieinem Punkt gradeaus läuft, um eine Grenze erstmal aufzufinden.
      Son Turtle findet allerdings keine Inseln (bzw. wenn doch, dann hält er sie für die Aussen-Grenzen seiner Welt).
      Für Insel-Detection müsste man das Innere der gefundenen Randlinie nochmal zeilenweise durchlaufen.


      Ich hab das mit Timer und pipapo gemacht - guckt sich sehr hübsch.
      Dateien

      • TurtleTester.zip

        (69,95 kB, 242 mal heruntergeladen, zuletzt: )

      Einfaches Rätsel ;) :

      Gegeben sei ein binärer Baum. (Eine Struktur zum (z.B.) Speichern von Daten, bei der ein Knoten lediglich 2 Knoten unter sich haben darf).
      Man hat also einen Urknoten, der hat 2 Knoten unter sich, die widerum 2 unter sich haben, usw. Pro "Ebene"/"Level" also doppelt so viele Knoten.

      Die Frage ist nun:
      Wie könnte ein Algorithmus aussehen, der den Baum in vollständiger Balance hält, egal wie groß er wird?
      (Damit ist gemeint, dass, egal an welchem Knoten man steht, die Differenz der totalen Anzahl der linken oder rechten (Unter-)Knoten eines jeden Knoten auf beiden Seiten [ggf. mit deren Unterknoten] den Wert 1 nicht überschreitet).
      Die ersten haben sicher schon Ideen ;)

      Lösung (soll sein):
      Ein Projekt, dass a) kompiliert und dem b) dem zum Beispiel 100 Knoten (eine Zahl) hingeworfen werden können und am Ende eine Liste von 100 Zahlen zurück gibt. Diese 100 Zahlen (ID's der Knoten) stehen für die Reihenfolge, wie die Knoten zu verteilen sind. Hä? Okay: Alle (möglichen) Knoten des Baumes werden 1. von oben nach unten und dann 2. von links nach Rechts durch numeriert. Somit hat jeder Knoten seine Zahl.

      Quellcode

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

      Der Knoten (0) ist der Wurzelknoten. (1) ist der linke Child von (0). (2) ist der rechte Child von (0). (3) ist der linke Child von (1), (4) der rechte. (5) ist der Linke von (2), etc.
      Das Ergebnis ist - wie gesagt - eine Reihenfolge. Gibt man dem Algorithmus hier die Zahl 10, sollte folgendes zurückgegeben werden:
      0 - 1 - 2 - 3 - 5 - 4 - 6 - 7 - 11 - 9
      Warum? Weil egal an welchem Knoten im "fertigen" Baum man steht, die Differenz der Anzahl der Knoten rechts oder links davon ist nicht größer als 1.
      Schaut man sich Knoten 0 an, hat seine linke Seite 5 Knoten unter sich (1, 3, 4, 7, 9), seine rechte Seite 4 Knoten (2, 5, 6, 11). Linke Seite plus eins, Bedingung erfüllt.
      Schaut man auf Knoten 1, so haben sowohl seine linke Seite (3, 7), als auch seine rechte (4, 9) gleich viele Knoten unter sich. Bedingung erfüllt.

      Kleine Einschränkung:
      Es dürfen ausschließlich Objekte des .Net Frameworks verwendet werden (keine eigenen Klassen) und um den Stand zur
      Zeit der Berechnung festzuhalten, lediglich
      ein List(of Integer) und ein List(of object). Außerdem alle nativen Datentypen und deren Grundrechenoperationen.

      Gut ist, wer es raus bekommen hat, perfekt ist, dessen Funktion am längsten Überlebt, je mehr Knoten reingegeben werden.

      Ich glaube nicht jeder von euch kommt SOFORT drauf, ist eher ne Denkaufgabe.
      Die Lösung ist technisch eigentlich ziemlich einfach, bei mir gings :| :S :huh: ?( 8| 8o :whistling:

    Facebook