1"""
  2[Title/Звание]
  3Neko Optimizer: Детерминистична Котка в Недетерминиран Свят
  4
  5[Description/Обрисовка]
  6Battle Cats е мобилна игра, в която хвърляш котки срещу извънземни, демони,
  7богове и в крайна сметка пространствено-времевия континуум. Проблемът е гача системата -
  8плащаш виртуална (понякога реална) валута и получаваш случайна котка. Или не
  9получаваш. Или получаваш Basic Cat за 42-ри пореден път, вместо Sexy Legs Cat или
 10Hatsune Miku, Baki, Chun-Li, или Pikotaro защото Battle Cats се съревновава с Fortnite по брой колаборации.
 11
 12Тази наука се оказва тривиална. Ponos (разработчикът) ползва XOR-shift
 13псевдослучаен генератор - три операции, реверс-инженерени от общността:
 14
 15    x ^= (x << 13) & 0xFFFFFFFF
 16    x ^= (x >> 17)
 17    x ^= (x << 15) & 0xFFFFFFFF
 18
 19Това е целият "рандом". Три реда. ФМИ домашните имат по-сложен entropy модел...
 20Познавайки началната стойност (seed-а), можем да предскажем всяко бъдещо
 21теглене за всички банери едновременно - защото всички банери споделят един
 22и същ seed. Теглене на всеки банер придвижва позицията с едно.
 23godfat.org е сайт, построен върху reverse-engineered RNG-то на играта,
 24който показва пълната последователност от тегления за даден seed. Ние го ползваме като извор на данни.
 25Въпросът "откъде и кога да тегля за тези котки с тези ресурси" е комбинаторен проблем върху граф от състояния.
 26
 27[Functionalities/Надарености]
 281. Паралелен скрейпинг на банери
 29   aiohttp изтегля всички активни банери едновременно от bc.godfat.org.
 30   Едновременно, защото имаме asyncio, а не AbstractBannerRequestHandlerFactory.
 31   BeautifulSoup парсва HTML таблиците в Python dataclass обекти. Резултатите се кешират локално.
 32
 332. Граф на състоянията и A* търсене
 34   Всяко теглене е преход в граф. Всяко състояние е четворка:
 35       (pull_position, tickets_left, catfood_draws, frozenset(намерени_котки))
 36
 37   pull_position - позицията в seed последователността, споделена между
 38   всички банери.
 39   tickets_left - безплатни тегления, изразходват се преди catfood.
 40   catfood_draws - брой оставащи catfood тегления (catfood // 150), защото
 41   1347 и 1349 catfood са едно и също нещо - и двете дават 8 тегления.
 42   frozenset - само целевите котки от wishlist-а. Hashable, защото е ключ в
 43   речника на алгоритъма. За n цели имаме 2^n подмножества - експоненциално -
 44   ще предупреждаваме потребителя.
 45
 46   Преди търсенето строим lookup таблица:
 47       next_wanted[banner][position] -> (steps_away, cat_name, cost)
 48   O(1) справка по време на търсене. Heuristic-ът: минимална цена до следваща
 49   целева котка през всички банери от текущата позиция. Admissible - не
 50   надценява - следователно A* е коректен и оптимален.
 51
 523. Beam Search режим
 53   За нетърпеливите - пазим само top-K най-обещаващи пътя.
 54   Като A* ама с по-малко гаранции и повече скорост.
 55   Ще го използваме вместо A* при повече от 7-8 желани котки. Друг вариант
 56   е да използвам Beam Search за намиране на горна граница за A* и така да подобрим
 57   A* алгоритъма.
 58
 594. Subset резултати
 60   Ако ресурсите не стигат за всички цели, приложението автоматично показва
 61   оптималния вариант за всяко подмножество - 3 от 4 цели, 2 от 4, всяка
 62   поотделно. Етапите на скръбта, сортирани по цена.
 63
 645. Wishlist и колекция от котки
 65   SQLite база с всички котки. Маркираш кои имаш. При избор на банери
 66   приложението предлага само котките, които нямаш. Seed-ът се запазва
 67   между сесии - единственото, което запазваме, защото е единственото,
 68   което не се сменя при всяко теглене, той само се придвижва.
 69
 70[Milestones/Възлови точки]
 71- Scraper модул: aiohttp паралелно изтегляне + BeautifulSoup парсинг на
 72  HTML таблици + JSON кеш
 73- Data models: dataclasses за Banner, State, Pull, Path - типизирано и
 74  четимо без AbstractXorShiftGeneratorFactoryImpl
 75- Graph builder: конструиране на граф от RNG изход; track-switch логика
 76  (при дублиращ се rare позицията прескача от A на B track)
 77- Heuristic precomputation: next_wanted lookup таблица за всеки банер
 78  преди търсенето
 79- A* search: heapq priority queue, admissible heuristic, frozenset tracking
 80- Beam Search: top-K вариант без гаранция за оптималност
 81- Subset solver: итерация по подмножества на целите, запазване на best
 82  result за всяко
 83- SQLite модул: котка колекция, wishlist, seed persistence
 84- Django views, forms, templates: валидация на входа, ORM за базата
 85- Frontend: HTML/CSS/JS - без React, без TypeScript, колкото по-малко толкова по-добре
 86- Тестове: pytest върху RNG, graph builder и A* с известни seed комбинации;
 87  unittest.mock за изолиране на HTTP заявките
 88- Като бонуси може да се развие да не ползва bc.godfat.org;
 89  да се развие самостоятелно RNG реимплементация (XOR-shift) и теглене на данни от играта
 90
 91
 92[Estimate in man-hours/Времеоценка в човекочасове]
 93- Scraper + кеш: 20 часа
 94- Data models + graph builder: 20 часа
 95- A* + Beam Search: 35 часа
 96- Subset solver: 15 часа
 97- SQLite колекция: 15 часа
 98- Django views + forms + templates: 20 часа
 99- Frontend: 25 часа
100- Тестове: 20 часа
101- Debugging защо Kasli пак не е на позиция 42: ∞
102
103Общо: ~170 часа
104
105[Usage of technologies/Потребление на технологии]
106- Django: ORM за котка колекция и wishlist, forms за валидация на
107  потребителски вход, вградена тестова инфраструктура, май е по-добре
108  от Flask в този случай, но ще разбера когато вече е късно
109- aiohttp + asyncio: паралелно изтегляне на банери
110- BeautifulSoup4: парсинг на godfat HTML таблици
111- heapq: stdlib priority queue за A*
112- sqlite3: stdlib, котка база данни
113- dataclasses: чисти модели без Java enterprise trauma
114- pytest + unittest.mock: тестване на детерминистичен алгоритъм -
115  ще си добавя като бонус задача да намеря някой на който би му било приятно това
116- HTML + CSS + Vanilla JS: frontend
117- GitHub: ще пуллна пранк и ще го кача в GitLab
118
119P.S.
120Нито една котка няма да пострада по време на разработката. Но curiosity may have killed the student developer.
121"""