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

    • VB.NET

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

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

      In diesem Thread kann jeder eine "Knobel-Aufgabe" stellen, und alle sind eingeladen, (zu) Lösungen beizutragen, oder Lösungen mit zu diskutieren.

      Unter Knobel-Aufgabe verstehe ich eine klar definierte Aufgabenstellung: Es sollte klar sein, was der Input ist, und was als Output rauszukommen hat.
      Eine Möglichkeit, eine Aufgabe eindeutig zu definieren, ist, zusätzlich zur Problembeschreibung auch gleich eine Methoden-Signatur vorzuschlagen, denn so ein Methodenkopf deklariert ja vorbildlich eindeutig den Input als Argument-Liste, und den Output als Rückgabewert.
      Aber ihr könnt natürlich auch komplette Test-Anwendungen zippen und anhängen (natürlich nur Sources!), sodass die Knobler nur modifizieren müssen, oder sogar nur fehlende Funktionalität einbauen.

      Hinweis: Wenn ihr eine Knobelei einstellt, bitte als Überschrift einen aussagekräftigen Namen wählen.

      benutzerdefinierte Sortierung von Adressen-Strings

      Diese Knobelei kommt aus diesem Thread:

      Eine Liste von Address-Strings soll zunächst nach Stadt, dann nach Strasse, dann nach Hausnummer sortiert werden. Natürlich sollen dabei die Hausnummern numerisch sortiert werden, nicht alphabetisch:

      Falsch:
      Bundesstrasse 11, Aurich
      Bundesstrasse 11, Zürich
      Bundesstrasse 20, Aurich
      Bundesstrasse 20, Zürich
      Bundesstrasse 4, Aurich
      Bundesstrasse 4, Zürich
      Bundesstrasse 5, Aurich
      Bundesstrasse 5, Zürich

      Richtig:
      Bundesstrasse 4, Aurich
      Bundesstrasse 5, Aurich
      Bundesstrasse 20, Aurich
      Bundesstrasse 31, Aurich
      Bundesstrasse 4, Zürich
      Bundesstrasse 5, Zürich
      Bundesstrasse 20, Zürich
      Bundesstrasse 31, Zürich
      Bitteschön:

      C-Quellcode

      1. IEnumerable<string> sorted = addresses.Select(address => address.Split(new[] { ", ", " " }, StringSplitOptions.RemoveEmptyEntries))
      2. .Select(parts => new { Town = parts[2], Street = parts[0], HouseNumber = int.Parse(parts[1]) })
      3. .OrderBy(address => address.Town).ThenBy(address => address.Street).ThenBy(address => address.HouseNumber);
      Konverter benutzen:

      VB.NET-Quellcode

      1. Dim sorted As IEnumerable(Of String) = addresses.[Select](Function(address) address.Split(New () {", ", " "}, StringSplitOptions.RemoveEmptyEntries)).[Select](Function(parts) New With { _
      2. Key .Town = parts(2), _
      3. Key .Street = parts(0), _
      4. Key .HouseNumber = Integer.Parse(parts(1)) _
      5. }).OrderBy(Function(address) address.Town).ThenBy(Function(address) address.Street).ThenBy(Function(address) address.HouseNumber)
      ja, und dann kompilierts nicht.
      Kompiliert das denn in c#?

      Also was ich daraus (lauffähig) übersetzt hab:

      VB.NET-Quellcode

      1. Dim addresses = "Bundesstrasse 11, Aurich°Bundesstrasse 11, Zürich°Bundesstrasse 20, Aurich°Bundesstrasse 20, Zürich°Bundesstrasse 4, Aurich°Bundesstrasse 4, Zürich°Bundesstrasse 5, Aurich°Bundesstrasse 5, Zürich" _
      2. .Split("°"c)
      3. Dim sorted = addresses.[Select](Function(address) address.Split({", ", " "}, StringSplitOptions.RemoveEmptyEntries)).Select(Function(parts) _
      4. New With {Key .Town = parts(2), Key .Street = parts(0), Key .HouseNumber = Integer.Parse(parts(1))}) _
      5. .OrderBy(Function(address) address.Town).ThenBy(Function(address) address.Street).ThenBy(Function(address) address.HouseNumber)
      Ungelöst ist auch, dass die Ausgabe nun ein anonymer Typ ist, statt einer String-Auflistung
      Ups, sorry, hatte irgendwie beim kopieren eine Zeile nicht erwischt. So siehts richtig aus, und ja, das kompilliert:

      C-Quellcode

      1. IEnumerable<string> sorted = addresses.Select(address => address.Split(new[] { ", ", " " }, StringSplitOptions.RemoveEmptyEntries))
      2. .Select(parts => new { Town = parts[2], Street = parts[0], HouseNumber = int.Parse(parts[1]) })
      3. .OrderBy(address => address.Town).ThenBy(address => address.Street).ThenBy(address => address.HouseNumber)
      4. .Select(address => string.Join(" ", address.Street, address.HouseNumber + ",", address.Town));
      jepp - so gehts (lauffähige Lsg):

      VB.NET-Quellcode

      1. Dim addresses = "Bundesstrasse 11, Aurich°Bundesstrasse 11, Zürich°Bundesstrasse 20, Aurich°Bundesstrasse 20, Zürich°Bundesstrasse 4, Aurich°Bundesstrasse 4, Zürich°Bundesstrasse 5, Aurich°Bundesstrasse 5, Zürich" _
      2. .Split("°"c)
      3. Dim sorted = addresses.[Select](Function(address) address.Split({", ", " "}, StringSplitOptions.RemoveEmptyEntries)).Select(Function(parts) _
      4. New With {Key .Town = parts(2), Key .Street = parts(0), Key .HouseNumber = Integer.Parse(parts(1))}) _
      5. .OrderBy(Function(address) address.Town).ThenBy(Function(address) address.Street).ThenBy(Function(address) address.HouseNumber) _
      6. .Select(Function(address) String.Join(" ", address.Street, address.HouseNumber, address.Town))
      7. MessageBox.Show(String.Join(Microsoft.VisualBasic.ControlChars.Lf, sorted))
      umh warum nicht einfach so?

      VB.NET-Quellcode

      1. Private Function orderByLogic(ByVal input As IEnumerable(Of String)) As IEnumerable(Of String)
      2. Return input.OrderBy(Function(item) item.Split({" "c, ","c})(3)).ThenBy(Function(item) Integer.Parse(item.Split({" "c, ","c})(1))).ThenBy(Function(item) item.Split(" "c)(0))
      3. End Function



      Dann einfach so aufrufen:

      VB.NET-Quellcode

      1. Public Class Form1
      2. Private words As New List(Of String) From {"Bundesstrasse 11, Aurich",
      3. "Bundesstrasse 11, Zürich",
      4. "Bundesstrasse 20, Aurich",
      5. "Bundesstrasse 20, Zürich",
      6. "Bundesstrasse 4, Aurich",
      7. "Bundesstrasse 4, Zürich",
      8. "Bundesstrasse 5, Aurich",
      9. "Bundesstrasse 5, Zürich"}
      10. Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
      11. For Each item In OrderByLogic(words)
      12. MessageBox.Show(item)
      13. Next
      14. End Sub
      15. Private Function orderByLogic(ByVal input As IEnumerable(Of String)) As IEnumerable(Of String)
      16. Return input.OrderBy(Function(item) item.Split({" "c, ","c})(3)).ThenBy(Function(item) Integer.Parse(item.Split({" "c, ","c})(1))).ThenBy(Function(item) item.Split(" "c)(0))
      17. End Function
      18. End Class

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „RushDen“ ()

      VB.NET-Quellcode

      1. private List<string> Liste = new List<string>() {"Bundesstrasse*11, Aurich",
      2. "Bundesstrasse*11, Zürich",
      3. "Bundesstrasse*20, Aurich",
      4. "Bundesstrasse*20, Zürich",
      5. "Arbeitsweg*4, Aurich",
      6. "Bundes strasse*4, Zürich",
      7. "Bundesstrasse*5, Aurich",
      8. "Bundes strasse*5, Zürich"};
      9. private IEnumerable<string> orderByLogic(IEnumerable<string> input)
      10. {
      11. return input.OrderBy(item => item.Substring(item.IndexOf(",") + 2, item.Length - item.IndexOf(",") - 2)).ThenBy(item => item.Substring(item.IndexOf("*"),item.IndexOf(",") - 1 - item.IndexOf("*"))).ThenBy(item => item.Substring(0,item.IndexOf("*") - 1)).Select(item => item.Replace("*"," "));
      12. }


      Das geht auch mit Leerzeichen in Stadt/Strasse
      ich hab hier noch ein mit Linq-Syntax:

      VB.NET-Quellcode

      1. Dim addresses = "Bundesstrasse 11, Aurich°Bundesstrasse 11, Zürich°Bundesstrasse 20, Aurich°Bundesstrasse 20, Zürich°Bundesstrasse 4, Aurich°Bundesstrasse 4, Zürich°Bundesstrasse 5, Aurich°Bundesstrasse 5, Zürich" _
      2. .Split("°"c)
      3. Dim sorteds = From str In addresses Let splits = str.Split({", ", " "}, StringSplitOptions.RemoveEmptyEntries) _
      4. Order By splits(2), splits(0), Integer.Parse(splits(1)) Select str
      5. MessageBox.Show(String.Join(Lf, sorteds))
      6. Listbox1.DataSource=sorteds.ToArray
      Wobei natürlich nicht das von @nikeee13: angesprochene Problem mit den Spaces im StrassenNamen gelöst ist.

      Auch nicht gelöst ist das Problem der Hausnummer-Zusätze, etwa "Bundesstrasse 20a" oder "Bundesstrasse 20-1" oder "Bundesstrasse 20/1"

      Aber das würde ich nicht zum Bestandteil dieser Knobelei machen, denn solch Überlegungen führen darauf hin, was @SpaceyX: bereits im ursprünglichen FrageThread gesagt hat: Nämlich dass es sich um Datensätze handelt, und daher kommt man mittelfristig mit Comboboxen und List(Of String) nicht mehr aus.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Folgendes Problemchen:
      Malt im Paint-Event oder auf einer Bitmap einen Kreis.
      Nebenbedingungen:
      Gegeben seien Mittelpunkt und Radius;
      zu berechnen sind die Pixelkoordinaten der Kreis-Punkte, sie sollen in einer List(Of Point) abgelegt werden, die Darstellung erfolgt dann mit e.Graphics.DrawPolygon().
      Es darf nur Integer-Arithmetik verwendet werden, keine trigonometrischen Funktionen, keine Gleitkomma-Werte und -Operationen :!:
      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!
      ist mir zu schwierig, aber ich kann ja die Test-Anwendung beisteuern (inklusive miserabler Annäherung)

      also die Aufgabe wäre definiert durch die Signatur GetCirclePoints(radius As Integer, center As Point) As Point()

      VB.NET-Quellcode

      1. Public Class frmCircleDrawer
      2. Private _Radius As Integer = 60
      3. Private _Center As New Point(200, 100)
      4. Private Sub FalscheLoesung_Paint(sender As Object, e As PaintEventArgs) Handles Me.Paint
      5. Dim r2 = _Radius * 2
      6. Dim rct = New Rectangle(_Center.X - _Radius, _Center.Y - _Radius, r2, r2)
      7. e.Graphics.DrawEllipse(Pens.Red, rct)
      8. End Sub
      9. Private Sub Loesung_Paint(sender As Object, e As PaintEventArgs) Handles Me.Paint
      10. e.Graphics.DrawPolygon(Pens.Green, GetCirclePoints(_Radius, _Center))
      11. End Sub
      12. Private Function GetCirclePoints(radius As Integer, center As Point) As Point()
      13. 'Un-Lösung: 8 Punkte auf dem Kreis, beginnend oben links
      14. Dim rSqrt = CInt(radius / Math.Sqrt(2))
      15. Dim r = radius
      16. Return {-rSqrt, 0, rSqrt, r, rSqrt, 0, -rSqrt, -r}.Zip({-rSqrt, -r, -rSqrt, 0, rSqrt, r, rSqrt, 0}, _
      17. Function(x, y) New Point(x + center.X, y + center.Y)).ToArray
      18. End Function
      19. End Class


      keine Gleitkomma-Werte und -Operationen
      d.h. Math.Sqrt() ist auch untersagt?

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

      Das ist n' fertiger Algo, der sich irgendwie aus dem Algo für das Zeichnen von Geraden ohne Gleitkommaaritmetik ableitet, erfunden von irgend nem Microsoft-Typen vor ~30 Jahren. Mir fällt nur nicht mehr ein, wir er hieß, weshalb ich es noch nicht gegooglet hab, aber er war nach seinem Erfinder benannt.
      Ich glaube übrigens, Wurzel ist eh nicht erlaubt, ist zumindest in besagtem Algo nicht enthalten
      Ich würd jetzt hier über die bekannten vier Punkte gehen (also oben, unten, rechts und links vom Mittelpunkt) und dann mit Matrix.RotateAt() und Matrix.TranformPoints() rotieren. Dann entsprechend der List hinzufügen. Das klappt nur mit ints allerdings verwendet die Matrix Klasse intern natürlich Trigonometrie. Wär das trotzdem ne akzeptable Lösung ?
      Ich glaub ich habs fast, aber keine Lust mehr. Müsste es nur noch schaffen die Points im Uhrzeigersinn zu sortieren.
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Private Sub Form1_Paint(sender As Object, e As PaintEventArgs) Handles Me.Paint
      2. pList = New List(Of Point)
      3. For i = -1000 To 1000
      4. For ii = -1000 To 1000
      5. Dim x As Integer = i
      6. Dim y As Integer = ii
      7. Dim res As Integer = CInt((x - 2) ^ 2 + (y - 1) ^ 2)
      8. If res > 495 And res < 505 Then
      9. pList.Add(New Point(x + 50, y + 50))
      10. End If
      11. Next
      12. Next
      13. e.Graphics.DrawPolygon(Pens.Black, pList.ToArray)
      14. End Sub

      Bilder
      • Unbenannt.JPG

        8,97 kB, 73×71, 3.512 mal angesehen
      Ok, ich habs doch noch gefunden, das, was ich meinte, war der Bresenham-Algorithmus.
      Ist zwar ein bisschen geschummelt, weil ichs nicht erfunden hab, aber ich frag mich sowieso, wie man sich sowas ausdenken kann, hätte ich selbst niemals geschafft. Hier meine Implementierung in C#:
      Spoiler anzeigen

      C-Quellcode

      1. public Point[] RasterizeCircle(Point center, int radius)
      2. {
      3. var lists = new List<Point>[8];
      4. for (int i = 0; i < lists.Length; i++)
      5. lists[i] = new List<Point>();
      6. lists[0].Add(new Point(center.X + radius, center.Y));
      7. lists[2].Add(new Point(center.X, center.Y + radius));
      8. lists[4].Add(new Point(center.X - radius, center.Y));
      9. lists[6].Add(new Point(center.X, center.Y - radius));
      10. int x = radius;
      11. int y = 0;
      12. int error = radius;
      13. while (y < x)
      14. {
      15. error -= (y++ << 1) + 1;
      16. if (error < 0)
      17. error += (x-- << 1) - 1;
      18. lists[0].Add(new Point(x + center.X, y + center.Y));
      19. lists[1].Add(new Point(y + center.X, x + center.Y));
      20. lists[2].Add(new Point(-y + center.X, x + center.Y));
      21. lists[3].Add(new Point(-x + center.X, y + center.Y));
      22. lists[4].Add(new Point(-x + center.X, -y + center.Y));
      23. lists[5].Add(new Point(-y + center.X, -x + center.Y));
      24. lists[6].Add(new Point(y + center.X, -x + center.Y));
      25. lists[7].Add(new Point(x + center.X, -y + center.Y));
      26. }
      27. for (int i = 1; i < lists.Length; i += 2)
      28. lists[i].Reverse();
      29. return lists.Aggregate<IEnumerable<Point>>((list1, list2) => list1.Concat(list2)).ToArray();
      30. }