https://habrahabr.ru/company/otus/blog/332180/

• Программирование
• Python
• Блог компании Отус

Коллеги, привет! Недавно передо мной встала задача розыграть бесплатные места на нашем курсе по Python разработке. Вообще говоря, разыграть пару бесплатных мест — это просто. Можно сделать буквально в две строчки, если уже есть готовый список участников:

emails = pandas.read_csv("emails.csv")
emails.sample(NUM_WINNERS, random_state=SEED)

И это хорошо, это работает. Да и бритва Оккама говорит, что не стоит сущности плодить без необходимости. Но есть проблема — это не весело. Плюс, так мы уже выбирали победителей на курсе по Java. Там, конечно, за две строчки это не сделаешь, нужна фабрика фабрик абстрактных классов и вот это все. Все равно повторяться не хочется.

Хотелось бы сделать робота, который сам выбирает реальные шары из корзины, распознает номера и отправляет в чатик по API (это весело!), но это не очень быстро. Решение должно быть бессмысленным, беспощадным и не особо времязатратным. Так в голову пришло число Пи. Вообще у нас с коллегами есть inside joke про идеальный Пи-архиватор. Суть проста: чтобы сжать любые данные нужно лишь найти то место в числе Пи, где они начинаются и запомнить позицию (+длину, конечно).

Непревзойденное сжатие! Получается, что также можно искать устаников, в частности их emai’ы в числе Пи, и считать победителем тех, кто найдется первым. Если хотите сразу к сути, то можно тут же перейти в notebook.

Непродолжительный поиск в интернетах выдал множество решений по генерации цифр числа Пи, в том числе на Python (также в процессе находится этот прекрасный ресурс: www.angio.net/pi, — не могу не поделиться). Я, честно говоря, не знал, что человечество до такой степени обеспокоено этой проблемой. Самые популярные решения: Gauss–Legendre algorithm, Chudnovsky algorithm, BBP formula.

Я же выбрал тот вариант, который позволяет генерировать цифры числа бесконечно, а не выдает заранее определенное количество цифр:

def pi_digits():
    """generator for digits of pi"""
    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3
    while True:
        if 4 * q + r - t < n * t:
            yield n
            q, r, t, k, n, l = (10*q, 10*(r-n*t), t, k, (10*(3*q+r))/t-10*n, l)
        else:
            q, r, t, k, n, l = (q*k, (2*q+r)*l, t*l, k+1, (q*(7*k+2)+r*l)/(t*l), l+2)

Это Spigot algorithm товарища Гиббонcа, который вычисляет цифры числа Пи в потоковом режиме. Все подробности есть в research paper, которая особенно понравится любителям Haskell.

Остается только связать email’ы участников с какими-то числами. Сначала я хотел брать md5 от почты и потом делить по модулю, чтобы получить число не больше заданной длины. Но это как-то не очень случайно, тем более что можно подобрать и зарегистрировать почту, которая окажется достаточно близко к началу числа Пи. Поэтому расчехляем старый добрый ПГСЧ:

np.random.seed(SEED)
emails["num"] = np.random.randint(10 ** (NUM_DIGITS - 1), 10 ** NUM_DIGITS - 1, size=len(emails))

Длина чисел задается заранее, чем длиннее число, тем, соответственно, сложнее найти его в Пи. Осталось только написать функцию поиска.

class _Num(object):
    def __init__(self, n):
        self.n = n
        self.s = str(n)
        self.p = 0 # pointer in number string representation
        self.l = len(self.s)
 
    def move_p(self, d):
        if self.p < self.l and d == self.s[self.p]:
            self.p += 1
        else:
            self.p = 0 if d != self.s[0] else 1
 
    
def find_nums_in_pi(nums, first_n=None):
    MAX_POS = 10 ** 6
    pi_gen = pi_digits()
    first_n = first_n if first_n is not None else len(nums)
    _nums = [_Num(n) for n in nums]
    nums_pos = {}
    for pos in itertools.count():
        if pos % 1000 == 0:
            print "Current Pi position: %s. Nums found: %s" % (pos, len(nums_pos))
        if pos == MAX_POS:
            raise RuntimeError("Circuit breaker!")
        d = str(pi_gen.next())
        found_num = None
        for cur_num in _nums:
            cur_num.move_p(d)
            # whole number found
            if cur_num.p == cur_num.l:
                nums_pos[cur_num.n] = pos - cur_num.l + 1
                # found enough numbers
                if len(nums_pos) == first_n:
                    return nums_pos
                found_num = cur_num.n
        # create new search array without found number
        if found_num:
            _nums = [num for num in _nums if num.n != found_num]

Тут я решил пойти простым путем. Кастую числа в строки, устанавливаю указатили в их начала, генерирую цифры Пи, если данная цифра есть в данном числе, то сдвигаю указатель вперед, если нет, то возвращаю назад. Когда число найдено, запоминаю его и позицию, удаляю из массива поиска. На всякий случай добавляю ограничитель, чтобы не ходить дальше миллионной цифры и делаю какое-то логирование прогресса.

Найти двух победителей, email’ам которых сопоставлены шестизначные числа, заняло около минуты на моей машине. Профит!

Как водится, “в бою” все пошло не совсем так гладко. Розыгрыш запускался в live режиме, с компа одновременно транслировалось видео, он немного поднапрягся и поиск занял уже 5 минут, вместо одной. Но чтобы еще более накалить обстановку я ненароком (честно!) перезапустил в notebook’е выполнение cell’а с поиском чисел после его успешного выполнения в первый раз. А notebook ошибок не прощает, старые значения не запоминает, выполняет ячейки синхронно. Нервы натянулись, как канаты. К счастью, все закончилось хорошо, победители были выявлены, награждены, справедливость восторжествовала. Слава роботам, слава числу Пи!

Кстати, впереди еще один розыгрыш мест на курсе 5 июля в 20-00. Хотите прикоснуться к прекрасному? Проходите тест и регистрируйтесь на День открытых дверей, время есть!