Pour le problème de ce jour, on se donne une grille composée de rochers, de jardins et d'un point de départ.
L'exemple est le suivant:
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
Les "." représentent les jardin, les "#" représentent les rochers et S est la position de départ.
Le but de la partie 1 est de compter le nombre de positions où le jardinier peut arriver en partant de la tuile de départ et en faisant exactement 64 mouvements dans les 4 directions possibles (nord, sud, ouest , est).
Dans la partie 2, on suppose que la grille est répétée dans les 4 directions un nombre infini de fois. Alors là, même question que la partie 1 mais avec 26501365 mouvements!!!
# Solution en Haskell
Posté par Guillaume.B . Évalué à 3.
300ms pour la partie 2.
Pour la partie 1, il faut remarquer vu que la parité de la distance au point de départ change à chaque déplacement. La distance entre le point de départ et un sommet accessible après 64 mouvements est donc toujours pair.
Du coup, les sommets à trouver sont ceux situés exactement à distance n où n est pair et
n <= 64
.Un simple parcours en largeur fait l'affaire.
Pour la partie 2, ça se complique.
Mais on repère que l'instance est assez particulière:
- la grille de départ est carrée;
- le point de départ se trouve au centre;
- la ligne horizontale, la ligne verticale ainsi que les diagonales autour du centre sont vides.
Notons
f(n)
le nombre de points accessibles après n mouvements et notons M la taille (verticale et horizontale) de la grille.On peut donc se dire qu'il doit y avoir une régularité entre f(n) et f(n+M).
Notons
r = 26501365 mod M
et regardons la suite desu_i = f(r + iM)
pour i entier naturel.Après avoir calculé les 5 ou 6 premières valeurs par ordinateur, on se rend compte que la suite est une séquence quadratique ou dit autrement que la suite des dérivées discrètes secondes est constante. Elle est donc de la forme
u_n = a *n^2 + b * n + c
.Il faut donc calculer
u_n
avecn = 26501365 // M
où//
désigne la division entière.Pour calculer
u_n
, on a besoin que des 3 premiers termes de la suite.Notons
d1 = u1 - u0
,d2 = u2 - u1
etd' = d2 - d1
alorsu_n = u0 + n * d1 + n * (n-1) * d' / 2
.Et voilà !
Voici le code un peu commenté.
Tout d'abord le parsing et un précalcul pour transformer l'entrée en matrice et repérer le sommet de départ.
Pour la partie 1, on définir une fonction
nbors
qui donne le voisinage d'une tuile.Comme on ne sort pas de la grille dans la partie 1 et pour factoriser avec la partie 2,
on fait des modulo sur les coordonnées.
Pour la partie 2, on définit d'abord une fonction générique pour calculer le n-ième d'une séquence quadratique.
Ensuite, on peut l'appliquer à notre problème en calculant les trois premiers termes de la suite grâce à un parcours en largeur.
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . Évalué à 2.
Alors j'ai rien compris à ton explication, mais je crois que je suis en train de tomber malade.
J'ai hyper galéré à débugger mon code, bourré de mauvaises bornes, jusqu'au bout du bout…
Bon, d'une façon ou d'une autre je n'ai pas fait comme toi.
Cf plus bas :)
[^] # Re: Solution en Haskell
Posté par Yth (Mastodon) . Évalué à 2.
Ça y est, j'ai, compris ton explication, bien vu !
Yth.
# Rhaaaaaa !!!
Posté par Yth (Mastodon) . Évalué à 3.
Un problème bien bien pénible aujourd'hui, où il faut être très précis pour éviter les effets de bords.
encore une fois on « voit » des trucs dans les données, qui sont indispensables à la résolution…
On explore en damier, soit les cases noires (x+y pairs) soit les cases blanches (x+y impairs).
Une exploration type celle de l'exercice 1 que tout le monde a dû réussir, nous permet facilement de trouver le nombre de cases blanches et noires, chez moi c'est 7509 et 7566, ce qui additionné avec les rochers ne fait pas la taille du terrain, car il y a 4 cases inaccessibles (chez moi). Jusqu'ici tout va bien.
Comme tu l'as fait remarquer, on peut aller en ligne droite vers les répétitions du terrain, donc l'exploration d'une zone répétée autour de la zone de départ se fait le plus efficacement à partir du point d'entrée : le milieu du côté.
Pour les zones en diagonale, on va rentrer par la case au coin.
Ya pas plus rapide.
Le terrain fait 131x131, et le départ au centre en 65x65.
Donc on peut explorer indépendamment les différentes zones, en notant simplement le temps nécessaire à les atteindre.
65 + 1 + 131 * (distance - 1)
quand on va en ligne droite nord, sud, est ou ouest.Et
65 + 1 + 65 + 1 + 131 * (distance de Manhattan - 2)
pour les cases qui sont au moins un peu en diagonale.Bon, ya des +1, des +2, des -1, des -2, c'est les effets de bords ça.
On rentre au nord en 66 mouvements, et deux fois au nord en 66+131 mouvements, etc.
On rentre au nord-ouest en 65+1+65+1 = 132 mouvements, et de là on se décale horizontalement ou verticalement par paquets de 131.
On sait donc rapidement combien d'étapes il nous reste quand on entre dans une zone. Ça va être
plein
tout du long, et on va soit valider les cases noires, soit les cases blanches, en alternance.Ben oui, si on entre dans une zone mettons via
(0, 0)
, la case(0, 0)
d'une zone adjacente est à 131 mouvements, qui est un nombre impair, donc on ne l'atteint pas.On a en fait un damier de damiers, yay !
Là on va donc simplement regarder combien d'étape il reste à parcourir, ou combien on en a parcouru, et choisir sans se tromper la bonne valeur entre noir et blanc.
On additionne.
En pratique, une exploration en distance de zone par rapport à celle du départ est assez simple : on a 4 zones directement en face de la zone de départ, et (distance -1) * 4 zones qui forment une diagonale, on a un joli losange.
En distance 0 on a la zone de départ.
En distance 1 on a 4 zones directement liées.
En distance 2 on a 4 zones directes, et 4 zones diagonales.
En distance 3 c'est 4 et 8.
En distance n, c'est 4 et (n-1)*4.
Il se trouve que tout le monde à une distance donnée est soit blanc, soit noir (blanc = on considère les cases blanches à l'intérieur de la zone, noir = on considère les cases noires).
Comme le nombre d'étape final est impair, on ne considère pas la case de départ, donc la case de départ sur mon schéma, dans une zone blanche, doit être noire.
Ceci nous amène presque au bout, parce que là on va commencer à avoir des zones qu'on n'explorera plus entièrement, à cause des pas restants, trop courts.
Dans mon code, je prends une marge suffisante, et je calcule les cases à partir des déplacements restants.
Mais c'est assez facile, j'ai 8 zones : nord, sud, est, ouest et nord-est, nord-ouest, sud-est, sud-ouest, chacune explorée à partir d'un point de départ spécifique.
Lors de l'exploration, je note pour chaque pas effectué les cases atteintes.
Donc il me suffit de regarder quelle distance je peux parcourir dans mon exploration, avec les déplacements restants, et je sais quelles cases sont atteintes.
Je dénombre, j'additionne.
Et comme pour le reste du problème, on a les 4 directions cardinales uniques, et les 4 directions diagonales répétées (distance - 1) fois, donc on calcule 8 valeurs, on multiplie 4 d'entre elles, on additionne et c'est ok.
On passe à la distance suivante.
On s'arrête avec une petite marge où on va additionner des zéros.
J'ai pas mal fait ça pour éviter d'être sûr de moi, vu que j'ai eu des quantités invraisemblables d'erreurs aux bornes…
Et puis, voilà, résultat :)
Ça permet aussi de résoudre l'exercice 1 avec le problème central, vu que pour chacune de mes zones, je ne regarde que ce qu'il se passe dedans, j'ai les infos pour le premier problème.
Voilà notre explorateur de zone, et la fonction explored qui retourne les cases explorées selon le parité (zone noire ou blanche), et le nombre de pas restant.
Pour le premier problème, on démarre en
START = (65, 65)
et on fait 64 pas, on a un damier pair puisque 64 est pair, donc en particulier la case de départ est prise en compte.Pour le second problème on a une seconde exploration à faire. D'abord le paramétrage.
La fonction
bigexploration
retourne le type de zone, et le nombre de pas effectués, pour entrer dans la zone en(x, y)
par rapport à celle de départ.FINESTEPS c'est la distance à partir de laquelle on va vraiment compter les pas dans chaque zone. J'ai mis
* 2
pour avoir de la marge et ne pas avoir à réfléchir aux effets de bords, mais je peux valider que simplementSTEPS2 - MAXEXPLORATION
fonctionne.Après ça le code est moche et répétitif, dans l'esprit de bigexploration.
Et bigre, même le
range(1, (STEPS2 - MIDDLE) // HAUTEUR + 2)
m'a causé 2h de prise de tête, j'avais oublié de ne pas commencer à 0, mais bien à 1, donc je comptais 5 fois la zone de départ, comme j'ai lutté pour trouver ça, rhaaa !On vérifie l'intérêt de nos
FINESTEPS
avec les sorties :On voit bien qu'on a les 4 sommets qui sont incomplets, et pour les diagonales on a deux couches de diagonales à considérer. Et à chaque fois, le résultat pratique dépend de la direction qu'on considère, parce que la distribution des rochers met le bazar.
C'est officiellement celui qui m'a le plus résisté jusqu'à présent, mais au final, l'algo était là assez rapidement, il était juste buggé de partout :(
# Méthode de Guillaume
Posté par syj . Évalué à 1. Dernière modification le 23 décembre 2023 à 02:37.
J'ai implémenté la méthode avec séquence quadratique de Guillaume B.
Je suis un peu décu de ne pas avoir trouvé par moi-même
Mais je suis très heureux d'avoir découvert ce point des maths que je ne connaissais pas.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.