"""Experiment 3: does a list contain a duplicate? Two ways.

Every pair: compare each item with every item after it (a loop inside a loop).
Remember what you've seen: one pass, checking a set.
The lists have no duplicates, so both methods do all their work.
"""
from common import save

SIZES = [100, 1_000, 10_000]


def every_pair(items):
    steps = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            steps += 1
            if items[i] == items[j]:
                return True, steps
    return False, steps


def remember_seen(items):
    seen = set()
    steps = 0
    for item in items:
        steps += 1
        if item in seen:
            return True, steps
        seen.add(item)
    return False, steps


results = []
print(f"{'items':>8} | {'every pair':>12} | {'remember seen':>13}")
for n in SIZES:
    items = list(range(n))
    _, pair_steps = every_pair(items)
    _, seen_steps = remember_seen(items)
    print(f"{n:>8,} | {pair_steps:>12,} | {seen_steps:>13,}")
    results.append({"n": n, "pair_steps": pair_steps, "seen_steps": seen_steps})

save("exp3", results)