[LeHack] - Alpha Walk

Introduction #

• Each matrix is 2^m * 2^m in size
• Each matrix is decomposed into 4 sub-matrices of size 2^m-1 * 2^m-1
• The order of filling is special for the 4 sub-matrices:
  • top-right
  • bottom-left
  • top-left
  • bottom-right
• This order is applied recursively
• Each cell of a matrix takes the value depending on its position

For M=1, the matrix is :

3 1

2 4

For M=2, the matrix is :

11 9 3 1

10 12 2 4

7 5 15 13

6 8 14 16

The aim is to find the value in position row=13 371 337, column=73 317 331 for a matrix M=60.

Analysis #

A matrix M=60 of size 2^60 * 2^60 has values ranging from 1 to 2^2x60 = 2^120, so we’ll need to use a language capable of handling large numbers (such as Python).

As the M=60 matrix is absolutely gigantic, it’s not possible to solve the problem by writing a Python script that constructs the matrix and reads the value we’re interested in, as this would take far too long (even with a powerful PC).

Instead of building the matrix by calculating the values of each cell, we position the value of each cell according to their position (row, column), for example with a M=2 matrix:

We then divide the matrix into cadrants! In fact, you can always divide the matrix into 4 parts, whatever its size:

• Q1: top right
• Q2: bottom left
• Q3: top left
• Q4: bottom right

Algorithm #

Thanks to these 2 principles, it’s quite simple to solve the challenge, just follow the algorithm below:

1. Determine the frame in which you’re looking for the value, which is easy because you know the position of the value you’re looking for.
2. Calculate the offset (= number of cells that have already passed before the current frame)

   

3. Add offset to a global counter.
4. Repeat the same algorithm, but the starting matrix is now this quadrant

Solving #

The following Python script takes this algorithm and displays the value of the (13371337, 73317331) cell in a M=60 matrix:

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}