[LeHack] - A lot of conditions
Sommaire
LeHack2025 - Cet article fait partie d'une série.
Introduction #
- Le fichier input.bin contient 10⁹ intervalles, chacun sous la forme [a, b], avec a et b des entiers 32 bits signés en little endian.
- Le but du challenge est trouver l’entier qui apparaît dans le plus d’intervalles et combien de fois.
- Format du flag :
leHACK{XXXXXXXYYYYYY}- XXXXXXX = entier (le plus couvert)
- YYYYYY = nombre d’intervalles qui le contiennent
Analyse #
On ne peut pas essayer de compter le nombre d’occurence de chaque valeur stockée dans chaque intervalle car ceci prendrait une place énorme dans la mémoire RAM de l’ordinateur et pourrait poser des problèmes de remplissage.
En fait, il n’est tout simplement pas possible de parcourir chaque intervalle, il y aurait trop de valeurs, cela prendrait trop de temps ou causerait des problèmes de mémoire pour les systèmes pas assez performant.
Seul un algorithme qui prend uniquement la ligne des entiers de chaque intervalle (c’est-à-dire la valeur minimale et maximale de chaque intervalle -> les bords de l’intervalle finalement) nous permettra de résoudre le challenge.
Ça tombe bien, un tel algorithme existe : Le Sweep Line Algorithme
Algorithme #
Le principe de cet algorithme est simple, pour chaque intervalle [a, b] :
- Il incrémente un compteur à a (= début de l’intervalle)
- Il décrémente un compteur à b + 1 (= extérieur de l’intervalle)
Après traitement de tous les intervalles, on trie les positions et fait un scan linéaire pour retrouver le pic de couverture.
Résolution #
Il suffit maintenant d’appliquer ce principe à un script Python et l’adapter pour qu’il puisse lire les entiers 32 bits signés en little endian :
import struct
from collections import defaultdict
def find_most_covered_point(filename):
# Dictionary to store the change in interval count at specific positions
# delta[x] += 1 means an interval starts at x
# delta[x] -= 1 means an interval ends just before x
delta = defaultdict(int)
# Open the binary file for reading
with open(filename, "rb") as f:
while True:
# Read chunks of 100,000 intervals at a time (each interval is 8 bytes)
chunk = f.read(8 * 100000)
if not chunk:
break # End of file
# Process each 8-byte interval in the chunk
for i in range(0, len(chunk), 8):
# Unpack two little-endian 32-bit signed integers (start and end of interval)
a, b = struct.unpack_from('<ii', chunk, i)
# Ensure the interval is in correct order: [a, b]
if a > b:
a, b = b, a
# Mark the start and end+1 in the delta map
delta[a] += 1
delta[b + 1] -= 1
# Perform the sweep line algorithm to find the point covered by the most intervals
current = 0 # Current number of active intervals
max_count = 0 # Maximum number of overlapping intervals seen so far
max_point = None # The integer point with the most overlaps
# Process the points in sorted order
for x in sorted(delta):
current += delta[x] # Update the current count based on interval change at x
if current > max_count:
max_count = current # Update max if current is greater
max_point = x # Remember the position where max occurred
return max_point, max_count
if __name__ == "__main__":
# Call the function with the input file
point, count = find_most_covered_point("input.bin")
# Format and print the flag in the required format
print(f"leHACK{{{point:07d}{count:06d}}}")
🚩 Flag : leHACK{6230382861128126}