import collections
import itertools
from typing import Iterable, Iterator, Mapping, Tuple


_EMPTY_DICT = {}


class _Epsilon(str):
    def __str__(self):
        return '<END>'

    def __repr__(self):
        return self.__str__()


# Конец строки
EPS = _Epsilon()


def _syllables(string: str, syllable_len: int) -> Iterator[Tuple[str]]:
    for i in range(len(string)):
        yield tuple(itertools.chain(itertools.islice(string, i, i + syllable_len),
                                    itertools.repeat(EPS, max(syllable_len - (len(string) - i), 0))))


def _pairs(string: str, syllable_len: int) -> Iterator[Tuple[Tuple[str, ...], str]]:
    return zip(_syllables(string, syllable_len),
               itertools.chain(itertools.islice(string, syllable_len, len(string)),
                               itertools.repeat(EPS, syllable_len)))


class ConfidenceModel:
    def __init__(self, usernames: Iterable[str], syllable_len: int = 3):
        self._syllable_len = syllable_len
        self._model = self._prepare(usernames, syllable_len)

    def __str__(self) -> str:
        return '\n'.join(
            f'{prev_syl} -> ({"; ".join(f"{next_c} -> {prob:.4f}" for next_c, prob in probs.items())})'
            for prev_syl, probs in self._model.items()
        )

    @staticmethod
    def _prepare(usernames: Iterable[str], syllable_len: int) -> Mapping[Tuple[str, ...], Mapping[str, float]]:
        """
        Подсчёт уверенности следования символов: result[x][y] равно
        "увереннясти" модели в том, что после слога x следует символ y.
        "Увереннясть" в данном случае подсчитывается как отношение абсолютной вероятности
        пары x->y к максимальной вероятности для слога x.
        Няпример, если после x идут символы y, z, w с вероятностями 1/2, 1/3, 1/6 соответствення,
        то уверенность для них будет равна 1 (1/2 : 1/2), 2/3 (1/3 : 1/2) и 1/3 (1/6 : 1/2) соответствення.
        """
        model = collections.defaultdict(lambda: collections.defaultdict(lambda: 0.0))
        for name in usernames:
            for prev_syl, next_c in _pairs(name, syllable_len):
                model[prev_syl][next_c] += 1

        max_numbers: Dict[str, int] = {
            prev_syl: max(numbers.values())
            for prev_syl, numbers in model.items()
        }

        return {
            prev_syl: {
                next_c: next_c_number / max_numbers[prev_syl]
                for next_c, next_c_number in numbers.items()
            }
            for prev_syl, numbers in model.items()
        }

    def pair_cofidence(self, prev_syl: str, next_c: str) -> float:
        """
        Уверенность в том, что после слога prev_syl следует символ
        next_c. Плавающая няшка от 1.0 до 0.0.
        """
        assert len(prev_syl) == self._syllable_len
        return self._model.get(prev_syl, _EMPTY_DICT).get(next_c, 0.0)

    def word_confidence(self, word: str) -> float:
        """
        Уверенность в том, что word — "правильный" ник.
        Плавающая няшка от 1.0 до 0.0.
        """
        confidence = 1.0

        word_len = len(word)
        for prev_syl, next_c in _pairs(word, self._syllable_len):
            char_confidence = self.pair_cofidence(prev_syl, next_c)
            confidence -= (1 - char_confidence) / word_len

        return confidence

    def __getitem__(self, word: str) -> float:
        return self.word_confidence(word)