Code Kata - Happy Numbers

  • Hi Leute,

    hier mal was fĂŒr zwischendurch, die "Happy Numbers" Code Kata.

    💡 Ziel: Ist es einen Algorithmus, bestehend aus einer oder mehreren Funktionen zu schreiben, womit erkannt wird ob eine gegebene Zahl "happy" ist oder nicht 😁 .

    • Ein "glĂŒckliche" Zahl ist eine Zahl, bei der die Summe der Quadrate ihrer Ziffern auf die Dauer 1 ergibt.
    • Beispiel fĂŒr Zahl 19: 19 -> 1^2 + 9^2 = 82 -> 8^2 + 2^2 = 68 -> 6^2 + 8^2 = 100 -> 1^2 + 0^2 + 0^2 = 1

    đŸ„ˆ Teil 1: Entwickle die Funktion(en) und lass dir 19 -> 1 :) mit ConsoleWrite() bspw. ausgeben.
    đŸ„‡ Teil 2: Lass dir alle "happy numbers" im Bereich von 1 bis 100 ausgeben (analog wie bei Teil 1).


    ⚡ Rahmenbedingungen:

    • Versuche es möglichst komplett ohne Hilfsmittel und ohne Google Suche.
    • Zeitliche Vorstellung fĂŒr diese kleine Challenge ist um die 30 min.
    • Wenn du eine Lösung hast und diese hier postest, dann bitte den Code in Spoiler einbinden, damit jeder selbst entscheiden kann ob er die Lösungsvariante der Anderen sehen möchte oder nicht 😉 .

    Ich bin gespannt auf eure Lösungen und wĂŒnsche happy coding 👍 .

    Viele GrĂŒĂŸe

    Sven

  • Mal was anderes...


    Hier mein Lösungsvorschlag:

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

    Einmal editiert, zuletzt von UEZ () aus folgendem Grund: Kleine Optimierung.

  • Das hat mich grad auch gecatcht. ^^


  • Hi zusammen,

    Xorianator ja das ist eine ganze Weile her 😅 , bei mir lĂ€nger als bei dir wenn deine Geburtsangabe stimmt. Jedoch wurde damals auf "agile" oder "clean code" nur wenig eingegangen.
    Egal [...], ich denke du kommst sicherlich noch mit deinem Lösungsvorschlag "um die Ecke" oder đŸ€ž ?

    UEZ Korrekt 👍 , kurz und Ă€h, kurz 😂 .

    chesstiger Korrekt 👍 , ebenfalls kurz und doch ein wenig anders.

    Hier mal mein Lösungsansatz:



    Viele GrĂŒĂŸe
    Sven

  • Hi, ich schreibe nicht mehr viel in AutoIt. Daher ist meine ursprĂŒngliche Lösung in Lua. Ich habe jedoch den Code nach AutoIt ĂŒbersetzt nachdem ich fertig war.


    Lua 5.4 Skript: Alle "Happy Numbers" von 1 bis 10'000'000 in ca. 8 Sekunden in eine Text Datei.

    AutoIt Skript: Alle "Happy Numbers" von 1 bis 100'000 in ca. 8 Sekunden in die Konsole.


    chesstiger

  • Hi Yjuq ,

    auch dein Lösungsvorschlag liefert das korrekte Ergebnis 👍 .

    • Sowohl bei Zahlen von 1 bis 100, aber auch bei 1 bis 10000 bspw. => dies gilt fĂŒr alle bisherigen Lösungen 😀 .
    • Bisher ist deine Variante auch die schnellste bei bspw. 10000 in meinem Test.
    • Eine Optimierung wĂŒrde jedoch in einem Folgeschritt folgen, daher nicht relevant fĂŒr die Aufgabenstellung.

    Danke fĂŒr's Mitmachen.

    Viele GrĂŒĂŸe
    Sven

  • Eine Optimierung wĂŒrde jedoch in einem Folgeschritt folgen, daher nicht relevant fĂŒr die Aufgabenstellung.

    Falls du daran denkst ggf. bereits gefundene Zahlen zwischenzuspeichern um den Rechenaufwand zu minimieren -> Das klappt nicht. Es stellt sich heraus (zumindest was ich dazu versucht hatte) dass dies langsamer ist und zusÀtzlich Speicher im RAM benötigt. Zumindest mit den LösungsansÀtzen welche ich versucht hatte. Es ist schneller die Zahlen einfach neu zu berechnen.

  • Hi Yjuq ,

    Falls du daran denkst ggf. bereits gefundene Zahlen zwischenzuspeichern um den Rechenaufwand zu minimieren -> Das klappt nicht. [...]

    Okay, spannend das du bereits einige Tests gemacht hast 👍 . In erster Linie geht es um die Aufgabenstellung nicht um Performanz oder Ă€hnliches - dennoch gut zu wissen, Danke.

    Viele GrĂŒĂŸe

    Sven

  • Das Makes Variante schneller ist, war zu erwarten. GrundsĂ€tzlich lassen sich rekursive Algorithmen immer sehr schön schreiben und lesen... Aber in der AusfĂŒhrung sind fast immer iterative Verfahren ĂŒberlegen. Dazu ist der Overhead bei rekursiven Funktionsaufrufen zu groß.

  • Und RegEx ist langsamer als die StringSplit Funktion.


    Benchmark nach der Reihenfolge der BeitrÀge:

    Rekursionen sind i.d.R. einfacher zu implementieren -> kĂŒrzerer Code, aber langsamer.

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

  • Da so wenige mitmachen, trage ich halt auch mal was dazu bei. Da die Aufgabenstellung war "von 1 bis 100" kann meine Version auch nur eine begrenzte Anzahl machen (nur bis 3-stellig, also max. 999)

  • Könnte hinhauen


  • Hi zusammen,


    zunÀchst muss ich sagen, dass ich noch nie von diesen "Happy Numbers" gehört hatte^^

    Daher bin ich mal völlig unvoreingenommen an diese ganze Sache herangegangen.

    Wie einige von euch sicherlich wissen, schwĂ€rme ich fĂŒr die "brotlose Kunst" aka Grafikspielereien und oldschool Assemblerprogrammierung, und so war mein Ziel, die Daten der "Happy Numbers" als Bitmap darzustellen.

    OT Das habe ich mir ĂŒbrigens bei diversen "Hackings" von unbekannten Daten angewöhnt, da findet man die interessantesten Sachen. Wer darĂŒber mehr erfahren will, bitte per PN.

    Diese Bitmap wÀre dann nichts weiter als eine LUT (LookUpTabelle), die Frage ob eine Zahl im Wertebereich Happy oder Unhappy ist beschrÀnkt sich dann nur noch auf eine Abfrage des Pixels an dieser Adresse.....


    Also sollte eine Bitmap erstellt werden, in der jede Happy Number ein gesetztes Pixel ist. Fehlte nur noch der Algorithmus^^

    Der "offensichtliche" Weg fĂŒr mich war, die Zahlen von 1 bis 9 hinzuschreiben und dann die "Folge" nach Vorschrift zu erstellen, die dann hoffentlich zur 1 (Zahl ist Happy) fĂŒhrt.....oder eben nicht (Zahl ist Unhappy).

    Dabei hatte ich festgestellt, dass die "Zwischensummen" (der Quadrate der Ziffern) unweigerlich ebenfalls Happy bzw. Unhappy sind, da sie ja in direkter Folge auf Happy bzw. Unhappy hinauslaufen.

    Man muss also wĂ€hrend der Ermittlung der Folge nur die aktuell ermittelte Quadratsumme auf Happy bzw. Unhappy ĂŒberprĂŒfen, um diese "Folge" frĂŒhzeitig abbrechen zu können.

    Bei Beispielsweise der 6 ergeben sich die Quadratsummen 36, 45, 41, 17, 50 ..... !!!BÄM!!!

    50 wird in der Folge zu nichts anderem als 5ÂČ+0ÂČ aufgelöst. 5 ist aber bereits Unhappy, daraus folgt, dass 6 auch Unhappy sein muss. Desweitern sind 36, 45, 41, 17 auch Unhappy.

    Ist eine Zahl Happy, dann sind definitiv sÀmtliche Quadratsummen auf dem Weg zur 1 auch Happy!

    Dann kam ich auf die Idee, diese Quadratsummen in ein Array einzutragen (aka Bitmap^^) und entsprechend zu markieren.

    Jede Zahl, die als Happy ermittelt wurde, wird im Array als 1 markiert ($array[happyzahl]=1), jede Unhappy Zahl als ihren Wert ($array[unhappyzahl]=unhappyzahl)

    Ich stellte fest, dass die maximale GrĂ¶ĂŸe einer einzelnen Quadratsumme höchstens die Summe aus der Anzahl der Ziffern multipliziert mit dem Quadrat der grĂ¶ĂŸten Ziffer, also 9, sein kann.

    Bsp. Eine Zahl hat 14 Ziffern, die grĂ¶ĂŸte Ziffer ist 9, das zum Quadrat ist 81, das mal 14 ergibt 1134.

    Man braucht also "nur" beim Test einer 14-stelligen Ziffer ein Array mit 1134 Feldern....

    Innerhalb dieses Arrays mĂŒssen nur noch die Indizes mit 1 fĂŒr Happy und mit Zahl fĂŒr Unhappy gesetzt werden (s.o) und tadaaa, im Algorithmus wird bei Zahlen von 1135 bis 99999999999999 nur noch EINE EINZIGE QUADRATSUMME (die immer kleiner ist als 1134) gebildet, aus der man dann ermittelt, ob diese Zahl dann Happy oder Unhappy ist!

    Ich hatte dafĂŒr eine rekursive Funktion _IsHappy() geschrieben, im Endeffekt bedeutet das, dass spĂ€testens ab der Zahl 1135 die Rekursion im ersten Schritt verlassen wird! Und das IMMER, egal wie groß die Zahl wird, es wird immer nur die Berechnung der ersten Quadratsummenzahl benötigt um per Lookup im Array sofort auf Happy bzw. Unhappy zu kommen....



    Und dann wurde es spannend!!!

    Ich erstellte eine Bitmap von 1000x1000 Pixeln (jaja, ermittelt wurden die Happy Numbers von 1 bis eine Million) und markierte nur die ermittelten Happy Numbers mit einem farbigen "rosa" Pixel.

    AutoIt-typisch erfolgte die "Berechnung" recht langsam, aber immerhin etliche Faktoren schneller als mit der von (bisher schnellsten _IsHappyNumber()-Funktion vom geschÀtzten Kollegen Yjuq!

    Mir fielen sofort "Muster" im Bild auf! OHA! Seht ihr auch diese "Fensterkreuze"?


    Als ich dann die obere linke Ecke stark vergrĂ¶ĂŸerte, wunderte ich mich noch mehr!



    FĂ€llt euch auch auf, dass die Happy Pixel an der Diagonale von oben links nach unten rechts gespiegelt sind!?

    Was nichts anderes bedeutet, als dass NUR BEI DER HÄLFTE der Zahlen ĂŒberhaupt der Status "Happy" ermittelt werden muss....

    Beispiel: In der obersten Pixelzeile sieht man von links die "Happy Pixel" 1, 7,10,13 usw. (in der Bitmap ist das erste Pixel an Adresse 0!)

    Das bedeutet, in der linken Pixelspalte von oben ist ebenfalls das 1te, 7te,10te,13te usw. Pixel gesetzt.

    Wenn also an den Koordinaten (x,y) ein Happy Pixel ist, dann auch das an der Koordinate (y,x).


    Anbei mein unoptimiertes und auf die schnelle hingehacktes Script zur Ermittlung der "Happy Numbers" incl. Erstellung der 1000x1000 Bitmap...ich werde mich morgen mal an die Beschleunigung machen...

    Im abschließenden Arraydisplay wird das Array angezeigt, welches zur Ermittlung der Happy Numbers erstellt wurde.

    Ist der Feldinhalt 1, dann ist die Indexzahl Happy, ansonsten der Feldinhalt (Indexzahl ist Unhappy)


    Nach schließen des Arraydisplay kann man mit der Maus in der Grafik die Positionen der Pixel anfahren und im Tooltip die dort "gespeicherte" Zahl ermittelt aus den Koordinaten erfahren, der Farbwert des Pixels bestimmt dann, ob die Zahl Happy (Pixelfarbe hat nicht Hintergrundfarbe) oder Unhappy ist (Pixelfarbe hat Hintergrundfarbe)



    //EDIT

    Script aktualisiert, es wird nun zuerst das Sieb mit den Happy/Unhappy Zahlen gefĂŒllt, danach muss fĂŒr jede Zahl nur noch die Quadratsumme ermittelt werden, die der Index fĂŒr das Sieb ist.

  • Coole Analyse Andy ! Die Tatsache der Spiegelung ist definitiv ein Booster bezgl. Performance (keine Impfung :P ). Mir kam intuitiv die Rekursion als Lösung in den Kopf, aber das Ganze grafisch darzustellen, war mit nicht eingefallen.

    Auch am Arsch geht ein Weg vorbei...

    ¯\_(ツ)_/¯

  • Andy : Wirklich eine coole Analyse :thumbup: . Danke zudem, dass Du die Herleitung so ausfĂŒhrlich beschrieben hast.

    86598-musashi-c64-png

    "Am Anfang wurde das Universum erschaffen. Das machte viele Leute sehr wĂŒtend und wurde allenthalben als Schritt in die falsche Richtung angesehen."

  • Hehe....die "Aufgabe" hat mich an die ”-It hier im Forum erinnert....das ist bestimmt schon 10 Jahre her, oder?!

    So etwas sollte/könnte man wieder mal aufleben lassen.


    BTT:

    Die Tatsache der Spiegelung ist definitiv ein Booster bezgl. Performance

    Ja, mich hat gewundert, dass das noch keiner gemacht hatte, ich habe jedenfalls keine Info darĂŒber gefunden. Daten "grafisch" zu analysieren ist ein uralter Hut, "frĂŒher" hatte ich bei Analysen von fremden Programmen einfach die gesamte (*-EXE-) Datei in eine Bitmap gemapped (omg, was ein Wortspiel^^) und diese Bitmap per Programm in diversen Pixelbreiten anzeigen lassen. Da hat man dann feine Sachen gefunden, ZeichensĂ€tze, eingebundene Bilder uvm.

    Im vorliegenden Fall war ich aber echt ĂŒberrascht, diese Muster zu finden...naja, wenn man mal bissl nachdenkt, dann ist ja auch klar wo die herkommen. 8)


    Die Idee mit dem "kleinen" Array habe ich mir bei einem eigenen Script, dem erweiterten Primzahlensieb (auch ein ”-It gewesen) abgeschaut, mit LUT geht vieles viel schneller und trotz meines biblischen Alters und fortschreitendem Gehirnschwund fallen mir doch noch so manche Tricks ein :rock:


    Jedenfalls hats Spass gemacht! Danke auch dafĂŒr an @SOLVE-SMART!

    Ich habe das zum Anlass genommen, wieder mehr mit AutoIt zu machen, hab noch soooo viele Sachen offen, OpenCL und OpenCV, und nicht zuletzt Assembler, habe letzte Woche Kontakt mit Jungs und MĂ€dels aus JĂŒlich gehabt, das ist da wo die RICHTIG DICKEN KISTEN stehen=O und die werden auch mit auf der letzten Rille optimierten Programmen gefĂŒttert, ggf. werde ich mir da mal den letzten Schliff holen. Die frei verfĂŒgbaren Unterlagen dort sichern mir schon die WochenendlektĂŒre fĂŒrs ganze Jahr^^

    Wen es interessiert https://www.fz-juelich.de/Shar
6/2016-04-jurecapt16.html


    Forschungszentrum JĂŒlich - JSC - Presentations in courses and talks - Slides of the Seminar on Modular Supercomputing Architectures (MSA)

    uvm....

  • Hi Leute,

    BananaJoe und Lambdax auch eure LösungsvorschlĂ€ge liefern das korrekte Ergebnis 👍 . Danke fĂŒr die weiteren Varianten und an sich fĂŒr's Mitmachen.

    Da die Aufgabenstellung war "von 1 bis 100" kann meine Version auch nur eine begrenzte Anzahl machen (nur bis 3-stellig, also max. 999)

    Ich finde es gut, dass du die Problemstellung zunĂ€chst so angegangen bist, wie die Aufgabe es verlangte 😀 , auch wenn ein Umbau nötig ist um mit den anderen Versionen mitzuhalten - dennoch sehr "Agile", nice 👍 .


    Nun zu dir Andy :

    • Deine Bezeichnugn "MĂ€rchenonkel" klingt super, wird dir aber nicht gerecht - du bist mehr 😁 .
    • Im ersten Augenblick war ich sprachlos wie viel KreativitĂ€t, Energie und Erfahrung in dir und in den Anderen hier stecken => #wow! #ErfĂŒrchtigSchauend 😇 .
    • Nachdem ich deinen Beitrag ein zweites Mal gelesen hatte war ich noch ĂŒberraschter, denn dein Ansatz/die Umsetzung war absolut verstĂ€ndlich und nachvollziehbar erlĂ€utert #HutAb!

    Die Idee mit dem "kleinen" Array habe ich mir bei einem eigenen Script, dem erweiterten Primzahlensieb (auch ein ”-It gewesen) abgeschaut, mit LUT geht vieles viel schneller und trotz meines biblischen Alters und fortschreitendem Gehirnschwund fallen mir doch noch so manche Tricks ein [...]

    Was soll man dazu sagen? Einfach Danke, konnte herzhaft darĂŒber lachen 😂 👍 .


    Jedenfalls hats Spass gemacht! Danke auch dafĂŒr an SOLVE-SMART!

    Ich habe das zum Anlass genommen, wieder mehr mit AutoIt zu machen [...]

    Bitteschön, das freut mich ehrlich ganz besonders!


    Viele GrĂŒĂŸe

    Sven

  • Hi zusammen....


    so ist das mit den BeweihrÀucherungen....taugt alles nix^^

    Ich hatte im vorgestellten Script beim "Verschönern" irrtĂŒmlich 3 Zeilen gelöscht....was das Script in seiner LauffĂ€higkeit zwar nicht beeinflusste, aber die Idee dahinter völlig gegen die Wand fuhr!


    Die fehlenden Zeilen waren genau die Schleife, welche die in der Rekursion gefundenen NICHT HAPPY - Zahlen in das Array eintragen.....

    AutoIt
            Else                             ;keine happynumber gefunden
                If $i < $maxarray Then
                    $sieb[$i] = $i           ;dann Zahl als zahl im index ins sieb eintragen
                    For $z = 1 To $maxrecurs ;alle in den rekursionen gefundene zahlen merken
                        $sieb[$temp[$z]] = $temp[$z] ;diese Zahl ist nicht auch nicht happy weil fĂŒhrt in der Folge nicht zu 1
                    Next
                EndIf
            EndIf

    Ich hab das jetzt im Post ergÀnzt, wenn man das _Arraydisplay() einkommentiert , sieht man den Unterschied zu vorher...shame on me...aber an euch noch mehr weil es keiner gemerkt hat :rofl:


    //EDIT

    Da es sinnvoll ist, erst das Sieb zu fĂŒllen und danach erst die Grafik zu erstellen habe ich mich entschlossen, das Script im Post #14 upzugraden.

    Was zur annĂ€hernden Verdopplung der Geschwindigkeit gefĂŒhrt hat....

  • Ich hab das jetzt im Post ergĂ€nzt, wenn man das _Arraydisplay() einkommentiert , sieht man den Unterschied zu vorher...shame on me...aber an euch noch mehr weil es keiner gemerkt hat :rofl:

    Wir waren wohl alle noch zu sehr vor Ehrfurcht erstarrt :P .

    86598-musashi-c64-png

    "Am Anfang wurde das Universum erschaffen. Das machte viele Leute sehr wĂŒtend und wurde allenthalben als Schritt in die falsche Richtung angesehen."