Testen ob ein Integer die Zahlen 1-9 enthält

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 26 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Ich kann dann ja auch mal meine Rekursion mit Backtracking anbringen

    VB.NET-Quellcode

    1. Public Sub Main(ParamArray args() As String)
    2. Dim sw = Diagnostics.Stopwatch.StartNew
    3. Dim nmbs = GetNumbsEDR()
    4. Console.WriteLine($"GetNumbsEDR: { nmbs.Count} Lösungen gefunden in {sw.ElapsedMilliseconds} ms")
    5. nmbs.ForEach(AddressOf Console.WriteLine)
    6. Console.ReadKey()
    7. End Function
    9. Private Function ComposeNumb(digits As Integer(), count As Integer) As Integer
    10. Dim result = 0
    11. For i = 0 To count - 1
    12. result = result * 10 + digits(i)
    13. Next
    14. Return result
    15. End Function
    17. Private Function GetNumbsEDR() As List(Of Integer)
    18. Dim result = New List(Of Integer)
    19. Dim digits = Enumerable.Range(1, 9).ToArray
    20. Dim recurse As Action(Of Integer) _
    21. = Sub(index)
    22. Dim divisor = index + 1
    23. For i = index To 8
    24. digits.Swap(index, i) ' ziffer am Index mit einer der Folge-Zahlen tauschen
    25. Dim testNumb = ComposeNumb(digits, divisor)
    26. If testNumb Mod divisor = 0 Then ' Regel wird eingehalten
    27. If divisor = 9 Then
    28. result.Add(testNumb) ' EndErgebnis
    29. Else
    30. recurse(divisor) ' ZwischenErgebnis, geeignet für rekursive Vertiefung
    31. End If
    32. End If
    33. digits.Swap(index, i) 'ziffern zurücktauschen, für den nächsten Versuch
    34. Next
    35. End Sub
    36. recurse(0)
    37. Return result
    38. End Function
    40. <Runtime.CompilerServices.Extension(), DebuggerStepThrough()>
    41. Public Sub Swap(items As IList, i1 As Integer, i2 As Integer)
    42. If i1 = i2 Then Return
    43. Dim Tmp = items(i1)
    44. items(i1) = items(i2)
    45. items(i2) = Tmp
    46. End Sub
    Der Vorteil ist, wenn eine kurze Ziffernfolge sich als falsch erweist, wird sie verworfen und die Untersuchung der Folge-Ziffern, die man damit auch noch bilden könnten, wird übersprungen (Backtracking)

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

    Neo127 schrieb:

    Habe es heute morgen abgeschickt.
    Täte mich noch interessieren, ob du Erfolg hattest.
    Wirklich verstehen tu ich dein Code zwar nicht, aber wenn man die ganzen Zwischen-Ausgaben weglässt hat er eine ausgezeichnete Laufzeit.
    Und das, obwohl viele performance-fressende Unzulänglichkeiten vorliegen.
    Daher vermute ich, du hast irgendwie auf iterativem Wege eine Lösung mit Backtracking zustande gebracht - und das, obwohl du vermutlich noch nie davon gehört hast - Respekt!

    Die Erklärung ist sehr einfach.

    @Neo127 hat einfach immer geschaut welche verketteten Zahlen durch die Stelle n teilbar ist.
    und die entsprechenden Zahlen dann zusammengesammelt. Also genau so wie die Aufgabe
    gestellt worden ist.

    Hier sein Beispiel ein bisschen anders gemacht wobei ich auch wieder mit einer BasisArray anfange.

    Freundliche Grüsse

    exc-jdbi
    Spoiler anzeigen
    ​

    VB.NET-Quellcode

    1. ​Private Lst As List(Of Int32)
    2. Private arraycounter As Int32
    3. Public Sub Main()
    4. Dim sw = New Stopwatch
    5. sw.Restart()
    6. Dim result = New List(Of Int32())
    7. Dim basicarray = Enumerable.Range(1, 9).
    8. Select(Function(x) {x}).ToArray
    9. For k As Int32 = 2 To 9
    10. result = New List(Of Int32())
    11. For i As Int32 = 0 To basicarray.Length - 1
    12. For j As Int32 = 1 To 9
    13. If basicarray(i).Contains(j) Then Continue For
    14. Dim t = ConcatenateNumerics(basicarray(i))
    15. If IsDivisible(t * 10 + j, k) Then
    16. Dim l = basicarray(i).ToList
    17. l.Add(j)
    18. result.Add(l.ToArray)
    19. End If
    20. Next
    21. Next
    22. '381654729
    23. basicarray = result.ToArray
    24. Next
    25. Console.WriteLine(sw.ElapsedMilliseconds & "ms")
    26. Console.ReadLine()
    27. End Sub
    28. Private Function ConcatenateNumerics(digits() As Int32) As Int32
    29. Dim result = 0I
    30. Array.ForEach(digits, Sub(x) result = result * 10 + x)
    31. Return result
    32. End Function
    33. Function IsDivisible(x As Int32, d As Int32) As Boolean 'Funktio
    34. Return (x Mod d) = 0
    35. End Function

    Ah - es wird also nicht wie bei mir ein Weg gegangen, bis nicht mehr weiter geht, und dann zurück zur letzten Abzweigung (rekursiven TiefenSuche).

    Sondern es werden alle gangbaren Wege gemerkt, und quasi gleichzeitig gegangen - je einen Schritt pro runde.
    Dabei sind zwischenzeitlich viele weitere gangbare (Teil-)Wege zu merken, was sich aber wieder reduziert, da die Wege rausgeworfen werden, die sich als ungangbar erweisen.

    Jo, sowas heisst: "BreitenSuche", und das ist tatsächlich die (soweit ich weiss immer mögliche) iterative Alternative zur rekursiven TiefenSuche.
    Klassischerweise implementiert man sowas mit einer Queue.

    Spasseshalber habichmal eine klassische Breitensuche zur Gegenüberstellung gebastelt, und die Benamungen aneinander angeglichen, dass man die Ähnlichkeit sieht:

    VB.NET-Quellcode

    1. Private Function Breitensuche() As List(Of Integer)
    2. Dim q As New Queue(Of List(Of Integer))
    3. Enumerable.Range(1, 9).Select(Function(x) New List(Of Integer)({x})).ToList.ForEach(AddressOf q.Enqueue) 'initiale Beaufschlagung der Queue
    4. Do
    5. Dim candidate = q.Dequeue
    6. Dim k = candidate.Count + 1
    7. For j = 1 To 9
    8. If candidate.Contains(j) Then Continue For
    9. Dim t = ComposeNumb(candidate)
    10. If (t * 10 + j) Mod k = 0 Then
    11. Dim newCandidate = candidate.ToList : newCandidate.Add(j)
    12. q.Enqueue(newCandidate)
    13. End If
    14. Next
    15. 'normalerweise endet eine Breitensuche, wenn die Queue leer ist, aber hier kann man abbrechen, wenn k=9 erreicht ist.
    16. 'weil alle in der Queue verbliebenen candidaten müssen jetzt länge 9 haben (naja, es ist nur einer, aber das konnte man ja nicht wissen)
    17. If k = 9 Then Return q.Select(Function(x) ComposeNumb(x)).ToList
    18. Loop
    19. End Function
    21. Public Function Exjdbi() As List(Of Integer)
    22. Dim candidates = Enumerable.Range(1, 9).Select(Function(x) New List(Of Integer)({x})).ToList
    23. For k As Int32 = 2 To 9
    24. Dim newCandidates = New List(Of List(Of Integer))
    25. For Each candidate In candidates
    26. For j As Int32 = 1 To 9
    27. If candidate.Contains(j) Then Continue For
    28. Dim t = ComposeNumb(candidate)
    29. If (t * 10 + j) Mod k = 0 Then
    30. Dim newCandidate = candidate.ToList : newCandidate.Add(j)
    31. newCandidates.Add(newCandidate)
    32. End If
    33. Next
    34. Next
    35. candidates = newCandidates
    36. Next
    37. Return candidates.Select(Function(x) ComposeNumb(x)).ToList
    38. End Function
    40. Private Function ComposeNumb(digits As ICollection(Of Integer), Optional count As Integer = -1) As Integer
    41. If count < 0 Then count = digits.Count
    42. Dim result = 0
    43. For i = 0 To count - 1
    44. result = result * 10 + digits(i)
    45. Next
    46. Return result
    47. End Function
    Das find ich eine sehr interessante Breiten-Such-Variante, wo die Elemente nicht sukzessive durchgequeuet werden, sondern quasi immer eine ganze "Schritt-Ebene" ausgetauscht wird.

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

    @ErfinderDesRades Hi ich würde gerne dein "Rekursiev-Code-Beispiel" verstehen (Post 21). Danke für deine Hilfe und Zeit die Du hier investierst!

    Komplett neu ist mir der Teil mit ... As Action(of Integer) = Sub(index) .... End Sub

    Sub(index) ist bei dem ersten Durchlauf (0) muss Index nicht irgendwo definiert werden?

    Dann beim zweiten Durchgang ist der Sub (Index) = Übergabewert (divisor)
    (also konkret index = 0,1,2,3, ... und divisor dementsprechend 1,2,3,4,...).

    Sobald eine Division einen Rest ergibt wird "abgebrochen" und die nächste Stelle in der 9stelligen Zahl "geswapt" (oder es klappt bis Division 9 ohne Rest -> dann Lösung abspeichern)

    Was muss ich mir unter ... As Action(Of ) vorstellen, hast Du da eventuell auch eines deiner vielen Tutoruials zu oder einen Link der das Thema verständlich erklärt? Danke


    VB.NET-Quellcode

    1. Dim recurse As Action(Of Integer) _
    2. = Sub(index)
    3. Dim divisor = index + 1
    4. For i = index To 8
    5. digits.Swap(index, i) ' ziffer am Index mit einer der Folge-Zahlen tauschen
    6. Dim testNumb = ComposeNumb(digits, divisor)
    7. If testNumb Mod divisor = 0 Then ' Regel wird eingehalten
    8. If divisor = 9 Then
    9. result.Add(testNumb) ' EndErgebnis
    10. Else
    11. recurse(divisor) ' ZwischenErgebnis, geeignet für rekursive Vertiefung
    12. End If
    13. End If
    14. digits.Swap(index, i) 'ziffern zurücktauschen, für den nächsten Versuch
    15. Next
    16. End Sub


    P.S. ...es scheint genau eine Zahl zu geben, wo die Bedingungen zutreffen ;) 381654729
    codewars.com Rank: 4 kyu

    @nogood

    Es ist fast das gleiche wie ich in meinem Beitrag #20 gemacht habe, nur das die permutation von links nach rechts läuft zum einen, und durch die Rekursion werden die Kombinationen gleich geprüft ob Gültigkeit besteht. Sofern nicht, wird zurückgegangen und wieder vorwärts in eine noch nicht gefundene Kombination (Backtracking). Man nennt es auch Tiefensuche (eines der Traversierung) . ich behaupte mal vorsichtig eine Breitensuche findet auch statt, einfach immer auf der entsprechenden Tiefe der Rekursion.

    EDR hat das Ganze clevererweise dann auch noch in eine anonyme Methode gepackt.

    Freundliche Grüsse

    exc-jdbi

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

    nogood schrieb:

    Was muss ich mir unter ... As Action(Of ) vorstellen
    naja - setze du im Code den Cursor auf Action und rufe per KontextMenü "Zu Definition gehen" auf.
    Das sollte den Objectbrowser öffnen, und dir zeigen, was darunter zu verstehen ist:
    Action(Of T) ist ein Delegat, der auf eine Sub passt, die ein Argument erwartet.
    Es gibt viele weitere solcher Action-Delegaten:
    • für eine Sub ohne Argument
    • für eine Sub mit einem Argument (hier verwendet)
    • für eine Sub mit zwei Argumenten
    • für eine Sub mit drei Argumenten
    • ...
    Der Datentyp der Argumente ist nicht bestimmt - es ist ein generischer Datentyp.
    Platzhalter für den unbestimmten Argument-Datentyp ist zunächstmal T.
    Also man spricht nicht von einer Action(Of , sondern es ist eine Action(Of T) (und T ist unbestimmt, ein TypParameter).
    T wird erst bestimmt, wenn ich eine Variable damit deklariere:

    VB.NET-Quellcode

    1. Dim recurse As Action(Of Integer)
    Hier ist das Argument bestimmt, nämlich sein Datentyp ist Integer.
    Also recurse ist eine Variable, wo man eine Methode reintun kann, die ein Integer-Argument erwartet.
    Jo, und das mache ich denn ja auch gleich:

    VB.NET-Quellcode

    1. Dim recurse As Action(Of Integer) = Sub(index)
    2. End Sub
    Der Compiler ist schlau genug, zu erkennen, dass das Argument index nur Integer sein kann - weil so ist die Action ja deklariert.
    Die Methode, die ich da zuweise ist eine Anonyme Methode - eines der "neueren" Features von vb.net - gibts glaub seit 2010.
    Das sind eben Methoden ohne Namen - man kann sie überall hinschreiben und an eine Variable zuweisen, oder sie als Argument einer anderen Methode übergeben. (Die Variable hat einen Namen, die Methode aber nicht. Ein spitzfindiger Unterschied - man ruft also nicht die Methode auf, sondern die Variable, wo die Methode drinne ist.)
    Jo, mehr erklär ich erstmal nicht, weil sonst wird schnell ein Buch draus.
    Stichworte sind genannt:
    • Delegat
    • Generica, TypParameter
    • anonyme Methode
    • Rekursion
    und da musste dich dann selbst nochmal schlau machen, aus Buch oder aus Internet.

    Zu Delegat und Generica habich einiges auch hier fallenlassen: Alles über Events
    Da gehts aber um Events - auch total wichtig, und baut auch vollkommen auf dem Delegat-Konzept auf - in einem Exkurs kommen die generischen Delegaten vor.

    Achso, wenn du den Objectbrowser nicht kennst, solltest du ihn spätestens jetzt kennenlernen: VisualStudio richtig nutzen (Google ist nicht deine Mami)

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

Facebook
Telefonspende