# Import libraries
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import seaborn as sns
import re
import zipfile
import os
from collections import defaultdict, Counter
from itertools import combinations
from mlxtend.frequent_patterns import apriori, association_rules
from mlxtend.preprocessing import TransactionEncoder
import warnings
from google.colab import drive
import gc
import lightgbm as lgb
from sklearn.linear_model import LogisticRegression
from sklearn.ensemble import RandomForestClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import (roc_auc_score, average_precision_score, classification_report)
from sklearn.model_selection import GroupShuffleSplit
import time

warnings.filterwarnings('ignore')

plt.style.use('seaborn-v0_8-whitegrid')
sns.set_palette('husl')
pd.set_option('display.max_columns', None)
pd.set_option('display.float_format', '{:.4f}'.format)
%matplotlib inline
print('✅ Libraries loaded')

# Mount drive to access data
drive.mount('/content/drive/')

data = {}

# Read files from zip
with zipfile.ZipFile('/content/drive/MyDrive/instacart/instacart.zip', 'r') as z:

    file_list = [f for f in z.namelist() if f.endswith('.csv')]

    print(f'Files in archive: {file_list}\n')

    for fn in file_list:

        key = fn.replace('.csv', '')

        # Update
        data[key] = pd.read_csv(z.open(fn))
        print(f'  ✓ {fn}: {data[key].shape[0]:,} rows × {data[key].shape[1]} cols')

print('\n✅ All datasets loaded')

# Inspect schema
print('=' * 65)
print('DATASET SCHEMA & NULL REPORT')
print('=' * 65)
for name, df in data.items():

    nulls = df.isnull().sum()
    null_info = {c: n for c, n in nulls.items() if n > 0}

    print(f'\n📂 {name}')
    print(f'   Rows: {df.shape[0]:,}  |  Cols: {df.shape[1]}')
    print(f'   Columns: {list(df.columns)}')

    if null_info:

        print(f'   ⚠️  Nulls: {null_info}')

    else:

        print(f'   ✓  No nulls')

    display(df.head(3))

# Inspect the eval data
eval_counts = data['orders']['eval_set'].value_counts()

print('Orders by eval_set:')

for k, v in eval_counts.items():

    print(f'  {k:8s}: {v:>10,} orders  ({v/len(data["orders"])*100:.1f}%)')

print(f'\nTotal unique users: {data["orders"]["user_id"].nunique():,}')
print(f'Total unique products: {data["products"].shape[0]:,}')
print(f'Total aisles: {data["aisles"].shape[0]}  |  Departments: {data["departments"].shape[0]}')

# Normalize product names (lowercase, strip punctuation)
data['products']['product_name'] = (data['products']['product_name'].apply(lambda x: re.sub(r'[^\w\s]', ' ', x.lower())).apply(lambda x: re.sub(r'\d+|  ', '', x).strip()))

# Merge the codes with the labels
products = (data['products'].merge(data['aisles'], on = 'aisle_id', how = 'left').merge(data['departments'], on = 'department_id',  how = 'left').drop(['aisle_id', 'department_id'], axis = 1).rename(columns = {'product_name': 'product'}))
print(f'Products enriched: {products.shape}')
products.head(3)

# Visualize order volumes
fig, axes = plt.subplots(1, 2, figsize=(20, 5))

dow_labels = {0: 'Sun', 1: 'Mon', 2: 'Tue', 3: 'Wed', 4: 'Thu', 5: 'Fri', 6: 'Sat'}
dow_counts = data['orders']['order_dow'].map(dow_labels).value_counts().reindex(['Sun','Mon','Tue','Wed','Thu','Fri','Sat'])

colors_dow = sns.color_palette('husl', 7)

bars = axes[0].bar(dow_counts.index, dow_counts.values, color = colors_dow, edgecolor = 'white', linewidth = 0.8)
axes[0].set_title('Orders by Day of Week', fontsize = 14, fontweight = 'bold')
axes[0].set_xlabel('Day of Week'); axes[0].set_ylabel('Number of Orders')

# Iterate
for bar, v in zip(bars, dow_counts.values):

    axes[0].text(bar.get_x() + bar.get_width()/2, v + 1500, f'{v:,}', ha = 'center', va = 'bottom', fontsize = 8)

hour_counts = data['orders']['order_hour_of_day'].value_counts().sort_index()
axes[1].plot(hour_counts.index, hour_counts.values, marker = 'o', linewidth = 2.5, color = '#2196F3', markersize = 5)
axes[1].fill_between(hour_counts.index, hour_counts.values, alpha=0.15, color='#2196F3')
axes[1].axvspan(8, 11, alpha=0.1, color='orange', label='Peak morning (8-11)')
axes[1].axvspan(14, 17, alpha=0.1, color='green', label='Peak afternoon (14-17)')
axes[1].set_title('Orders by Hour of Day', fontsize=14, fontweight='bold')
axes[1].set_xlabel('Hour of Day'); axes[1].set_ylabel('Number of Orders')
axes[1].set_xticks(range(0, 24)); axes[1].legend()

plt.suptitle('When Do Customers Shop?', fontsize=16, fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()

print(f'Peak ordering day:  {dow_counts.idxmax()}    ({dow_counts.max():,} orders)')
print(f'Peak ordering hour: {hour_counts.idxmax()}:00  ({hour_counts.max():,} orders)')

# Visualize user data
fig, axes = plt.subplots(1, 2, figsize = (20, 5))

# Days since prior order
dspo = data['orders']['days_since_prior_order'].dropna()

axes[0].hist(dspo, bins = 31, color = '#4CAF50', edgecolor = 'white', alpha = 0.85)
axes[0].axvline(dspo.mean(),   color = 'red',    linestyle = '--', lw = 2, label = f'Mean: {dspo.mean():.1f}d')
axes[0].axvline(dspo.median(), color = 'orange', linestyle = '--', lw = 2, label = f'Median: {dspo.median():.0f}d')
axes[0].axvline(7,  color = 'gray', linestyle = ':', alpha = 0.7, label = 'Weekly')
axes[0].axvline(30, color = 'gray', linestyle = ':', alpha = 0.7, label = 'Monthly')
axes[0].set_title('Days Since Prior Order Distribution', fontsize = 14, fontweight = 'bold')
axes[0].set_xlabel('Days'); axes[0].set_ylabel('Frequency')
axes[0].legend()

# Orders per user
orders_per_user = data['orders'].groupby('user_id')['order_id'].count()
axes[1].hist(orders_per_user, bins=50, color='#9C27B0', edgecolor='white', alpha=0.85)
axes[1].axvline(orders_per_user.mean(), color='red', linestyle='--', lw=2, label=f'Mean: {orders_per_user.mean():.1f}')
axes[1].set_title('Orders per User (all-time)', fontsize=14, fontweight='bold')
axes[1].set_xlabel('Number of Orders'); axes[1].set_ylabel('Number of Users')
axes[1].legend()

plt.tight_layout()
plt.show()

print(f'Average days between orders:    {dspo.mean():.1f}')
print(f'Users who order weekly (≤7d):   {(dspo <= 7).mean()*100:.1f}%')
print(f'Users who order monthly (~30d): {(dspo.between(25,35)).mean()*100:.1f}%')
print(f'Users with 10+ orders:          {(orders_per_user >= 10).sum():,} ')
print(f'({(orders_per_user >= 10).mean()*100:.1f}%)')

# Truncate the data and track memory
all_user_ids = data['orders']['user_id'].unique()
sampled_uids = set(np.random.default_rng(100).choice(all_user_ids, size = min(150000, len(all_user_ids)), replace = False))
print(f'Working with {len(sampled_uids):,} sampled users')

# Filter the orders index to only sampled users — still cheap
orders_slim = data['orders'][data['orders']['user_id'].isin(sampled_uids)][['order_id','user_id','eval_set','order_number', 'order_dow','order_hour_of_day','days_since_prior_order']]

# Cast to smaller dtypes immediately
orders_slim = orders_slim.astype({'order_id':               'int32',
                                  'user_id':                'int32',
                                  'order_number':           'int16',
                                  'order_dow':              'int8',
                                  'order_hour_of_day':      'int8',})

print(f'orders_slim: {orders_slim.shape}  |  {orders_slim.memory_usage(deep = True).sum()/1e6:.1f} MB')

# Get only the order_ids belonging to sampled users
sampled_order_ids = set(orders_slim['order_id'].values)

# Filter prior and train BEFORE any merge
prior_raw = data['order_products__prior'][data['order_products__prior']['order_id'].isin(sampled_order_ids)].astype({'order_id':'int32','product_id':'int32','add_to_cart_order':'int16','reordered':'int8'})

train_raw = data['order_products__train'][data['order_products__train']['order_id'].isin(sampled_order_ids)].astype({'order_id':'int32','product_id':'int32','add_to_cart_order':'int16','reordered':'int8'})

print(f'prior_raw:  {prior_raw.shape[0]:,} rows  |  {prior_raw.memory_usage(deep = True).sum()/1e6:.1f} MB')
print(f'train_raw:  {train_raw.shape[0]:,} rows  |  {train_raw.memory_usage(deep = True).sum()/1e6:.1f} MB')

# Downcast products lookup (tiny, but keeps dtypes consistent)
products_slim = products
products_slim['product_id'] = products_slim['product_id'].astype('int32')

# Enrich prior and train separately — small frames now, safe to merge
def enrich(raw_df, eval_label):

    return (raw_df.merge(products_slim, on = 'product_id', how = 'left').merge(orders_slim.drop(columns = 'eval_set'), on = 'order_id', how = 'left').assign(eval_set=eval_label))

prior_op = enrich(prior_raw, 'prior')
del prior_raw; gc.collect()

train_op = enrich(train_raw, 'train')
del train_raw; gc.collect()

orders_master = pd.concat([prior_op, train_op], ignore_index = True)

print(f'\norders_master: {orders_master.shape}')
print(f'  prior rows:  {prior_op.shape[0]:,}')
print(f'  train rows:  {train_op.shape[0]:,}')
print(f'  total RAM:   {orders_master.memory_usage(deep=True).sum()/1e6:.1f} MB')

# Visualize top products
fig, axes = plt.subplots(1, 3, figsize = (20, 6))

# Top 20 products
top_prod = prior_op['product'].value_counts().head(20)
axes[0].barh(top_prod.index[::-1], top_prod.values[::-1], color = sns.color_palette('viridis', 20))
axes[0].set_title('Top 20 Products (Prior Orders)', fontsize = 12, fontweight = 'bold')
axes[0].set_xlabel('Order Count')

for i, v in enumerate(top_prod.values[::-1]):

    axes[0].text(v + 1000, i, f'{v:,}', va = 'center', fontsize = 7)

# Department breakdown
dept_counts = prior_op['department'].value_counts().head(12)
axes[1].bar(range(len(dept_counts)), dept_counts.values, color = sns.color_palette('rocket', len(dept_counts)))
axes[1].set_xticks(range(len(dept_counts)))
axes[1].set_xticklabels(dept_counts.index, rotation=40, ha='right', fontsize=9)
axes[1].set_title('Orders by Department', fontsize=12, fontweight='bold')
axes[1].set_ylabel('Order Count')

# Reorder rate by department
dept_reorder = prior_op.groupby('department')['reordered'].mean().sort_values(ascending=False).head(12)
bars = axes[2].barh(dept_reorder.index[::-1], dept_reorder.values[::-1], color = sns.color_palette('mako', len(dept_reorder)))
axes[2].axvline(0.5, color='red', linestyle='--', alpha=0.6, label='50% line')
axes[2].set_title('Reorder Rate by Department', fontsize=12, fontweight='bold')
axes[2].set_xlabel('Reorder Rate')
axes[2].legend()

for bar in bars:

    w = bar.get_width()
    axes[2].text(w + 0.005, bar.get_y() + bar.get_height()/2, f'{w:.1%}', va='center', fontsize=8)

plt.suptitle('Product & Category Landscape', fontsize=16, fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()

print(f'Overall reorder rate: {prior_op["reordered"].mean()*100:.1f}%')
print(f'Highest reorder dept: {dept_reorder.idxmax()} ({dept_reorder.max():.1%})')
print(f'Lowest reorder dept:  {dept_reorder.idxmin()} ({dept_reorder.min():.1%})')

# Visualize frequency of product categories
aisle_summary = prior_op.groupby('aisle').agg(order_count = ('order_id', 'count'), reorder_rate = ('reordered', 'mean')).reset_index().sort_values('order_count', ascending = False).head(30)

fig, ax = plt.subplots(figsize=(20, 8))

scatter = ax.scatter(aisle_summary['order_count'],
                     aisle_summary['reorder_rate'],
                     c = aisle_summary['reorder_rate'],
                     cmap = 'RdYlGn',
                     s = 100,
                     alpha = 0.8,
                     edgecolors = 'gray',
                     linewidth = 0.5)

for _, row in aisle_summary.iterrows():

    ax.annotate(row['aisle'], (row['order_count'], row['reorder_rate']), fontsize = 7, ha = 'left', va = 'bottom', alpha = 0.85)

plt.colorbar(scatter, ax=ax, label='Reorder Rate')
ax.set_xlabel('Total Orders (Prior)', fontsize=12)
ax.set_ylabel('Reorder Rate', fontsize=12)
ax.set_title('Top 30 Aisles: Volume vs Reorder Rate\n(high-right = popular & habitual)', fontsize = 13, fontweight='bold')
ax.axhline(prior_op['reordered'].mean(), color='gray', linestyle='--', alpha=0.5, label='Avg reorder rate')
ax.legend()
plt.tight_layout()
plt.show()

# Visualize cart size and user behavior patterns
fig, axes = plt.subplots(1, 3, figsize=(20, 5))

# Cart size distribution
cart_sizes = prior_op.groupby('order_id')['product_id'].count()
axes[0].hist(cart_sizes.clip(upper=50), bins=50, color='#FF5722', edgecolor='white', alpha=0.85)
axes[0].axvline(cart_sizes.mean(), color='black', linestyle='--', lw = 2, label = f'Mean: {cart_sizes.mean():.1f}')
axes[0].set_title('Cart Size Distribution', fontsize=13, fontweight='bold')
axes[0].set_xlabel('Items per Order (capped at 50)'); axes[0].set_ylabel('Orders')
axes[0].legend()

# Reorder rate by cart position
atco = prior_op.groupby('add_to_cart_order')['reordered'].mean()
atco = atco[atco.index <= 30]

axes[1].plot(atco.index, atco.values, marker='o', linewidth=2.5, color='#FF9800')
axes[1].fill_between(atco.index, atco.values, alpha=0.15, color='#FF9800')
axes[1].set_title('Reorder Rate by Cart Position', fontsize=13, fontweight='bold')
axes[1].set_xlabel('Add-to-Cart Position'); axes[1].set_ylabel('Reorder Rate')
axes[1].set_ylim(0, 1)
axes[1].annotate('First items\nare most habitual', xy=(1, atco.iloc[0]), xytext=(5, 0.85), arrowprops=dict(arrowstyle='->', color='gray'), fontsize=9)

# User reorder rate distribution
user_reorder = prior_op.groupby('user_id')['reordered'].mean()
axes[2].hist(user_reorder, bins=40, color='#3F51B5', edgecolor='white', alpha=0.85)
axes[2].axvline(user_reorder.mean(), color='red', linestyle='--', lw=2,
                label=f'Mean: {user_reorder.mean():.2f}')
axes[2].set_title('User Reorder Rate Distribution', fontsize=13, fontweight='bold')
axes[2].set_xlabel('Reorder Rate'); axes[2].set_ylabel('Number of Users')
axes[2].legend()

plt.suptitle('User Behavior Patterns', fontsize=16, fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()

print(f'Average cart size:                  {cart_sizes.mean():.1f} items')
print(f'Median cart size:                   {cart_sizes.median():.0f} items')
print(f'% users with reorder rate > 50%:    {(user_reorder > 0.5).mean()*100:.1f}%')
print(f'First-position reorder rate:        {atco.iloc[0]:.1%}')

## <a id="section-7"></a>7. Association Rule Mining (Market Basket Analysis)

We apply the **Apriori** algorithm to a stratified sample of prior orders to discover which products are frequently purchased together.

**Key metrics:**
- **Support** — fraction of baskets containing the itemset; a measure of how common the pair is
- **Confidence** — P(B | A), the probability B is bought given A is already in the basket
- **Lift** — confidence ÷ P(B alone); values > 1 indicate a genuine positive association beyond chance

**Sampling strategy:**
1. Draw 50,000 users from the large `prior` set
2. Use only each user's *most recent* prior order (most predictive of future behaviour)
3. Restrict the product space to the top-5,000 items to keep the boolean matrix tractable
4. Set `min_support = 0.01` (at least 1% of sample baskets) so item pairs are discoverable
5. Retain only rules with `lift > 1.0` — positive associations only

The resulting rule dictionaries (`rule_lookup`, `rule_single`) are used directly by **Strategy 3** (Association Rules recommender).

# Derive user features
user_order_enriched = prior_op.merge(data['orders'][['order_id','order_number','days_since_prior_order']], on = 'order_id', how = 'left', suffixes = ('','_o'))

user_stats = user_order_enriched.groupby('user_id').agg(total_orders          = ('order_id',                'nunique'),
                                                        total_items_purchased = ('product_id',              'count'),
                                                        unique_products       = ('product_id',              'nunique'),
                                                        avg_cart_size         = ('order_id', lambda x: x.count() / x.nunique()),
                                                        reorder_rate          = ('reordered',               'mean'),
                                                        avg_days_between      = ('days_since_prior_order',  'mean'),
                                                        std_days_between      = ('days_since_prior_order',  'std'),).reset_index()

user_stats['variety_ratio'] = (user_stats['unique_products'] / user_stats['total_items_purchased'])

print(f'User features shape: {user_stats.shape}')
print('\nUser statistics summary:')
display(user_stats[['total_orders','avg_cart_size','reorder_rate', 'avg_days_between','variety_ratio']].describe())

# Find user/product interactions
up_stats = user_order_enriched.groupby(['user_id','product_id']).agg(times_ordered     = ('order_id',            'count'),
                                                                     times_reordered   = ('reordered',            'sum'),
                                                                     avg_cart_position = ('add_to_cart_order',    'mean'),
                                                                     last_order_num    = ('order_number',          'max')).reset_index()

user_max_order = (data['orders'][data['orders']['eval_set'] == 'prior'].groupby('user_id')['order_number'].max().reset_index().rename(columns = {'order_number': 'max_order_num'}))

up_stats = up_stats.merge(user_max_order, on='user_id', how='left')
up_stats['orders_since_last'] = up_stats['max_order_num'] - up_stats['last_order_num']
up_stats['reorder_rate']      = up_stats['times_reordered'] / up_stats['times_ordered'].clip(lower=1)

# Recency-weighted score: high orders + high reorder rate + low gap
up_stats['reorder_score']     = (up_stats['times_ordered'] * up_stats['reorder_rate']) / (up_stats['orders_since_last'] + 1)

print(f'User-product interaction features: {up_stats.shape}')
print(f'Avg interactions per user: {len(up_stats)/up_stats["user_id"].nunique():.1f} products')
up_stats.head()

# Get a sample, increase for more comprehensive rules (takes longer)
rng = np.random.default_rng(100)
sample_uids = rng.choice(prior_op['user_id'].unique(), size = 50000, replace = False)

# Use the most recent prior order per sampled user (most predictive of future)
recent_prior_orders = (data['orders'][(data['orders']['user_id'].isin(sample_uids)) & (data['orders']['eval_set'] == 'prior')].sort_values(['user_id', 'order_number']).groupby('user_id').last().reset_index()[['user_id', 'order_id']])
sample_op = prior_op[prior_op['order_id'].isin(recent_prior_orders['order_id'])]

print(f'Sample baskets:        {sample_op["order_id"].nunique():,}')
print(f'Avg basket size:       {sample_op.groupby("order_id")["product"].count().mean():.1f} items')
print(f'Total unique products: {sample_op["product"].nunique():,}')

# Reduce the product space by filtering the top products
top_products = (sample_op['product'].value_counts().head(5000).index.tolist())
top_product_set = set(top_products)

# Filter each basket to only include top-N products
filtered_baskets = (sample_op[sample_op['product'].isin(top_product_set)].groupby('order_id')['product'].apply(list).tolist())

# Drop baskets that now have fewer than 2 items (no pairs possible)
filtered_baskets = [b for b in filtered_baskets if len(b) >= 2]

print(f'Baskets after filtering:       {len(filtered_baskets):,}')
print(f'Avg basket size (top-N only):  {np.mean([len(b) for b in filtered_baskets]):.1f} items')
print(f'Product space:                 {len(top_products):,} items')
print(f'\nMin support threshold (1%):    {int(0.01 * len(filtered_baskets)):,} baskets required')

# Perform apriori
te = TransactionEncoder()
te_array = te.fit_transform(filtered_baskets)
basket_df = pd.DataFrame(te_array, columns = te.columns_)

# Get frequencies
frequent_itemsets = apriori(basket_df, min_support = .01, use_colnames = True, max_len = 2)
frequent_itemsets['length'] = frequent_itemsets['itemsets'].apply(len)

# Mine the rules
rules = association_rules(frequent_itemsets, metric = 'confidence', min_threshold = 0.05)
rules = rules[rules['lift'] > 1.0].sort_values('lift', ascending = False).reset_index(drop = True)

# Summarize results
print(f'Frequent itemsets: {len(frequent_itemsets):,}')
print(f'  Singletons: {(frequent_itemsets["length"]==1).sum()}')
print(f'  Pairs:      {(frequent_itemsets["length"]==2).sum()}')
print(f'\nAssociation rules (lift > 1): {len(rules):,}')
print('\nTop 20 rules by lift:')
display(rules[['antecedents','consequents','support','confidence','lift']].head(20).assign(antecedents=lambda df: df['antecedents'].apply(lambda x: list(x)[0]), consequents = lambda df: df['consequents'].apply(lambda x: list(x)[0])))

# Visualize association rules
fig, axes = plt.subplots(1, 2, figsize=(20, 6))

# Scatter: support × confidence, coloured by lift
sc = axes[0].scatter(rules['support'], rules['confidence'], c = rules['lift'], cmap = 'YlOrRd', alpha = 0.7, s = 40, edgecolors = 'gray', linewidth = 0.3)
plt.colorbar(sc, ax = axes[0], label = 'Lift')
axes[0].set_xlabel('Support'); axes[0].set_ylabel('Confidence')
axes[0].set_title('Support × Confidence (colour = Lift)', fontsize=12, fontweight='bold')

# Top 15 rules by lift — horizontal bar
top15 = rules.head(15).copy()
top15['rule_label'] = top15.apply(lambda r: f"{list(r['antecedents'])[0][:22]} → {list(r['consequents'])[0][:22]}", axis=1)
bar_colors = sns.color_palette('YlOrRd', 15)
axes[1].barh(top15['rule_label'][::-1], top15['lift'][::-1], color=bar_colors)
axes[1].axvline(1.0, color='gray', linestyle='--', alpha=0.6, label='Lift = 1 (independent)')
axes[1].set_xlabel('Lift'); axes[1].set_title('Top 15 Rules by Lift', fontsize=12, fontweight='bold')
axes[1].legend(); axes[1].tick_params(axis='y', labelsize=8)

plt.suptitle('Market Basket — Association Rules', fontsize=15, fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()

# Build rule lookup dicts (used by prediction model) ant_frozenset → [(confidence, lift, consequent_name)]
rule_lookup = defaultdict(list)

for _, row in rules.iterrows():

    ant = frozenset(row['antecedents'])
    con = list(row['consequents'])[0]
    rule_lookup[ant].append((row['confidence'], row['lift'], con))

# single item → [(conf, lift, consequent, full_antecedent)]
rule_single = defaultdict(list)

for ant, recs in rule_lookup.items():

    for item in ant:

        for conf, lift, con in recs:

            rule_single[item].append((conf, lift, con, ant))

# Helper lookup dicts
pid_to_name = dict(zip(products['product_id'], products['product']))
name_to_pid = dict(zip(products['product'], products['product_id']))
pid_to_dept = dict(zip(products['product_id'], products['department']))

print(f'Rule lookup entries: {len(rule_lookup)}')
print(f'Single-item lookup:  {len(rule_single)} distinct items have rules')

fn(user_id, cart_sequence, K=10) → [product_id, ...]

# Develop the ground truth for model scoring
train_truth = (train_op.groupby('user_id')['product_id'].apply(set).reset_index().rename(columns = {'product_id': 'true_items'}))

# Simulate "current shopping session" using the LAST prior order per user,
last_prior_oids = (orders_slim[orders_slim['eval_set'] == 'prior'].sort_values(['user_id', 'order_number']).groupby('user_id')['order_id'].last().reset_index().rename(columns = {'order_id': 'last_oid'}))

last_prior_seq = (prior_op[prior_op['order_id'].isin(last_prior_oids['last_oid'])].sort_values(['order_id', 'add_to_cart_order']).groupby('order_id')['product_id'].apply(list).reset_index().rename(columns = {'order_id': 'last_oid', 'product_id': 'cart_sequence'}))

eval_df = (train_truth.merge(last_prior_oids, on = 'user_id').merge(last_prior_seq, on = 'last_oid', how = 'inner'))

# Reproducible subsample for fast evaluation across all strategies
eval_sample = eval_df.sample(n = min(3000, len(eval_df)), random_state = 100).reset_index(drop = True)

print(f"Evaluation set  : {len(eval_df):,} users")
print(f"Eval sample     : {len(eval_sample):,} users")
print(f"Avg true basket : {eval_sample['true_items'].apply(len).mean():.1f} items")
print(f"Avg cart length : {eval_sample['cart_sequence'].apply(len).mean():.1f} items")
eval_sample[['user_id','cart_sequence','true_items']].head(3)

# ─────────────────────────────────────────────────────────────────────────────
# Strategy 1 — Global Popularity Baseline
# ─────────────────────────────────────────────────────────────────────────────
# Recommend the most-ordered products globally.  No personalisation, no cart
# context — pure frequency signal.  Serves as the floor baseline.

POPULARITY_POOL = (product_stats.sort_values('order_count', ascending=False)['product_id'].head(300).tolist())

def s1_popularity(user_id, cart_sequence, K = 10, **_):

    """Top-K globally popular products not already in the cart."""
    in_cart = set(cart_sequence)
    return [p for p in POPULARITY_POOL if p not in in_cart][:K]

print("✅  S1 (Global Popularity) ready")
print(f"   Pool: top {len(POPULARITY_POOL)} products")
print(f"   Sample recs: {[pid_to_name.get(p,'?')[:25] for p in s1_popularity(0, [], K=5)]}")

# ─────────────────────────────────────────────────────────────────────────────
# Strategy 2 — Personal History
# ─────────────────────────────────────────────────────────────────────────────
# Rank the user's previously purchased products by reorder_score
# (frequency × reorder-rate / recency gap), then return the top-K
# not yet in the current cart.

user_history = (up_stats.sort_values(['user_id', 'reorder_score'], ascending=[True, False]).groupby('user_id')['product_id'].apply(list).to_dict())

def s2_personal(user_id, cart_sequence, K = 10, **_):

    """Top-K products from user's personal purchase history by reorder_score."""
    in_cart = set(cart_sequence)
    return [p for p in user_history.get(user_id, []) if p not in in_cart][:K]

coverage = sum(1 for uid in eval_sample['user_id'] if uid in user_history)
print("✅  S2 (Personal History) ready")
print(f"   History coverage : {coverage}/{len(eval_sample)} ({coverage/len(eval_sample):.1%})")

_u0 = eval_sample['user_id'].iloc[0]
_c0 = eval_sample['cart_sequence'].iloc[0]
print(f"   Sample recs (user {_u0}): {[pid_to_name.get(p,'?')[:22] for p in s2_personal(_u0,_c0,K=3)]}")

# ─────────────────────────────────────────────────────────────────────────────
# Strategy 3 — Association Rules  (cart-content-aware)
# ─────────────────────────────────────────────────────────────────────────────
# Every item currently in the cart fires its association rules.
# Consequents are scored by the SUM of (confidence × lift) across all
# triggering cart items, then ranked.  Falls back to personal history
# when the rule set yields fewer than K candidates.

# Build a fast name-keyed lookup: item_name → {consequent_name: agg_score}
assoc_lookup = defaultdict(lambda: defaultdict(float))

for ant_name, recs in rule_single.items():

    for conf, lift, con_name, _ in recs:

        assoc_lookup[ant_name][con_name] += conf * lift

def s3_rules(user_id, cart_sequence, K=10, **_):

    """Score candidates via association rules fired by the current cart."""
    in_cart_ids  = set(cart_sequence)
    in_cart_names = {pid_to_name.get(p, '') for p in cart_sequence}

    scores = defaultdict(float)

    for name in in_cart_names:

        for con_name, score in assoc_lookup.get(name, {}).items():

            pid = name_to_pid.get(con_name)

            if pid and pid not in in_cart_ids:

                scores[pid] += score

    ranked = sorted(scores, key=scores.get, reverse=True)

    if len(ranked) >= K:

        return ranked[:K]

    # Backfill with personal history when rules are sparse
    extra = [p for p in s2_personal(user_id, cart_sequence, K * 3) if p not in set(ranked)]

    return (ranked + extra)[:K]

print("✅  S3 (Association Rules) ready")
print(f"   Assoc lookup items : {len(assoc_lookup)}")
print(f"   Sample recs : {[pid_to_name.get(p,'?')[:22] for p in s3_rules(_u0,_c0,K = 3)]}")

# ─────────────────────────────────────────────────────────────────────────────
# Strategy 4 — Sequential Markov Chain  (O(N) single-pass, no loops)
# ─────────────────────────────────────────────────────────────────────────────
MAX_POS        = 20
MAX_SUCCESSORS = 100
MAX_POS_ITEMS  = 200
MAX_USER_HIST  = 50

print("Building Markov transition matrix…")
t0 = time.time()

# ── Step 1: extract + sort ────────────────────────────────────────────────────
arr  = prior_op[['order_id','product_id','add_to_cart_order']].to_numpy(dtype = 'int32')
arr  = arr[np.lexsort((arr[:,2], arr[:,0]))]

oids = arr[:,0]; pids = arr[:,1]; pos0 = arr[:,2] - 1
del arr; gc.collect()

# ── Step 2: transition pairs ──────────────────────────────────────────────────
same   = oids[:-1] == oids[1:]
prev_p = pids[:-1][same].astype('int32')
next_p = pids[1: ][same].astype('int32')
del same; gc.collect()

# Sort pairs so identical (prev,next) rows are adjacent → count with diff
order  = np.lexsort((next_p, prev_p))
prev_s = prev_p[order]; next_s = next_p[order]
del prev_p, next_p, order; gc.collect()

# Find group boundaries in O(N) — no per-node mask scan
boundaries = np.flatnonzero(np.diff(prev_s)) + 1
boundaries = np.concatenate([[0], boundaries, [len(prev_s)]])

# Count runs of identical (prev,next) using diff on next_s within each prev group
pair_counts = np.diff(
    np.concatenate([np.flatnonzero(
        np.concatenate([[True], (prev_s[1:] != prev_s[:-1]) | (next_s[1:] != next_s[:-1]), [True]])
    ), [len(prev_s)]])
)
# Unique (prev,next) pairs
keep = np.concatenate([[True], (prev_s[1:] != prev_s[:-1]) | (next_s[1:] != next_s[:-1])])
u_prev = prev_s[keep]; u_next = next_s[keep]
del prev_s, next_s, keep; gc.collect()

# Group boundaries on the unique pairs
grp_bounds = np.flatnonzero(np.diff(u_prev)) + 1
grp_bounds = np.concatenate([[0], grp_bounds, [len(u_prev)]])

trans_prob = {}
for i in range(len(grp_bounds) - 1):
    lo, hi = grp_bounds[i], grp_bounds[i+1]
    node = int(u_prev[lo])
    c = pair_counts[lo:hi]; t = u_next[lo:hi]
    if len(c) > MAX_SUCCESSORS:
        top = np.argpartition(c, -MAX_SUCCESSORS)[-MAX_SUCCESSORS:]
        c, t = c[top], t[top]
    total = c.sum()
    trans_prob[node] = {int(ti): float(ci/total) for ti, ci in zip(t, c)}

del u_prev, u_next, pair_counts, grp_bounds; gc.collect()
print(f"  trans_prob done  ({len(trans_prob):,} nodes)  {time.time()-t0:.1f}s")

# ── Step 3: position-popularity ───────────────────────────────────────────────
mask  = pos0 < MAX_POS
p_pos = pos0[mask].astype('int32'); p_pid = pids[mask].astype('int32')
del oids, pids, pos0, mask; gc.collect()

order2  = np.lexsort((p_pid, p_pos))
pp_s = p_pos[order2]; pid_s = p_pid[order2]
del p_pos, p_pid, order2; gc.collect()

keep2 = np.concatenate([[True], (pp_s[1:] != pp_s[:-1]) | (pid_s[1:] != pid_s[:-1])])
pc = np.diff(np.concatenate([np.flatnonzero(keep2), [len(pp_s)]]))
u_pos = pp_s[keep2]; u_pid = pid_s[keep2]
del pp_s, pid_s, keep2; gc.collect()

grp2 = np.flatnonzero(np.diff(u_pos)) + 1
grp2 = np.concatenate([[0], grp2, [len(u_pos)]])

pos_prob = {}
for i in range(len(grp2) - 1):
    lo, hi = grp2[i], grp2[i+1]
    pos = int(u_pos[lo])
    c = pc[lo:hi]; t = u_pid[lo:hi]
    if len(c) > MAX_POS_ITEMS:
        top = np.argpartition(c, -MAX_POS_ITEMS)[-MAX_POS_ITEMS:]
        c, t = c[top], t[top]
    total = c.sum()
    pos_prob[pos] = {int(ti): float(ci/total) for ti, ci in zip(t, c)}

del u_pos, u_pid, pc, grp2; gc.collect()

# ── Step 4: per-user reorder-score list (capped) ─────────────────────────────
user_rs_list = (up_stats
                .sort_values('reorder_score', ascending=False)
                .groupby('user_id').head(MAX_USER_HIST)
                .groupby('user_id')
                .apply(lambda g: list(zip(g['product_id'].tolist(),
                                          g['reorder_score'].tolist())))
                .to_dict())

print(f"✅  Markov chain built in {time.time()-t0:.1f}s")
print(f"   Source nodes            : {len(trans_prob):,} products")
print(f"   Avg successors per node : {np.mean([len(v) for v in trans_prob.values()]):.1f}")
print(f"   Positions tracked       : 0 – {MAX_POS-1}")

# Strategy 4 — Sequential Markov Chain inference function
def s4_markov(user_id, cart_sequence, K = 10, n_gram = 2, alpha = 0.4, beta = 0.25, **_):

    """
    Sequential Markov Chain recommender.

    Score(X) = Σ P(next=X | prev ∈ cart[-n_gram:])          [Markov]
             + α · P(X appears at cart position len(cart))   [position]
             + β · reorder_score(user, X)                    [personal]

    Parameters
    ----------
    cart_sequence : list of product_ids in add-to-cart order
    n_gram        : how many trailing items to use as context (default 2)
    alpha         : weight for the position-popularity signal
    beta          : weight for the user's personal reorder score
    """
    in_cart  = set(cart_sequence)
    next_pos = len(cart_sequence)
    context  = cart_sequence[-n_gram:] if len(cart_sequence) >= n_gram else cart_sequence

    scores = defaultdict(float)

    # (A) Markov transition scores from the last n_gram cart items
    for prev in context:
        for nxt, prob in trans_prob.get(prev, {}).items():
            if nxt not in in_cart:
                scores[nxt] += prob

    # (B) Position-specific popularity at the *next* cart slot
    capped_pos = min(next_pos, MAX_POS - 1)
    for pid, prob in pos_prob.get(capped_pos, {}).items():
        if pid not in in_cart:
            scores[pid] += alpha * prob

    # (C) Blend personal purchase affinity
    for pid, rs in user_rs_list.get(user_id, []):
        if pid not in in_cart and rs > 0:
            scores[pid] += beta * float(rs)

    ranked = sorted(scores, key=scores.get, reverse=True)
    if len(ranked) >= K:
        return ranked[:K]

    extra = [p for p in s2_personal(user_id, cart_sequence, K * 2) if p not in set(ranked)]
    return (ranked + extra)[:K]

# Apply function
print("✅  S4 (Sequential Markov Chain) ready")
recs4 = s4_markov(_u0, _c0, K=3)
print(f"   Sample recs : {[pid_to_name.get(p,'?')[:22] for p in recs4]}")
print()
print("Position signal demo — top 3 products per cart slot:")
print(f"{'Pos':>4}  {'#1 product':<30} {'#2 product':<30} {'#3 product':<30}")
print("─" * 97)

for pos in range(6):
    slot = pos_prob.get(pos, {})
    top3 = sorted(slot, key=slot.get, reverse=True)[:3]
    cols = [f"{pid_to_name.get(p,'?')[:26]} ({slot[p]:.2%})" for p in top3]
    while len(cols) < 3:
        cols.append("—")
    print(f"{pos:>4}  {cols[0]:<30} {cols[1]:<30} {cols[2]:<30}")