Haskell adventure: Project Euler #191

I thought I'd try to be like one of the cool Haskell kids and do one of those literate programming blog posts. That means you can copy and paste this whole blog post into a .lhs file and it will actually compile. This is about how I solved Project Euler problem 191 in Haskell. So if you're trying to work through the problems on your own, don't read this yet!

Let's get to it. Already read the problem statement? Cool.

> import Control.Monad ( guard )
> import Data.List ( groupBy
>                  , isInfixOf
>                  , sort 
>                  )

One of the most obvious things you might want to do, especially since the problem statement used the word "string," would be to represent the O's, L's, and A's as Chars. But I think it's nicer to use a distinct type like this:

> data Day = O | L | A
>   deriving ( Eq, Show )

As you'll see, it will also be helpful to have a list of the three possible "day" values:

> days :: [Day]
> days = [O, L, A]

Then we can represent a student's attendance record as a list of those values. (I'm calling it Record1 here because I'm later came up with a better representation, as you'll see.)

> type Record1 = [Day]

How do we know whether a particular record is prize-winning or not? This is more or less just a translation of what the problem tells us.

> prize1 :: Record1 -> Bool
> prize1 record = (not $ [A,A,A] `isInfixOf` record) && notLateTwice record
>
> notLateTwice :: Record1 -> Bool
> notLateTwice record = case filter (== L) record of
>   (L:L:_) -> False
>   _       -> True

Now we can attack the actual question: After n days, how many prize strings are possible? For n=0, there is only one, namely, an empty record:

> prizes1 :: Int -> [Record1]

> prizes1 0 = [[]]

On the nth day, take all the prize-winning strings from the (n-1)th day, and for each one, tack on an O, L, and A. Now you have three times as many strings, and you can check each of them to see if they're prize-winning. (We don't have to check the non-prize-winning strings from day n-1, because once you've lost the prize, there's no way to get it back.)

> prizes1 n = do

>   prevPrizeString <- prizes1 (n - 1)

>   nextDay <- days

>   let newString = nextDay:prevPrizeString

>   guard $ prize1 newString

>   return newString

The code after "do" gets evaluated several times, once for each possible combination of a string from prizes1 (n - 1) and a day from [O,L,A]. In another language, you might write this as a double "for" loop, or possibly a list comprehension. I probably could have used a Haskell list comprehension instead but I think this is nicer. Anyway, then we add the 'nextDay' onto the prize string from the (n - 1)th day, and check whether the result is still a prize string. If it is, we "return" it which means it will end up in the list of prize strings for day "n" and if not, the "guard" function ensures it will not be returned.

You may notice that I stuck nextDay onto the front of the list instead of the end. That's just because it's faster and cleaner than writing "++ [nextDay]" although it turns out to be useful later too, as you'll see. You can check that "length $ prizes1 4" is 43 which is a good sign we probably haven't messed up too badly yet. And then "length $ prizes1 30" should be the answer. I fired up ghci and typed it in, and ... nothing. The CPU cranked away but after several seconds, it hadn't come up with anything. The rule of thumb for Project Euler is that your code should run in a minute or less. But I had a sneaking suspicion that there was a solution for this problem that would run almost instantly. So let's optimize!

One thing to notice is, we don't really care about absences in the distant past. You only lose the prize if you're absent three consecutive times. And we'll never end up with a string like OAAAO because once you hit the third A, you've already lost your prize and we stop keeping track of you at all. So the function we pass to "guard" can just look for A's at the beginning of the string (remember, more recent days are at the beginning, not the end), rather than using "isInfixOf" to look for an "AAA" sequence anywhere in the string.

> checkRecord :: Record1 -> Bool

> checkRecord (A:A:A:_) = False

> checkRecord (L:ds) = L `notElem` ds

> checkRecord _ = True

If today is your third consecutive absence (A:A:A:_), you don't get a prize. If you were late today, you can still get a prize, but only if you were never late in the past. In all other cases, if you haven't already lost your prize, then you're still eligible for it. Now in the definition for "prizes1," we can just replace "guard $ prize newString" with "guard $ checkRecord newString" and it should be a bit faster. It was still well short of "instant" so I kept looking for better approaches.

Writing "checkRecord" was a step in the right direction, but we were still keeping track of lots of information we didn't actually care about. All that really matters is a student's current absence streak, and total number of times being late. So let's just store those, and not the actual sequences:

> data Record2 = Record2 { consecutiveAbsences :: Int, lates :: Int }

>   deriving ( Eq, Ord, Show )

You could also just use a tuple ((Int, Int)) but this way there's no risk of forgetting which field is which. Plus, this syntax is called "record syntax" so it's only appropriate to use it for our "Record" type, right? Right. Now that records aren't just lists, we can't tack on the next O, L, or A with the (:) operator -- we have to actually keep track of what those two Ints should be. That's what the (#) function does. (Why did I choose "#"? No particular reason, I just picked a character.) Anyway, here it is:

> (#) :: Record2 -> Day -> Record2

> r # O = r { consecutiveAbsences = 0 }

> r # L = r { consecutiveAbsences = 0, lates = lates r + 1 }

> r # A = r { consecutiveAbsences = consecutiveAbsences r + 1 }

If you're absent, we increase "consecutiveAbsences" by 1. If not, we reset it to 0. And if you're late, we increase "lates" by 1. Now it's really easy to check whether a particular record is prize-winning:

> prize2 :: Record2 -> Bool

> prize2 r = consecutiveAbsences r < 3 && lates r < 2

And we can do more or less the same thing we did before:

> prizes2 :: Int -> [Record2]

> prizes2 0 = [Record2 0 0]

> prizes2 n = do

>   r <- prizes2 (n - 1)

>   d <- days

>   let r' = r # d

>   guard (prize2 r')

>   return r'

This should be a bit faster, I think, at least in theory. But I was still convinced the "right" solution was instantaneous, and this one definitely wasn't. The problem is, we're still dealing with a number of records on the order of 3³⁰, and we really don't need to. If you look at the new Record2 type, you realize that there are only a few distinct records we ever care about: consecutiveAbsences only goes up to 3 and lates only goes up to 2 so there are only 3*2=6 possible records we'll ever care about. So instead of keeping a huge list containing several copies of identical records, we could just keep a list of the six possible records we actually care about, paired with a number indicating how many times that record should appear in the list:

> prizes3 :: Int -> [(Record2, Integer)]

> prizes3 0 = [(Record2 0 0, 1)]

> prizes3 numDays = reduce $ do

>   (record, count) <- prizes3 (numDays - 1)

>   day <- days

>   let record' = record # day

>   guard (prize2 record')

>   return (record', count)

If we leave out the "reduce" this will be the same as "prizes2", except that every record will be paired with a "1" which is kind of useless. The "reduce" function takes all the Record 0 0's and puts them together, then takes all the Record 0 1's and puts them together, and so on, each possible record value being paired with its total count. There are at least a couple ways to do this, but what I did was this:

> reduce :: [(Record2, Integer)] -> [(Record2, Integer)]

> reduce = map f . group . sort where

>   group = groupBy (\(r,_) (s,_) -> r == s)

>   f list@((r,_):_) = (r, sum $ map snd list)

Remember that with the (.) function, it's often easier to read right to left. So the reduce function takes a list of (Record2, Integer) pairs, sorts it, then calls "group" on that sorted list, then maps the function "f" over the result of that. The "group" function groups all the identical records together, returning a list of lists. Then the "f" function reduces each list into a single (Record2, Integer) pair. To get the total number of prize strings after n days, we can't just use "length" anymore; we need to sum the counts from all the pairs:


> prizeCount :: Int -> Integer

> prizeCount = sum . map snd . prizes3

Again, you can check that prizeCount 4 is 43 (really nice of the Project Euler people to give you that sanity check, isn't it?) and then

> answer :: Integer

> answer = prizeCount 30

and it runs instantly! If you didn't know much Haskell before. I hope you learned something from this post, or at least enjoyed kind of half-following along. If you did, maybe you can point out something I did wrong, or a more elegant way to accomplish one of these steps. Either way, leave a comment and let me know what you think!

If Programming Languages Were Types of Music

Thanks to the classic If Programming Languages Were Religions for the inspiration. Actually, it turns out there are a bunch of If Programming Languages Were X things out there.

Assembly would be scales: They're the foundation that all music is based on.

Fortran would be a Gregorian Chant: Ancient and methodical, but still sung occasionally in certain dark places.

C would be Bach: Almost all modern music is based on Bach in one way or another. The music can be pretty elaborate, but if you break it down, it's actually pretty straightforward.



C++ would be Beethoven: To the untrained ear, it sounds just like Bach -- classical and easy to listen to. But once you start listening more closely, it's actually a lot more complicated than most people realize.



Java would be The Beatles: Familiar to almost everyone, simple and uncontroversial, though as time went on, they started adding more stuff to their act and getting a little weirder.





BASIC would be kids music: Everyone liked it when they were younger, but no one takes it seriously once they start listening to anything else.



JavaScript would be Lady Gaga: Everyone knows her hits and thinks they can play them even if they're not a musician, but few know how talented she really is.



Perl would be The Ugliest Piece of Music Ever Written: You're required to make fun of Perl when you write a post like this, right? (Skip to 7:45 if you just want to hear the song.)




Python would be OK Go: You watch them occasionally on YouTube, but you would never listen to a full album from them.




Haskell would be Radiohead: You've heard them a few times, but you've never really understood what they're singing about, or what their fans are talking about.

Ruby would be electronic music: It's not bad or anything, but fans of electronic music act like it's the best music in the world, and rarely listen to anything else. Most people don't see what the big deal is.



Edit: Thank you to commenter Mike for this one: Lisp would be Jazz: It was a big deal when it came out and supposedly it still has a big following, but you can't name a single person who likes it.

I apologize if I left out your favorite programming language. It's either because I'm not familiar with it, or I couldn't think of a good musical analogy. Leave a comment and let me know what type of music it would be.

Scribe 1.0 released

I have officially released version 1.0 of Scribe, my first Android app ever! (insert confetti and cheering here) It's an Android implementation of the paper-and-pencil game, Scribe. It's a two player game, so find a friend and give it a try!

If you are viewing this on an Android device, or if you have the ChromeToPhone or FoxToPhone extension, then you can just click right here to download it. If you have a barcode reader app, then you can point it at the QR code below. Otherwise, just open the Android Market and search for "Scribe." Let me know what you think!

New Android game, Scribe: Coming soon!

Remember how I said I would update this blog, like, all the time? Me neither. Anyway, I'm working on a game for Android called Scribe (pdf):

Scribe is a pen and paper game for two players. Nine mini grids together form one super grid. The 19 glyphs of Scribe are listed in the left margin. Draws cannot occur in Scribe. Mark Steere invented Scribe on October 1, 2006.

I've played a sort of "play by email" version of it at superdupergames and I always thought it would be more fun in real time, so I decided to make it my first Android development project. I've already cranked out all the data structures and tricky logic (specifically, the difficult task of figuring out who won a particular mini-grid), so all that's left is the UI. As it's my first Android project, I don't know how long it will take, but my (admittedly rather arbitrary) goal is to have a beta version ready for download by the beginning of August.

If you want to follow along with the development, keep an eye on my github account. (The Scribe project that's up there now is a desktop version, hastily thrown together in Swing, but I couldn't get the github "downloads" feature to work, so you'll have to build it from source, or wait a little while.)

In the meantime, can you prove Mark Steere's claim that ties are impossible?

TDD with Infinitest

As I posted last time, I'm writing a game in Java called Flood It, copied from inspired by the game of the same name by Lab Pixies. I encourage you to play it and if you find any bugs, or would like to request enhancements, add an issue in the issue tracker. In fact, if you do play it, you'll probably understand this post better.

One of the most important classes in the game is called Grid: It represents the big grid of squares and also keeps track of which ones are in the upper-left group. Because it's so important, I decided to write some unit tests for it, because that's supposed to be the best way to write great code and all that. I'm also using a great little tool called Infinitest which continuously runs your tests for you in the background, all the time. What happened just now is, I think, a great example of why everyone says unit testing is so important.

The constructor for Grid takes a width, a height, and a number of colors. It picks some colors and then populates the grid with a random assortment of squares. So far, so good. But I'm trying to implement an undo/redo feature so I think I'm probably going to need to override clone(). In this case, the constructor will fill the grid with a bunch of incorrect squares, only to have the clone() method overwrite all that data. I decided not to worry about it. Here was my original clone() method:

protected Grid clone() {
 Grid clone = new Grid(this.getWidth(), this.getHeight(), this.colors.size());
 clone.colors = this.colors;
 for (int x=0; x<getWidth(); x++) {
   for (int y=0; y<getHeight(); y++) {
     clone.data[x][y] = this.data[x][y].clone();
   }
 }
 clone.update();
 return clone;
}

The update() method just checks for any squares that may have suddenly become part of the upper left group because the player changed the color of the group, and adds them to the set. Can you see the bug yet? There are actually two bugs, very closely related. I might have caught both of them eventually by playing the game itself, but this method isn't called anywhere in the actual game yet so that might not be until a few days from now. Luckily, I thought to write a unit test:

private void testClone(Grid orig) {
 Grid clone = orig.clone();

 System.out.println("Original:");
 System.out.println(orig);
 System.out.println("Clone:");
 System.out.println(clone);

 assertEquals(orig.getWidth(), clone.getWidth());
 assertEquals(orig.getHeight(), clone.getHeight());
 assertEquals(orig.getColors().size(), clone.getColors().size());
 assertEquals(orig.getNumInUpperLeftGroup(), clone.getNumInUpperLeftGroup());

 for (Color color : orig.getColors()) {
   assertTrue(clone.getColors().contains(color));
 }

 for (int x=0; x<orig.getWidth(); x++) {
   for (int y=0; y<orig.getHeight(); y++) {
     Square origSquare = orig.get(x,y);
     Square cloneSquare = clone.get(x,y);
     assertNotSame(origSquare, cloneSquare);
     assertTrue(origSquare.sameColor(cloneSquare));
   }
 }
}

Actually, it was the comparison of the toString() outputs that led me to the first bug. Then I decided to add the getNumInUpperLeftGroup() method and use it in the unit test, which led me to the second bug. Which is why you shouldn't put information in toString() that's not accessible somewhere else. But anyway. The first bug was that clone.update() was not adding anything to the upper left group. I knew this because the toString() showed squares in the upper left group as capital letters and others in lowercase. In the clone, it was all lowercase. What was wrong with the clone's update() method? Nothing, actually. For a Grid constructed normally, the last thing in the constructor is upperLeftGroup.add(get(0, 0)); and then update(); My new grid needed that first square to "seed" the update method. So I added clone.upperLeftGroup.add(clone.get(0,0)); to the bottom of the clone() method, before the update, and ran the test again. This time the toString() outputs matched perfectly, but the test still failed.

I leave it as an exercise to the reader to find the second bug. And by that I mean I'm tired of typing so I'll post it later. But suffice it to say that without this unit test having caught the second bug, I might have had some very strange behavior that only showed up in a very particular case. It might have gone uncaught for weeks and when I did find it, it would have driven me crazy and taken me quite a long time to figure out.

This is why everyone says unit testing is so important. I think I get it now.

New project: Flood It

Through a stroke of luck, I managed to gain possession of an iPhone for a few days, and I downloaded a game I really liked called Flood It. Knowing I'd only have the iPhone for a few days, and not knowing whether any implementations of the game existed online anywhere, I decided to try and make my own, and try to learn a little about Swing and GUI programming as I go.

If you have Java, download it and play it and let me know what you think. Hopefully I will continue working on it at least a little every day so try it out and if you have any suggestions or bug reports, put them in the issue tracker (I don't know if you need a Google account or what).

Enjoy!

easy-to-use!

I'm beginning to think that Python being really easy to use is not a wholly positive feature. In a language where refactoring your code takes a long time, you're more likely to stop and think before you write something, like you're supposed to do. That's all for now.

Finally, an update

Since the last time I posted anything of substance:

* I turned 21. That went pretty much how it should have gone.
* Classes have started again. I have two Physics classes, both of which started off kinda slowish, one much more than the other, but are now starting to become legitimately challenging and fun.
* I'm an SI Leader for Physics 152. I don't think I'm doing so well with that, but it's hard to know. I think I'm slowly improving.
* I've been working hard on the no on 8 campaign, which now has a small but mighty corps of volunteers here at USC, with phonebanks two days a week.
* I did the USC Programming Contest again, but I didn't really prepare for it at all, like I did last year. Did very badly, but it was also a tougher contest than the last one. And we all got t-shirts!
* I've agreed to help Elizabeth with a journalism project that will require some programming. I'm not even sure how I want to do it. It's the kind of thing that would be web-based in real life but Javascript is meh and other web programming languages I don't know at all. So I'm going to see if I can build up a proof-of-concept in Python. I guess.

Next post will be something about prop 8 I think.

Python Challenge

I've been learning Python lately, both for my job and just for fun. After all, all the cool kids are learning Python, aren't they? Best of all, I found a great puzzle called Python Challenge, which consists of several cryptic puzzles that require programming to solve.

If you're learning programming, or want to learn, or you already know some and want to expand your realm of expertise, I highly recommend it. Out of the levels I've done so far, there is one that requires Python. The others were designed to be solved in Python, but could probably be done in any other language.

If you get stuck, there is a help forum, but they usually help you more with the concepts rather than how to write the code, so I wouldn't necessarily think of it as "cheating"--but try to do them on your own. It's more fun that way.

Writing "code"?

My friend from freshman year, Elliot, has recently started a new blog, Anyone Can Code. I guess he's going to teach some programming courses over the summer, partly because he, like me, doesn't like the way most of the courses he's taken at USC have been taught. And because he believes that, well, anyone can code.

His first post on the Anyone Can Code blog lamented the people who are somewhat interested in computer science, but think they can't code. I've always thought that "people who can't do math" were just people who had terrible math teachers and never took them time to learn any math on their own. There isn't really anything wrong with this, but it's now become relatively socially acceptable to know almost no math. It's also socially acceptable to know literally no coding, since most people never take any computer science classes.

I've digressed a little, but the point I wanted to make here is that perhaps referring to programming as "coding" is not good for making it accessible to the general public. Code, in everyday language, is a message which is unreadable until a person or machine performs some kind of operation on it to decode it, so that humans can read it. Back in the days of punchcards, that may have been somewhat accurate, but now writing computer programs is (or at least should be) almost the opposite. You write down what you want the computer to do, in as clear and straightforward a way as possible. Then the computer compiles or interprets it, which is when it becomes completely unreadable. But the programmer isn't writing "code". They're just writing down a set of instructions, in another language. So maybe instead of "coding," we should look at programming as writing in another language. Because that's all programming languages are--they're just languages, where the rules of grammar must be followed much more strictly than in languages like English or Spanish.

Oh great, you say, so coding is just like learning a language, except with even more emphasis on grammar? Sounds lovely. Well yes, but there's very little emphasis on learning new vocabulary. In fact, most of the important words in most languages are actually words you already know. And the grammar rules are much clearer and completely unambiguous, especially in languages like Ruby and (from what I hear, although I haven't used it myself) Python, which were deliberately intended to be easier to use. I think Elliot is right that anyone can code. It doesn't mean everyone will find it fun. But if we stop thinking of code as "code," perhaps everyone will be able to do it.

USC Programming Contest: 6th Place!

This past Saturday, I participated in the USC Programming Contest. As you can see here, they used my code as one of the sample solutions. More importantly, as you can see here, I slipped in just two minutes shy of 5th place! I would have gotten to choose a video game as a prize, but since I had to leave early to volunteer at the GLAAD awards, I had someone grab one for me. I realize now that since my taste in video games differs so much from most people's, I probably could have just asked the contest organizers to give me whatever was left, and it would have been something I really liked. Instead, I ended up with an FPS from the Medal of Honor series, which Andy assures me is badly designed, badly coded, and generally just not a good series of games. So I'll probably sell it. It's more about the glory anyway.

In any case, I'm pretty excited, and the GLAAD awards were fun too. We got to watch the show for a few minutes, including seeing Kathy Griffin win for best reality show. The GLAAD people were so grateful for our help, they let us take gift bags with all kinds of swag in them. One paper, one programming project, and three big dance performances away from the end of classes! Then finals, then commencement (playing, not graduating), and then Brazil!

Star shapes

So I skipped Philosophy today and went to my CSCI 101 midterm pretty early. Before it started, I was talking to Ashley and Rollerblades Kid (I call him that because I don't know his name, but he uses rollerblades as his primary mode of transportation) about the impending midterm, and computer programming in general. Ashley has no programming experience other than this class, and she was telling me how she had been having trouble on a recent assignment with opening an input file. The relevant code would go something like:

ifstream fin;
string filename;
/* ... */
cout<<"Please enter filename: "; cin>>filename;
fin.open(filename.c_str());

I don't think I ever figured out, based on her description, what she had done wrong, but she said she contacted a friend who works at Google, and her friend had told suggested some sort of modification using character arrays in place of strings. It makes you wonder why, when C++ was designed, they didn't rewrite ifstream::open() to accept strings. I mean, you could just do:

void ifstream::open(string filename) {
open(filename.c_str());
}

C++ just seems so user-unfriendly after playing around with things like Javascript and Ruby. It would be interesting to learn the history of various languages, because programming languages do grow and evolve like spoken languages, but there are also some clear differences between the way they evolve. In any case, I suppose they use C++ for the 101 class because it's well established, and the people running the department probably aren't familiar with a lot of the newer languages anyway. Plus, C++ forces you to think a little bit about the way the computer deals with data, internally, when you pass things by reference, or try to access an array value that's out of range. I suppose that would be helpful when you get to classes on data structures. (One of many classes, by the way, that I should be taking this fall, but can't because it conflicts with a required physics class.)

However, Ashley is a chemical engineer. Many of the people who take this class are business majors. They're not taking a data structures class, and have no desire to become programmers of any kind. There really ought to be another class for such people. In fact, sometimes I think a few basic programming skills ought to be required of all students. However, I would never wish this particular class upon the student body at large. This other class would be like Physics 100, which I gather is a physics class for people who really don't like physics. It would probably be taught in some version of BASIC, maybe VBA since it's infinitely more useful for many people than any other language. Ideally, it would be something where students can type things in at a command line, rather than having to write, compile, fix compiler errors, recompile, test, fix runtime errors, recompile, etc. There would probably be no need to deal with OOP, but maybe they'd touch on it at the very end.

As it is, no one is going to learn anything from a single class like CSCI 101, especially when we spend more time worrying about things like header files than we do actually writing code. I guess that's the whole point of Ruby. The programmer's job is to write code, and the interpreter takes care of everything else, like memory allocation. Anyway, I have a few problems with the way our class is taught, as well, but I'm sure I'll post about that another day.

What I wanted to post about was actually an exchange with Rollerblades Kid. I was complaining about what I called "bullshit" on the test. I tried to reproduce one from today's test from memory, but Blogger tried to interpret the << operator as the beginning of an HTML tag and it got all messed up. In any case, we have a couple of functions that have a more or less random assortment of +'s, -'s, switch statements, if statements, arguments being passed by value/reference, etc. They don't correspond to anything real at all, it's just arbitrary data manipulation. We have to trace through the program, then write down the output it would generate. Admittedly, these problems are pretty simple, and I guess they're okay for test questions, but it completely goes against the principles of good code writing. You can't use descriptive variable names when your variables do not in fact describe anything.

In any case, Rollerblades Kid didn't seem that concerned with this type of problem, because he was used to them from the AP Computer Science test (which I didn't take), but he and Ashley both objected strongly to "Star shapes" problems. The kind which are supposed to print output like:

*
**
***
****
*****
******

or

*
***
*****
*******
*****
***
*

I must admit that, in modern times, when we have the ability to use "real" graphics, there is no need to learn this particular skill. Yet for some reason, I find it much less like a pointless busywork assignment than the "bullshit" trace problems. I think that's because it solves a real problem. Not real as in real-world. Just real as in, there's an actual problem with a non-trivial solution, and the code is that solution. Yes, it's a problem you may never face, but the same could be said of so many problems you're asked to solve as classwork. Still, it's hard to explain just what it is that, to me, makes Star Shapes problems seem not to be completely worthless. You can actually learn something about good programming style from such problems. But of course, there is absolutely no guarantee that will actually happen.

Pet Peeve

When people mix up dates and days of the week. For example, my next math assignment is due on "Monday, March 11" but March 11 is a Tuesday. How do you fuck this up? Look at a calendar.

Philosophy class is just starting to get interesting again after a couple weeks of being kind of tedious. I think the idea that a complex enough computer can be, at least for all intents and purposes, conscious, is really fascinating.

I'm going to Northrop Grumman on Monday for an interview for a summer internship. It'll be something software-related but I don't really know anything else. I feel like my strategy needs to be to prove that while I don't know a whole lot, I can learn new things really quickly. Also I'm totally a team player.

Google All-Nighter (or, I am so tired I feel like I'm about to die)

Well, I decided to go ahead and enter the contest, and I'm glad I did because we ended up winning some prizes! We mashed up the data from Citysearch Los Angeles (screen-scraped... shhhhh!) and Google maps, so that users could find restaurants in their area, and find out how much money they would spend in gasoline to drive there from their house, as well as how much CO2 they would be releasing into the atmosphere over the course of the drive, which is how we tied it into the theme of the contest, "Think Green." We ended up with a really good team. Ben pulled the data from Citysearch, I did the mapping stuff, Josh did the HTML, CSS, and processed the data so that I could use it, and David designed some awesome icons to use as map markers. In the end, we won "most useful" and I got a beanbag chair and a sweet Google lava lamp. Now I'm extremely tired, and I still have philosophy homework due in about 13 hours.

Google All-Nighter

There's a contest this Sunday and Monday, taking advantage of the long weekend, called the Google All-Nighter. You have 24 hours to write an application that uses one of Google's APIs in some way, and fits the theme, which will be announced at the start of the competition. It looks like I'll probably team up with this kid Ben I met, and I'll have to leave in the middle of it for the big ucla game, but it should be pretty fun. All this week, Google and USC UPE have been holding workshops on the various Google APIs and other technologies that may be useful in the contest, like Javascript. On Tuesday, we learned how to use the Google Maps API, so I made a little USC trivia game, where a marker appears, pointing at a building on the USC campus, and the user is supposed to guess the name of the building. I'll post a link once I get it working better. Luckily, a lot of the data I need, including a couple of really nice USC map overlays, already exists, but I didn't realize that when I started writing, so when I get some time, I'm going to rewrite my code to deal with that data, and it will be awesome. Perhaps the hardest part will be making it forgiving, so that if the user misspells something, or adds a tiny bit of extra whitespace, the game will still count it as right. I guess I could make it multiple choice instead. What I really want to do is learn the Google Calendar API since I could probably make things that are actually useful, rather than just fun, with that.

In other news, the white-space-phobically named LetMePracticeAtUSC system could be improved so much by a couple of tiny changes, and I have a feeling that, given several hours to understand the code, I could fix it. It appears I would have to learn ASP, and the source code isn't publically available, AFAIK. Which makes it a lot easier to say that kind of thing, I guess.

Spring Semester 2008

There's no better way to celebrate surviving the first week of class than going directly into the first three-day-weekend of the semester. And no better way to spend a Sunday afternoon on such a weekend than to blog about that week. These are my classes for the semester:

MATH 445: This class is going to be all about partial differential equations and such, but so far all we've done is Fourier analysis, which allegedly is an important step towards solving PDEs. My favorite parts of this class are the professor telling us that the required textbook kinda sucks, but we have to buy it anyway, and the fact that we spent almost no time on boring administrative stuff, instead diving right into Fourier series, deriving the formula for it, and then proving it converges, all in three lectures. For the first time in a USC math class, the homework is actually required, but there's none assigned yet.

EE 101: Very low-level digital logic stuff. Binary representations of numbers, and gates, or gates, etc. The "textbook" for this class is a course reader that only cost about $18, and since everything so far is fairly trivial, I've been reading ahead about how to build multiplexers and adders and such. Seems like this is going to be an easy A.

MUEN 308: Men's choir. I did this last spring, but I've never done it in the fall. I guess this is a pattern that could continue to work: Band in the fall, choir in the spring. Anyway, the director is redoing some pieces from last semester, which puts the new people (there are about five of us) a little behind. This was fun last year and it's looking like it will be fun again this year.

PHIL 262: This is my category I GE. The title is something about "Mind and Self." Since this is a philosophy class, I was worried it would be a little like this. And it might be, but I'm very optimistic about it, at this point. The professor told us we can call him Jake. "You do NOT need to call me Professor Ross. My father was Professor Ross. Well, my father wasn't a professor, but if he had been, then he would have been Professor Ross." What's more amazing, he actually listens when students ask questions, instead of assuming he knows what they're going to ask, then going on and on about something unrelated. Again, it's only the first week, and we've already examined five alleged "proofs" for the existence of God. Not an easy A, but it should be interesting.

CSCI 101: I had already heard from my friend Greg, who took this class last semester from the same professor, that the professor wouldn't be all that great, and it's looking like it's going to be a few weeks before we get into anything remotely challenging. Eventually, I might learn something, and it looks like another easy A.

Basketball Band: Another semester of Tony Fox. Joy. This week, we recorded this Foo Fighters song for some youtube contest. Every other week is going to be pretty lame in contrast.

Concert Band: This year's show is all Broadway songs, so I couldn't really pass this up. Still, I feel like the music is way over my head, so I'm going to have to practice a lot. Apparently, I'm allowed to reserve PIC rooms since I'm officially in this class, even though I'm not a music major. This could end up being a really rewarding experience.

Overall, I'm pretty excited about this semester, and I'm fairly confident that my GPA will go up when it's all over.

Project Euler

I saw this talk on youtube by Randall Munroe, author of the webcomic xkcd, and he mentioned a site called Project Euler, where mathematical problems of varying difficulty levels are presented, usually meant to be solved with the help of a computer program. It's a great way to develop programming skills in the language of your choice, and a great way for me to pass the time before I go back to USC for bowl week. Check it out!