Fizz Buzz

The infamously simple FizzBuzz problem.

Reportedly a high percentage of programmer applicants can't solve this quickly.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

A deep dive on this problem has been done in jest many times, e.g., deliberate over-engineering or code golf. But in all seriousness, let's consider what's the most Pythonic solution. A truncated version of the common solution:

In [1]:
for num in range(1, 16):
    if num % 5 == 0 and num % 3 == 0:
        print('FizzBuzz')
    elif num % 3 == 0:
        print('Fizz')
    elif num % 5 == 0:
        print('Buzz')
    else:
        print(num)
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

Naturally interview questions tend to focus on output, e.g. print, but that's no reason to skip over basic abstractions or data structures. First, this could be written as a generator, to decouple the print operation and parametrize the numeric range. Alternatively, Python has such strong iterator support that it could also be just a function, ready to be mapped. So let's reframe the basic solution as:

In [2]:
def fizzbuzz(stop):
    for num in range(1, stop):
        if num % 5 == 0 and num % 3 == 0:
            yield 'FizzBuzz'
        elif num % 3 == 0:
            yield 'Fizz'
        elif num % 5 == 0:
            yield 'Buzz'
        else: 
            yield str(num)

' '.join(fizzbuzz(16))
Out[2]:
'1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz'

Even at this size, it's already violating DRY, or the Rule of 3. Clearly the same logic is being repeated with different data.

In [3]:
def fizzbuzz(stop):
    items = (15, 'FizzBuzz'), (3, 'Fizz'), (5, 'Buzz')
    for num in range(1, stop):
        yield next((text for div, text in items if num % div == 0), str(num))

' '.join(fizzbuzz(16))
Out[3]:
'1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz'

However, that variation had to introduce the concept of the least common multiple. Even in such a trivial problem, there's a subtlety in how one interprets requirements. The final directive to output "FizzBuzz" can be seen as a mere clarification of the previous directives; certainly not a coincidence. Making this the more obvious solution:

In [4]:
def fizzbuzz(stop):
    for num in range(1, stop):
        text = ''
        if num % 3 == 0:
            text += 'Fizz'
        if num % 5 == 0:
            text += 'Buzz'
        yield text or str(num)

' '.join(fizzbuzz(16))
Out[4]:
'1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz'

Arguably that insight is more important, because its duplication grows exponentially, not linearly. There's a 2**N sized case statement to handle N cases, luckily N == 2. Adding just one more directive for the number 7 would make the basic solution unwieldy.

And of course both approaches can be combined.

In [5]:
def fizzbuzz(stop):
    items = (3, 'Fizz'), (5, 'Buzz')
    for num in range(1, stop):
        yield ''.join(text for div, text in items if num % div == 0) or str(num)

' '.join(fizzbuzz(16))
Out[5]:
'1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz'

So is that over-engineered? This author would argue that both deduplication and decoupling logic from data are worth observing. So maybe at this size the final version isn't necessary, but surely the basic version is not the most Pythonic.

Cheryl's Birthday

How to solve the Cheryl's Birthday puzzle programmatically.

  1. Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gave them a list of 10 possible dates:
     May 15     May 16     May 19
    June 17    June 18
    July 14    July 16
    August 14  August 15  August 17
  2. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.
  3. Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.
  4. Bernard: At first I don't know when Cheryl's birthday is, but I know now.
  5. Albert: Then I also know when Cheryl's birthday is.
  6. So when is Cheryl's birthday?

As with the pytudes solution, the goal is to solve the puzzle in code. A different approach is taken here though, for simplicity and extensibility.

The first step is to model the data. A set of Date objects is suitable to represent the current possible dates. Since datetime.date objects require a year, a minimal collections.namedtuple is used instead.

In [1]:
from typing import NamedTuple

DATES = ['May 15',    'May 16',    'May 19',
        'June 17',   'June 18',
        'July 14',   'July 16',
      'August 14', 'August 15', 'August 17']

class Date(NamedTuple):
    month: str
    day: str

    def __repr__(self):
        return ' '.join(self)  # pretty printing
DATES = {Date(*date.split()) for date in DATES}
DATES
Out[1]:
{August 14,
 August 15,
 August 17,
 July 14,
 July 16,
 June 17,
 June 18,
 May 15,
 May 16,
 May 19}

As is typical of these kinds of puzzles, it assumes all participants have perfect Theory of Mind. That is, each participant making a statement is applying their private knowledge to what is publicly known, and assuming everyone else will do the same. With that in mind, the claims made fall into 3 categories:

  • I know ...
  • I don't know ...
  • They don't know ...

The temporal variations "now" and "at first" can be modeled by the current set of dates. Any claim then can be implemented functionally in this form:

In [2]:
def claim(field: str, dates: set) -> set:
    """Return subset of possible dates which would make the claim true.
    
    :param field: the field known by the claimant
    :param dates: the current set of dates publicly known
    """

So what does it mean for Albert or Bernard to "know" the correct date? It would mean applying their knowledge of the month or day leaves only one possibility. The "I know ..." function therefore groups and filters for uniqueness.

In [3]:
import collections

def known(field, dates):
    """Return subset of possible dates which would make the claim "I know ..." true."""
    counts = collections.Counter(getattr(date, field) for date in dates)
    return {date for date in dates if counts[getattr(date, field)] == 1}

# test what is already publicly known
assert known('month', DATES) == set()
known('day', DATES)
Out[3]:
{June 18, May 19}

To implement "I don't know ...", known could be parametrized with a different predicate (> 1), or simply use set.difference. "I don't know ..." is so trivial it's arguably not worth the abstraction.

In [4]:
def unknown(field, dates):
    """Return subset of possible dates which would make the claim "I don't know ..." true."""
    return dates - known(field, dates)

The challenging part is what does it mean for Albert to claim Bernard doesn't know. All dates that would be knowable to Bernard must clearly be excluded, but Albert would have to exclude them based on his knowledge of the month. So "They don't know ..." is similar to unknown, but the exclusion is based on a different field.

In [5]:
def unknowable(field, dates):
    """Return subset of possible dates which would make the claim "They don't know ..." true."""
    other, = set(Date._fields) - {field}
    exclude = {getattr(date, field) for date in known(other, dates)}
    return {date for date in dates if getattr(date, field) not in exclude}

This is sufficient to simply walk through the statements, one at a time.

In [6]:
# Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.
dates = unknown('month', DATES)
assert dates == DATES  # already public known
dates = unknowable('month', dates)
dates
Out[6]:
{August 14, August 15, August 17, July 14, July 16}
In [7]:
# Bernard: At first I don't know when Cheryl's birthday is, but I know now.
assert dates.isdisjoint(known('day', DATES))  # already claimed by Albert
dates = known('day', dates)
dates
Out[7]:
{August 15, August 17, July 16}
In [8]:
# Albert: Then I also know when Cheryl's birthday is.
known('month', dates)
Out[8]:
{July 16}

Exactly one date is left, indicating success. Now the succinct in-lined version, with no superfluous statements.

In [9]:
known('month',                        # Albert: I know
    known('day',                      # Bernard: I know
        unknowable('month', DATES)))  # Albert: Bernard doesn't know
Out[9]:
{July 16}