Programming Praxis: Goldbach’s Conjecture
Since I mentioned in my last post that I live in fear of the tech interview, I decided to do something about it rather than live in fear. To that end, I subscribed to a website called Programming Praxis, which publishes short programming problems to sharpen your saw on. (Well, I’d actually been a subscriber for a while, but it’s just now that I’ve actually took the time to do my own saw sharpening.)
Geek Content Ahead. Feel Free to Ignore.
Today’s Praxis is on the Goldbach Conjecture which states that any even number greater than 2 can be expressed as the sum of two primes. The challenge is to write a program that will take in an even number, and spit out the two primes that can be added together to make it.
I realize my solution is extremely naive, but it’s the first time in a long time that I’ve actually worked on programming problems other than “get data from database a, transform it somehow, and put it in database b.” Also, for extra difficulty (and speed, although my algorithm is the real speed hangup in this case) I wrote it in C.
For the one or two people still reading, here is my extremely naive solution, cobbled together while watching West Side Story on TCM.
#include <stdio.h>
#include <stdlib.h>
void show_usage();
unsigned long *create_sieve_to_number(unsigned long number);
int main (int argc, const char * argv[]) {
if (argc != 2) {
show_usage();
return -1;
}
unsigned long number = atol(argv[1]);
if ((number % 2) != 0) {
show_usage();
return -1;
}
unsigned long *sieve = create_sieve_to_number(number);
for (unsigned long i = 2; i < number; i++) {
if (sieve[i] == 1) {
for (unsigned long j = i; j < number; j++) {
if (sieve[j] == 1) {
if (i + j == number) {
printf("Solution found: %d + %d\n", i, j);
return 0;
}
}
}
}
}
printf("no solution found! pick up your Fields Medal!\n");
return 0;
}
void show_usage(void) {
printf("usage: goldbach [even number]\n");
}
unsigned long *create_sieve_to_number(unsigned long number) {
unsigned long *sieve;
sieve = (unsigned long *)malloc(sizeof(unsigned long) * (number + 1));
for (int i = 0; i < number; i++) {
sieve[i] = 1;
}
for (unsigned long i = 2; i < number; i++) {
if (sieve[i] == 1) {
for (unsigned long j = i * i; j < number; j = j + i) {
sieve[j] = 0;
}
}
}
return sieve;
}
Edit: See what happens when you’re watching TV when you’re doing your homework? The flags marking numbers as prime can be a bool (or even a bit) and most certainly does not have to be an unsigned long. Yay for massive, massive wastes of memory! (But hey, I was watching West Side Story…)
The Dreaded Technology Test
A recent post on Coding Horror about “Non-Programmer Programmers” kind of terrified me. Not because I think that my job is going away, and not because I think my skills aren’t up to snuff, but because the technical interview terrifies me like nothing else.
Jason, with performance anxiety? Yes, it’s true!
As a performer, I come from the world of improv, where the mantra is “Just make it up! What you say will always be correct!” Naturally, this level of bullshittery, while it might get you through a real interview, will never do in a technical interview where you will be eviscerated if you don’t know the systems you claim to know. (Or even some detail of a system you really do know, but had never previously used.) Now I’ve never put something on my résumé that I did not actually use, but in some cases, it’s just been a while and I need a few minutes with my friend Google to get back up to speed.
Part of the problem is that the tech interview is like flying an airplane. Once you stall once, it’s really hard not to crash and burn. You just get more and more flustered until you can’t even answer questions about things that you do know extensively.
I had an interview like that just before I interviewed for my current job. It was October/November 2001, and as you could imagine, New York City was on edge and not in a hiring mood, especially in the “dot-com” world which had gone bust. I interviewed downtown with a famous phone company for a unix administrator job. I can’t remember what question started the stall… I think it was something about rpc, or what port something listened on… But after that, I was dead in the water. They asked me a bog-simple RAID question that I totally blew. As they escorted me out of the building, one of the managers sypathetically said to me, “It must be hard getting a job in this economy…” Shellshocked, I agreed.
Reading that article on Coding Horror, and remembering that interview, kept me awake far too late last night. Again, I’m reasonably confident that my job’s not going anywhere, and I’m confident in my abilities, but one has to plan for these things.
Then today, sitting in the office that I’ve occupied for almost nine years now, I remembered a tech interview that was tough, but I knocked out of the park. (In particular, I remember totally killing a question about DNS.) Naturally, its the one that got me the job I have today. And they seem to like me after all these years, to the point where they actually let me write production code.
Scary though the tech interview may be, if I keep my skills up, keep my cool, and remember how to pull out of a stall, I should be okay. Besides, the “weed out” questions on that Coding Horror article are laughably easy. And if your tech interview feels like the Spanish Inquisition, did I really want to work for you in the first place?
Long Walks: Sea to Shining Sea (Broadway/Grand)
You can sometimes tell the old roads in a developed area because of the way they twist and turn and cut strange swaths through an otherwise orderly street grid. Two of the older roads in Queens are Broadway (although it’s western terminus in Astoria/Long Island City is somewhat younger) and Grand Ave., which becomes Grand St. in Brooklyn. Grand Ave./St. is particularly old, as it used to be the main drag to get to the ferries that would take the masses to Manhattan in the pre-bridge era. And both these streets have the interesting property that they meet exactly at their terminus at Queens Blvd., as if they were one continuous road.
So I vowed that one day I’d walk Broadway/Grand from terminus to terminus. That day was today.
I started at Broadway near Costco at about 1:00 PM. I stopped off to use Costco’s restroom, as it is one of the few places along the way that I’d have a chance to do so without buying anything. The trip began through the familiar territory of the Astoria/Long Island City border. (I had a doctor in the hospital tell me quite emphatically that Broadway was that border…)
Broadway is one of the great international streets of Queens. It’s got some Greek flavor in Astoria, which rapidly becomes Hispanic as you approach Woodside. Then it actually becomes quite Asian for a bit, then tilts back to Hispanic. At Northern Blvd., you encounter one of my favorite sights: the viaduct that carries Amtrak traffic out of the Sunnyside Yards and eventually to the Hell Gate Bridge and points north. The cement work is beautiful, but is falling apart with pieces of ancient rebar visible.
A bit further down Broadway, you cross over the BQE for the first time, and just beyond you cross over the Bay Ridge branch of the Long Island Railroad (which now carries only freight), also for the first time.
After about two hours of walking, I hit Queens Blvd., the aptly named Boulevard of Death. In fact, when you go to cross it at Broadway/Grand, there is a sign that specifically says that a pedestrian died here, and you should be careful.
Shortly after crossing Queens Blvd., I hit Patacon Pisao, a place that serves Patacon: a Venezuelan sandwich that uses smooshed-together plantains in place of bread. I’d been holding out for some good ethnic food, and I was not disappointed. Just as I was leaving, Paula texted me, “Where are you?” “Elmhurst.” I replied. What else is there to say? When I go on these long walks, I walk a long way, and then I come home…
Grand Ave. gradually morphs into Maspeth and Ridgewood. I crossed the LIRR Main Line, and then the Bay Ridge branch again, with even less fanfare. During its stint as the main drag of Maspeth, the street is downright quaint, dotted with old looking pizza places that I would assuredly have patronized had I not already had my fill of Venezuelan goodness. It crosses over the LIE… It was at this point that I bailed the last time I attempted this walk, scurrying down 69th Ave. to catch the M train. But not today. Today, I was determined to make it to the sea.
I briefly stopped at an Italian pastry shop called Russo’s, to grab an apple turnover and a coffee. I’d been out in the cold for about three hours now, and it was starting to get to me. It was unremarkable, but warming. I continued along some lovely residential areas, that gradually became less lovely until, quite suddenly, I came to the real fascinating part of the trip: The industrial wastelands near Newtown Creek.
During the week, so I hear, the area is a busy industrial zone. But during the weekends, the only time I can visit, the place is eerily desolate, with huge, idle factories the only thing in sight. Occasionally, a car will race by at a completely unsafe speed. I passed the aptly named Rust St., and the almost-never-used Lower Montauk Branch of the LIRR (which I vow to ride someday while it’s still in passenger service).
It is in the industrial wasteland area where you cross the Grand Ave. Bridge, which traverses the fascinatingly polluted Newtown Creek and brings the road into Brooklyn. Large swaths of the waterway were frozen when I crossed.
At this point, Brooklyn and Queens are indistinguishable zones of the same wasteland. Then, gradually, life returns to the road, now called Grand St. Crossing over the Metropolitan Ave. Bridge gave me my second view of Newtown Creek. Shortly thereafter I stopped at a gas station to use the facilities and grab another cup of coffee. The sun was setting, and a real chill was setting in.
It’s hard to say when one crosses from hardscrabble East Williamsburg to Williamsburg proper. (Well, I’m sure it’s easy to say if someone knows where the specific border is.) But the neighborhood just becomes gradually more human, and then more hipster. I got to Bushwick Ave. and the L train, the first subway I’d seen since Elmhurst. It was about here, Paula texted me again, “Are you still in Elmhurst? You okay?” Imagine her surprise when I replied, “No, I’m in Williamsburg right now. Almost at my final destination.”
And so I was. I was somewhat depressed but unsurprised to find that the ancient and storied Grand St. was cleft in twain by the BQE. I knew I had to meet that road again, but I had no idea our second encounter would be so abrupt. I walked around to Borinquen Pl., up Marcy Ave., and continued down Grand.
Grand St. here showed its next personality, transitioning from hipster poverty to hipster wealth. Upscale restaurants, boutique stores, art galleries. And then, just as I reached Wythe, I could see it: The shining blue waters of the East River, and the island of Manhattan beyond. There was a spring in my step despite the blister developing in my right foot. Finally, I went beyond Kent, to the End of the Road. I stopped only briefly to appreciate my accomplishment, and the lovely views of the Williamsburg Bridge at sunset. The time: 5:07 PM.
I texted Paula about my Great Pedestrian Accomplishment, and somehow she wasn’t feeling the same sense of victory I was. Her response was, “Are you crazy! Get in a train and come home, please.” Well, that was going to take some doing, as the closest train was the L, which wasn’t going my way, and the second closest was the G which wasn’t running this weekend. So I decided to walk some more.
I walked along Kent Ave., past the behemoth condo towers, that, while I’m sure someone will buy, I can’t imagine who. I mean, at the prices they charge, I’d rather live closer to, you know, things and people. But whatever. I continued along Kent, where industrial Williamsburg is engaged in a pitched battle with condo development. I passed Bushwick Inlet, near which industry is still very much in the lead. Kent became Franklin, and industry became actually kind of quaint Greenpoint, a place I might like to live, but the utter lack of G train today wasn’t selling it very well. I turned down Greenpoint Ave., and then up McGuinness, with an eye to crossing the Pulaski Bridge. I’d never noticed how narrow Greenpoint proper is, and how the almost highway-like McGuinness Blvd. separates residential from the hard-core industry near Newtown Creek. On the way, I saw a “ghost bike” tied to a sign, another sobering reminder of the danger of the roads I like to travel on.
As I crossed the Pulaski Bridge (and hence, Newtown Creek for the final time at its widest point), the wind really began to pick up, and the chill of the evening started to reach my bones. But I did take the time to appreciate the lovely views of Manhattan, and then on the Queens side of the creek, the very end of the LIRR Old Montauk Branch at Long Island City Station, and the entrance to the Queens Midtown Tunnel.
Just as I finished crossing the bridge and headed down Jackson Ave., a B62 bus appeared and opened its door. Chilled to the bone, I ran to it appreciatively. My walk was done.
Here’s how far I went:
View Walking the Broadway/Grand Ave./Grand St. Trail in a larger map
According to Google Maps, I walked about 12.3 miles, and cut a satisfyingly large section of Brooklyn and Queens. It would have been nice to have made it all the way home, and completed the “D” shape, but by the time I got on the bus, I was freezing and exhausted.
I love these long walks of mine. It may seem trite, but setting an ambitious goal and reaching it, even if it’s simply a long distance to walk along a specific path, is extremely satisfying. When I’m in a funk, as I was earlier this weekend, it’s quite restorative.
In Praise of My Team
So, as I promised, this past Sunday, my Level 1 Improv class at the PIT performed our class show. Our final class, in which we basically practiced the form of the show, seemed a little rough to me. I still feel like I’m struggling to be a relaxed, grounded performer. I was a little worried.
I shouldn’t have been. We rocked. Everyone in the class brought their “A” Game.
We got to the theater a bit early – 6 PM for a 7 PM show. We actually managed to do a fairly extensive rehearsal with our teacher beforehand, which I think really helped us get our heads into the game. Before the house opened, I took a moment to stand on the stage and just breathe in the theatrical air. Although I’ve done a few brief performances on that stage before now, it was the first time I ever got to just stand there and worship the space. It’s an important part of my theatrical ritual, and something I’ve missed desperately.
So, as I said, everything just seemed to fall into place with everyone. Sure, there were a few clunkers for scenes. I promised myself that I’d play more grounded, real characters. When I forgot that, it was rough (although I was often saved by my scene partners). But when I kept it in mind, I felt like we did some really good stuff up there.
Don, Alex, and Tesse were there to cheer me on, and they joined me for a few drinks at Mustang Sally’s afterwards. It was especially gratifying that Alex was there, since it was her Level 1 UCB class show that inspired me to get back into this crazy business we call improv in the first place.
I would be remiss if I didn’t mention our wonderful teacher, Tom Ridgely. He’s knowledgeable to be sure, but a lot of people are knowledgeable. More importantly, he’s endlessly patient and encouraging. Where my own experience might drive me (back in my improv directing days) to issue an authoritative rebuke, Tom steers the ship so gently that you can barely feel it, until 8 weeks later you find the ship has mysteriously taken the proper course. He took a motley crew of improvisers with experience ranging from extensive to none at all and made us, for one night, perform as a team.
Right now, I’m in a bit of limbo. I will definitely take a Level 2 class, but right now the only one available is during Paula’s Icky House Club rehearsals. I’m wary of going up for the open jams, just because it’s very hard to get into a groove with people that you don’t know at all. No matter what happens, though, I will continue this journey. It felt so good to be welcomed back in the congregation to worship at the altar of the theater.
Still “Yes, And” After All These Years…
Last night, I attended my penultimate level 1 improv class at The Pit. One of the consequences of having a class is having a class show at the end of the term. For the first time last night, we practiced doing the actual form we’ll be performing in our show. After being kind of down about my performance ability last week, I was actually quite encouraged.
We’re still a bit rough around the edges, but I think that (by level 1 standards) we’ll put on a solid show. For much of the rest of the class, it will be a possibly terrifying learning experience. For me, it will be getting back on a saddle that had been long collecting dust in a closet. This is the first time that I’ve performed improv on a public stage as part of a real team in 8 years.
Please come, won’t you?
The People’s Improv Theater
154 W 29th St. Between 6th and 7th Ave.
Sunday, December 20, 2009
7:00 P.M.
Thanksgiving — Favorite Photos
Here are some of my favorite photos from our trip:
Thanksgiving in Virginia — A Brief Summary…
I realize that I have committed the ultimate blogger sin, and not commented about the family’s Thanksgiving trip to Virginia to visit my mom. Heck, I haven’t even taken notes on it to build into a blog post.
First, I’ve discovered that travelling actually makes me insane. I made the mistake of having the three of us take the bus and the subway to Penn Station with all of our luggage. The N train was not running for some reason, so the bus was incredibly crowded and slow and not at all amenable to our luggage. When we finally made it to Penn Station, we attempted to check our bags, only to be told that we were two minutes too late to do so. So enraged was I that I shouted and screamed and kicked my bags across the floor of the Amtrak terminal. This caused Paula some consternation as you can imagine. In the future, I should probably consider taking a Valium, or at least taking a cab.
We took Amtrak directly from New York City to Charlottesville. As much as I hate Amtrak for very long distance travel (like to Florida), the medium distance to Virginia was actually quite nice. I’ll trade Monster Chiller Airport Security Theater for a bit longer travel time any day.
We spent most of our time with my sister, brother-in-law, and two nieces. Our days in Virginia were pretty much spent either entertaining the kids or desperately trying to take in natural beauty as quickly as humanly possible.
Entertaining the kids was actually quite fun. We went apple picking. We went to a story-time at a bookstore downtown. We took the kids to a “discovery museum” type place. Benjamin rode on his first carousel. Frankly, these things where kids can just run around and be kids make me happy, not just because I like to see my kid happy, but because I can relax and not worry about what trouble he’s getting into or who he’s bothering.
(By the way, having picked apples in both New York and Virginia, I must say that the apples in Virginia were the most unbelievably sweet, juicy, wonderful apples I’ve ever bitten into. Highly recommended.)
Taking in natural beauty is more problematic, because kids just don’t care about that stuff. I wonder why, since it seems to be kind of an innate feeling that all (adult) humans experience upon experiencing the vastness and beauty of unbridled nature. But kids who have otherwise infinite energy develop droopy legs of rubber when asked to walk in nature and appreciate it for its own sake.
That being said, I can absolutely agree with everyone who says that Virginia is God’s country. It is just about the most beautiful place I could ever imagine.
Thanksgiving Day itself was something of a nightmare. We had reservations (all 11 of us!) at the historic Boar’s Head Inn at 7:30. After waiting in a lovely but not particularly kid-friendly waiting room for over an hour, they agreed to seat us in a private dining room. Nothing kids like better than sitting down to dinner at 9:00 PM… So we finally sit down and look at the menus. When Mom made the reservations, lo these many months ago, she asked if they had a children’s menu. They said yes. Well, they technically did, but it was nothing but an abbreviated version of the adult menu. There was nothing and I mean nothing any three-year-old in the history of the world would eat. Every time the waiter set something down at the table, one of my nieces would exclaim, “I don’t like this!” And I could hardly blame her. To add insult to injury, the food wasn’t even all that good for the adults, especially considering the price.
(I snarked to Paula later, “For that price, I could have leaned out my window and shouted, ‘You there! Boy! What day is it?’ and he would reply, ‘Why it’s Christmas Day, Sir!’, and I could say, ‘Oh, wonderful! I haven’t missed it! Do you know that turkey in the window?’ ‘The one as big as me, sir?’, etc.)
What do I really want for Thanksgiving? A big family at home sitting around a messy table with a whole turkey (none of this “turkey roulade” crap like they served at the Boar’s Head) and my Grandma’s kishka stuffing. I talked to my sister the other day, and she said she was making a turkey dinner for her family to make up for the one they didn’t have on Thanksgiving. That sounds like a wonderful idea.
After Thanksgiving Day itself, things calmed down a lot as people started to head home. Highlights of the post-turkey period include our trip to Monticello, Thomas Jefferson’s home and the most beautiful historic mansion (on the most beautiful grounds) I’d ever seen. Its functionality and good-sense are a stark contrast to the garishness of Vizcaya in Miami, the only other historic mansion and grounds I’ve been to.
Truth be told, although it’s always wonderful to see family, the trip was actually incredibly stressful. There were just too many people in the same place at the same time. Still, the sheer beauty of the place makes me eager to visit again in a hopefully more relaxed atmosphere. Unfortunately, the next time I’ll be there will be in April for a wedding, and weddings are not known for being laid-back or kid-friendly…
You Say Tomato, I Say Productive
All my life I’ve had trouble concentrating and staying on-task. When I need to focus, there always seems to be some shiny bauble destined to lure my novelty-seeking wandering eye. I struggled with this all through high school and college with this, and as you could imagine the advent of the infinite novelty hole called the Internet has made this tendency even worse.
Over time, I’ve tried several time-management systems. I was a big fan of “Getting Things Done” for a while. But, as is often the case with self-help-type things, the wagon was eventually fallen off of.
Then, one day in the recent past, while once again seeking novel baubles of memage when I should have been working, I came across a post extolling The Pomodoro Technique.
The way it works is pretty simple. You just break up your day into 25-minute windows called Pomodoros. During each Pomodoro (or Pom, for short), you set a timer for 25 minutes, shut out all outside distractions as much as you can, and work with complete focus on one task. After you complete the Pom, you take a 5 minute break. Every four Poms, you take an extended break, which works out nicely into either your lunch hour or a coffee break. If you go to the website, there are all kinds of online resources for using the technique, but the only thing I use (besides a pencil and paper to keep track of my Poms) is a free 25-minute timer program called Focus Booster.
Naturally, I’m a bit wary to write about a new productivity technique, since I’m so prone to chronic gradual wagon departure. However, since I started it a few weeks before my vacation, my productivity really has shot up markedly. One thing that has worked well for me in particular is that it’s very forgiving if I “fail” my Pom and get distracted by a shiny object. Before Pomodoro, I could spend hours down the Internet Rabbit Hole if I got distracted. Now, I can give myself permission to blow off the current Pom and get back to work when the next one arrives. And as a bonus, I have super-granular time-tracking data for free, which is great because before now time tracking was something I loathed and feared more than death itself.
If your job description fits the general category of “knowledge workers who work mostly independently at their computers and are prone to distraction,” I highly recommend this technique. It might not work quite so well for “I attend a thousand meetings a day” people, or “I have a boss who constantly gives me specific things to do” people, but for me it has been nothing short of revolutionary.
Why “Pomodoro?” Because the person who invented it is Italian, and had a 25-minute timer in the shape of a tomato.
Awesome Things My Friends Do: Sleigh Ride in Bora Bora
We got back from Virginia on Monday afternoon, and I’ve been procrastinating writing and posting the photos about it. However, an incredibly delightful Christmas-wrapped bag of awesome has just been dropped into my lap, and I can not let another moment go by without telling you about it.
It is “Sleigh Ride in Bora Bora” by my wonderful friends Melissa Axel and James Jacoby. (And some of their friends who I’m sure are actually wonderful themselves, but I’ve never actually met.)
Get the song now. No, seriously. Do it.
It’s kitschy and delightful, and I double-dog-dare you not to smile while listening to it. It is immediately jumping head-first into our family Christmas music rotation. Not that we really had one before, but thanks to this song, we’re totally starting one.
Someday Somebody Else Besides Him Will Call Him By His Stage Name…
You’d think that, being a They Might Be Giants fan myself, that I’d pushed Benjamin into loving TMBG more than anything else in the world. Unless there’s a genetic component to musical taste, (which has been confirmed to be not true by generations of teenagers) Benjamin has picked up this love all on his own.
Case in point…
