"""Exact fair-bit enumeration: search choices change chance-match probability."""
from pathlib import Path
import csv,json,math
import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
OUT=Path(__file__).resolve().parent
N=16;M=4;W=N-M+1;TOTAL=2**N
# This ordering is fixed before enumeration. It is arbitrary, not optimized.
ORDER=[10]+[i for i in range(16) if i!=10]
RANK={p:r for r,p in enumerate(ORDER)}
hist=np.zeros((W,16),dtype=np.int64)
for sequence in range(TOTAL):
    best=16
    for window in range(W):
        word=(sequence>>(N-M-window))&15
        best=min(best,RANK[word]);hist[window,best]+=1
counts=np.cumsum(hist,axis=1)
rows=[]
for w in range(1,W+1):
    for k in range(1,17):
        rows.append({'positions_tested':w,'patterns_tested':k,'pattern_position_comparisons':w*k,'matching_sequences':int(counts[w-1,k-1]),'all_equally_likely_sequences':TOTAL,'exact_probability':int(counts[w-1,k-1])/TOTAL,'independent_positions_approximation':1-(1-k/16)**w,'union_bound':min(1,w*k/16)})
with (OUT/'pattern-search-exact.csv').open('w',newline='',encoding='utf-8') as f:
    wr=csv.DictWriter(f,fieldnames=list(rows[0]));wr.writeheader();wr.writerows(rows)
# Independently verify all one-position cases by the number of accepted words.
assert all(counts[0,k-1]==k*2**(N-M) for k in range(1,17))
assert np.all(np.diff(counts,axis=0)>=0) and np.all(np.diff(counts,axis=1)>=0)
assert np.all(counts[:,-1]==TOTAL)
assert all(r['exact_probability']<=r['union_bound']+1e-15 for r in rows)
# Independent avoidance automaton for the single word, over the whole string.
pattern='1010';states={'':1}
for _ in range(N):
    nxt={}
    for suffix,num in states.items():
        for bit in '01':
            s=suffix+bit
            if s.endswith(pattern):continue
            prefixes=[pattern[:j] for j in range(M) if s.endswith(pattern[:j]) or j==0]
            retained=max(prefixes,key=len);nxt[retained]=nxt.get(retained,0)+num
    states=nxt
avoid=sum(states.values());assert TOTAL-avoid==int(counts[-1,0])
# Non-overlapping starts 0,4,8,12 are independent under fair iid bits.
nonoverlap=sum(any(((s>>(N-M-j))&15)==10 for j in [0,4,8,12]) for s in range(TOTAL))
assert nonoverlap==TOTAL*(1-(15/16)**4)
metadata={'title':'Finding patterns by chance','data_kind':'Exact enumeration of all fair independent 16-bit strings; no measured or decoded messages','bits_per_string':N,'word_length':M,'equally_likely_strings':TOTAL,'window_starts':'first w starts, counted from 0 through w-1; w=1..13','pattern_order':[format(x,'04b') for x in ORDER],'pattern_selection':'first k entries of the prespecified order, k=1..16','event':'At least one of the k allowed 4-bit words appears at one of the w tested positions.','exact_formula':'P(match)=count_of_matching_16_bit_strings/65536','one_position_formula':'P(match)=k/16','union_bound':'P(match)<=min(1,w*k/16)','warning':'1-(1-k/16)^w assumes independent windows and is generally not exact for overlapping windows. Different word sets can have different overlap behaviour.','validation':{'one_position_closed_form':'passed for all k','single_word_avoidance_automaton_matching_count':TOTAL-avoid,'nonoverlapping_four_window_matching_count':nonoverlap,'nonoverlapping_formula':'1-(15/16)^4','monotonicity':'passed','union_bound':'passed'},'limitations':['Each bit is independent and equally likely to be zero or one.','Search choices are fixed before enumeration; a real analyst may try other word lengths, offsets, transforms or codebooks too.','A match is a combinatorial coincidence, not evidence of an intended message.','Results depend on word length, string length and which patterns are allowed.','No uncertainty intervals: all strings in this finite null model are enumerated exactly.']}
(OUT/'study.json').write_text(json.dumps(metadata,indent=2)+'\n',encoding='utf-8')
plt.rcParams.update({'font.family':'DejaVu Sans','font.size':10,'axes.spines.top':False,'axes.spines.right':False})
fig,ax=plt.subplots(1,2,figsize=(11.6,4.9),constrained_layout=True)
x=np.arange(1,W+1)
ax[0].plot(x,counts[:,0]/TOTAL*100,'o-',color='#393f94',label='Exact enumeration: word 1010',ms=4)
ax[0].plot(x,(1-(15/16)**x)*100,'--',color='#a75921',label='Independent-window approximation')
ax[0].set(xlabel='Starting positions searched',ylabel='Chance of at least one match (%)',title='A  |  Search more places, find more matches',xticks=[1,3,5,7,9,11,13]);ax[0].legend(fontsize=8,loc='upper left')
k=np.arange(1,17)
ax[1].plot(k,k/16*100,'o-',color='#087f8c',label='One preselected position',ms=4)
ax[1].plot(k,counts[-1,:]/TOTAL*100,'s-',color='#b42e8d',label='All 13 overlapping positions',ms=4)
ax[1].set(xlabel='Allowed 4-bit patterns (prespecified order)',ylabel='Chance of at least one match (%)',title='B  |  Accept more patterns, find more matches',xticks=[1,4,8,12,16]);ax[1].legend(fontsize=8,loc='lower right')
for a in ax:a.grid(alpha=.2);a.set_ylim(0,103)
fig.suptitle('A chance match is not a recovered message',fontsize=16,weight='bold')
fig.supxlabel('Exact null model: all 65,536 equally likely 16-bit strings. Every permitted match counts; no decoding is inferred.',fontsize=9)
for ext in ['png','svg','pdf']:fig.savefig(OUT/f'pattern-search.{ext}',dpi=180)
print(json.dumps({'rows':len(rows),'fixed_one_position':counts[0,0]/TOTAL,'single_pattern_anywhere':counts[-1,0]/TOTAL,'single_pattern_anywhere_count':int(counts[-1,0]),'independent_approximation':1-(15/16)**13,'four_patterns_anywhere':counts[-1,3]/TOTAL,'validation':metadata['validation']}))