code

# ============================================
#  HACKMAN – Final Corrected Implementation (Colab)
# ============================================
import numpy as np, torch, torch.nn as nn, torch.optim as optim, random, math, re
from collections import defaultdict, deque, namedtuple, Counter
from tqdm import tqdm, trange

# ---------------- GLOBAL CONSTANTS ----------------
LETTERS = [chr(ord('A') + i) for i in range(26)]
idx = {c: i for i, c in enumerate(LETTERS)}

# ---------------- CLEAN WORD LOADER ----------------
def load_words(path):
    """Load and clean words: keep only alphabetic A-Z words."""
    words = []
    for line in open(path):
        w = line.strip().upper()
        if w and re.fullmatch(r'[A-Z]+', w):  # filters out spaces, symbols, etc.
            words.append(w)
    return words

# ---------------- HMM ----------------
class HMM:
    def _init_(self, alpha=1.0, max_len=20):
        self.alpha = alpha
        self.max_len = max_len
        self.models = {}

    def train(self, words):
        bylen = defaultdict(list)
        for w in words:
            if len(w) <= self.max_len:
                bylen[len(w)].append(w)
        for L, wl in bylen.items():
            self.models[L] = self._trainL(wl)
        return self

    def _trainL(self, wl):
        A, END = 26, 26
        init = np.zeros(A)
        trans = np.zeros((A, A + 1))
        for w in wl:
            s = [idx[c] for c in w]
            if not s:
                continue
            init[s[0]] += 1
            for a, b in zip(s, s[1:]):
                trans[a, b] += 1
            trans[s[-1], END] += 1
        init = (init + self.alpha) / (init.sum() + self.alpha * A)
        trans = (trans + self.alpha) / (trans.sum(1, keepdims=True) + self.alpha * (A + 1))
        return {'init': np.log(init), 'trans': np.log(trans)}

    def post(self, mask):
        L = len(mask)
        model = self.models.get(L) or self.models[min(self.models, key=lambda x: abs(x - L))]
        init, trans = model['init'], model['trans']
        emit = np.zeros((L, 26))
        for t, ch in enumerate(mask):
            if ch == '_':
                emit[t] = 0
            else:
                arr = np.full(26, -np.inf)
                arr[idx[ch]] = 0
                emit[t] = arr
        a = np.full((L, 26), -np.inf)
        a[0] = init + emit[0]
        for t in range(1, L):
            s = a[t - 1][:, None] + trans[:, :26]
            mv = np.max(s, 0)
            a[t] = emit[t] + mv + np.log(np.sum(np.exp(s - mv), 0))
        b = np.full((L, 26), -np.inf)
        b[-1] = 0
        for t in range(L - 2, -1, -1):
            r = trans[:, :26] + emit[t + 1][None, :] + b[t + 1][None, :]
            mv = np.max(r, 1)
            b[t] = mv + np.log(np.sum(np.exp(r - mv[:, None]), 1))
        m = np.exp(a + b)
        m /= m.sum(1, keepdims=True) + 1e-12
        return m

    def letter_probs(self, mask):
        m = self.post(mask)
        blanks = [i for i, c in enumerate(mask) if c == '_']
        if not blanks:
            return np.zeros(26)
        notp = np.prod(1 - m[blanks], 0)
        p = 1 - notp
        return p / (p.sum() + 1e-12)

# ---------------- ENVIRONMENT ----------------
class Hangman:
    def _init_(self, word, hmm, max_len=20):
        self.word = word.upper()
        self.hmm = hmm
        self.max_len = max_len
        self.reset()

    def reset(self):
        self.guessed = set()
        self.lives = 6
        self.mask = ['_'] * len(self.word)
        return self.state()

    def step(self, a):
        L = LETTERS[a]
        if L in self.guessed:
            return self.state(), -2, False, {'repeated': True}
        self.guessed.add(L)
        if L in self.word:
            for i, c in enumerate(self.word):
                if c == L:
                    self.mask[i] = L
            r = 0.5
        else:
            self.lives -= 1
            r = -1
        done = self.lives <= 0 or '_' not in self.mask
        if done and '_' not in self.mask:
            r += 10
        return self.state(), r, done, {'repeated': False}

    def state(self):
        ml = self.max_len
        enc = np.zeros((ml, 27))
        for i in range(ml):
            if i < len(self.mask):
                c = self.mask[i]
                enc[i, 26 if c == '_' else idx[c]] = 1
            else:
                enc[i, 26] = 1
        enc = enc.flatten()
        g = np.zeros(26)
        for c in self.guessed:
            g[idx[c]] = 1
        p = self.hmm.letter_probs(self.mask)
        return np.concatenate([enc, g, p, [self.lives / 6]])

# ---------------- BASELINES ----------------
def freq_order(corpus):
    cnt = Counter(''.join(corpus))
    order = [c for c, _ in cnt.most_common()]
    for c in LETTERS:
        if c not in order:
            order.append(c)
    return order

def eval_freq(test, order, hmm):
    w, wr, rep = 0, 0, 0
    for t in tqdm(test):
        e = Hangman(t, hmm)
        e.reset()
        for g in order:
            s, r, d, i = e.step(idx[g])
            if i['repeated']:
                rep += 1
            elif r < 0:
                wr += 1
            if d:
                if '_' not in e.mask:
                    w += 1
                break
    return w, wr, rep

def eval_hmm(test, hmm):
    w, wr, rep = 0, 0, 0
    for t in tqdm(test):
        e = Hangman(t, hmm)
        e.reset()
        while True:
            p = hmm.letter_probs(e.mask)
            for g in e.guessed:
                p[idx[g]] = 0
            a = int(np.argmax(p))
            s, r, d, i = e.step(a)
            if i['repeated']:
                rep += 1
            elif r < 0:
                wr += 1
            if d:
                if '_' not in e.mask:
                    w += 1
                break
    return w, wr, rep

# ---------------- DQN ----------------
Transition = namedtuple('T', ['s', 'a', 'r', 's2', 'd'])
class Replay:
    def _init_(self, cap=200000):
        self.buf = deque(maxlen=cap)
    def push(self, *x):
        self.buf.append(Transition(*x))
    def sample(self, b):
        x = random.sample(self.buf, b)
        return Transition(*zip(*x))
    def _len_(self):
        return len(self.buf)

class Net(nn.Module):
    def _init_(self, n):
        super()._init_()
        self.net = nn.Sequential(
            nn.Linear(n, 512), nn.ReLU(),
            nn.Linear(512, 256), nn.ReLU(),
            nn.Linear(256, 128), nn.ReLU(),
            nn.Linear(128, 26)
        )
    def forward(self, x):
        return self.net(x)


def train_dqn(corpus, episodes=3000, max_len=20):
    hmm = HMM().train(corpus)
    sdim = max_len * 27 + 26 + 26 + 1
    dev = 'cuda' if torch.cuda.is_available() else 'cpu'
    net, tar = Net(sdim).to(dev), Net(sdim).to(dev)
    tar.load_state_dict(net.state_dict())
    opt = optim.Adam(net.parameters(), lr=1e-4)
    buf = Replay()
    B = 128
    g = 0.99
    eps_s, eps_e = 1, 0.05
    eps_d = episodes * 0.8
    up = 2000
    steps = 0

    for ep in trange(episodes):
        eps = eps_e + (eps_s - eps_e) * math.exp(-ep / eps_d)
        e = Hangman(random.choice(corpus), hmm, max_len)
        s = e.reset()
        done = False

        while not done:
            steps += 1
            st = torch.tensor(s, dtype=torch.float32, device=dev).unsqueeze(0)
            with torch.no_grad():
                q = net(st).cpu().numpy().squeeze()
            for g_ in e.guessed:
                q[idx[g_]] = -1e9

            if random.random() < eps:
                cand = [i for i in range(26) if LETTERS[i] not in e.guessed]
                a = random.choice(cand) if cand else random.randrange(26)
            else:
                a = int(np.argmax(q))

            s2, r, done, _ = e.step(a)
            buf.push(s, a, r, s2, done)
            s = s2

            if len(buf) >= B:
                b = buf.sample(B)

                # ✅ Convert lists to numpy arrays first (faster + safer)
                sb = torch.tensor(np.array(b.s), dtype=torch.float32, device=dev)
                ab = torch.tensor(b.a, dtype=torch.long, device=dev).unsqueeze(1)
                rb = torch.tensor(b.r, dtype=torch.float32, device=dev).unsqueeze(1)
                s2b = torch.tensor(np.array(b.s2), dtype=torch.float32, device=dev)
                db = torch.tensor(b.d, dtype=torch.float32, device=dev).unsqueeze(1)  # float, not bool

                qv = net(sb).gather(1, ab)

                with torch.no_grad():
                    nxt = tar(s2b).max(1)[0].unsqueeze(1)
                    tgt = rb + g * (1.0 - db) * nxt   # ✅ ensure float arithmetic

                loss = nn.MSELoss()(qv, tgt)
                opt.zero_grad()
                loss.backward()
                opt.step()

            if steps % up == 0:
                tar.load_state_dict(net.state_dict())

    torch.save(net.state_dict(), 'dqn_final.pth')
    return net, hmm

def eval_dqn(net, hmm, test, max_len=20):
    dev = 'cuda' if torch.cuda.is_available() else 'cpu'
    w, wr, rep = 0, 0, 0
    for t in tqdm(test):
        e = Hangman(t, hmm, max_len)
        s = e.reset()
        done = False
        while not done:
            st = torch.tensor(s, dtype=torch.float32, device=dev).unsqueeze(0)
            with torch.no_grad():
                q = net(st).cpu().numpy().squeeze()
            for g in e.guessed:
                q[idx[g]] = -1e9
            a = int(np.argmax(q))
            s, r, done, i = e.step(a)
            if i['repeated']:
                rep += 1
            elif r < 0:
                wr += 1
        if '_' not in e.mask:
            w += 1
    return w, wr, rep

def score(w, total, wr, rep):
    sr = w / total
    return sr * total - wr * 5 - rep * 2, sr

# =========================================================
# Load Data & Run Baselines
corpus = load_words('corpus.txt')
test = load_words('test.txt')

hmm = HMM().train(corpus)
order = freq_order(corpus)

print("→ Frequency baseline")
fw, fwg, fr = eval_freq(test, order, hmm)
print("→ HMM-greedy baseline")
hw, hwg, hr = eval_hmm(test, hmm)
print("→ DQN training (short demo)")

net, hmm = train_dqn(corpus, episodes=1000, max_len=20)
dw, dwg, dr = eval_dqn(net, hmm, test)

for name, (w, wr, rep) in {'Freq': (fw, fwg, fr), 'HMM': (hw, hwg, hr), 'DQN': (dw, dwg, dr)}.items():
    fs, sr = score(w, len(test), wr, rep)
    print(f"{name}: Score={fs:.2f}, SuccessRate={sr*100:.2f}%  Wrong={wr} Repeats={rep}")