How to search for people among Pi and what's the point about Python

Colleagues, hello! Recently, I faced the challenge of playing free places on our course on Python development. Generally speaking, playing a few free places is easy. You can do it in literally two lines if you already have a list of participants:

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

And it is good, it works. Yes, and Occam's razor says that you should not produce an entity without the need. But there is a problem - it is not fun. Plus, this is how we selected the winners in the Java course . There, of course, you can't do it in two lines, you need a factory of factories of abstract classes and that’s all. I don't want to repeat anyway.

I would like to make a robot that chooses real balls from the basket, recognizes numbers and sends them to the chat via API (it's fun!), But this is not very fast. The solution should be meaningless, merciless and not particularly time-consuming. So the number pi came to mind. In general, my colleagues and I have inside joke about the perfect Pi-archiver. The essence is simple: to compress any data you just need to find the place in Pi number where they start and remember the position (+ length, of course).

Unsurpassed compression! It turns out that you can also look for Ustanik, in particular their emai'y among Pi, and consider the winner of those who will be the first. If you want to immediately to the point, then you can immediately go to notebook .
')
A short search on the Internet gave a lot of solutions for generating numbers of Pi, including Python (this wonderful resource is also in the process: www.angio.net/pi , I can not share). I honestly did not know that humanity is so concerned about this problem. Most popular solutions: Gauss – Legendre algorithm , Chudnovsky algorithm , BBP formula .

I chose the option that allows you to generate digits of the number infinitely, but does not give a predetermined number of digits:

 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*(rn*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) 

This is Comrade Gibbon's Spigot algorithm, which calculates the digits of Pi in streaming mode. All the details are in the research paper , which Haskell lovers will especially like.

It remains only to associate the emails of the participants with some numbers. At first I wanted to take md5 from the mail and then divide by module to get the number not more than the specified length. But this is somehow not very random, especially since you can pick up and register mail, which will be close enough to the beginning of Pi. Therefore, uncover the good old PSPP:

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

The length of the numbers is set in advance; the longer the number, the more difficult it is to find it in Pi, respectively. It remains only to write a search function.

 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] 

Kastuyu numbers in the line, I set pointers in their beginning, I generate digits Pi, if this digit is in this number, then I move the pointer forward, if not, I am looking for the greatest suffix of the current part of Pi, which is also a prefix of the desired number. When the number is found, I memorize it and the position, delete it from the search array. Just in case, I add a limiter in order not to go beyond the millionth figure and do some kind of logging of progress. ( Search in some marginal cases may not work correctly, but, fortunately, this is not very important for our purposes )

Finding two winners whose emails are mapped to six-digit numbers took about a minute on my machine. Profit!

As usual, “in battle” everything went not quite so smoothly. The drawing was launched in the live mode, the video was simultaneously broadcast from the computer, it was a little podnapryaglsya and the search took already 5 minutes, instead of one. But in order to further aggravate the situation, I inadvertently (honestly!) Restarted in the notebook the execution of the cell with the search for numbers after its successful execution for the first time. And notebook does not forgive errors, does not remember old values, performs cells synchronously. Nerves stretched like ropes. Fortunately, everything ended well, the winners were revealed, awarded, justice prevailed. Glory to the robots, glory to the Pi number!

By the way, there is another draw of places on the course on July 5 at 20-00. Want to touch the beautiful? Pass the test and register for the Open Day, there is time!