Codility-Training: Finden Sie die maximale Anzahl von Uhren mit Händen, die beim Drehen identisch aussehen

Meine Antwort ähnelt der von TonyWilk, aber wie das OP habe ich alle Uhren gedreht, um eine kanonische Position zu finden, die mit anderen verglichen werden kann.

Die kanonische Position ist diejenige, bei der die Summe aller Handpositionen minimal ist (d. h. alle Hände sind so nahe wie möglich bei 1).

Ich habe ziemlich viel Zeit damit verbracht, eine numerische Funktion zu finden, mit der ich eine eindeutige Signatur basierend auf den Werten für die Handposition generieren kann.

Obwohl dies mathematisch möglich ist (indem eine steigende Funktion verwendet wird, die eine dichte Menge für Ganzzahlen definiert), ist die Rechenzeit und / oder die Fließkommazahl immer im Weg.

Ich kehrte zu einer einfachen Array-Sortierung zurück und verbinde mich, um eine einzigartige Taktsignatur zu erzeugen.
Das brachte mich zu 95% mit einer Zeitüberschreitung ( siehe die Ergebnisse ).

Ich habe dann noch ein bisschen Zeit damit verbracht, das letzte Timeout zu optimieren bis mir etwas Seltsames aufgefallen ist:
dieses Ergebnis erzielte nur 85% mit 2 Timeouts, aber wenn du dir die Zeitangaben ansiehst, ist es schneller schneller als das, was ich bei meinem vorherigen 95% Score notiert habe.

Ich vermute, dass die Timings in diesem Fall ein bisschen wackelig sind, oder vielleicht werden sie irgendwie basierend auf der erwarteten Reihenfolge des Algorithmus angepasst Streng genommen ist meins in o (N * M ² ) wegen der Signaturberechnung, obwohl du Uhren mit vielen tausend Händen brauchst, um es zu bemerken.
Mit einer Anzahl von Händen, die in den Speicher passen können, ist die Array-Sortierung dominant und die praktische Reihenfolge ist o (N * M * log 2 <2 (M))

Hier ist die letzte Version, mit einem Versuch, die Paarzählung zu optimieren, die den Code weniger lesbar macht:

Im Grunde genommen hat die gleiche Lösung in Plain C mir eine 90% Punktzahl :

Ich finde das Timing-Kriterium ein bisschen hart, da diese Lösung keinen zusätzlichen Speicher verbraucht (sie verwendet die Uhren selbst als Signatur).
Sie könnten schneller gehen, indem Sie eine sortierte Einfügung manuell in einem dedizierten Signatur-Array durchführen, aber das würde N * M temporäre Ganzzahlen verbrauchen und den Code ziemlich aufblähen.

Ich denke, die Schwierigkeit in der Frage dreht sich um das Wort "Uhr", was mich dazu brachte, viel zu lange an zwei Hände zu denken:)

Die Ähnlichkeit zwischen "Uhren" sieht so aus, als könnte sie durch die Reihenfolge der Trennung der "Hände" gegeben sein; im Beispiel der Frage sind die Unterschiede 1,2,1,1,2. Die Hauptproblembereiche werden jedoch durch diesen sehr einfachen Fall gut vermieden ...

Einwickeln: z.B. bei einer normalen Zeituhr sind die Hände bei 4,6 und 11,1 beide eine Entfernung von 2;

Mehrere Hände: z.B. eine 4-Zeiger-Uhr mit 8 Punkten kann Hände bei 1,2,5,6 und 1,4,5,8 haben gibt Trennungen von 1,3,1 oder 3,1,3, aber diese sind rotatorisch identisch!

Wenn Sie an Uhren mit einer großen Anzahl von Händen denken, können Sie sich vorstellen, dass Sequenzen von Trennungen zwischen den Händen nicht einfach abgeglichen oder sortiert werden können.

Also, wir messen alle Zwischenräume zwischen den Händen - das obige 4-Zeiger-Beispiel wäre 1,3,1,3 und 3,1,3,1 (dazu füge ich einfach das erste Element am Ende hinzu das Array) und versuchen Sie dann, das mit vorherigen Mustern zu vergleichen. Wir behalten nur einzigartige Muster zusammen mit einer Zählung für jeden von ihnen.

Der Mustervergleich versucht, die Arrays zu vergleichen, dreht dann das Array um ein Element und versucht es erneut (was viel Zeit kostet!)

Am Ende summieren wir einfach die Kombinationen für jede Zählung.

Der aktuelle Code erhält eine Punktzahl von 90, die aufgrund von Timeout nur bei einigen Tests fehlschlägt. Ich bin sicher, dass jemand mit einem besseren Verständnis von Javascript ein paar 100 Millisekunden davon rasieren könnte.

Hier ist die Ausgabe: Ссылка

und hier ist der Code:

Ich habe herausgefunden, was das Problem ist. Es ist in der Funktion rotate .

Ich nahm an, dass durch Drehen der Liste der Abstände zwischen den Taktsignalen, bis der Listenkopf das minimale Element ist, identische Handpositionen in die gleiche Liste übertragen werden, aber das ist nicht der Fall.

Wenn in einer Handdistanzliste mehrere Mindestelemente vorhanden sind, kann die Rotationsfunktion zu unterschiedlichen Listen für identische Handpositionen führen.

Beispiel: [4, 1, 3, 2, 1] und [2, 1, 4, 1, 3] sind identisch, weil sie ineinander gedreht werden können, aber rotate führt zu [1, 3 , 2, 1, 4] für die erste und [1, 4, 1, 3, 2] für die zweite.