Skip to content

Instantly share code, notes, and snippets.

@fvicente fvicente/denise.py
Last active Sep 13, 2015

Embed
What would you like to do?
Denise’s birthday problem solution (in Python)
# -*- coding: utf-8 -*-
from collections import defaultdict
# (dd, mmm, yyyy)
dates = [
(17, "Feb", 2001),
(13, "Mar", 2001),
(13, "Apr", 2001),
(15, "May", 2001),
(17, "Jun", 2001),
(16, "Mar", 2002),
(15, "Apr", 2002),
(14, "May", 2002),
(12, "Jun", 2002),
(16, "Aug", 2002),
(13, "Jan", 2003),
(16, "Feb", 2003),
(14, "Mar", 2003),
(11, "Apr", 2003),
(16, "Jul", 2003),
(19, "Jan", 2004),
(18, "Feb", 2004),
(19, "May", 2004),
(14, "Jul", 2004),
(18, "Aug", 2004),
]
# Albert = mmm
# Bernard = dd
# Cheryl = yyyy
dd = 0
mmm = 1
yyyy = 2
def my_filter(dates, what_i_know, what_other_knows):
# count repetitions
other_counter = defaultdict(int)
for d in dates:
other_counter[d[what_other_knows]] += 1
# group
others_by_me = defaultdict(list)
for d in dates:
others_by_me[d[what_i_know]].append(d[what_other_knows])
possible = []
for k, v in others_by_me.iteritems():
if len(filter(lambda x: other_counter[x] > 1, v)) == len(set(v)):
possible.append(k)
return filter(lambda x: x[what_i_know] in possible, dates)
# Albert: I don’t know when Denise’s birthday is, but I know that Bernard does not know.
dates = my_filter(dates, mmm, dd)
# Bernard: I still don’t know when Denise’s birthday is, but I know that Cheryl still does not know.
dates = my_filter(dates, dd, yyyy)
# Cheryl: I still don’t know when Denise’s birthday is, but I know that Albert still does not know.
dates = my_filter(dates, yyyy, mmm)
print dates
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.