Tuesday, August 23, 2016

An end, and a beginning

How lucky I am to have something that makes saying goodbye so hard.
If you've been paying attention to my blog, I don't delve into personal stuff often. Or at all, really. This is a reasonably big time in my life, so I thought I'd break with "tradition" - much as a barely-active 5-year old blog can have, at least - and talk a little bit about myself.

For starters, I'm now a student of Computer Science at the University of Texas at Dallas. As I type this, the second day of class has come to an end, and I'm sitting in an empty residence hall lobby late at night; the only sounds I can hear are the air conditioning, my fingers on the keyboard, and the celebratory welcome banners brushing against the walls in time with the A/C. I'm still suffering from the stubborn vestiges of a cold I came down with over the past weekend that also took out several of my newfound friends and colleagues. Additionally, the internet has been out in my dorm room since I've moved in, so I've had to use the lobby Wifi for email and the like instead. Regardless, college life has been fun so far. Plenty of friends to hang out with, lots of campus events to go to, friendly faculty to network with - you get the idea. Contrary to popular opinion, there's more to life than what's on the internet. I've barely noticed I don't have a dorm connection except when I have to do something I can't do from my phone.

From a high school student's limited perspective, college is an interesting place. You're given enough freedom that you're basically in a loosely-padded training environment for being an adult. You're given opportunities to seriously succeed, and to seriously fail, both by your own hands. You're given the freedom to stay up at 2AM to go to Walmart to get milk, or to sit in a lobby blogging, if you want. You're free to make your own choices, and live with the consequences; there's relatively few instances where there is someone looking over your shoulder, telling you what you should and shouldn't do. For someone who has potentially lived their entire life with someone else at the wheel, that kind of freedom can be a very scary feeling, and a daunting adjustment. But enough about that.

For someone who lived at home with family their whole life - like me, for example - being away from family and old friends can be a bitter pill to swallow. For almost 2 decades, I grew used to being able to see parents and siblings when I got up, to them being there when I went to bed. I grew used to having conversational partners in my siblings that I could engage whenever I wanted, who held interests similar to mine. Being away from people that you've built such powerful connections with can be a difficult ordeal, indeed. But, it's something you have to learn to cope with. You call friends and family as often as you can, and visit when possible. You find new friends that you can trust and open up to. Maybe even discover that you have family members living nearby and visit them.
Eventually, you might lose these people too. If I get a Masters out of state, and decide not to move back to the Dallas/Richardson area, this whole process of loss will repeat. And I'll start from square 0, again. I wouldn't blame anyone in my shoes for not feeling a little depressed over the whole situation, for wondering whether or not it was worth it to build all those precious connections in the first place, only to painfully tear them all down again.
However, at the time, I know my feelings were real. I know that the memories of elated moments with friends and family were genuine, were not fake; that they were caused by me being sincerely happy to be with them in that instant. And those memories - those fleeting, ephemeral instants in time - stick with you forever, regardless of how long your friendships last. And nobody can take them away from you. I don't want to stop making them because I might be afraid the people involved might eventually leave me. It's a common occurrence, with an element of certainty to it: People drift away over time, and finally, die. But until the day that you yourself leave this earth, those memories will faithfully serve as a living testament that the people you cherished so dearly ever existed. And I think that's a beautiful thing.

So here's to making many more memories, with the many people I've met and will meet. To my parents, thank you. To my dear old group of friends, goodbye, I wish you all the best. And to all my fellow incoming freshmen: Congratulations.
Life is a continuous cycle of losses, you see. But in order to lose, you must first gain. And the greater the joy at your gain, the greater the sorrow will be at your loss. But as long as we have the memories of those happy times - indeed, because we have those memories - people are able to go on. 

Thursday, May 19, 2016

FuzzBuzz and the Art of Programming

Programming: It's as much an art as it is a science. The general distinction between art and science being the realm of subjectivity - in other words, while in the realm of science, "correctness" is still debated, nobody is under the illusion that there is more than one "correct" solution. Art, on the other hand, has no single "correct solution," though at the same time, the merits of each solution are generally weighed against each other solutions, debated, and so on.

Programming is a mix of both: There are certainly "solutions" - algorithms, programs, etc. - that can be objectively proven without a shadow of a doubt to be ineffective or outright incorrect. There is also the possibility of an algorithm that solves the solution, but is objectively inferior to another, such as an algorithm that runs in O(n) time versus one that runs in O(1) time. On the other hand, there is a fair amount of subjective nuance involved in arriving to a correct solution. Design methodologies, languages, and APIs all come and go in a technological blink of an eye, and each will have its pros and cons, its proponents and its skeptics.

Nobody - sane, at least - involved in all this is under the impression that there is One True Way to do things. You could lock several seasoned programmers up in separate rooms, all of whom subscribe to the exact same design methodologies and use the exact same programming languages, ask them to design a program, and they would all likely emerge with completely separate, and likely equally or near-equally satisfactory, solutions. So, without further ado, let's talk about a simple programming problem, and some possible solutions to solve it. At the end, we'll discuss for a quick minute about which of these solutions someone might actually end up using.

The problem in question is one I've named FuzzBuzz, which was definitely not a reference to an overused programming interview question. To solve FuzzBuzz, one must write a program that considers the numbers from 1 to 100, inclusive. For each number, if the number in question is even, the program must print "Fuzz." If the number is odd, the program must print "Buzz." If the number is a multiple of 3, the program should ignore its even or odd nature and print "FuzzBuzz" instead.

This is an intentionally simplified problem, both to make it easy to make multiple solutions, and to make the solutions themselves clearer. By the time you finish reading this sentence, I bet you'll probably have thought of at least one way to solve this problem, but let me go over a couple first.

First up is probably the one that came to everyone else's mind, just a simple restating of the problem's definition in code.

for x in xrange(1, 101): # range/xrange stops at the integer before the 2nd argument
    if x % 3 == 0:
        print "FuzzBuzz"
    elif x % 2 == 0:
        print "Fuzz"
    else:
        print "Buzz"

Not really a whole lot to talk about with this one; like I said earlier, it's probably the first one you thought up yourself - it was the first one I came up with, as well. Honestly, if this were a real-world problem, most people would (and probably should) stop here. But innovation never sprung from a contented mind, right?

So, for our next solution, let's limit ourselves in some way. The modulo operator is pretty central to the prior solution, so let's take that out next.

def is_multiple_of(number, mul):
    """Return True if number is multiple of mul, false otherwise.
    Okay, so here's how this works: Normally, Python - and most
    other programming languages - chops off the decimal part of the quotient
    if both terms are integers, i.e, integer division is performed. However,
    if one of the terms is a float, then the decimal part will be kept.
    Any number plus a decimal part is going to be greater than simply the number itself,
    so we compare the two. If number is in fact a multple of mul, then there will be
    no decimal part, and both sides of the expression will be equal."""
    if float(number) / mul == number / mul:
        return True
    else:
        return False


def multiple_of_three(number):
    return is_multiple_of(number, 3)


def multiple_of_two(number):
    return is_multiple_of(number, 2)
    
    
for x in xrange(1, 101):
    if multiple_of_three(x):
        print "FuzzBuzz"
    elif multiple_of_two(x):
        print "Fuzz"
    else:
        print "Buzz"

Still pretty straightforward. Not having access to the modulo operator means we had to basically reinvent one ourselves, though. But we could go further still, couldn't we? How about no floating-point math?

def is_multiple_of(number, mul):
    """Return True if number is multiple of mul, False otherwise.
    So again we're exploiting the properties of integer division.
    For any divisor, there are at least two pairs of two consecutive dividends that will return
    the exact same quotient under integer divison, and the smaller number in each
    is a multiple of the divisor. All we have to do is check that number
    is the smaller of the pair. We do that by seeing if the result changes
    if we subtract 1. If so, number is the smaller of the pair (i.e, number - 1
    is part of some other pair), so return True.
    Otherwise, we were given the larger of the pair, or alternatively,
    some completely different number, so return False.
    """
    if number / mul > (number - 1) / mul:
        return True
    else:
        return False


def multiple_of_three(number):
    return is_multiple_of(number, 3)


def multiple_of_two(number):
    return is_multiple_of(number, 2)
    
    
for x in xrange(1, 101):
    if multiple_of_three(x):
        print "FuzzBuzz"
    elif multiple_of_two(x):
        print "Fuzz"
    else:
        print "Buzz"


Now things are getting ever-so-slightly hairy. But let's get dangerous now. How about no Boolean logic whatsoever?

from collections import deque
sequence = deque(["Buzz", "Fuzz", "FuzzBuzz", "Fuzz", "Buzz", "FuzzBuzz"])


def next_in_sequence():
    """Return next string in FuzzBuzz sequence.
    The FuzzBuzz problem follows a pattern:
        * Odd
        * Even
        * Multiple of 3
        * Even
        * Odd
        * Multiple of 3
    All we have to do is keep track of where we are in the sequence.
    To accomplish this, we use a deque and a little bit of pushing and popping
    to keep from having to either pre-generate the entire sequence beforehand,
    or from having to use an iterator.
    """
    next = sequence.popleft()
    sequence.append(next)
    return next


for x in xrange(1, 101):
    print next_in_sequence()

Alright, now we're talking. Admittedly, you probably saw this one coming if you were running the programs alongside reading this article - once you recognize the pattern, this solution is pretty obvious. But let's make one final push: No modulo operator, no math, no Boolean logic, and no loops.

from collections import deque
import sys
# Python allows the user to manually set the recursion limit.
# So, we exploit this by setting it to 101, which simulates the number of
# loop iterations we'd execute if we were using a loop.
# Eventually, we'll exceed this number, and Python will throw
# a RuntimeError, essentially accomplishing the same thing as
# a regular for/while loop.
sys.setrecursionlimit(101)


sequence = deque(["Buzz", "Fuzz", "FuzzBuzz", "Fuzz", "Buzz", "FuzzBuzz"])


def next_in_sequence():
    """Print next string in FuzzBuzz sequence.
    This is identical to the deque solution in sequence.py, save for
    printing out the next string instead of returning it, and the recursion bit,
    so go see sequence.py for an explanation of what's going on here.
    """
    next = sequence.popleft()
    sequence.append(next)
    print next
    next_in_sequence()


try:
    next_in_sequence()
except RuntimeError:
    # swallow the eventual exception due to recursion taking one step too many
    pass

I feel now is a good time to stop and discuss the various solutions, now that we have an ample amount. Like I mentioned earlier on, if this were a real-world problem, I imagine most people using the first solution. It's clear, concise, and gets its point across without needing much in the way of hand-holding. It's easy to extend if we need to tackle additional multiples, as well.

Most of the rest of the solutions are pretty silly if we examine them without the restrictions we came up with. The modulo operator is a pretty useful tool for this problem, so it makes no sense to try to work around it, or reimplement it with our own code. I could see an argument being made for the non-recursive sequence solution - some might consider it more "elegant" than the original solution, though obviously that's up for debate.

Some might also think the sequence version is faster, considering the O(1) performance time of deque.popleft() and deque.append() (collections.deque is implemented as a doubly-linked list under the hood), but at least on my machine, the initial solution is faster when testing 10,000,000 numbers, completing in about 3.1 seconds versus 3.3 seconds for the sequence version. After some fiddling around, I was able to produce a variant on the sequence solution that ran in about 2.9 seconds on the same set:

from collections import deque
sequence = deque(["Buzz", "Fuzz", "FuzzBuzz", "Fuzz", "Buzz", "FuzzBuzz"])


# Binding oft-used functions to local scope results in a speed increase
# due to decreased variable lookup time
popleft = sequence.popleft
append = sequence.append


for x in xrange(1, 101):
    # Moving the function's code to the loop body removes the function call,
    # which actually increases performance slightly
    next = popleft()
    append(next)
    print next

By this point though, we've lost a fair amount of readability, which was one of the main reasons to use the sequence solution. On the upside, we have a reasonable increase in speed, which might be useful in a performance-critical application. On a side note, the performance of the other solutions is pretty abysmal in comparison; the modulo-less solution ran in about 8.5 seconds, whereas the float-less solution ran in about 6 seconds. As for the recursion-based solution, it segfaulted on my machine before it could actually complete the 10,000,000-iteration loop.

So, to summarize: Programming is about 50% art and 50% science; there's usually more than one demonstrably correct solution to the problem, and on top of that, there's often some fair room for debate about which of the solutions one should proceed with. We presented a simple programming problem, came up with some possible solutions for it, and discussed their pros and cons.

As an added bonus, I've set up a Github repository at http://github.com/DangerOnTheRanger/fuzzbuzz that contains all the solutions in this article, as well as reference output to test your own solutions with. If you come up with a solution you like, regardless of its performance or what language it's written in, send me a pull request, and I'll add it to the repo.