So wie ich es verstehe:
Hier ist ein Bild:
........... ........... ...X....... ........... .....Y..... <---1N from top X, 2N from bottom X ........... .......Y... <---2N from top X, 1N from bottom X ........... .........X. ...........
Es ist optisch klar.
Wie könnte ich es algorithmisch ermitteln?
Hier ist das Beispielraster:
............ ........0... .....0...... .......0.... ....0....... ......A..... ............ ............ ........A... .........A.. ............ ............
Ich werde mich auf die Nullen konzentrieren:
Vergleich der ersten beiden:
1,8 vs. 2,5 1 row apart 3 col apart 2 possible antinodes: 0,11: 0 = min(1,2) - 1 3,2 For 0,11 0 = min(1,2) - 1 11 = ....
Mir wurde beim Schreiben klar, dass ich wirklich die Steigung der Linie kennen muss, die das Punktepaar verbindet.
Auf diese Weise kann ich wissen, ob ich von jeder Achse addieren oder subtrahieren muss, um zu bestimmen, wo sich der Gegenknoten befindet.
Die Formel lautet:
(y2 - y1) / (x2 - x1)
Das Ergebnis wird eines dieser vier sein:
Zurück zum Beispiel:
1,8 and 2,5 (5 - 8) / (2 - 1) = -3 / 1 = -3
Was? Eine negative Steigung? Nein, diese Linie hat eine positive Steigung!
Oh...ich verstehe.
Array-Indizierung zählt hoch, bewegt sich aber optisch nach unten.
Ich muss Indizes umgekehrt zählen.
Statt so:
0 ............ 1 ........0... 2 .....0...... 3 .......0.... 4 ....0....... 5 ......A..... 6 ............ 7 ............ 8 ........A... 9 .........A.. ............ ............ 0123456789
Ich muss so zählen:
............ ........0... 9 .....0...... 8 .......0.... 7 ....0....... 6 ......A..... 5 ............ 4 ............ 3 ........A... 2 .........A.. 1 ............ 0 ............ 0123456789
Es sollte nur etwas mehr Mathematik erfordern:
array length - current row/col index
Ich werde es versuchen.
Für die oberste 0:
12 rows Row index: 1 12 - 1 = 11 Column index: 8 Coordinates: 8,11
Für die 0 in der nächsten Zeile:
Row index: 2 12 - 2 = 10 Column index: 5 Coordinates: 5,10
Und die Steigung:
(10 - 11) / (5 - 8)
-1 / -3
1/3
Eine positive Steigung! Das ist richtig!
Ein leeres Objekt, das mit einer verschachtelten for-Schleife gefüllt ist:
let graph = input.split('\n').map(el => el.split(''))
let antennas = {}
for (let y = 0; y < graph.length; y++) {
for (let x = 0; x < graph[0].length; x++) {
if (graph[y][x] !== '.') {
if (!(graph[y][x] in antennas)) {
antennas[graph[y][x]] = []
}
antennas[graph[y][x]].push([graph.length - y,x])
}
}
}
<p>Erstellt dieses Objekt für die Beispieleingabe:<br>
</p>
<pre class="brush:php;toolbar:false">{
'0': [ [ 11, 8 ], [ 10, 5 ], [ 9, 7 ], [ 8, 4 ] ],
A: [ [ 7, 6 ], [ 4, 8 ], [ 3, 9 ] ]
}
Sieht toll aus!
Als nächstes berechnen wir die Steigung.
Meine Scope-Funktion ist einfach:
function getScope(p1,p2) {
return (p2[0] - p1[0]) / (p2[1] - p1[1])
}
Es erwartet zwei Arrays und gibt den Bereich unter Verwendung aller vier Koordinaten zurück.
Ich möchte diese Funktion aufrufen, wenn ich alle Paare von Koordinaten ähnlicher Häufigkeit vergleiche.
Dieser Vergleich erfolgt in dieser superverschachtelten for-Schleife:
for (let freq in antennas) {
let f = antennas[freq]
for (let i = 0; i < f.length; i++) {
for (let j = i + 1; j < f.length; j++) {
// Comparing two antennas of the same frequency
}
}
}
Bestätigen, dass es mit der Beispieleingabe funktioniert:
[ 11, 8 ] [ 10, 5 ] [ 11, 8 ] [ 9, 7 ] [ 11, 8 ] [ 8, 4 ] [ 10, 5 ] [ 9, 7 ] [ 10, 5 ] [ 8, 4 ] [ 9, 7 ] [ 8, 4 ] [ 7, 6 ] [ 4, 8 ] [ 7, 6 ] [ 3, 9 ] [ 4, 8 ] [ 3, 9 ]
Neun Vergleiche. Das stimmt!
Und die Bereiche für jeden?
Die sehen zum Glück auch richtig aus.
Jetzt zum übermäßig komplizierten Teil, denke ich.
Sie sind:
........... ........... ...X....... ........... .....Y..... <---1N from top X, 2N from bottom X ........... .......Y... <---2N from top X, 1N from bottom X ........... .........X. ...........
Lass uns das in den Griff bekommen.
Es ist viel, aber die Feinheiten in jedem Abschnitt sind wichtig:
............ ........0... .....0...... .......0.... ....0....... ......A..... ............ ............ ........A... .........A.. ............ ............
Zum Glück scheinen alle identifizierten Bäuche korrekt platziert zu sein.
Als nächstes werden diejenigen ausgeschlossen, die außerhalb der Grenzen liegen
Geben Sie...weitere Bedingungen ein!
1,8 vs. 2,5 1 row apart 3 col apart 2 possible antinodes: 0,11: 0 = min(1,2) - 1 3,2 For 0,11 0 = min(1,2) - 1 11 = ....
Ich überprüfe, ob jede Koordinate zwischen 0 und der Länge der Zeilen oder Spalten liegt.
Dann rufe ich am Ende jeder Klausel in meinem Antinode-Finder die Funktion auf beiden möglichen Knoten auf:
(y2 - y1) / (x2 - x1)
Und meine Antwort wird die Größe meines gültigen Satzes sein.
Beim Ausführen werden 12 generiert. Nicht 14.
Warum nicht?
...
Nach einigem Debuggen habe ich meinen Fehler gefunden:
1,8 and 2,5 (5 - 8) / (2 - 1) = -3 / 1 = -3
Ich liege in meiner Reihenaufgabe um eins daneben. Ich brauche einen Wert, der eins weniger ist:
0 ............ 1 ........0... 2 .....0...... 3 .......0.... 4 ....0....... 5 ......A..... 6 ............ 7 ............ 8 ........A... 9 .........A.. ............ ............ 0123456789
Das behebt die Dinge.
Ich sehe jetzt 14.
Zeit, es auf meiner Puzzle-Eingabe auszuführen.
...
Richtige Antwort!!!
Das hat viel länger gedauert, als ich erwartet hatte, aber ich habe es geschafft!
Ich kann mir nur vorstellen, was Teil 2 erfordern wird.
Schluck.
Das fühlt sich schwieriger an, obwohl es möglicherweise eine relativ einfache Anpassung ist.
Zeit, darüber nachzudenken.
...
Hauptsächlich wegen diesem Problem:
genau auf einer Linie mit mindestens zwei Antennen der gleichen Frequenz
Ich glaubeich verstehe diese Kriterien.
Meine Vermutung ist, dass alle drei Antennen auch Schwingungsbäuche sind, solange es drei einer bestimmten Frequenz gibt.
Wenn ich falsch liege, ist das wahrscheinlich der Grund, warum meine Antwort falsch lautet: Eine Antenne mit einem Gegenknoten verwechseln.
Aber ich glaube, ich habe eine Strategie, um alle neuen Bäuche zu identifizieren.
Mein aktueller Algorithmus findet die Bäuche an beiden Enden von zwei Antennen.
Stattdessen möchte ich die Linie in beide Richtungen entlanggehen, bis ich kurz davor bin, das Spielfeld zu verlassen.
Dies erfordert einige Umgestaltungen.
Ich bin bereit.
Hier ist meine aktualisierte Bedingung für positive Neigungslinien:
............ ........0... 9 .....0...... 8 .......0.... 7 ....0....... 6 ......A..... 5 ............ 4 ............ 3 ........A... 2 .........A.. 1 ............ 0 ............ 0123456789
Was hat sich geändert:
Ich musste dies für jede Klausel tun.
Ich habe einen leicht durcheinander gebracht, was dazu führte, dass ich anhand der Beispieleingabe eine um eins versetzte Antwort erhielt und ein wirklich seltsames Raster sah, das mir bei der Diagnose half, welche Klausel nicht richtig funktionierte.
Irgendwann gelang es mir, mit der Beispieleingabe zu arbeiten.
Dann habe ich es auf meiner Puzzle-Eingabe ausgeführt.
Und...
Ich habe die richtige Antwort generiert!!!
Ich bin so stolz auf mich!
Und ich bin so dankbar, dass es in meinem Rätsel-Input keinen Sneaky-Edge-Fall gab!
Wow, das hat mehrere Tage passiven Denkens gekostet, um es durchzuarbeiten.
Auf zu einem weiteren Tag mit zwei hart verdienten goldenen Sternen.
Das obige ist der detaillierte Inhalt vonResonante Kollinearität. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
