Chris Griffith

The Birthday Paradox – The Proof is in the Python

This month is my wife’s, mother’s and my own birthday, all within a span of nine days. What are the odds of that? No idea, I’m no statistician. However, as a developer, I thought it would be fun to prove (or disprove?) the Birthday Paradox with some Python coding.

 

If you haven’t heard of the Birthday Paradox, it states that as soon as you have 23 random people in a room, there is a 50 percent chance two of them have the same birthday. Once the number of people in the room is at least 70, there is a 99.9 percent chance. It sound counter intuitive as it takes a full 366 (a full year + 1) people to have a 100% chance.

So instead of doing this from the statistical side, let’s do it from the experimentation angle. We are going to generate 23 random days in a year and see if there is a duplicate day.

First, we create a function that will return a list of N number of datetime objects within a given year. We will then use that list to see if there are duplicates within it. In the first case, with 23 people, exactly half the time we run this function there should be at least one duplicate date.

from random import randint
from datetime import datetime, timedelta

def random_birthdays(number_of_people):
    first_day_of_year = datetime(2017, 1, 1)
    return [first_day_of_year + timedelta(days=randint(0, 365))
            for _ in range(number_of_people)]

We need to run this function a lot of times to get an average of how often there is a duplicate.  We’ll create a function that runs it a thousand times and returns percentage average of duplicate found. (As a percentage is between 0 and 1, such as .50, we are multiplying it by 100 so that .5 looks like “50% chance” later.)

def determine_probability(number_of_people, run_amount=1_000):
    dups_found = 0
    for _ in range(run_amount):
        birthdays = random_birthdays(number_of_people)
        duplicates = set(x for x in birthdays if birthdays.count(x) > 1)
        if len(duplicates) >= 1:
            dups_found += 1

    return dups_found/run_amount * 100

Feel free to run it even more times than a 1000 for higher accuracy, max I tried was 100,000 which did have the most consistent results.

Finally, we add that last bit of code that actually calls the function and prints our findings.

if __name__ == '__main__':
    msg = ("{people} Random people have a {chance:.1f}%"
           " chance of having a birthday on the same day")
    for people in (23, 70):
        print(msg.format(people=people, chance=determine_probability(people)))

And wouldn’t ya know it, those fancy statisticians seem to be right.

23 Random people have a 50.4% chance of having a birthday on the same day
70 Random people have a 99.9% chance of having a birthday on the same day

At the top of the post, you saw a plot generated by calculating the first 100 people’s worth of probabilities, with red vertical markers at 23 and 70.  It is rather smooth due to increasing the run_amount to 10,000. Below is a plot of an entire 366 people, but only a 1000 runs per number of people.

 

To accomplish this, I used matplotlib and mixed in some multiprocessing to speed up the probability generation. Here is the final entire file.

from random import randint
from datetime import datetime, timedelta
from multiprocessing import Pool, cpu_count

import matplotlib.pyplot as plt


def random_birthdays(number_of_people):
    first_day_of_year = datetime(2017, 1, 1)
    return [first_day_of_year + timedelta(days=randint(0, 365))
            for _ in range(number_of_people)]


def determine_probability(number_of_people, run_amount=1000):
    dups_found = 0
    print(f"Generating day {number_of_people}")
    for _ in range(run_amount):
        birthdays = random_birthdays(number_of_people)
        duplicates = set(x for x in birthdays if birthdays.count(x) > 1)
        if len(duplicates) >= 1:
            dups_found += 1

    return number_of_people, dups_found/run_amount * 100


def plot_yearly_probabilities(max_people, vertical_markers=(23, 70)):
    with Pool(processes=cpu_count()) as p:
        percent_chances = p.map(determine_probability, range(max_people))

    plt.plot([z[1] for z in sorted(percent_chances, key=lambda x: x[0])])

    plt.xlabel("Number of people")
    plt.ylabel('Chance of sharing a birthday (Percentage)')

    for marker in vertical_markers:
        if max_people >= marker:
            plt.axvline(x=marker, color='red')

    plt.savefig("birthday_paradox.png")


if __name__ == '__main__':
    plot_yearly_probabilities(100)

 

Notice that our generate image lines near perfectly alongside the statically generated image on Wikipedia*.

Hope you enjoyed, and maybe even learned something alone the way!

* By Rajkiran g (Own work) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0) or GFDL (http://www.gnu.org/copyleft/fdl.html)], via Wikimedia Commons

 

Reusables – Part 2: Wrappers

Spice up your code with wrappers! In Python, a wrapper, also known as a decorator, is simply encapsulating a function within other functions.

@wrapper
def my_func(a, b=2):
    print(b)

@meta_decorator(foo="bar")
def my_other_func(**kwargs):
    print(kwargs)

In Reusables, all the wrappers take arguments, aka meta decorators, so you will at minimum have to end them with parens ()s. Let’s take a look at the one I use the most first.

time_it

import reusables

@reusables.time_it()
def test_func():
    import time, random
    time.sleep(random.randint(2, 5))

test_func()
# Function 'test_func' took a total of 5.000145769345911 seconds

time_it documentation
The message by default is printed. However it can also be sent to a log with a customized message. If log=True it will log to the Reusables logger, however you can also specify either a logger by name (string) or pass in a logger object directly.

reusables.add_stream_handler('reusables')

@reusables.time_it(log=True, message="{seconds:.2f} seconds")
def test_time(length):
    time.sleep(length)
    return "slept {0}".format(length)

result = test_time(5)
# 2016-11-09 16:59:39,935 - reusables.wrappers  INFO      5.01 seconds

print(result)
# slept 5

It’s also possible to capture time taken in a list.

@reusables.time_it(log='no_log', append=my_times)
def test_func():
    import time, random
    length = random.random()
    time.sleep(length)
    
for _ in range(10):
    test_func()
    
my_times
# [0.4791555858872698, 0.8963652232890809, 0.05607090172793505, 
# 0.03099917658380491,0.6567622821214627, 0.4333975642063024, 
# 0.21456404424395714, 0.5723555061358638, 0.0734819056269771, 
# 0.13208268856499217]

unique

The oldest wrapper in the Reusables library forces the output of a function to be unique, or else it will raise an exception or if specified, return an alternative output.

import reusables
import random


@reusables.unique(max_retries=100)
def poor_uuid():
    return random.randint(0, 10)


print([poor_uuid() for _ in range(10)])
# [8, 9, 6, 3, 0, 7, 2, 5, 4, 10]

print([poor_uuid() for _ in range(1000)])
# Exception: No result was unique

unique documentation

lock_it

A very simple wrapper to use while threading. Makes sure a function is only being run once at a time.

import reusables
import time


def func_one(_):
    time.sleep(5)


@reusables.lock_it()
def func_two(_):
    time.sleep(5)


@reusables.time_it(message="test_1 took {0:.2f} seconds")
def test_1():
    reusables.run_in_pool(func_one, (1, 2, 3), threaded=True)


@reusables.time_it(message="test_2 took {0:.2f} seconds")
def test_2():
    reusables.run_in_pool(func_two, (1, 2, 3), threaded=True)


test_1()
test_2()

# test_1 took 5.04 seconds
# test_2 took 15.07 seconds

log_exception

It’s good practice to catch and explicitly log exceptions, but sometimes it’s just easier to let it fail naturally at any point and log it for later refinement or debugging.

@reusables.log_exception()
def test():
    raise Exception("Bad")

# 2016-12-26 12:38:01,381 - reusables   ERROR  Exception in test - Bad
# Traceback (most recent call last):
#     File "<input>", line 1, in <module>
#     File "reusables\wrappers.py", line 200, in wrapper
#     raise err
# Exception: Bad

queue_it

Add the result of the function to the specified queue instead of returning it normally.

import reusables
import queue

my_queue = queue.Queue()


@reusables.queue_it(my_queue)
def func(a):
    return a


func(10)

print(my_queue.get())
# 10

New in 0.9

catch_it

Catch specified exceptions and return an alternative output or send it to an exception handler.

def handle_error(exception, func, *args, **kwargs):
    print(f"{func.__name__} raised {exception} when called with {args}")

@reusables.catch_it(handler=handle_error)
def will_raise(message="Hello"):
    raise Exception(message)


will_raise("Oh no!")
# will_raise raised Oh no! when called with ('Oh no!',)

retry_it

Once is never enough, keep trying until it works!

@reusables.retry_it(exceptions=(Exception, ), tries=10, wait=1)
def may_fail(dont_do=[]):
    dont_do.append("x")
    if len(dont_do) < 6:
        raise OSError("So silly")
    print("Much success!")

may_fail()
# Much success!

 

This post is a follow-up of Reusables – Part 1: Overview and File Management.

Exploit the work of others for profit! (Vega 64 Edition)

As I sit here, anxious for the new AMD Vega 64 to be released, I decide to keep myself busy writing some Python code….designed to text me as soon as a new “rx vega 64” search term showed up on Amazon (I have the patience of a child on Christmas Eve, so sue me.)

When writing code, I try to be as lazy efficient as possible. That means I look for other’s to do the hard part for me. Other people might phrase it more kindly like “don’t reinvent the wheel,” but let’s be real, you are receiving benefit for no cost. So next time a project saves your bacon, consider sending a little cash or cryptocoin to the dev(s). Or throw your hat into the open source community and provide dev work yourself, it’s a great way to learn a lot more about the coding community and gain a lot of experience along the way while still giving back.

Back to the Vega 64 stock tracking tool. It would totally be possible to do that all with the Python internals; using urllib and re to download and find stuff on the page, then using email to send a message to my phone’s SMS; but that would take forever, and is honestly stupid to do. There are much better tools for that at this point, like requests and BeautifulSoup , then using some gmail or other common email provider library.

But as Amazon is a rather big website with an API available, there are Python libraries for that API. There are also different ways to easily send a text message to yourself via online services, like twilo. In the end, I created the script using Python 3.6 on Windows (should be cross-platform compatible), and the libraries I used for this were:

python-amazon-simple-product-api
twilio
reusables
python-box

If you are interested in using this as well (comes as-is, no promises it works or won’t bite you) before using the script you will need to get AWS access keys and sign up for twilio, then fill in the appropriate variables at the top of the script.

from datetime import datetime
from time import sleep

from amazon.api import AmazonAPI
from twilio.rest import Client
from box import Box, BoxList
from reusables import setup_logger

amazon_access_key = "XXXXXXXXXXXXXXXXXXXX"
amazon_secret = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
amazon_associate_tag = "codecalamity-20" 

twilio_from = "+"  # Twilio phone number
twilio_to = "+"  # Phone number to text
twilio_key = "ACXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
twilio_secret = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"

search_product_keywords = "rx vega 64"
search_product_name_includes = "vega"
search_product_brand = "amd"
search_index = 'Electronics'
search_region = 'US'

log = setup_logger("vega")


def update(search, saved_data):
    new_prods = BoxList()
    for x in (product for product in search if
              search_product_name_includes in product.title.lower()
              and (search_product_brand in product.brand.lower() or
                   search_product_brand in product.manufacturer.lower())):
        if x.title not in saved_data:
            data = Box({"price": float(x.price_and_currency[0]),
                        "url": x.detail_page_url,
                        "updated": datetime.now().isoformat()})
            log.info(f"New item: {x.title} - {data}")
            new_prods.append((x.title, data))
            saved_data[x.title] = data

    saved_data.to_json(filename="products.json")
    return new_prods


def format_message(new_prods):
    product_list = [f"{prod[0]}-{prod[1].price}-{prod[1].url}"
                    for prod in new_prods]
    return f"New Prods: {', '.join(product_list)}"


def send_message(client, message):
    log.info(f"About to send message: '{message}'")
    client.messages.create(to=twilio_to,
                           from_=twilio_from,
                           body=message)


def main():
    amazon = AmazonAPI(amazon_access_key, amazon_secret, amazon_associate_tag)
    # Only search the first two pages to not spam the server
    products = amazon.search_n(2, Keywords=search_product_keywords,
                               SearchIndex=search_index, region=search_region)
    twilio_client = Client(twilio_key, twilio_secret)

    try:
        prods = Box.from_json(filename="products.json")
    except FileNotFoundError:
        prods = Box()

    while True:
        new_prods = update(products, prods)
        if new_prods:
            message = format_message(new_prods)
            send_message(twilio_client, message)
        sleep(60)


if __name__ == '__main__':
    main()

So now that possibly huge pure python standard library multifaceted application has turned into fifty lines of code (not counting imports / globals) designed to do nothing but feed my anxiety as efficiently as possible. Luckily it’s self testing to make sure it works, as it will find the result for the Vega Frontier Edition first, so if you chose to use it, make sure you get that text.

2017-08-07 22:09:23,938 - vega             INFO      About to send message: 
'New Prods: Radeon Vega Frontier Edition Liquid Retail-1579.48-
https://www.amazon.com/Radeon-Vega-Frontier-Liquid-Retail/dp/B072XLR2K7?SubscriptionId=AKIAIF3WXFESZ53UZKDQ&tag=codecalamity-20&linkCode=xm2&camp=2025&creative=165953&creativeASIN=B072XLR2K7'

Be warned that this may spam your phone a lot when the product does drop, and that the code doesn’t have a lot of safety checks as-is so may fail and stop reporting. It also doesn’t check if it is available to buy yet, just that the product page for the Vega 64 exists.

If you don’t want to have your own script constantly running, try out sites like nowinstock.net, as they have great options to text or email you when products are available.

Is it easier to ask for forgiveness in Python?

Yes, we are looking for graphic artists

Yes, we are looking for graphic artists

Is Python more suited for EAFP1 or LBYL2  coding styles? It has been debated across message boards, email chains, stackoverflow, twitter and workplaces. It’s not as heated as some other battles; like how spaces are better than tabs, or that nano is indisputably the best terminal editor 3; but people seem to have their own preference on the subject. What many will gloss over is the fact that Python as a language doesn’t have a preference. Rather, different design patterns lend themselves better to one or the other.

I disagree with the position that EAFP is better than LBYL, or “generally recommended” by Python – Guido van Rossum 4

If you haven’t already, I suggest taking a look at Brett Cannon’s blog post about how EAFP is a valid method with Python that programmers from other languages may not be familiar with. The benefits are EAFP are simple: Explicit code, fail fast, succeed faster, and DRY (don’t repeat yourself). In general I find myself using it more than LBYL, but that doesn’t mean it’s always the right way.

Use Case Dependent

First, a little code comparison to see the differences between them. Lets try to work with a list of list of strings. Our goal is that if the inner list is at least three items long, copy the third item into another list.

messages = [["hi there", "how are you?", "I'm doing fine"]]
out = []
 
# LBYL
if messages and messages[0] and len(messages[0]) >= 3:
    out.append(messages[0][2])

# EAFP
try:
    out.append(messages[0][2])
except IndexError as err:
    print(err)  # In the real world, this should be a logging `.exception()`

Both pieces of code are short and easy to follow what they are accomplishing. However, when there are at least three items in the inner list, LBYL will take almost twice the amount of time! When there aren’t any errors happening, the checks are just additional weight slowing the process down.

But if we prune the messages down to [["hi there", "how are you?"]]   then EAFP will be much slower, because it will always try a bad lookup, fail and then have to catch that failure. Whereas LBYL will only perform the check, see it can’t do it, and move on. Check out my speed comparison gist yourself.

Some people might think putting both the append and lookup in the same try block is wrong. However, it is both faster; as we only have to do the lookup once; and the proper way; as we are only catching the possible IndexError and not anything that would arise from the append.

The real takeaway from this is to know which side of the coin you area dealing with beforehand. Is your incoming data almost always going to be correct? Then I’d lean towards EAFP, whereas if it’s a crap shoot, LBYL may make more sense.

Sometimes one is always faster

There are some instances when one is almost always faster than the other (though speed isn’t everything). For example, file operations are faster with EAFP because the less  IO wait, the better.

Lets try making a directory when we are not sure if it was created yet or not, while pretending it’s still ye olde times and os.makedirs(..., exist_ok=True) doesn’t exist yet.

import os 

# LBYL 
if not os.path.exists("folder"):
    os.mkdir("folder")

# EAFP 
try:
    os.mkdir("folder")
except FileExistsError:
    pass

In this case, it’s always preferential to use EAFP, as it’s faster (even when executed on a m.2 SSD) , there are no side effects, and the error is highly specific so there is no need for special handling.

Be careful though, many times when dealing with files you don’t want to leave something in a bad state, in those cases, you would use LBYL.

What bad things can happen when you don’t ask permission?

Side effects

In many cases, if something fails to execute, the state of the program or associated files might have changed. If it’s not easy to revert to a known good state in the exception clause, EAFP should be avoided.

# DO NOT DO

with open("file.txt", "w") as f:
    try: 
        f.write("Hi there!\n") 
        f.write(message[3])   
    except IndexError: 
        pass  # Don't do, need to be able to get file back to original state

Catching too much

If you are wrapping something with except Exception or worse, the dreaded blank except:, then you shouldn’t be using EAFP (if you’re using black except: still, you need to read up more on that and stop it!)

# DO NOT DO

try:
    do_something()
except:  # If others see this you will be reported to the Python Secret Police
    pass 

Also, sometimes errors seem specific, like an OSError, but could raise multiple different child errors that must be parsed through.

# DO 
import errno

try:
    os.scandir("secret_files")
except FileNotFoundError: # A child of OSError
    # could be put as 'elif err.errno == errno.ENOENT' below
    log.error("Yo dawg, that directory doesn't exist, "
              "we'll try the backup folder")
except OSError as err:
    if err.errno in (errno.EACCES, errno.EPERM):
        log.error("We don't have permission to access that capt'n!"
                  "We'll try the backup folder")
    else:
        log.exception(f"Unexpected OSError: {err}") 
        raise err # If you don't expect an error, don't keep going. 
                  # This isn't Javascript

When to use what?

EAFP (Easier to Ask for Forgiveness than Permission)

  • IO operations (Hard drive and Networking)
  • Actions that will almost always be successful
  • Database operations (when dealing with transactions and can rollback)
  • Fast prototyping in a throw away environment

LBYL (Look Before You Leap):

  • Irrevocable actions, or anything that may have a side effect
  • Operation that may fail more times than succeed
  • When an exception that needs special attention could be easily caught beforehand

Sometime you might even find yourself using both for complex or mission critical applications. Like programming the space shuttle, or getting your code above that 500 lines the teacher wants.

 

First steps into GUI design with Kivy

Boring Background

I have always had in interest in making a local photo organization tool, that supports albums and tagging the way I want to do it. Maybe down the line allowing others to connect and use it too. So I started on one a few years ago, using what I knew best, Python REST back-end with Angular JS web based front end.

And it worked decently well.

However I was never happy with it’s performance past 10K images (and I am dealing with hundreds of thousands) and I tried halfway through development to switch to Angular 2. And everything blew up.

Now that I am older and wiser less stupid, I can face the fact that local data is best served with a desktop native application. It also removes the need for trying to keep up to date with ever changing web standards and libraries, in exchange for ones that might last through an entire development process (crazy thought, I know.)

Choosing Kivy

To be honest, I didn’t even think about using Kivy for a desktop application at first. I went straight to PySide, as it’s less bad licensing compared to PyQT. However, at the time, it didn’t want to play ball with a halfway modern python version, 3.5, the oldest I will create new content on, 3.7-dev is preferred or 3.6 for stable. I then looked into alternatives, such as wx and Kivy. Lets just say a quick view at both of their home pages tells you plenty about who you trust more with front end design off the bat.

Even thought Kivy seems to be aimed at more mobile development, including touch capabilities, I have found it to be extremely capable as a desktop application. It is also very appealing to me as it is no BS, MIT licensed.

First Steps

Just like any good python GUI, Kivy was a pain in the arse to install. On Windows, I just ended up grabbing the pre-compiled binaries from a well-loved unofficial binaries page. On my Linux VirtualBox, ended up having to disable 3D acceleration for it to start.

However, once I was able to start coding, it became stupid simple to be able to get content on the screen fast, and manipulate them. After about four hours of coding in one night, I had this:

An image viewer app that could display any directory of images. It included a preview bar that you could select past or upcoming images from, and control with either mouse clicks or keyboard presses. The actual code for it can be found here (just be aware it isn’t ready for the lime light yet, plenty of fixes to go.)

Application Layout

The application is composed of six widget classes overall. Here is a simple visual diagram of what they look like, and the Kivy widget classes they are using. (The padding is for visual ease only, not part of the program or to scale).

First Lessons learned

The two biggest issues I ran into were proper widget alignment, and the fact there is no built-in ‘on_hover’ like I am used to with CSS. I wrote up a quick class to do the latter, and including it here as it should be a drop-in for other’s kivy projects.

Kivy Mouse Over Code

from kivy.factory import Factory
from kivy.properties import BooleanProperty, ObjectProperty
from kivy.core.window import Window
from kivy.uix.widget import Widget


class MouseOver(Widget):

    def __init__(self, **kwargs):
        Window.bind(mouse_pos=self._mouse_move)
        self.hovering = BooleanProperty(False)
        self.poi = ObjectProperty(None)
        self.register_event_type('on_hover')
        self.register_event_type('on_exit')
        super(MouseOver, self).__init__(**kwargs)

    def _mouse_move(self, *args):
        if not self.get_root_window():
            return
        is_collide = self.collide_point(*self.to_widget(*args[1]))
        if self.hovering == is_collide:
            return
        self.poi = args[1]
        self.hovering = is_collide
        self.dispatch('on_hover' if is_collide else 'on_exit')

    def on_hover(self):
        """Mouse over"""

    def on_exit(self):
        """Mouse leaves"""


Factory.register('MouseOver', MouseOver)

Then you simply have to subclass it as well as the original widget class you want your object to be, and override the on_hover and on_exit methods.

class Selector(Button, MouseOver):
    """ Base class for Prev and Next Image Buttons"""

    def on_hover(self):
        self.opacity = .8

    def on_exit(self):
        self.opacity = 0

Widget alignment

Proper widget alignment was fun to figure out, because Kivy has both hard set properties width and height for objects, as well as a more lose size_hint feature. By default, everything has a size_hint of (1, 1)  , think of this as a percentage of the screen,  so (1,1) == (100% height, 100% width).

Simple right? Well, now add two of those objects in base layout. Some layouts, like BoxLayout and GridLayout will then make each of them 50% of the screen. Others, like FloatLayout will let each of them take up the entire layer, so one will be hidden. Even more fun, is to disable it, you manually have to set size_hint to (None, None).

Then on top of that, you can start mix and matching, hinting and absolutes with different elements on the screen. I chose to do that in this case, because I always wanted the preview bar of images at the bottom to be only 100px tall. But I wanted the large image to expand to the full height.  But if you set the bar to 100px tall, and leave the image (1,1), with just raising it’s starting position 100px from the bottom, it now is 100px off the top of the page. So now on top of the size_hint you need to add an on_size method, that will reduce the height of the image object every time the window is resized, like so:

    def on_size(self, obj, size):
        """Make sure all children sizes adjust properly"""
        self.image.height = self.height - 100
        self.next_button.pos = (self.width - 99, self.next_button.hpos)

You can notice we also have make sure that the right hand button always looks attached to the right hand of the screen. (Which I later learned could probably be accomplished with the RelitiveLayout, but am still unsure how that would work compared to everything else I already have with my FloatLayout.)

So the takeaway for me was, even without CSS, you’re going to have fun with alignment issues.

Next Steps

So I have am image viewer, great! But you want to organize images into more manageable groups. I want to create a folder / album view to be able to select at a higher level what you want to view.

After that I am sure I will want to create a database system to store tags, album info and thumbnails (for faster preview loading).