[LeHack] - Alpha Walk

Introduction #

• Chaque matrice est de taille 2^m * 2^m
• Chaque matrice est décomposée en 4 sous-matrices de taille 2^m-1 * 2^m-1
• L’ordre de remplissage est spécial pour les 4 sous-matrices :
  • top-right
  • bottom-left
  • top-left
  • bottom-right
• Cet ordre s’applique récursivement
• Chaque case d’une matrice prend la valeur dépendant de sa position

Pour M=1, la matrice est donc :

3 1

2 4

Pour M=2, la matrice est :

11 9 3 1

10 12 2 4

7 5 15 13

6 8 14 16

Le but est de trouver la valeur en position ligne=13 371 337, colonne=73 317 331 pour une matrice M=60.

Analyse #

Une matrice M=60 est de taille 2^60 * 2^60 possèdent des valeurs allant de 1 à 2^2x60 = 2^120, on devra donc utiliser un langage capable de gérer de grands nombre (tel que Python).

La matrice M=60 est absolument gigantesque, il n’est pas possible de résoudre le problème en écrivant un script Python qui construit la matrice et qui va lire la valuer qui nous intéresse, cela prendrait beaucoup trop de temps (même avec PC puissant).

A la place de construire la matrice en calulant les valeurs de chaque case, on positionne la de chaque case en fonction de leur position (ligne, colonne), exemple avec une matrice M=2 :

Puis on va utiliser découper la matrice en cadrants ! En effet, on peut toujours diviser la matrice en 4 parties, peu importe sa taille :

• Q1 : en haut à droite
• Q2 : en bas à gauche
• Q3 : en haut à gauche
• Q4 : en bas à droite

Algorithme #

Grâce à ses 2 principes, il est assez simple de résoudre le challenge, il suffit de suivre l’algorithme suivant :

1. Déterminer le cadrant dans lequel on cherche la valeur, ce qui est simple car on connaît la position de la valeur que l’on cherche
2. Calculer l’offset (= nombres de cases qui sont déjà passées avant la cadrant actuel)

   

3. Ajouter l’offset à un compteur global
4. Recommencer ce même algorithme mais la matrice de départ est maintenant ce cadrant

Résolution #

Le script Python suivant reprend cet algorithme et permet d’afficher la valeur de la case (13371337, 73317331) dans une matrice M=60 :

def get_value(r, c, m):
    value = 0
    for level in reversed(range(m)):
        size = 1 << level  # 2^level
        block_size = 4 ** level

        # Determine quadrant and adjust (r, c) accordingly
        if r < size and c >= size:
            # Top-right
            c -= size
            quadrant = 0
        elif r >= size and c < size:
            # Bottom-left
            r -= size
            quadrant = 1
        elif r < size and c < size:
            # Top-left
            quadrant = 2
        else:
            # Bottom-right
            r -= size
            c -= size
            quadrant = 3

        value += quadrant * block_size
    return value + 1  # Add 1 because values are 1-indexed

def get_matrix(size):
	mat = []
	for i in range(2**size):
		ligne = []
		for j in range(2**size):
			ligne.append(get_value(i,j,size))
		mat.append(ligne)
	print(mat)

if __name__ == '__main__':
	#get_matrix(60)
	print(get_value(13371337, 73317331, 60))

🚩 Flag : leHACK{886151997189943915260142838930733156}