Colinéarité résonante

Avènement du Code 2024 Jour 8

Partie 1

Je pense que je comprends. Puis-je le faire ?

Si je comprends bien :

• Pour chaque paire de ligatures identiques
• Trouvez le point X où une ligature est 1N et l'autre est 2N - où N est à une certaine distance de X
• Tant qu'il se trouve dans les limites de la grille, comptez-le pour la réponse

Voici un visuel :

...........
...........
...X.......
...........
.....Y.....   <---1N from top X, 2N from bottom X
...........
.......Y...   <---2N from top X, 1N from bottom X
...........
.........X.
...........

C'est clair visuellement.

Comment pourrais-je le déterminer de manière algorithmique ?

Calcul algorithmique de 1N et 2N

Voici l'exemple de grille :

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

Je vais me concentrer sur les 0 :

• Il y en a quatre
• Les coordonnées sont : 1,8, 2,5, 3,7, 4,4

En comparant les deux premiers :

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 = ....

J'ai réalisé en écrivant que j'avais vraiment besoin de connaître la pente de la droite reliant la paire de points.

De cette façon, je peux savoir s'il faut ajouter ou soustraire de chaque axe pour déterminer où se trouve le ventre.

Rafraîchir ma mémoire sur la pente

La formule est :

(y2 - y1) / (x2 - x1)

Le résultat sera l'un de ces quatre :

• > 0 signifie pente positive : vers le haut et vers la droite
• < 0 signifie pente négative : vers le bas et vers la droite
• 0 signifie ligne horizontale
• L'infini signifie ligne verticale

Reprenons l'exemple :

1,8 and 2,5

(5 - 8) / (2 - 1) = -3 / 1 = -3

Quoi ? Une pente négative ? Non, cette droite a une pente positive !

Oh... je vois.

L'indexation des tableaux augmente, mais visuellement diminue.

Je dois compter les indices à l'envers.

Au lieu de comme ça :

0 ............
1 ........0...
2 .....0......
3 .......0....
4 ....0.......
5 ......A.....
6 ............
7 ............
8 ........A...
9 .........A..
  ............
  ............
  0123456789

Je dois compter comme ceci :

  ............
  ........0...
9 .....0......
8 .......0....
7 ....0.......
6 ......A.....
5 ............
4 ............
3 ........A...
2 .........A..
1 ............
0 ............
  0123456789

Cela devrait juste nécessiter un peu plus de mathématiques :

array length - current row/col index

Je vais essayer.

Pour les 0 les plus élevés :

12 rows
Row index: 1
12 - 1 = 11

Column index: 8

Coordinates: 8,11

Pour le 0 de la ligne suivante :

Row index: 2
12 - 2 = 10

Column index: 5

Coordinates: 5,10

Et la pente :

(10 - 11) / (5 - 8)
   -1     /    -3
         1/3

Une pente positive ! C'est exact !

Commencer à coder

Construire la liste des coordonnées de l'antenne

Un objet vide rempli d'une boucle for imbriquée :

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>Crée cet objet pour l'exemple d'entrée :<br>
</p>

<pre class="brush:php;toolbar:false">{
  '0': [ [ 11, 8 ], [ 10, 5 ], [ 9, 7 ], [ 8, 4 ] ],
  A: [ [ 7, 6 ], [ 4, 8 ], [ 3, 9 ] ]
}

Ça a l'air génial !

Ensuite, calcul de la pente.

Écrire un outil de recherche de ventre trop complexe

Ma fonction scope est simple :

function getScope(p1,p2) {
  return (p2[0] - p1[0]) / (p2[1] - p1[1])
}

Il attend deux tableaux et renvoie la portée en utilisant les quatre coordonnées.

Je souhaiterai appeler cette fonction lors de la comparaison de toutes les paires de coordonnées de fréquence similaire.

Cette comparaison se produit dans cette boucle for super imbriquée :

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
    }
  }
}

Confirmer que cela fonctionne sur l'exemple d'entrée :

[ 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 ]

Neuf comparaisons. C'est vrai !

Et les périmètres pour chacun ?

Ceux-ci ont l'air bien aussi, heureusement.

Maintenant, la partie trop compliquée, je pense.

Gestion des quatre types de pente

Ils sont :

...........
...........
...X.......
...........
.....Y.....   <---1N from top X, 2N from bottom X
...........
.......Y...   <---2N from top X, 1N from bottom X
...........
.........X.
...........

Gérons ça.

C'est beaucoup, mais les subtilités sont importantes au sein de chaque clause :

............
........0...
.....0......
.......0....
....0.......
......A.....
............
............
........A...
.........A..
............
............

Heureusement, tous les ventres identifiés semblent correctement placés.

Ensuite, en excluant ceux qui sont hors limites

Exclure les ventres hors limites

Entrez...plus de conditions !

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 = ....

Je vérifie si chaque coordonnée est comprise entre 0 et la longueur des lignes ou des colonnes.

Ensuite, au bas de chaque clause dans mon ventre-finder, j'appelle la fonction sur les deux nœuds possibles :

(y2 - y1) / (x2 - x1)

Et ma réponse sera la taille de mon ensemble valide.

Est-ce que cela fonctionne réellement ?

L'exécuter génère 12. Pas 14.

Pourquoi pas ?

...

Après quelques débogages, j'ai trouvé mon erreur :

1,8 and 2,5

(5 - 8) / (2 - 1) = -3 / 1 = -3

Je m'éloigne d'un dans mon affectation du rang. J'ai besoin d'une valeur de moins :

0 ............
1 ........0...
2 .....0......
3 .......0....
4 ....0.......
5 ......A.....
6 ............
7 ............
8 ........A...
9 .........A..
  ............
  ............
  0123456789

Cela corrige les choses.

J'en vois 14 maintenant.

Il est temps de l'exécuter sur mon entrée de puzzle.

...

Bonne réponse !!!

Cela a pris beaucoup plus de temps que prévu, mais je l'ai fait !

Je ne peux qu'imaginer ce que nécessitera la partie 2.

Avaler.

Partie 2

Ouais. Beaucoup plus de ventres à identifier.

Cela semble plus difficile, même si cela peut être un ajustement relativement simple.

Il est temps d'y réfléchir.

...

Entrer avec une faible confiance dans la génération de la bonne réponse

Principalement à cause de ce piège :

exactement en ligne avec au moins deux antennes de même fréquence

Je pense Je comprends ce critère.

Mon intuition est que tant qu'il y en a trois d'une fréquence donnée, les trois antennes sont également des ventres.

Si je me trompe, c'est probablement pour cela que ma réponse sera erronée : confondre une antenne avec un ventre.

Mais je pense avoir une stratégie pour identifier tous les nouveaux ventres.

Entrez : plus de boucles while pour parcourir les lignes

Mon algorithme actuel trouve les ventres à chaque extrémité de deux antennes.

Je veux plutôt marcher le long de la ligne dans les deux sens jusqu'à ce que je sois sur le point de sortir des limites.

Cela nécessitera une refactorisation.

Je suis prêt.

Voici ma condition mise à jour pour les lignes à pente positive :

  ............
  ........0...
9 .....0......
8 .......0....
7 ....0.......
6 ......A.....
5 ............
4 ............
3 ........A...
2 .........A..
1 ............
0 ............
  0123456789

Ce qui a changé :

• J'effectue les mathématiques une fois à l'avance
• À l'intérieur de la boucle while, j'ajoute la coordonnée, puis j'incrémente ou décrémente simplement chaque coordonnée du diff correspondant
• La condition utilise ma fonction mise à jour qui renvoie un booléen au lieu d'ajouter automatiquement les coordonnées

Je devais faire ça pour chaque clause.

J'en ai légèrement raté une, ce qui m'a amené à obtenir une réponse décalée par 1 en utilisant l'exemple d'entrée et à voir une grille vraiment étrange, ce qui m'a aidé à diagnostiquer quelle clause fonctionnait mal.

Finalement, je l'ai fait fonctionner sur l'exemple d'entrée.

Ensuite, je l'ai exécuté sur mon entrée de puzzle.

Et...

J'ai généré la bonne réponse !!!

Je suis tellement fière de moi !

Et je suis tellement reconnaissant qu'il n'y ait pas eu de cas sournois dans ma contribution au puzzle !

Wow, il a fallu plusieurs jours de réflexion passive pour y parvenir.

En route vers une autre journée avec deux étoiles d'or durement gagnées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!