Category Archives: How To

Quick and Dirty Word Counting in JavaScript

Here’s an interesting problem that came up today during my Gradesolve development: counting the number of words in a particular div. It’s remarkably simple to do so (approximately), efficiently, and correctly. I pass this method the results of a $(“#myelement”).text() call to jQuery:

function wordCount(bodyText){
	var split = bodyText.split(/ |\n|-/);
	var count = 0;
	for (var i = 0; i < split.length; i++){
		if (split[i] != "") count++;
	}
	return count;
}

This returns a result very close to that returned by LibreOffice. It also runs in O(n) (and Θ(n) and Ω(n)). On my hyperthreading-enabled, 3.6GHz Pentium 4 test PC, it took about 0.76ms to count the words in a 400-word document. That means counting the words in a 100,000-word novel would take 190ms or so (not including any memory allocation time) even on a relatively old machine. In other words, it’s quick!

Creating Profiles with Django-registration

As part of developing Hawgrade, I’m learning the Django framework. That seemed like a noble idea about a week ago, and I’m practically competent already, but I have run into several snags so far. Major snags. Hair-pulling snags. One of the big ones was how to create a profile while simultaneously registering a user with django-registration 1.0 (FYI: I am using Python 2.7.4 with Django 1.5.1 on Ubuntu 13.04 “Raring Ringtail” x86). I’ve decided to do this post because I saw about a million questions about this topic on StackOverflow. This tutorial assumes that you have already installed django-registration and have included it in your urls.py file such that you access the django-registration app in your accounts/ url:

urlpatterns = patterns('',
    # ...
 
    url(r'^accounts/', include('registration.backends.default.urls')),
 
    # ...
)

We’re going to do the following:

  1. Define a model for our profile.
  2. Define a registration form that inherits from registration.forms.RegistrationForm.
  3. Attach to the django-registration user_registered signal so we know when the user registers. We save the user’s profile in the callback.
  4. Modify urls.py to use our custom registration view.

And now, we get to the Python! We’ll start in models.py. Our example profile stores whether or not a user is human.

class ExUserProfile(models.Model):
    user = models.ForeignKey(User, unique=True)
    is_human = models.BooleanField()
 
    def __unicode__(self):
        return self.user

Next, we need the custom registration form. If you don’t already have a file named forms.py in your app, make one. You’re going to make a custom form.

from registration.forms import RegistrationForm
from django import forms
 
class ExRegistrationForm(RegistrationForm):
    is_human = forms.ChoiceField(label = "Are you human?:")

After the form, we need to attach to the user_registered signal. This is easily accomplished. We’re going to put the method in our models.py file, because, well…I’m new to this…the Django documentation says so!

from registration.signals import user_registered
 
def user_registered_callback(sender, user, request, **kwargs):
    profile = ExUserProfile(user = user)
    profile.is_human = bool(request.POST["is_human"])
    profile.save()
 
user_registered.connect(user_registered_callback)

The last step is the simplest one: editing the urls in urls.py so that users can actually access your cool new registration form. It is REALLY IMPORTANT to put your new entry BEFORE the django-registration include entry.

from YOUR_APP.forms import ExRegistrationForm
from registration.backends.default.views import RegistrationView
 
urlpatterns = patterns('',
 
    # ...
 
    url(r'accounts/register/$', 
        RegistrationView.as_view(form_class = ExRegistrationForm), 
        name = 'registration_register'),
 
    url(r'^accounts/', include('registration.backends.default.urls')),
 
    # ...
)

This code should be fairly extensible–even if you’re not very familiar with Django. One thing I have noticed is that the documentation is very thorough. Good luck!

Computational Chemistry is the Spice of Life

Actually, no, it isn’t. It’s pretty darn interesting, though.

Since AP Chemistry ran out of things to do (since we took the AP test), my teacher decided to assign our class a project: come up with a way to relate chemistry to your future career field. Easy, I thought. MIT has Course 6-7 (computational biology), so some sort of chemistry equivalent (computational chemistry) must exist somewhere on the Internet. As it turned out, I was spot on. Computational chemistry is big.

I started looking at computational chemistry software. All of it carried a steep learning curve and a steeper price tag, and I couldn’t really think of much high-level research, since I just finished AP Chemistry. Instead, I decided to take matters into my own hands. I thought it might be interesting to do some “exploration” around the Ideal Gas Law. At first, the goal of my project was simply to show that PV did indeed equal nRT. After I finished the first step, I started looking into why (hint: gas molecules aren’t very big). After that, it dawned on me that I could calculate an approximate value of R, the Universal Gas Constant.

What’s more, I wrote my program in Python:

#!/usr/bin/env python3
# Computational chemistry: does PV = nRT?
# Copyright (c) 2013 John Parsons. All rights reserved.
import sys
import random
import math
import copy
 
class Particle:
    """Gas molecule."""
    def __init__(self, vel, pos):
        """Creates a new object instance. Vel: (xVelocity, yVelocity, zVelocity). Pos = (x, y, z) coordinates."""
        # Set up variables
        self.velocity = vel
        self.position = pos
 
    def getListOfDistances(self, allParticlesInTank):
        """Gets a sorted list of distances between the current particle and all other particles. allParticlesInTank: list of all other particles."""
 
        particles = [x for x in allParticlesInTank if x.velocity != self.velocity and x.position != self.position] # Get a shallow copy of the particle list and remove the current particle
        particleDistances = [] # List of tuples that stores distances
 
        for particle in particles: # Loop through particles
            distance = 0
 
            # Quick way of implementing 3D distance formula
            for x in range(3):
                distance += (self.position[x] - particle.position[x])** 2
 
            distance = distance ** 0.5 # Take the square root
 
            particleDistances.append((particle, distance)) # Add the particle - distance tuple to the list
 
        return sorted(particleDistances, key = lambda x:x[1]) # Return particles sorted by their distance from the current particle
 
 
# Shameless self-promo        
print("compchem.py -- Copyright (c) 2013 John Parsons")
print("Compares simulated gas pressure with the Ideal Gas Law.")
# Print usage if user doesn't know what he's doing
if len(sys.argv) < 7:
    print("USAGE: python compchem.py TEMPERATURE_IN_KELVIN MOLAR_MASS_IN_GRAMS NUMBER_OF_PARTICLES ITERATIONS ATOMIC_RADIUS_PICOMETERS INTERMOLECULAR_COLLISIONS_TRUE-FALSE")
    print("EX: python compchem.py 300 16.00 1000 1000 200 True")
    exit()
 
# Constants / calculations to make the later code more verbose
AVOGADRO_NUMBER = 6.022 * (10 ** 23)
CUBE_SIDE_WIDTH = 1000000 # Bounds of simulation, in nanometers
SURFACE_AREA_M = (6 * (CUBE_SIDE_WIDTH ** 2)) * 10**-18 
NUMBER_OF_PARTICLES = int(sys.argv[3]) # User-defined number of particles to play with
GAS_CONSTANT = 8.3144621 # R
GAS_TEMPERATURE = float(sys.argv[1]) # T
GAS_MOLAR_MASS = float(sys.argv[2]) # M (grams -- note that we must convert to KG for momentum!)
GAS_PARTICLE_MASS = GAS_MOLAR_MASS / AVOGADRO_NUMBER # Convenient mass of single particle
GAS_SPEED = (3 * GAS_CONSTANT * GAS_TEMPERATURE / (GAS_MOLAR_MASS / 1000)) ** 0.5 # (3rt/m)^.5, root-mean-square velocity of gas
TANK_VOLUME = CUBE_SIDE_WIDTH ** 3 # Volume of container in nm^3, used later.
SIMULATOR_ITERATIONS = int(sys.argv[4])
ATOMIC_RADIUS = float(sys.argv[5]) # In picometers = 10**-12m
INTERMOLECULAR_COLLISIONS = False
if sys.argv[6].lower() == "true": # Whether or not to check for collisions between molecules
    INTERMOLECULAR_COLLISIONS = True
 
 
# Print all the simulation parameters (calculated and hard-coded) in a nicely formatted manner
print("Simulation paramaters:\r\n\tGAS_SPEED = " + str(GAS_SPEED) + " m/s\r\n\tGAS_MOLES = " + str(NUMBER_OF_PARTICLES / AVOGADRO_NUMBER) + " moles\r\n\tTANK_VOLUME = " + str(TANK_VOLUME) + " nm^3\r\n\tATOMIC_RADIUS = " + str(ATOMIC_RADIUS) + " pm\r\n\tCHECK_INTERMOLECULAR_COLLISIONS = " + str(INTERMOLECULAR_COLLISIONS) + "\r\n\tSIMULATION_TIME = " + str(SIMULATOR_ITERATIONS * 10**-8) + " s")
 
# Apply ideal gas law: num particles/Avogadro = n; GAS_CONSTANT = R, GAS_TEMPERATURE = T, tank_volume * 10**-24 = tank volume in m^3
IDEAL_PRESSURE = ((NUMBER_OF_PARTICLES / AVOGADRO_NUMBER) * GAS_CONSTANT * GAS_TEMPERATURE) / (TANK_VOLUME * (10 ** -27))
print("\r\nIdeal Gas Law calculated pressure: " + str(IDEAL_PRESSURE) + " Pa\r\n")
 
def velocityVectorWithSpeed(speed):
    """Creates a velocity vector with random direction and specified speed."""
    x = random.randint(-500, 500) # Create random vector components
    y = random.randint(-500, 500)
    z = random.randint(-500, 500)
    magnitude = (x**2 + y**2 + z**2)**0.5 # Magnitude of vector
    unitVector = (x/magnitude, y/magnitude, z/magnitude)
 
    return ([i * speed for i in unitVector]) # Return vector such that its magnitude is the specified speed
def randomPosition():
    """Generates a random tuple (x, y, z) that stores a position."""
    return ([random.randint(0, CUBE_SIDE_WIDTH) for x in range(3)])
 
particles = [] # list of particles
 
# Create all our cute little particles
for i in range(0, NUMBER_OF_PARTICLES):
    particles.append(Particle(velocityVectorWithSpeed(GAS_SPEED), randomPosition()))
 
sumOfMomenta = 0 # Used for storing total impulse imparted to walls of container
print("Simulating: 0/" + str(SIMULATOR_ITERATIONS) + "\r", end = "")
sys.stdout.flush() # Force printing
 
# Now run the simulation -- each iteration will represent 10^-8 seconds
for ii in range(0, SIMULATOR_ITERATIONS): # Do some number of 10**-8 second iterations (as defined by user)
    if ii % 100 == 0: # Make it pretty as hell
        print("Simulating: " + str(ii) + "/" + str(SIMULATOR_ITERATIONS) + "\r", end="")
        sys.stdout.flush() # Make it actually print
 
    for particle in particles: # Loop through all the particles
        repositionVector = ([x * 10 for x in particle.velocity]) # x m/s * 10**9 nm/m * 10**-8 s/iteration = nm/iteration
 
        # Loop through and change positions
        for i in range(3):
            particle.position[i] = particle.position[i] + repositionVector[i] # Adjust particle position
            if particle.position[i] >= CUBE_SIDE_WIDTH or particle.position[i] <= 0: # Check to see if we need to change direction
                particle.velocity[i] = particle.velocity[i] * -1 # We do! Now we need to figure out how much impulse is imparted
                if particle.position[i] >= CUBE_SIDE_WIDTH: # Prevent the particle from being turned around again by putting the particle where it should really be.
                    particle.position[i] = CUBE_SIDE_WIDTH - (particle.position[i] - CUBE_SIDE_WIDTH) 
                else:
                    particle.position[i] = -particle.position[i]
                # p = mv (mass in kilograms). J = delta p = dp
                dp = (GAS_PARTICLE_MASS * 2 * math.fabs(particle.velocity[i])) / 1000
                sumOfMomenta += dp
 
        # Now we do collision detection
        if INTERMOLECULAR_COLLISIONS:
            distances = particle.getListOfDistances(particles)
            for distance in distances:
                if distance[1] <= ATOMIC_RADIUS * 10**-3: # If they're too close together, we have a collision
                    # We had a collision!
                    print("Collision between molecules.")
                    sys.stdout.flush()
                else:
                    break # There will be no distances greater than this one
 
print("Simulating: " + str(ii + 1) + "/" + str(SIMULATOR_ITERATIONS), end="")
print("\n\r\nSum of momentum changes: " + str(sumOfMomenta) +" m*N")
 
# We ran for (10**-8 * SIMULATOR ITERATIONS) seconds; P=F/A; mv = Ft so P = mv/tA
ACTUAL_PRESSURE = sumOfMomenta / ((10**-8 * SIMULATOR_ITERATIONS) * SURFACE_AREA_M)
PERCENT_ERROR = (math.fabs(IDEAL_PRESSURE - ACTUAL_PRESSURE) / IDEAL_PRESSURE) * 100 # |actual-experimental|/actual
 
# Let the user know how we did
print("Average pressure: " + str(ACTUAL_PRESSURE) + " Pa")
print("Pressure error: " + str(PERCENT_ERROR) + "%")
 
if PERCENT_ERROR > 5:
    print("Percent error was too great; Ideal Gas Law did not hold.")
else:
    print("Percent error was reasonable; Ideal Gas Law held as expected.")
 
print() # Formatting
 
# Now calculate the simulated value of the gas constant
# PV/nT = R
ACTUAL_GAS_CONSTANT = (ACTUAL_PRESSURE * (TANK_VOLUME * 10**-27)) / ((NUMBER_OF_PARTICLES / AVOGADRO_NUMBER) * GAS_TEMPERATURE)
GAS_CONSTANT_ERROR = (math.fabs(GAS_CONSTANT - ACTUAL_GAS_CONSTANT) / GAS_CONSTANT) * 100 # Same error formula as above
 
print("Calculated gas constant: " + str(ACTUAL_GAS_CONSTANT) + " m^3*Pa*K^-1*mol^-1")
print("Gas constant error: " + str(GAS_CONSTANT_ERROR) + "%")
 
input("Press enter to exit.")

I won’t go into any sort of massive description of my code. I will go through a few points, though.

  • You will notice from my (likely very improvable) code that adding molecular collisions will add significantly to the running time of the program. 
  • You will get a significant amount of error when molecules are travelling very quickly. This is expected. The error, however, is on the wrong side of the Ideal Gas Law. It happens because particles literally escape the “test chamber” and thus are unable to impart pressure on the inside of its walls.
  • Low temperatures also create significant error.
  • Newtonian Mechanics are exclusively used. You won’t see Schrodinger’s Equation anywhere in this program. There are a few reasons for this. First, it’s written in Python, so it’s slow to begin with. Second, I have no idea what a partial differential equation is. I might come back to this issue next year!
  • Everything in the program is based on the idea that impulse, or change in momentum, is equal to force times change in time, which is equal to mass times the change in velocity. Thus, mass times change in velocity divided by total change in time is equal to total average force. Divide that by area and you get a pressure! Woo-hoo! Physics!
  • My code probably isn’t very “pythonic.” That’s because I don’t know Python very well. Yet. I’ll get better!
  • Estimation quality and computing time, as they should be, are inversely related (as opposed to the direct relation to time spent doing computational chemistry and fun). The more molecules you simulate for more time, the better your results will be. Fewer molecules give crappier results. Numbers in the thousands for both iterations and particles seem to do okay.

Here’s the program in action. Note the relatively accurate estimation! Fun-fun-fun!

Mmmmmm. Semiconductor chemistry simulating physics. I wonder if the transistors in my CPU feel like actors.

Mmmmmm. Semiconductor chemistry simulating more chemistry. I wonder if the transistors in my CPU feel like actors.

Oh. By the way. This trial eventually finished. FYI, the accepted value of the Universal Gas Constant is 8.3144621 m^3 Pa mol^-1 K^-1. We were off by about 0.0001–we had four sig figs of perfection!

Not bad for a rough approximation that uses "10^-20 moles of gas" and runs for "0.0001 seconds!"

Not bad for a rough approximation that uses “10^-20 moles of gas” and runs for “0.0001 seconds!”

Whoops.

I know I haven’t posted for far too long. It’s really embarrassing, especially since I now aspire to be an admissions blogger at MIT.

Wait, what?

Yeah. I committed to MIT. I’m going to be a Beaver (or maybe an Engineer or an IHTFPer or whatever), and I couldn’t be happier! So now that the college admissions process is done until I (hopefully don’t have to) apply to grad school, what am I up to? Moreover, what have I been up to for the past month and a half? Why haven’t I been blogging?

I could post myriad excuses, and depending on how the rest of this blog post goes, I very well might. However, for the time being, I think it would be more appropriate if I directed your attention to Hawgrade!

Hi, Hawgrade!

Hi, Hawgrade! What the heck are you, anyway?

You can actually see the live version of this website at www.hawgrade.com. Now, to answer the caption’s snarky question, Hawgrade is grading for the Twenty First Century, developed with the help of one of the social studies teachers at my school, Dave Hawley. Mr. Hawley also goes by Hawley, hence the name Hawgrade. The website will eventually join forces with an iPad app, and the two will offer the following functionality:

  • Easy, paperless submitting of student papers.
  • Grading that stores data remotely. Teachers can keep their students’ papers anywhere!
  • Corrections for the most common student mistakes built in. This makes grading most papers as simple as highlighting passages and pressing a few buttons.
  • Recording voice comments to end the time consuming process of actually writing comments on students’ work.
  • Returning students’ corrected papers over email.

Most of that functionality has been implemented by now. It’s a wonderful culmination to my high school career, although it is unfortunate that I (a second semester senior) actually have to work on something! It’s also an enormous project. Maybe I’ll post some of my secret, proprietary code samples on this blog.

Regardless, I’ll definitely start posting more!

Drawing the Mandelbrot Fractal in C#

I suppose you could say I had a deprived coding childhood; I already wrote about how I never calculated pi and now I am about to tell you that until this afternoon, I had never drawn the Mandelbrot set. I don’t know why I never took the time to do so, but as with the pi calculator, when I decided to plot the Mandelbrot set, I found a very interesting coding challenge waiting for me.

The first step in the process was to fix the notoriously slow Bitmap.SetPixel() method. I haven’t decompiled System.Drawing to look at .NET’s implementation but I assume it involves some sort of Marshal.Copy()ing of unmanaged bitmap data to a managed byte array, modifications to pixels in the managed byte array, and recopying the array to unmanaged memory. That’s well and good for setting three pixels. We’re going to render Mandelbrot sets of an arbitrary size; 2800×1600 is about 4.5 million pixels. Bitmap.SetPixel() would make this process way, way longer than necessary.

I created a class with a readable, writable bitmap as well as a method to set any of its pixels using unsafe code.

public class FastBitmap
{
    public FastBitmap(int width, int height)
    {
        this.Bitmap = new Bitmap(width, height, PixelFormat.Format24bppRgb);
    }
 
    public unsafe void SetPixel(int x, int y, Color color)
    {
        BitmapData data = this.Bitmap.LockBits(new Rectangle(0, 0, this.Bitmap.Width, this.Bitmap.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
        IntPtr scan0 = data.Scan0;
 
        byte* imagePointer = (byte*)scan0.ToPointer(); // Pointer to first pixel of image
        int offset = (y * data.Stride) + (3 * x); // 3x because we have 24bits/px = 3bytes/px
        byte* px = (imagePointer + offset); // pointer to the pixel we want
        px[0] = color.B; // Red component
        px[1] = color.G; // Green component
        px[2] = color.R; // Blue component
 
        this.Bitmap.UnlockBits(data); // Set the data again
    }
 
    public Bitmap Bitmap
    {
        get;
        set;
    }
}

This class isn’t very useful outside of this program; it would need some modifications to use pixel formats other than 24bpp RGB. However, it gets the job done! The SetPixel method is what makes this class useful. It locks the provided Bitmap’s pixels, then gets a pointer to where the first color byte of the first pixel is in memory (Scan0.ToPointer()). It then figures out what the offset is to the pixel we want to modify. Finally, it creates a pointer to the pixel we want. It sets the blue, green and red to the specified color’s blue, green and red, then finally unlocks the bitmap data. When the data gets unlocked, it is saved in memory.

The SetPixel method presented here does not provide tremendous performance. It does, however, let you work with a bitmap fast enough that you won’t get bored. Most Mandelbrot rendering time is in calculations, anyway.

Now that we have an image class, we can get down to the math. The Mandelbrot fractal is based on the following formula:

Where C is the starting point on the complex plane and the starting value is zero.

Where C is the starting point on the complex plane and the starting value is zero.

The formula is given a starting value, C, that lies somewhere in the complex plane. If the formula (using C) does not tend to infinity, then C is part of the Mandelbrot set. If C tends to infinity, it is part of the Mandelbrot set. As a quick programmatic note, if the absolute value of Z sub N (the value of the formula after N iterations) ever becomes greater than two, the formula will tend to infinity.

Knowing that, we can start coming up with some pseudo-code:

for x on the screen:
  for y on the screen:
    scale (x, y) to the complex plane to figure out where we are
    c = where we are on the screen
    z = 0 + 0i
    b = a bitmap
    for i = 0 to however many iterations:
      z = z^2 + c
      if |z| > 2:
        plot (x, y) on b as some color that indicates how much "infinite tendency" there is at C
        break

If you read the Wikipedia article about rendering the Mandelbrot set, you will notice that it uses two real numbers to accomplish the same thing as one complex one. C# has a complex number class, which we will use in our code. However, before we talk about the actual rendering, we need a color palette. The members of the Mandelbrot set will be rendered black (or actually, based on the flow of the pseudo-code, not rendered at all), while the rest of the set will be rendered some color based on how many iterations it takes for the absolute value of Z to eclipse two. The more iterations it takes, the whiter the pixel. The fewer iterations, the bluer the pixel. It all comes together in the following (very simple) method:

public static List<Color> GenerateColorPalette()
{
    List<Color> retVal = new List<Color>();
    for (int i = 0; i <= 255; i++)
    {
        retVal.Add(Color.FromArgb(255, i, i, 255));
    }
    return retVal;
}

Okay, we can finally translate the pseudo-code into a real Mandelbrot-rendering method:

public static Bitmap DrawMandelbrot(int width, int height, double rMin, double rMax, double iMin, double iMax)
{
    List<Color> Palette = GenerateColorPalette();
    FastBitmap img = new FastBitmap(width, height); // Bitmap to contain the set
 
    double rScale = (Math.Abs(rMin) + Math.Abs(rMax)) / width; // Amount to move each pixel in the real numbers
    double iScale = (Math.Abs(iMin) + Math.Abs(iMax)) / height; // Amount to move each pixel in the imaginary numbers
 
    for (int x = 0; x < width; x++)
    {
        for (int y = 0; y < height; y++)
        {
            Complex c = new Complex(x * rScale + rMin, y * iScale + iMin); // Scaled complex number
            Complex z = c;
            for (int i = 0; i < Palette.Count; i++) // 255 iterations with the method we already wrote
            {
                if (z.Magnitude >= 2.0)
                {
                    img.SetPixel(x, y, Palette[i]); // Set the pixel if the magnitude is greater than two
                    break; // We're done with this loop
                }
                else
                {
                    z = c + Complex.Pow(z, 2); // Z = Zlast^2 + C
                }
            }
        }
    }
 
    return img.Bitmap;
}

Some notable points about this method:

  1. The rScale and iScale variables represent the change in real or imaginary value in the complex plane of each pixel on the screen.
  2. Some good parameters to pass to this method are rMin = -2.5, rMax = 1.0, iMin = -1.0 and iMax (no copyright infringement intended!) = 1.0.
  3. This method could be significantly improved on multi-core machines by dividing up the x-values to render and running a thread on each core. However, any rendering would have to be done after all the threads finished to avoid any cross-thread bit-locking issues. Luckily, the part that takes a while is the iterating, not the rendering.

That’s all it takes to draw a pretty good-looking Mandelbrot fractal. Here’s a fairly large one that you can give to your math teacher. I promise it will make him or her proud. I’m totally giving one to my math team coach as a New Year’s present.

Very blue...

Very blue…

It serves!

Writing a Working Web Server in Under 100 Lines of Code

UPDATE 12/30/12: You must run the compiled executable as an administrator on systems with UAC. Otherwise, the program will crash and exit.

I was reading some coding blogs last night and I happened across a guy who had written a minuscule web server in C# over his lunch break. I knew right away that I had to have one, too. A server like this one serves little practical purpose; it does not support any sort of server-side scripting (though adding a BASIC interpreter to it would be extremely cool). It does, however, serve a wide variety of documents (and will detect their MIME type prior to serving them.

The first thing I did was write a Log method to make console output look fancy:

static void Log(string message)
{
    Console.WriteLine("[{0}]: {1}", DateTime.Now, message);
}

That was quick. Next was to create an actual server method, which would continuously loop and be started asynchronously by the Main() method.

static void RunServer(int port)
{
    HttpListener listener = new HttpListener();
    listener.Prefixes.Add(string.Format("http://+:{0}/", port)); // Where to listen
    listener.Start(); // Fire up the server
    while (true)
    {
        HttpListenerContext context = listener.GetContext(); // Get a connection
        Log("Requested: " + context.Request.Url);
 
        if (context.Request.RawUrl.EndsWith("/")) // Just asking for index; redirect
        {
            context.Response.StatusCode = 301;
            context.Response.StatusDescription = "301 Moved Permanently";
            context.Response.RedirectLocation = context.Request.RawUrl + "index.html"; // Just send browser to index.html
            context.Response.Close();
            Log("Redirected client to /index.html.");
        }
        else
        {
            byte[] retVal;
            try
            {
                retVal = File.ReadAllBytes("www" + context.Request.RawUrl); // Give the client the requested page
            }
            catch
            {
                context.Response.StatusCode = 404; // File not found; tell the client.
                context.Response.StatusDescription = "404 Not Found";
                Log("404: " + context.Request.RawUrl);
                context.Response.Close();
                continue;
            }
            string mime = GetMimeType(context.Request.RawUrl);
            context.Response.Headers.Add(HttpResponseHeader.ContentType, mime); // Give response a MIME type
 
            Stream respStream = context.Response.OutputStream; // Response stream we'll write to
            respStream.Write(retVal, 0, retVal.Length);
 
            context.Response.StatusCode = 200;
            context.Response.StatusDescription = "200 OK"; // Let client know stuff is okay
 
            respStream.Close();
            context.Response.Close();
            Log("Served: " + context.Request.RawUrl + " as " + mime + ".");
        }
    }
}

There’s quite a bit going on here; I’ll try to explain it all. The beginning of this method configures an HttpListener to wait for connections and starts it. It then starts an infinite loop (the user can stop the server by closing the console window) of continuously waiting for and serving requests (listener.GetContext() blocks until something makes a request). A client can ask for three things in this simple server (since we’re not running server-side scripts):

  1. A page that exists (e.g. /index.html)
  2. A page that doesn’t exist (e.g. __++++_____-sdasfash1234.abcdf)
  3. A directory root that may or may not exist (e.g. /mysite/)

The first thing we check for is the directory root case. We check the URL to see if it ends in a slash. If it does, we redirect the client to whatever the path is, plus “index.html.” We could simply serve the “index.html” off the bat, but we’re (poorly) code golfing right now! That would take more code and accomplish essentially the same thing!

If the RawUrl does not end in a slash, we’re serving a page! Anyway, the server stores all its files in a “www” folder that lives in the same directory as the executable. Fetching “www” plus the raw path with File.ReadAllBytes gets the data of the file we are looking for. The try statement is used in the event we can’t find the file. If an exception does get raised, the server returns a “404 File Not Found” error to the client. If this server were fancy, it would also serve a 404 error page.

If the server can find the file, it determines the MIME type through a simplistic process I will detail in a moment, sets the MIME type in the header, writes the data to the client stream, gives the client a “200 OK” (I am not sure if the order matters for all this, or if all the data simply gets flushed when the HttpResponse gets closed, but this code worked fine in Chrome and IE 9), and closes the connection.

The last thing is to determine the MIME type of the file. Rather than using WIN32 interop calls, I decided to write a simplistic method of my own based on the file extension being served.

static string GetMimeType(string fileName)
{
    // Fast way of determining if the lowercase file name ends with something
    Func<string, bool> fendw = new Func<string, bool>(inp => fileName.ToLower().EndsWith(inp));
 
    // Use our function to figure out the mime type
    if (fendw(".htm") || fendw(".html")) return "text/html";
    else if (fendw(".ico")) return "image/vnd.microsoft.icon";
    else if (fendw(".png")) return "image/png";
    else if (fendw(".jpg") || fendw(".jpeg")) return "image/jpeg";
    else if (fendw(".gif")) return "image/gif";
    else if (fendw(".js")) return "text/javascript";
    else if (fendw(".css")) return "text/css";
    else return "application/octet-stream";
}

This method wouldn’t be very interesting were it not for the Lambda Expression (remember those things I love?). The Lambda Expression takes as a string as an argument and returns a Boolean of whether the lowercase version of the provided file name ends with the specified text. In other words, it checks to see if the file has whatever extension you pass to it and ignores case. The “fendw” name, although cryptic, is short for “file ends with;” it prevented me from having to type fileName.ToLower().EndsWith(…) over and over again!

That’s it. The web server works — we just need to add a Main() method:

static void Main(string[] args)
{
    Console.WriteLine("On what port should the server run?:");
    int port = int.Parse(Console.ReadLine());
 
    Task server = new Task(() => RunServer(port)); // Start the server async
    server.Start();
    Log("Server started on port " + port.ToString() + ". Close this window to stop it.");
 
    while (!server.IsCompleted) ; // Wait infinitely
}

The first part of this method gets the port the user wants to run the server on. I used 2013, since it’s almost New Year’s! Next, it creates an asynchronous task (using a Lambda Expression again!) to run the server on, then fires it up and blocks indefinitely. The use of the Lambda expression is unnecessary here (since the thread Main() runs on will just loop forever), but if you wanted to listen on more ports, you could create more tasks to run new instances of the server on. It makes the code more extensible, right?

It serves!

It serves!

Serving a real web page from a website I built for a charity organization last year!

Serving a real web page from a website I built for a charity organization last year!

If you desired, you could actually open a port in your router and let your friends connect to your cool new server. I should probably warn you that doing so would be a terribly risky idea, even if you only have the port open for a short while. You wouldn’t run through wolf-infested woods with a steak or swim at the Great Barrier Reef with a gaping leg wound for ten minutes, so why would you do the same on the Internet? In other words: this code is provided “AS-IS” with no express or implied warranty, especially since I do not really know how secure this server is. My guess is that it isn’t. Still, it’s hard to go wrong with a 100-line server!

Calculating Pi

One programming task that I had never taken on (up until this morning, anyway), was a pi calculator. Finding pi is not an overwhelmingly daunting task; one can get an extremely precise approximation from the System.Math.PI constant. However, that’s no fun. The real fun is in rolling your own pi calculator. As it turns out, this was no beginner project. It was math-heavy, theory-heavy and CPU-heavy. Oh, and it was a blast!

The trouble was that at first, I had no idea where to begin. In C#, there is no “arbitrary precision” decimal type; the decimal class can hold 28 or so significant figures (remember the calculator tutorial?). No self-respecting pi calculator would ever stop at 28 significant figures. 28,000 would be a bit better! The first challenge in coding the pi calculator would be coming up with a way to store an unlimited number of significant figures. I’d read about some pi calculator authors implementing “BigFraction” or “BigRational” classes based off of the fairly new BigInteger (arbitrarily-sized .NET integer) class, so I thought I’d take a crack at writing one of those. I also decided that before I wrote a single line of code, I needed to choose a pi calculation formula.

The requirements for a formula are simple: that it converges relatively quickly and requires relatively few calculations per iteration. Unfortunately, the use of a “BigRational” class adds another requirement: no fractional powers of numbers that have irrational fractional powers. That’s a real drag, because it means we can’t use the Chudnovsky Algorithm, which is the Holy Grail of fast pi calculation algorithms:

The trouble is with the 3k + 3/2 part; 640320 is not a perfect square (it is almost 800.2^2, but not quite).

The trouble is with the 3k + 3/2 part; 640320 is not a perfect square (it is almost 800.2^2, but not quite).

With the really good algorithm out of the way, I started trying to find another good algorithm. My first thought took me back to my trig identity days a few years ago (okay, the past three years of high school):

So then if you take the deriv... actually, no.

So then if you take the derivat… actually, no.

This is actually a sound, correct thought. In fact it has a name: the Gregory-Leibniz formula. This will eventually converge to pi. However, after following a link off the handy, dandy Wikipedia page I used to decide which algorithm I would use in my program, I learned that it takes five billion iterations of arctan(1) (which I will get to in a moment) to produce ten correct digits of pi. YIKES! It was a good thought.

Anyway, I eventually decided on the original Machin formula, from 1706:

Although it was created in 1706, Wikipedia says it is still one of the fastest-converging pi-calculation algorithms!

Despite its age, it converges quickly and is relatively easy to compute.

Awesome. We have a formula. Now we need to figure out how an arctangent can be computed. It is actually rather simple, especially with programmatic help:

See. Not that bad.

See. Not that bad.

Alright! We have the formula for computing pi and we have the formula for computing arctangent, so now we’re done. Not so fast. Remember when I mentioned the BigRational class? As it turns out, writing a BigRational class is the bulk of this project. I won’t bore you with too many tiny details of the way I implemented it; I will tell you that it was designed for simplicity over speed. It definitely needs some refining, but it works.

The basic concept behind the BigRational class is simple: it is a fraction. It has a numerator and a denominator. The numerator and denominator are arbitrarily-precise, so the entire ratio is arbitrarily-precise. The class has a bunch of methods to help the numerator and denominator do their fraction-y duty:

As it turns out, a lot of help.

As it turns out, a lot of help.

Most of the methods listed in the class diagram are pretty self-explanatory; I won’t go into detail here (but you can download the source code to the project at the bottom of the page). All the operators help the BigRationals play well together, and the * operator has an overload that allows “scalar” multiplication. That is, it allows multiplication by a BigInteger.

The two methods that I will delve into are the Reduce method and the ToDecimalString method. The Reduce method reduces a BigRational into its simplest form. It implements Euclid’s Algorithm, which is a means of reducing a fraction. It works in steps:

  1. The larger of the numerator and the denominator is set as the “big number.” The smaller is set as the “small number.”
  2. The program finds the remainder when the big number is divided by the small number.
  3. If the remainder is not zero, the small number becomes the big number and the remainder from step two becomes the small number.
  4. If the remainder is zero, both the numerator and denominator may be divided by the small number. At this point, the small number is the greatest common factor of the numerator and denominator.
  5. Steps 2, 3 and 4 are repeated until step four terminates with the small number equal to one. At this point, the fraction is in simplest form.

In code, the above steps look like this:

public void Reduce()
{
    // Set up big and small number
    BigInteger bigNumber, smallNumber = 0;
    if (Numerator > Denominator)
    {
        bigNumber = Numerator;
        smallNumber = Denominator;
    }
    else
    {
        bigNumber = Denominator;
        smallNumber = Numerator;
    }
 
    // Now divide a bunch of times
    while (smallNumber != 1)
    {
        // Find the remainder
        BigInteger rem = (bigNumber % smallNumber);
        if (rem != 0)
        {
            bigNumber = smallNumber; // Set up the numbers for the next iteration
            smallNumber = rem;
        }
        else
        {
            // We can divide both the numerator and denominator by the previous remainder
            Numerator /= smallNumber;
            Denominator /= smallNumber;
 
            // Re-assign bigNumber and smallNumber
            if (Numerator > Denominator)
            {
                bigNumber = Numerator;
                smallNumber = Denominator;
            }
            else
            {
                bigNumber = Denominator;
                smallNumber = Numerator;
            }
        }
    }
 
    // One last thing -- if the numerator is positive and the denominator is negative, the numerator needs to become negative and the denominator needs to become positive.
    // If they're both negative, they should both be positive
    if (Denominator < 0 && Numerator > 0 || Numerator < 0 && Denominator < 0)
    {
        Numerator = -Numerator;
        Denominator = -Denominator;
    }
}

The only change between the pseudo-code and actual implementation was the addition of the small if-statement at the bottom. I noticed that the denominator would sometimes be negative instead of the numerator being negative. That would probably throw off some calculations, so I made sure that only the numerator of the BigRational could ever be negative.

The ToDecimalString method converts a BigRational into its decimal equivalent — a handy helper when it comes to calculating pi (since it’s no fun unless it starts with 3.14159…). I considered two different implementation styles:

  1. Multiplying the entire fraction by 10^however many digits I wanted.
  2. Creating my own long division algorithm that would return a string of digits of a specified length.

Contrary to what seems sane, I chose the second method. I suppose it was partially because I had always wanted to write an actual long division algorithm, but by any means, it took some head-scratching at first. Long division isn’t something I have to do very much, so I started by doing out a few long division problems. As it turns out, there is a nice pattern. The non-decimal part of the number may be calculated in one fell swoop by using integer division. It may then be committed to a string. After that, a decimal point should be committed to the string. Then, a “new numerator” should be created. Its value is the remainder from the previous iteration multiplied by ten. The next decimal digit is equal to the “new numerator” minus the remainder when it is divided by the denominator of the fraction, all divided by the denominator of the fraction. This process can be repeated until the desired number of digits is reached.

Okay, it makes more sense in code. Wow.

public string ToDecimalString(BigInteger decimalDigits)
{
    StringBuilder rv = new StringBuilder();
    this.Reduce(); // Go as fast as possible
    BigInteger remainder = Numerator % Denominator;
 
    // Get the non-decimal part
    rv.Append(((Numerator - remainder) / Denominator).ToString() + ".");
    remainder = Numerator % Denominator;
 
    BigInteger newNum = remainder * 10;
 
    // Now get the decimal part
    for (BigInteger i = 0; i < decimalDigits; i++)
    {
        rv.Append(((newNum - (newNum % Denominator)) / Denominator).ToString()); // This literally just does long division
        newNum = (newNum % Denominator) * 10;
    }
 
    return rv.ToString();
}

The only real advantage this method presents is the lack of any string parsing. It is all basic use of a StringBuilder. Plus, it seems to work very well!

With the BigRational class done, the next step was the actual pi calculation. The first step was to implement an arctangent method, in accordance with the formula I mentioned earlier.

public static BigRational ArcTangent(BigRational input, BigInteger iterations)
{
    BigRational retVal = input;
    for (BigInteger i = 1; i < iterations; i++)
    {
        // arctan(x) = x - x^3/3 + x^5/5 ...
        // = summation(n->infinity) (-1)^(n) * x^(2n+1)/(2n+1)
        BigRational powRat = input.Pow((2 * i) + 1);
        retVal += new BigRational(powRat.Numerator * (BigInteger)Math.Pow(-1d, (double)(i)), ((2 * i) + 1) * powRat.Denominator);
        if (i % 100 == 0)
        {
            Console.WriteLine("ArcTangent {0}: {1}/{2} iterations complete.", input, i, iterations); // Status update.
        }
    }
 
    return retVal;
}

Wait. There’s a parameter called “iterations.” How do we figure out how many iterations are necessary? This page provided the answer. As it turns out…

I find it's a good idea to add twenty or so digits to the end to make sure everything is correct.

I find it’s a good idea to add twenty or so digits to the end to make sure everything is correct.

In other words…

public static BigInteger GetConversionIterations(BigInteger digits, BigRational q)
{
    return (BigInteger)((double)digits / (2 * Math.Log10((double)q.GetReciprocal())));
}

That was quick. That also finished laying the foundation for actually calculating pi. Phew. That was a lot of keystrokes.

public static BigRational GetPi(BigInteger numDigits)
{
    // pi = 16 arctan(1/5) − 4 arctan(1/239)
    BigRational oneFifth = new BigRational(1,5);
    BigRational oneTwoThirtyNine = new BigRational(1, 239);
    BigRational arcTanOneFifth = PiCalc.ArcTangent(oneFifth, PiCalc.GetConversionIterations(numDigits + 1, oneFifth)); // Start computing
    BigRational arcTanOneTwoThirtyNine = PiCalc.ArcTangent(oneTwoThirtyNine, PiCalc.GetConversionIterations(numDigits + 1, oneTwoThirtyNine));
 
    return (arcTanOneFifth * 16) - (arcTanOneTwoThirtyNine * 4);
}

This code block implements Machin’s formula as discussed above. An improved version of this program could take advantage of multi-core computing by calculating one arctangent on one thread and the other arctangent on another. More formulas should also be tested to determine which is the fastest; this program really slows down as the iteration count gets higher because the fractions get really, really, really huge. Of course, this program was never going to break any records anyway because it was written in C#. JIT-compiled, super high-level languages aren’t exactly speed demons. Then again, my Phenom II x4 (overclocked to 3.7 gHz) is also beginning to show its age. I’d be curious to see how performance compares on one of the latest-generation i7s.

Although it is sluggish, it does seem to compute pi properly. Here are the first 10,001 digits:

Although it looks like a lot of pi, it's not a lot of pi.

Although it looks like a lot of pi, it’s not a lot of pi.

So that’s it. It’s done. It works. Now it just needs to run for a few days so I can brag to my friends! The funny thing about calculating pi is how although we believe pi is completely irrational and will never end, we’ve calculated enough digits that it might as well end. If my calculations are correct, it only takes about 80 digits of pi to calculate the volume of the observable universe to the nearest cubic meter. Thus, ten thousand would calculate it to the nearest 1/10^9920 cubic meter, whatever that would be. That’s some mind-blowing precision. Imagine what a million digits would do.

Download this Project (MIT License)

A Brainf**k Interpreter in JavaScript

Brainf**k (I bet you can guess what the asterisks are covering…) is a tiny, esoteric programming language. It is classified as Turing-complete, but its practical use is very limited (if not nonexistent). BF is an interesting challenge because it is so simple. Many devoted developers spend lots of time creating the smallest, fastest BF interpreters and compilers they can. One user on Codegolf created a BF implementation that was only 106 bytes long. That’s pretty impressive.

BF has eight commands (which will be discussed in a moment). Every program has access to a series of memory blocks that can have any range of values. When a BF program loads, all the “cells” in the memory (really just an array) are initialized in value to zero. BF programs can switch between different blocks of memory (change the array index that they are accessing), increment the values of specific blocks, decrement the values of specific blocks, print a character representation of a block to the screen, or put a character’s value into a block. Programs can also loop. They are executed command-by-command from left to right.

There is no official language specification for BF, so many details are left up to the individual implementation. However, the following standards are pretty common (and were implemented in my BF interpreter):

  • Using bytes for memory. My BF interpreter limits values in cells to [0, 255].
  • Allowing overflows. Blocks overflow when their value goes outside the permissible range of [0, 255]. That is, when a program tries to make a block’s value -1, its value becomes 255, and when a program tries to make a block’s value 256, its value becomes zero.
  • 30,000 blocks (29.3kb) of available memory.
  • Non-command characters are ignored.

The eight commands:

  •  + increases the value of the current block by one.
  • - decreases the value of the current block by one.
  • > increases the block index by one.
  • < decreases the block index by one.
  • . prints the block to the screen as an ASCII character.
  • , gets an ASCII character and puts it in the current block.
  • [ opens a loop. It will jump to the end of the loop if the current block’s value is zero.
  • ] closes a loop. It will jump to the beginning of the loop if the current block’s value is not zero. If it is zero, the program will continue.

I’m not going to teach you how to write BF programs in this post; I’m hardly a maestro of it myself. If you want to learn more about BF, Google is an awesome resource.

My interpreter is pretty simple. The first task was to create a crash-reporting function, since I figured that would probably happen a lot. For future reference, “output” is the ID of the part of the page where BF script output goes.

function crash(reason, at){ // When the program dies
	$("#output").text("CRASHED: " + reason + " ( at char index " + at + ")");
}

The actual interpreter starts out with the declaration of a run function and all sorts of BF-related variables.

function run(data){ // Runs the BF program. Data: program to run.
	var mem = []; // Program memory
 
	// Initialize all the memory
	for(var i = 0; i < 30000; i++){
		mem[i] = 0;
	}
 
	var pointer = 0; // Pointer to memory
 
	$("#output").text(""); // Clear output field

Next, it loops through each character in the program (specified to the function as data) and if it is BF-legal, the required action is performed. The simple ones (that aren’t loops) are self-explanatory.

for(var i = 0; i < data.length; i++){ 	
        if(data[i] === ">"){ // Right one cell
		if(pointer < 30000) pointer++;
		else{
			crash("There are only 30,000 usable cells of memory. Sorry.", i); // Trying to use too many cells.
			return;
		}
	}
	else if(data[i] === "<"){ // Left one cell 		
                if (pointer > 0) pointer--;
		else {
			crash("Cannot decrement pointer when pointer is at first cell.", i); // Trying to go below cell zero.
			return;
		}
	}
	else if(data[i] === "+"){ // Increment cell value
		mem[pointer]++;
		if(mem[pointer] > 255) mem[pointer] = 0; // Overflow
	}
	else if(data[i] === "-"){ // Decrement cell value
		if (mem[pointer] > 0) mem[pointer]--;
		else {
			mem[pointer] = 255; // Overflow back to 255
		}
	}
	else if(data[i] == "."){ // Put character to screen
		var memChar = String.fromCharCode(mem[pointer]);
		if (memChar == "\n") memChar = ""; // Turn newlines into breaks
		$("#output").append(String.fromCharCode(mem[pointer])); // Log the correct character from its code
	}
	else if(data[i] == ","){
		mem[pointer] = window.prompt("Please enter one character.").charCodeAt(0); // Set memory to char code
	}

Next come loops. There are loads of elegant ways of going about loops; a stack storing the start indices of loops could be used to avoid all the searching my implementation does. However, simplicity was on my mind when I wrote this program: it suffices to say I took the slow, not-so-elegant way out. When the interpreter encounters the start of a loop (a [), it checks to see if the value of the current cell is zero. If it is not, it just continues along. If it is, things get more interesting. The interpreter loops through the program until it finds the corresponding end of the loop so that the program can continue executing properly.

The task is not as simple as incrementing i (the “instruction pointer,” so to speak) until data[i] is a ]. Other loops could be in the way. The solution is shockingly simple: keep track of the number of newly open loops as the program searches for the end of the original loop. I used a counter to keep track of the loop openings. Every [ increments it; every ] decrements it. When the counter gets to zero and the program finds a ], the index has been found. All that is left is to change the “instruction pointer” to the new location in the program.

The ] routine works in the exact opposite way. It keeps track of ]s instead of [s but is otherwise very similar. Here’s what it looks like:

else if(data[i] == "["){
	if(mem[pointer] != 0) continue;
	else{ // Search for corresponding ]
		var openCount = 0; // # of open loops
		for(var j = i; j < data.length;j++){ // Loop through more characters
			if(data[j] === "[") openCount++; // Another open loop
			else if(data[j] === "]"){ // A closing of a loop
				openCount--; // Decrement open count
				if(openCount === 0){ // If we're at zero, we're done.
					i = j; // Move the program forward
					break; // Stop looping
				}
			}
		}
		if(openCount != 0){
			crash("Open loop.", i);
			return;
		}
	}
}
else if(data[i] === "]"){
	// Same deal as [ except going backwards
	if(mem[pointer] != 0){
		var closeCount = 0; // We use close count on this one because it makes more sense (since we're doing the opposite from before!)
		for(var j = i; j >= 0; j--){
			if(data[j] === "]") closeCount++;
			else if(data[j] === "["){
				closeCount--;
				if(closeCount === 0){
					i = j;
					break;
				}
			}
		}
		if(closeCount != 0) {
			crash("Too many loop closings.", i);
			return;
		}
	}
}

That’s all there is to it. The rest of the page that contains the interpreter, which you can find here, is instructions and a textbox to let you put a program in.

Here’s what the finished product looks like:

It's not as pretty as TextRacer but it gets the job done.

The interpreter running a ROT13 cipher example I found on Wikipedia.

Overall, I was surprised with how quickly I managed to get my interpreter working. I was also glad I went with the architecture I did; though it would have been possible to convert the BF to JavaScript and then eval() it, the program would have lost most of its charm. This program could certainly use some refining but overall, it gets the job done! Happy BFing!

I LOVE Lambda Expressions

Lambda Expressions essentially add anonymous methods (methods that are attached to a piece of code, have no name and cannot really be explicitly called) to C#. I have not used them very much in my time as a developer, partly because they are newish and partly because I have never really had a need to use them. Yesterday, I decided to do some research into them and I really liked what I saw. Using Lambda Expressions in C# code adds a real JavaScript feel. It’s like the inline, more organized beauty of JavaScript without all sorts of annoying asynchronousness (though asynchronous delegates are possible in C#).

C# and the .NET Framework have always had very slick event handling. I have heard horror stories about listeners and hundreds of lines of code in Java, but since I am not a Java developer, I cannot relay a firsthand account of just how scary it gets. I can tell you that C# event handling started out great and became even better.

For the purposes of this blog post, I made a Windows application with three buttons (aptly named button1, button2 and button3).

Lambda Expressions at Work

Hey look, a sneak preview! Yippee!

In early versions of the language, if you wanted to do something when one of the buttons got clicked, you had to attach an event handler method like this:

button1.Click += new EventHandler(button1_Click);
 
void button1_Click(object sender, EventArgs e)
{
    MessageBox.Show("You clicked button1!");
}

Granted, this is awesome, but for quick snippets to run in event handlers, it’s not a very efficient use of space. Additionally, it’s hard to keep track of your code flow because you have to scroll down from where the method is attached to see what the event handler does. I am not advocating for cluttering your methods with tons of anonymous method code. I am saying that sometimes, you just want to see what is happening in your program without looking all over the place.

That’s where a delegate method comes in:

button2.Click += delegate(object sender, EventArgs e)
{
    MessageBox.Show("You clicked button2!")
};

Whoa! That’s way better! But wait, there’s more! Enter the Lambda Expression! To use Lambda Expressions, you need to use the Lambda operator. Since λ and Λ aren’t standard keyboard characters, C# uses => (not to be confused with >=) as the lambda operator. On the left side of your expression are the parameters. They do not need to be strongly-typed (scary, I know); you only have to provide a name for each and the type is inferred. On the right side of the expression is what you want to do with the code. Ready, set…

button3.Click += (sender, e) => MessageBox.Show("You clicked button3!");

WOW! That saved a lot of code! Unfortunately, it was kind of a silly example. Let’s try a slightly more complicated, relevant one. Let’s say you wanted to return the first name in a list that started with “B”. Ordinarily, you’d use a foreach loop:

List names = new List();
names.AddRange(new string[] { "John", "Bob", "Steve", "Mike", "Bill", "Emily", "Jenny", "Morgan" });
 
foreach (string name in names)
{
    if (name.StartsWith("B"))
    {
        MessageBox.Show(name);
        break;
    }
}

That’s seven lines of code for the loop. With a Lambda Expression, you can cut that done to one:

List names = new List();
names.AddRange(new string[] { "John", "Bob", "Steve", "Mike", "Bill", "Emily", "Jenny", "Morgan" });
 
MessageBox.Show(names.First(name => name.StartsWith("B")));

Uhhh… okay. What the heck. Maybe that example is worth dissecting a little bit!

Just as before, we create a list of strings and add a bunch of names to it. Then, instead of manually looping through the list, we use a LINQ extension method. The LINQ extension will return a string (because names is a list of strings) and takes a Lambda Expression as an argument. The Lambda expression takes an argument of its own, which will be a string. It will return true if name.StartsWith(“B”) is true (note that you do not use the “return” keyword with it), and names.First will return whatever string causes the Lambda Expression to return true. Basically you end up with the first name that starts with a capital letter B, which in this case is “Bob.” Try it!

Bob Message Box

Success.

Of course, Lambda expressions have an associated type: System.Func. System.Func is a generic type; the List<string>.First method we’ve been using actually takes a parameter of the type System.Func<string, bool> where string is the parameter and bool is the return value of the Lambda Expression with which it is associated. Thus, you can actually declare Lambda expressions as variables!

Func fd = st => st.StartsWith("B"); // Declare Lambda Expression
 
MessageBox.Show(names.First(fd)); // Pass the Lambda Expression variable as an argument.
 
MessageBox.Show(fd("Steve").ToString()); // Use the Lambda Expression just like any other method (displays "False" here).

I have barely scratched the surface of Lambda Expressions in this post. You can use them asynchronously and do countless, really cool things with them with the help of LINQ. As I am hoping to get a Macbook for Christmas so I can learn Objective-C, I won’t get to use Lambda Expressions very much but I already know I am going to miss them.

If you want to learn more about Lambda Expressions, go to the MSDN page about them here or this really good StackOverflow post.

Happy expressing!

Quotebook, a Grotesquely Over-complicated Version of a Program I Wrote for a Quiz

Last week in my video game development class (which is an introductory-level course on Python 3 with some focus on games), we had a quiz. We had to talk about some things we’d learned, describe the intricate differences between Python’s if, elif and else statements, then write a program. The program intrigued me: the goal was to “simulate a fortune cookie” and display one of five different, pre-determined strings at random.

My first reaction was relief that I was going to be able to write the program with little issue. My second reaction was how incredibly far I could take that idea. An entire social network materialized in my head; a place where people could go to share and discuss quotes or fortunes. Then I realized that I was crazy, but I did decide to make some changes to the program we’d written in my spare time:

  1. Create an online component that would allow anyone to submit quotes to the “fortune cookie”. The “cookie” has become a system that I call Quotebook, for lack of a better name.
  2. Create a Python client for some kind of bare-bones Quotebook API that would accomplish the same task as the quiz program, except after retrieving the quote from Quotebook.

I knew the Python part would be the easy part, so I fired up Visual Studio and got cracking. I used most of the default template but changed the top text and removed the menu. I kept the HeadLoginView and all the other assorted login-related items so I could use the Membership class to attribute submitted quotes to a user. I also added a database to the project and created a table called quotes. Quotes has four columns:

  1. id (int)
  2. byUser (nvarchar)
  3. timestamp (timestamp)
  4. quoteText (nvarchar)

On the homepage, I added a big TextBox and a submit button. Then, I wired it up to write to the database:

protected void btnSubmitQuote_Click(object sender, EventArgs e)
{
    if (HttpContext.Current.User.Identity.IsAuthenticated) // Make sure user is authed before writing bad things to DB
    {
        // Connect to the DB
        SqlConnection sconn = new SqlConnection(System.Configuration.ConfigurationManager.ConnectionStrings["messageDB"].ConnectionString);
        sconn.Open();
 
        // Create the command to insert the values into the database
        // PARAMETERS are used to STERILIZE all inputs.
        SqlCommand scomm = new SqlCommand("INSERT INTO quotes (byUser, quoteText) VALUES (@byuser, @quotetext)", sconn);
        scomm.Parameters.Add(new SqlParameter("@byuser", System.Data.SqlDbType.NVarChar));
        scomm.Parameters.Add(new SqlParameter("@quotetext", System.Data.SqlDbType.NVarChar));
        scomm.Parameters["@byuser"].Value = Membership.GetUser().UserName;
        scomm.Parameters["@quotetext"].Value = tbQuote.Text;
 
        // Commit to DB
        scomm.ExecuteNonQuery();
 
        // Close and refresh page.
        sconn.Close();
        Response.Redirect("Default.aspx");
    }
    else
    {
        lblError.Text = "
 
You must login or register before adding a quote!"; // Alert user
    }
}

There are a lot of points to cover here. First, the user state gets checked so quotes don’t get attributed to some kind of phantom (and so no exceptions get thrown!). I added a red, textless label to the area next to the submit button so that if the user isn’t logged in, he will get an error message. If he is logged in, the quote gets written to the database. I had to provide my own connection string in the web.config file. The connection string gets used to connect to the database, and a command gets created on that connection.

The command has two parameters: the text of the quote and the user’s name. Those are set through SQL parameters. Although I have no plans to SQL injection attack my own database, it is good practice to use parameters whenever user input is to be committed to a database. After the parameters get set, the data gets written and the connection gets closed.

With the input side of the Quotebook I/O taken care of, I set out to write the output. I wanted two different kinds of output: a mess of all the quotes in reverse chronological order on the homepage and the “bare-bones API” I mentioned earlier. Before I wrote either, I created an easy way to get data out of the database that I call the QuoteEnumerator class. I created a struct called Quote, which contains the quote text and the name of the quote submitter. QuoteEnumerator has a static method that returns a list of all the Quotes stored in the database. I implemented the two like this:

/// <summary>
/// Reads the DB and creates lists of quotes.
/// </summary>
public class QuoteEnumerator
{
    /// <summary>
    /// Obtains a list of quotes from the ASP.NET database.
    /// </summary>
    /// <returns></returns>
    public static List<Quote> GetQuotes()
    {
        List<Quote> retval = new List<Quote>();
 
        // Connect to DB and set up the query
        SqlConnection sconn = new SqlConnection(System.Configuration.ConfigurationManager.ConnectionStrings["messageDB"].ConnectionString);
        sconn.Open();
        SqlCommand scomm = new SqlCommand("SELECT * FROM quotes", sconn);
 
        // Read the database
        SqlDataReader sdr = scomm.ExecuteReader();
        if (sdr.HasRows)
        {
            while (sdr.Read())
            {
                // Iterate through the results
                Quote q = new Quote();
                q.QuoteSubmitter = sdr["byUser"].ToString();
                q.QuoteText = sdr["quoteText"].ToString();
 
                retval.Add(q);
            }
        }
 
        return retval;
    }
}
 
/// <summary>
/// Contains a quote once it is extracted from the DB.
/// </summary>
public struct Quote
{
    public string QuoteText { get; set; }
    public string QuoteSubmitter { get; set; }
}

The QuoteEnumerator.GetQuotes() method is a relatively simplistic database reading method. It utilizes a SqlDataReader to iterate through all the rows. For each row, it retrieves the quote text and quote submitter, then adds them to a list containing all the other quotes. It returns that list. Using GetQuotes made implementing the homepage side of the output easy.

// Default.aspx.cs
protected void Page_Load(object sender, EventArgs e)
{
    foreach (Quote q in QuoteEnumerator.GetQuotes())
    {
        // Append the quote to the page in a pretty-looking (?) way
        lblError.Text += string.Format("<div style='display:block; padding:2px; margin:0 auto; border:1px solid black; width:80%; text-align:center;'>{0}<br/><br/><span style='font-size:smaller'>Submitted by {1}</span></div><br>", q.QuoteText.Replace("\n", "<br/>"), q.QuoteSubmitter);
    }
}

The result is, uh, kinda stunning…

Quotebook Image

That comment was sure telling the truth!


I only had two obstacles left: implementing the API and implementing the Python script that would utilize it. The API came first. I created a page called getmessage.aspx and deleted all of the code from the ASPX page except the top line indicating that it was, indeed, ASPX. In the code behind, I came up with this little gem to write a random quote as a string to the page (and to give credit to the submitter):

protected void Page_Load(object sender, EventArgs e)
{
    // Grab a random quote
    List<Quote> allQuotes = QuoteEnumerator.GetQuotes();
    Quote chosen = allQuotes[new Random().Next(0, allQuotes.Count)];
 
    // Write the quote as the response text
    Response.Write(chosen.QuoteText + "\n\nSubmitted by " + chosen.QuoteSubmitter);
}

Lastly, I created a Python script to read from the API. It uses urllib, and given my limited Python knowledge, it is more than good enough! (Keep in mind that this is Python 3; my last Python post was written in Python 2)

# randomMessage.py
# Random message downloader python script
print("Fortune Cookie")
DLURL = "http://localhost:6642/getmessage.aspx" # Replace with yours
 
import urllib.request
while input("Enter Q to quit or press ENTER to continue: ").lower() != "q":
    # Open the API page
    response = urllib.request.urlopen(DLURL)
    data = response.read().decode("utf-8") # Download and decode to a string
 
    print("\n" + data, end="\n\n")

With that, I entered some quotes and fired my creation up!

Quotebook Python Script Running

The awesome thing about Python is how incredibly easy it is to build relatively useful programs like this one.


Sure, it’s seven or eight times more code than the school version, but it’s extensible.

Do you have any improvements for this? Additional features? Let me know!