Pull to refresh
826.42
OTUS
Цифровые навыки от ведущих экспертов

Как искать людей в числе Пи и при чем тут Python

Reading time 4 min
Views 8K
Коллеги, привет! Недавно передо мной встала задача розыграть бесплатные места на нашем курсе по 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:
            return
        if d == self.s[self.p]:
            self.p += 1
        else:
            # find largerst prefix in num that is suffix in current part of Pi (dumb algorithm)
            pi_part = self.s[:self.p] + d
            self.p = 0
            for i in xrange(1, len(pi_part)):
                if self.s[:i] == pi_part[-i:]:
                    self.p = i
          

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. Хотите прикоснуться к прекрасному? Проходите тест и регистрируйтесь на День открытых дверей, время есть!
Tags:
Hubs:
+4
Comments 25
Comments Comments 25

Articles

Information

Website
otus.ru
Registered
Founded
Employees
101–200 employees
Location
Россия
Representative
OTUS