Coding-Herbst: Die coding-board.de coding challenge

-AB-

Well-Known Member
c-b Team
c-b Experte
#42
Hm, mal sehen.
Bringt nichts, ein Sudoku zu bewerten, was bei allen in einem Sekundenbruchteil durchrauscht.
Auch nix, wenn es bei allen zu lang dauert.

Da jeder vermutlich einen anderen Lösungsansatz hat, ist es für mich nicht so einfach, abzusehen welche Sudokus wohl irgendwo im Mittelfeld liegen. Werde denke ich mal so oder so viele durchlaufen lassen, einen Chart erstellen, und einige rausnehmen, bis wir vernünftige Daten haben.

Also: Schwer zu sagen. ;) Solche und solche.
 

Jan Krüger

Well-Known Member
c-b Team
c-b Experte
#48
Na gut, ich hab auch mal eine Implementierung gemacht.
[Edit: Beispiele entfernt, will ja nicht zu sehr spoilern]

Für das "schwerste" Beispiel aus diesem Thread (sudoku_05.txt von @-AB-) braucht mein Programm in meiner Testumgebung ca. 0,4 Sekunden; wenn ich meine Rekursionsoptimierung ausschalte, braucht es etwa doppelt so lange.
 
Zuletzt bearbeitet:

German

Well-Known Member
c-b Experte
#49
Klingt sehr gut :)
[Edit: Beispiele entfernt, will ja nicht zu sehr spoilern]
Hatte es schon gelesen ;) Damit schießt du schon ein gutes Stück über's Ziel hinaus. Möglicherweise kannst du die 0,4 noch optimieren wenn du abbrichst, sobald du herausgefunden hast dass es mehr als eine Lösung gibt. (EDIT: Ach nee, für das Beispiel gibt's ja nur eine ...)

@-AB- Have fun!
 

Jan Krüger

Well-Known Member
c-b Team
c-b Experte
#50
Ich hab den Optimierer übrigens mal testweise so umgebaut, dass ich die extrem lange Laufzeit reproduzieren kann. An dem sudoku_05.txt knabbert es jetzt schon mehr als eine Stunde...

(Update: 4h sind rum und es hat immer noch keine Lösung)
 
Zuletzt bearbeitet:

JR Cologne

Well-Known Member
c-b Experte
#51
Hm... :confused:

Hatte ursprünglich mit einer Java-Implementierung begonnen. Lief im Grunde erstmal ganz gut. Irgendwann habe ich dann allerdings festgestellt, dass es vielleicht einfacher wäre, auf Node.js zu setzen, schließlich fühle ich mich im Web-Umfeld letztendlich doch ein wenig wohler und des Weiteren hatte ich eh einen Fehler drin, den ich nicht so richtig gefunden habe.

Habe dann also angefangen, den ganzen Code nach JS zu übersetzen und gleichzeitig gewisse Optimierungen vorzunehmen. Ging halbwegs schnell und ich habe zumindest dadurch dann auch den Fehler entdeckt, weswegen das Java-Programm nicht richtig lief. So konnte ich gestern das Programm bisschen rödeln lassen, zu einem korrekten Ergebnis kam es aber nicht.

Also wieder paar Dinge geändert... Ergebnis: Ich stecke fest, weil die Rekursion anscheinend nicht richtig funktioniert und Node immer RangeError: Maximum call stack size exceeded ausspuckt...

Update:

Habe mich jetzt zumindest vorübergehend erstmal für einen Workaround entschieden. Nutze schlicht und ergreifend keine Rekursion. Dann funktioniert es auch. :D
 
Zuletzt bearbeitet:

Alan001

Well-Known Member
#57
Ich habe es geschafft! Wow, mein erstes Projekt. Ich bin echt froh und auch stolz.
Kurze Frage zu der Zeit: Setzt du den Timer vor die Methode und stoppst danach, oder wie kann ich mir das vorstellen? Ich habe bspw. einige prints etc. drinnen, die es übersichtlicher machen, aber wohl auch verlangsamen. Kenne mich da nicht sehr gut aus.

Ok, die 5 scheint er nicht lösen zu können. Die 1 aber in 85 Millisekunden. Kann mir jemand sagen, wie lange das erste bei euch braucht, nur um einen Richtwert zu haben?
 
Zuletzt bearbeitet:

-AB-

Well-Known Member
c-b Team
c-b Experte
#58
Hatte vor, den kompletten Programmaufruf zu messen. Aber wenn ihr mit Millisekunden ankommt, müssen wir vllt noch was ändern.

Ach, die 5 klappt bei dir auch nicht, dann bin ich ja wenigstens nicht allein... Vllt machen wir beide das gleiche falsch?
 

Jan Krüger

Well-Known Member
c-b Team
c-b Experte
#59
Nummer 1 braucht bei mir im Schnitt 30 Millisekunden... aber bei so kurzlebigen Programmen macht es kaum Sinn, die Ausführungsdauer zu vergleichen, da geht mutmaßlich das meiste für das Laden und Initialisieren des Binaries drauf.

PS. Nummer 1 lässt sich mit den allersimpelsten Strategien und ohne Ausprobieren lösen... Nummer 5 nicht. Ich hab die Nummer 5 an mehreren automatischen Lösungsprogrammen ausprobiert und keins davon war in der Lage, es ohne (potenzielles) Backtracking zu lösen.
 
Oben