# Tugas GENETIKA — Pertemuan 4
# Target: GENETIKA = 7 5 14 5 20 9 11 1 (A=1 … Z=26)
# Jalankan: python3 tugas.py

import random

TARGET = [7, 5, 14, 5, 20, 9, 11, 1]
GENES = len(TARGET)
MAX_ALLELE = 26
MAX_FIT = GENES * MAX_ALLELE  # 208 = skor sempurna
POP_SIZE = 8
PROB_CO = 0.9
PROB_MUT = 0.2
MAX_GEN = 400
ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


# Huruf dari 8 angka (1=A … 26=Z). Dipakai di langkah 1 dan 6.
def letters(ind):
    return "".join(ALPHA[g - 1] for g in ind)


# Langkah 1. Jarak satu kata = jumlah |tebakan − target| di 8 kotak.
def jarak(ind):
    return sum(abs(g - t) for g, t in zip(ind, TARGET))


# Langkah 1. Skor = 208 − jarak. GENETIKA → jarak 0 → skor 208.
def skor(ind):
    return MAX_FIT - jarak(ind)


# Langkah 1. Populasi awal: undi 8 kata, tiap kotak angka 1–26.
def populasi_awal():
    return [
        [random.randint(1, MAX_ALLELE) for _ in range(GENES)]
        for _ in range(POP_SIZE)
    ]


# Langkah 2. Irisan kata i = skor i / jumlah skor. Rentang kumulatif 0–1.
def rentang_roulette(pop):
    fits = [skor(ind) for ind in pop]
    total = sum(fits)
    cursor = 0.0
    ranges = []
    for i, fit in enumerate(fits):
        cursor += fit / total
        ranges.append({"i": i, "hi": cursor})
    return ranges


# Langkah 2. Undi 0–1. Irisan yang memuat angka itu yang terpilih jadi induk.
def pilih_induk(pop, ranges, dart):
    for i, r in enumerate(ranges):
        if dart < r["hi"] or i == len(ranges) - 1:
            return pop[r["i"]][:]
    return pop[ranges[-1]["i"]][:]


# Langkah 2. Seleksi: empat pasangan, dua undian roulette per pasangan.
def seleksi(pop):
    ranges = rentang_roulette(pop)
    pasangan = []
    for _ in range(POP_SIZE // 2):
        a = pilih_induk(pop, ranges, random.random())
        b = pilih_induk(pop, ranges, random.random())
        pasangan.append((a, b))
    return pasangan


# Langkah 3. Crossover: undi p. Tukar kotak i–j hanya jika p < 0.9.
def crossover(a, b):
    p = random.random()
    if p >= PROB_CO:
        return a[:], b[:]
    i = random.randrange(GENES)
    j = random.randrange(GENES)
    if i > j:
        i, j = j, i
    c1, c2 = a[:], b[:]
    c1[i : j + 1] = b[i : j + 1]
    c2[i : j + 1] = a[i : j + 1]
    return c1, c2


# Langkah 4. Mutasi: tiap kotak anak, kalau undian < 0.2 ganti angka 1–26 yang lain.
def mutasi(ind):
    out = ind[:]
    for k in range(GENES):
        if random.random() < PROB_MUT:
            prev = out[k]
            nxt = random.randint(1, MAX_ALLELE)
            while nxt == prev:
                nxt = random.randint(1, MAX_ALLELE)
            out[k] = nxt
    return out


# Langkah 5. Elitisme: 8 induk + 8 anak = 16, urut skor, 8 teratas lolos.
def elitisme(induk, anak):
    gabung = induk + anak
    gabung.sort(key=skor, reverse=True)
    return [row[:] for row in gabung[:POP_SIZE]]


# Langkah 6. Kata skor tertinggi di populasi (untuk jejak).
def terbaik(pop):
    return max(pop, key=skor)


# Langkah 6. Ulang langkah 2–5 sampai skor 208 atau generasi ke-400.
def jalankan():
    pop = populasi_awal()
    champ = terbaik(pop)
    jejak = [(0, champ[:])]

    print("=== Langkah 1. Populasi awal ===")
    print(f"{'#':<3} {'Angka':<24} {'Kata':<10} {'Jarak':<7} Skor")
    for i, ind in enumerate(pop, 1):
        angka = " ".join(str(g) for g in ind)
        print(f"{i:<3} {angka:<24} {letters(ind):<10} {jarak(ind):<7} {skor(ind)}")
    print(
        "Generasi Terbaik 0:",
        letters(champ),
        "jarak",
        jarak(champ),
        "skor",
        skor(champ),
    )
    print()

    gen = 0
    for gen in range(1, MAX_GEN + 1):
        pasangan = seleksi(pop)
        anak = []
        for a, b in pasangan:
            c1, c2 = crossover(a, b)
            anak.append(mutasi(c1))
            anak.append(mutasi(c2))
        pop = elitisme(pop, anak)
        champ = terbaik(pop)
        last_ind = jejak[-1][1]
        if letters(champ) != letters(last_ind) or skor(champ) != skor(last_ind):
            jejak.append((gen, champ[:]))
        if skor(champ) == MAX_FIT:
            break

    print("=== Langkah 6. Jejak kata terbaik ===")
    print(f"{'Gen':<5} {'Angka':<24} {'Kata':<10} {'Jarak':<7} Skor")
    for g, ind in jejak:
        angka = " ".join(str(x) for x in ind)
        print(f"{g:<5} {angka:<24} {letters(ind):<10} {jarak(ind):<7} {skor(ind)}")
    print()
    if skor(champ) == MAX_FIT:
        print("Selesai di generasi " + str(gen) + ": GENETIKA, jarak 0, skor 208.")
    else:
        print(
            "Berhenti di generasi 400. Terbaik",
            letters(champ),
            "jarak",
            jarak(champ),
            "skor",
            skor(champ),
        )


# Rumus skor harus sama dengan walkthrough: sample → 162, target → 208.
def _cek():
    sample = [1, 7, 8, 19, 17, 5, 2, 3]
    assert letters(TARGET) == "GENETIKA"
    assert jarak(TARGET) == 0 and skor(TARGET) == 208
    assert skor(sample) == 162


if __name__ == "__main__":
    _cek()
    jalankan()