[LeHack] - A lot of conditions

Table of Contents

LeHack2025 - This article is part of a series.

Part 1: [LeHack] - Modbus

Part 2: [LeHack] - Poor

Part 3: [LeHack] - Singularity

Part 4: [LeHack] - Alpha Walk

Part 5: This Article

Introduction #

The file input.bin contains 10⁹ intervals, each in the form [a, b], with a and b integers 32 bits signed in little endian.
The aim of the challenge is to find the integer that appears in the most intervals and how many times.
Flag format: leHACK{XXXXXXXYYYYY}
- XXXXXXX = integer (most covered)
- YYYYYY = number of intervals containing it

Analysis #

We can’t try to count the number of occurrences of each value stored in each interval, as this would take up an enormous amount of space in the computer’s RAM memory and could cause filling problems.

In fact, it’s simply not possible to go through each interval, there would be too many values, it would take too long or cause memory problems for under-performing systems.

Only an algorithm that takes only the integer line of each interval (i.e. the minimum and maximum value of each interval -> the edges of the interval) will enable us to solve the challenge.

The Sweep Line Algorithm.

Algorithm #

The principle of this algorithm is simple: for each interval [a, b] :

It increments a counter at a (= start of interval)
Decrement a counter at b + 1 (= outside of interval)

After processing all the intervals, the positions are sorted and a linear scan is performed to find the peak coverage.

It’s a bit like noting when someone enters a room and when someone leaves. By going through the positions in order, we can find out how many people are in the room at any given time, and thus detect the most crowded moment.

Résolution #

All we need to do now is apply this principle to a Python script and adapt it so that it can read 32-bit integers signed in 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}}}")

To avoid memory problems, intervals are processed in packets of 100,000.

🚩 Flag : leHACK{6230382861128126}