Generate triplets within lattice

lattice_triplets.py

import random
import time


def rolling_hash(rect, prev_hash=0):
    base = 256
    mod = 2 ** 64  # Large prime to reduce collisions

    h = prev_hash
    for val in rect:
        h = (h * base + val) % mod

    return h


def generate_triplets(n_triplets=100000):
    triplets = set()
    actual_triplets = []
    max_attempts = 10000

    start_time = time.time()

    while len(triplets) < n_triplets:
        attempts = 0
        while attempts < max_attempts:
            attempts += 1

            lattice = [[0] * 10 for _ in range(10)]

            rects = []
            valid_triplet = True
            triplet_hash = 0

            for _ in range(3):
                width = random.randint(1, 3)
                height = random.randint(1, 3)
                x = random.randint(0, 10 - width)
                y = random.randint(0, 10 - height)

                if check_fit(lattice, x, y, width, height):
                    place_rectangle(lattice, x, y, width, height)
                    rect = (x, y, width, height)
                    rects.append(rect)
                    triplet_hash = rolling_hash(rect, triplet_hash)
                else:
                    valid_triplet = False
                    break

            if valid_triplet and triplet_hash not in triplets:
                triplets.add(triplet_hash)
                actual_triplets.append(tuple(rects))
                break

        if len(triplets) % 10000 == 0:
            print(f"Generated {len(triplets)} unique triplets...")

    generation_time = time.time() - start_time
    print(f"Generated {len(triplets)} triplets in {generation_time:.2f} seconds")

    # Brute-force check for duplicates
    print("Performing final brute-force check for duplicates...")
    check_start_time = time.time()
    unique_triplets = set()
    duplicates = 0
    for triplet in actual_triplets:
        if triplet in unique_triplets:
            duplicates += 1
        else:
            unique_triplets.add(triplet)

    check_time = time.time() - check_start_time
    total_time = time.time() - start_time

    print(f"Brute-force check completed in {check_time:.2f} seconds")
    print(f"Found {duplicates} duplicate triplets")
    print(f"Final number of unique triplets: {len(unique_triplets)}")
    print(f"Total time (including check): {total_time:.2f} seconds")

    return list(unique_triplets)


def check_fit(lattice, x, y, width, height):
    for i in range(y, y + height):
        for j in range(x, x + width):
            if lattice[i][j] == 1:
                return False
    return True


def place_rectangle(lattice, x, y, width, height):
    for i in range(y, y + height):
        for j in range(x, x + width):
            lattice[i][j] = 1


# Generate 100,000 unique triplets
triplets = generate_triplets(100000)