#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
static constexpr int K = 56;
static constexpr int S = 65536; // symbols: 1..65535
static constexpr int T = 1 << 18; // trigram hash bins (262144)
// Tunables
static constexpr double ALPHA1 = 0.25; // unigram smoothing
static constexpr double ALPHA3 = 0.25; // trigram smoothing
static constexpr double BETA = 1.0; // prior smoothing (avoid log(0))
static constexpr double W3 = 0.90; // weight for trigram score vs unigram
// Unigram model
static uint32_t cnt1[K][S];
static uint32_t tot1[K];
static uint32_t types1[K];
static uint32_t ex[K];
static bitset<S> seen1[K];
// Trigram model (hashed)
static uint32_t cnt3[K][T];
static uint32_t tot3[K];
static uint32_t types3[K];
static bitset<T> seen3[K];
static inline uint32_t h3(uint32_t a, uint32_t b, uint32_t c) {
// Fast-ish mix for 3 ints, output in [0, T)
uint32_t x = a * 0x9e3779b1u;
x ^= b + 0x85ebca6bu + (x << 6) + (x >> 2);
x ^= c + 0xc2b2ae35u + (x << 6) + (x >> 2);
x ^= x >> 16;
x *= 0x7feb352du;
x ^= x >> 15;
return x & (T - 1);
}
static inline void learn(int L, const int E[100]) {
ex[L]++;
// unigrams
for (int i = 0; i < 100; i++) {
int x = E[i];
tot1[L]++;
if (!seen1[L].test(x)) {
seen1[L].set(x);
types1[L]++;
}
cnt1[L][x]++;
}
// trigrams
for (int i = 0; i + 2 < 100; i++) {
uint32_t id = h3((uint32_t)E[i], (uint32_t)E[i + 1], (uint32_t)E[i + 2]);
tot3[L]++;
if (!seen3[L].test(id)) {
seen3[L].set(id);
types3[L]++;
}
cnt3[L][id]++;
}
}
void excerpt(int E[100]) {
// Pre-hash trigrams once
uint32_t tri[98];
for (int i = 0; i < 98; i++) {
tri[i] = h3((uint32_t)E[i], (uint32_t)E[i + 1], (uint32_t)E[i + 2]);
}
int bestL = 0;
double bestScore = -1e300;
for (int L = 0; L < K; L++) {
// Prior (smoothed)
double score = log((double)ex[L] + BETA);
// --- unigram log-likelihood with "UNK bucket" ---
double denom1 = (double)tot1[L] + ALPHA1 * ((double)types1[L] + 1.0);
score -= 100.0 * log(denom1);
for (int i = 0; i < 100; i++) {
int x = E[i];
if (seen1[L].test(x)) score += log((double)cnt1[L][x] + ALPHA1);
else score += log(ALPHA1);
}
// --- trigram log-likelihood (hashed) ---
double score3 = 0.0;
double denom3 = (double)tot3[L] + ALPHA3 * ((double)types3[L] + 1.0);
score3 -= 98.0 * log(denom3);
for (int i = 0; i < 98; i++) {
uint32_t id = tri[i];
if (seen3[L].test(id)) score3 += log((double)cnt3[L][id] + ALPHA3);
else score3 += log(ALPHA3);
}
score += W3 * score3;
if (score > bestScore) {
bestScore = score;
bestL = L;
}
}
int correct = language(bestL);
learn(correct, E);
}
