import hashlib
import random
import time
import math
import statistics
import scipy.stats as st
from math import ceil

# Configuration
TOTAL_SIZE = 100_000
RANGE_SIZE = 4_096
PREFIX_LENGTH = 3
SIMULATIONS = 1000
SECP256K1_ORDER = int("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)

print(f"""
=== Configuration ===
Total numbers: {TOTAL_SIZE:,}
Block size: {RANGE_SIZE:,}
Total blocks needed: {ceil(TOTAL_SIZE/RANGE_SIZE)}
Prefix: {PREFIX_LENGTH} characters (16^{PREFIX_LENGTH} = {16**PREFIX_LENGTH:,} combinations)
Simulations: {SIMULATIONS}
secp256k1 order: {SECP256K1_ORDER}
""")

def generate_h160(data):
    h = hashlib.new('ripemd160', str(data).encode('utf-8'))
    return h.hexdigest()

def shuffled_block_order(total_blocks):
    blocks = list(range(total_blocks))
    random.shuffle(blocks)
    return blocks

def sequential_search(dataset, block_size, target_hash, block_order):
    checks = 0
    for block_idx in block_order:
        start = block_idx * block_size
        end = min(start + block_size, len(dataset))
        for i in range(start, end):
            checks += 1
            if generate_h160(dataset[i]) == target_hash:
                return {"checks": checks, "found": True, "index": i}
    return {"checks": checks, "found": False}

def prefix_search(dataset, block_size, prefix_len, target_hash, block_order):
    prefix_hash = target_hash[:prefix_len]
    checks = 0
    ranges_to_scan = []
    skip_counter = 0
    scan_increment = 1

    for block_idx in block_order:
        start = block_idx * block_size
        end = min(start + block_size, len(dataset))  # Límite seguro
        found_prefix = False

        for i in range(start, end):
            checks += 1
            h = generate_h160(dataset[i])
            if h == target_hash:
                return {"checks": checks, "found": True, "index": i}
            if not found_prefix and h.startswith(prefix_hash):
                found_prefix = True
                ranges_to_scan.append({"start": i + 1, "end": end})
                skip_counter += 1
                break

        if skip_counter >= 4 and ranges_to_scan:
            for _ in range(min(scan_increment, len(ranges_to_scan))):
                r = ranges_to_scan.pop(0)
                for i in range(r["start"], r["end"]):
                    checks += 1
                    if generate_h160(dataset[i]) == target_hash:
                        return {"checks": checks, "found": True, "index": i}
            skip_counter = 0
            scan_increment += 1

    ###for r in ranges_to_scan:
        ###for i in range(r["start"], r["end"]):
            ###checks += 1
            ###if generate_h160(dataset[i]) == target_hash:
                ###return {"checks": checks, "found": True, "index": i}

    return {"checks": checks, "found": False}

def compute_cohens_d(list1, list2):
    if len(list1) < 2 or len(list2) < 2:
        return float('nan')
    n1, n2 = len(list1), len(list2)
    m1, m2 = statistics.mean(list1), statistics.mean(list2)
    s1, s2 = statistics.stdev(list1), statistics.stdev(list2)
   
    pooled_std = math.sqrt(((n1-1)*s1**2 + (n2-1)*s2**2) / (n1+n2-2))
    if pooled_std == 0:
        return float('nan')
    return (m1 - m2) / pooled_std

def correct_coefficient_of_variation(data):
    if not data or statistics.mean(data) == 0:
        return float('nan')
    return (statistics.stdev(data) / statistics.mean(data)) * 100

def longest_streak(outcomes, letter):
    max_streak = current = 0
    for o in outcomes:
        current = current + 1 if o == letter else 0
        max_streak = max(max_streak, current)
    return max_streak

def ascii_bar(label, value, max_value, bar_length=50):
    bar_count = int((value / max_value) * bar_length) if max_value > 0 else 0
    return f"{label:12}: {'#' * bar_count} ({value})"

def compare_methods():
    results = {
        "sequential": {"wins": 0, "success": 0, "checks": [], "times": []},
        "prefix": {"wins": 0, "success": 0, "checks": [], "times": []},
        "ties": 0
    }
    outcome_history = []
    total_blocks = ceil(TOTAL_SIZE / RANGE_SIZE)

    for _ in range(SIMULATIONS):
        max_offset = SECP256K1_ORDER - TOTAL_SIZE - 1
        offset = random.randint(0, max_offset)
        dataset = [offset + i for i in range(TOTAL_SIZE)]
        target_num = random.choice(dataset)
        target_hash = generate_h160(target_num)
        block_order = shuffled_block_order(total_blocks)

        start = time.perf_counter()
        seq_res = sequential_search(dataset, RANGE_SIZE, target_hash, block_order)
        seq_time = time.perf_counter() - start

        start = time.perf_counter()
        pre_res = prefix_search(dataset, RANGE_SIZE, PREFIX_LENGTH, target_hash, block_order)
        pre_time = time.perf_counter() - start

        for method, res, t in [("sequential", seq_res, seq_time), ("prefix", pre_res, pre_time)]:
            if res["found"]:
                results[method]["success"] += 1
                results[method]["checks"].append(res["checks"])
                results[method]["times"].append(t)

        if seq_res["found"] and pre_res["found"]:
            if seq_res["checks"] < pre_res["checks"]:
                results["sequential"]["wins"] += 1
                outcome_history.append("S")
            elif pre_res["checks"] < seq_res["checks"]:
                results["prefix"]["wins"] += 1
                outcome_history.append("P")
            else:
                results["ties"] += 1
                outcome_history.append("T")

    def get_stats(data):
        if not data:
            return {"mean": 0, "min": 0, "max": 0, "median": 0, "stdev": 0}
        return {
            "mean": statistics.mean(data),
            "min": min(data),
            "max": max(data),
            "median": statistics.median(data),
            "stdev": statistics.stdev(data) if len(data) > 1 else 0
        }

    seq_stats = get_stats(results["sequential"]["checks"])
    pre_stats = get_stats(results["prefix"]["checks"])
    seq_time_stats = get_stats(results["sequential"]["times"])
    pre_time_stats = get_stats(results["prefix"]["times"])

    seq_success_rate = results["sequential"]["success"] / SIMULATIONS
    pre_success_rate = results["prefix"]["success"] / SIMULATIONS

    total_comparisons = results["sequential"]["wins"] + results["prefix"]["wins"] + results["ties"]
    seq_win_rate = results["sequential"]["wins"] / total_comparisons if total_comparisons > 0 else 0
    pre_win_rate = results["prefix"]["wins"] / total_comparisons if total_comparisons > 0 else 0

    cv_seq = correct_coefficient_of_variation(results["sequential"]["checks"])
    cv_pre = correct_coefficient_of_variation(results["prefix"]["checks"])

    effect_size = compute_cohens_d(results["sequential"]["checks"], results["prefix"]["checks"])
    if len(results["sequential"]["checks"]) > 1 and len(results["prefix"]["checks"]) > 1:
        t_test = st.ttest_ind(results["sequential"]["checks"], results["prefix"]["checks"], equal_var=False)
    else:
        t_test = None

    print(f"""
=== FINAL ANALYSIS ===

[Success Rates]
Sequential: {seq_success_rate:.1%} ({results['sequential']['success']}/{SIMULATIONS})
Prefix:    {pre_success_rate:.1%} ({results['prefix']['success']}/{SIMULATIONS})

[Performance Metrics]
               | Sequential          | Prefix
---------------+---------------------+--------------------
Checks (mean)  | {seq_stats['mean']:>12,.1f} ± {seq_stats['stdev']:,.1f} | {pre_stats['mean']:>12,.1f} ± {pre_stats['stdev']:,.1f}
Time (mean ms) | {seq_time_stats['mean']*1000:>12.2f} ± {seq_time_stats['stdev']*1000:.2f} | {pre_time_stats['mean']*1000:>12.2f} ± {pre_time_stats['stdev']*1000:.2f}
Min checks     | {seq_stats['min']:>12,} | {pre_stats['min']:>12,}
Max checks     | {seq_stats['max']:>12,} | {pre_stats['max']:>12,}
Coef. Variation| {cv_seq:>11.1f}% | {cv_pre:>11.1f}%

[Comparison When Both Succeed]
Sequential wins: {results['sequential']['wins']} ({seq_win_rate:.1%})
Prefix wins:    {results['prefix']['wins']} ({pre_win_rate:.1%})
Ties:          {results['ties']}

[Statistical Significance]
Cohen's d: {effect_size:.3f}
Welch's t-test: {'t = %.3f, p = %.4f' % (t_test.statistic, t_test.pvalue) if t_test else 'Insufficient data'}
""")

    non_tie_outcomes = [o for o in outcome_history if o != "T"]
    streak_analysis = f"""
=== STREAK ANALYSIS ===
Longest Sequential streak: {longest_streak(outcome_history, 'S')}
Longest Prefix streak:    {longest_streak(outcome_history, 'P')}
Expected max streak:      {math.log(len(non_tie_outcomes), 2):.1f} (for {len(non_tie_outcomes)} trials)
"""
    print(streak_analysis)

    max_wins = max(results["sequential"]["wins"], results["prefix"]["wins"], results["ties"])
    print("=== WIN DISTRIBUTION ===")
    print(ascii_bar("Sequential", results["sequential"]["wins"], max_wins))
    print(ascii_bar("Prefix", results["prefix"]["wins"], max_wins))
    print(ascii_bar("Ties", results["ties"], max_wins))

if __name__ == '__main__':
    compare_methods()

=== Configuration ===
Total numbers: 100,000
Block size: 4,096
Total blocks needed: 25
Prefix: 3 characters (16^3 = 4,096 combinations)
Simulations: 1000
secp256k1 order: 115792089237316195423570985008687907852837564279074904382605163141518161494337


=== FINAL ANALYSIS ===

[Success Rates]
Sequential: 100.0% (1000/1000)
Prefix:    85.1% (851/1000)

[Performance Metrics]
               | Sequential          | Prefix
---------------+---------------------+--------------------
Checks (mean)  |     49,871.6 ± 28,366.8 |     42,476.4 ± 23,538.4
Time (mean ms) |       124.07 ± 71.32 |       107.76 ± 60.40
Min checks     |          106 |          106
Max checks     |       99,737 |       89,445
Coef. Variation|        56.9% |        55.4%

[Comparison When Both Succeed]
Sequential wins: 214 (25.1%)
Prefix wins:    603 (70.9%)
Ties:          34

[Statistical Significance]
Cohen's d: 0.282
Welch's t-test: t = 6.129, p = 0.0000


=== STREAK ANALYSIS ===
Longest Sequential streak: 6
Longest Prefix streak:    12
Expected max streak:      9.7 (for 817 trials)

=== WIN DISTRIBUTION ===
Sequential  : ################# (214)
Prefix      : ################################################## (603)
Ties        : ## (34)