How to excel in Computer Science or Engineering

13 01 2012

It’s official: I’m the proud new owner of a Bachelor’s of Engineering in Computer Systems Engineering, and managed to graduate with highest honors and a GPA that makes most people hate me. After nearly 5 years of intense procrastination (er, I mean intense studying), living on a diet of Monster energy drinks and ramen, and having a sleep schedule so erratic my friends call me a voluntary insomniac,  my time in college is over for the time being. Having theoretically gained at least some wisdom and experience over the last five years, I thought I would offer it to the Internet for future generations.

Learn to program before college

I learned HTML/CSS when I was 12, was using Linux by 15, and knew enough about security to hack into my school’s webserver by 16. I took up programming at maybe 17 by teaching myself Python from online tutorials (which I’ve entirely forgotten the syntax of, but many things are universal in programming languages). Am I an unusual ubergeek? Well, yes and no. The fact is that if you enter CSE101 not knowing how to program, you’ll probably be in the minority. Does this mean that you’re behind and won’t be able to do well in CS? Certainly not. But this does mean you don’t know,

  • If you’re going to like programming
  • If you’re going to do well at programming
  • If you’ll enjoy sitting at computers for hours learning stuff or go stark raving mad
  • If you’ll be frustrated  not knowing what you’re doing or just accept it and keep searching for the answers
  • If you’ve accepted the fact that you’re going to be a geek in every sense of the word (or at the very least, be surrounded by them)
  • If you can handle spending 30 minutes writing a program and 3 hours debugging it
How do you choose to devote 4 years to life into something if you haven’t tried it? The answer is that it’s a lot easier to do if you get your feet in the water early. Another advantage of learning to program before you start is that your first CS classes will be a breeze. You’ll probably be disappointed that they’re so slow and boring, but don’t be. Spend your first couple of semesters,
  • Surviving Calculus (I-III), Linear Algebra, and any other hard classes your college requires
  • Using CS classes as GPA boosters (a pile of A+’s early on is how I graduated with highest honors even though my grades slipped a bit in the end)
  • Getting rid of pesky required humanities on things like ancient mesoamerican rubber ball making cultures (true story)

Don’t be too hard on yourself as a new programmer

When I started programming, I thought I was a horrible programmer, and it scared me. Now, I do have one of those personalities that make job interview terrible because I’m always self deprecating when it comes to what I’ve done, but the truth is you’re going to start out being a terrible programmer. Take a look at something I wrote on this blog nearly 4 years ago.

Do I have the art of programming? Nothing I’ve written is very impressive, half finished and unmaintained projects clutter my hard drives. The most complicated thing I wrote was a nearly 3,000 line IRC bot, with a plethora of useless features. The architecture got so bad that I couldn’t even figure out how to fix it to make it connect to esper’s servers correctly after they changed to a new version.The !google feature also mysteriously broke. I admit, when I started writing it I knew a lot less than I did now, and I wouldn’t make a lot of the same mistakes (variables all over the global namespace, lack of comments, horribly inefficient algorithms that make it take up over 100MB of RAM when the log files are loaded) if I rewrote it from scratch, which is the only way to really salvage the project, and too much work to bother with. Meh.

On the other hand, I can’t conceive of any other career that I’d like to peruse with even half as much enthusiasm, so even if my fate is that of a mediocre code monkey, it seems better than the other possibilities.

Did I turn into a mediocre code monkey? No, I’d like to think I turned into a decent software developer. I’m still a newb in many fields and feel behind sometimes (mainly in all the new web development technology), but in general programming areas I feel rather confident. It just took a lot of practice, and frankly a lot of mistakes. That little IRC bot I wrote taught me a lot about big projects. I don’t use tons of global variables anymore, I try not to write programs that take 100MB of RAM. I once learned the hard way by taking down a big company’s production database for a night that making sure your database connection code handles disconnects properly is really important.You’re going to start out a terrible programmer; see above point about getting a head start before college.

Part of the problem that made me question my computer science talent was the stress on the science part of some of my classes. Part of me back then thought that algorithm development was really important, and without it you aren’t a good programmer, since half of what you did in classes was go out and implement merge sort or Red Black Trees while sitting around studying linear algebra and calculus. The truth is you can still be a good software developer even if tracing through dijkstra’s algorithm gives you a headache. In the real world you’re far more likely to use a library implementation of an algorithm than code it from scratch, and high level abstract understanding is far more important than detailed understanding of the implementation or the ability to come up with such an algorithm on your own.

Learning the IT stuff

Now that you’re hopefully convinced you should be getting a head start on CS stuff, how do you do it? Having a solid foundation of computer skills is essential, and something they won’t teach you in college. Go get yourself an old computer from a swapmeet or online and install Linux. Never seen hard drive jumpers or power supply connectors before? Crack that baby open and see what’s inside. Then, install Linux. The reason is not because Linux is better than Windows, it’s because Linux is more transparent and actually more difficult to use. It’ll fail to install correctly, and in the process you might figure out what a bootloader is. You’ll pick up some terms about make tools and shared libraries when you install solitaire. You’ll pick up new concepts like dependency hell and kernel panic. It will be a love hate relationship and the process may lead to shark attacks.

You could call Linux a sort of bootcamp for computer people. When I started, everything that could go wrong went wrong with it. I once by accident destroyed my windows partition. I found that my video drivers were buggy as hell, my wifi cards needed custom firmware loaded into them, and that trying to get sound to work in Linux is less fun than herding mutant cat mules. I once managed to destroy X because it was a package dependency for a Firefox upgrade and the AMD64 bit version was unstable (or incompatible with something, I never found out for sure since that was the day I gave up using Gentoo). I once spent 3 hours trying to track down and manually compile all of the dependencies for a side scrolling open source game that only provided 30 minutes of entertainment actually playing. My SSH log in was always being harassed by strange Chinese IP addresses and the server was screwed up once from SQL injections on something I wrote.

The point is: when things are working fine in Windows all day, you don’t learn anything. Linux is actually becoming easier to use than ever with distributions like Ubuntu: don’t be afraid to jump into the more “advanced” distributions. I suggest Slackware as a good middle ground between working out of the box and being a good learning experience, then pick up something like Gentoo. Remember: pain is weakness leaving the body. Sometimes the old people complaining you kids have it too easy are actually right. When I was a kid, I remember having to wander the filesystem in a MSDOS command prompt… now get off my lawn (I’m a college graduate, I have the right to say that now, right?)!

Back to the details. What do you do with Linux now that it’s working?

  • Learn to use the command line (+1 for learning shell scripting)
  • Learn Vim (+1 if you become a vim junky and install vim shortcut emulation plugins in your browser)
  • Get SSH working
  • Get a webserver working (http, ftp)
  • Did you pick up HTML yet? Go host your own webpage
  • Get Samba working
  • Play with cron jobs for doing backups and maintenance
  • Try different GUIs (KDE, Gnome, xfce, Fluxbox)
  • Try to recompile your kernel, explore start up scripts, and make it boot as fast as possible
  • Look up guides on how to keep it secure and maybe play with some offensive security (hacking) network tools on your own network

Learning the programming stuff

Alright, you’ve either gotten the basics of computer stuff down or skipped it since you want to get straight to programming that video game idea you’ve been dreaming about. Either way I would recommend that your first programming language is something high level with a decent GUI library built in. Personally I went with Python/Tk followed by TCL/Tk. Other options could be Ruby or PHP if you can find decent tutorials on the internet for them. The reason for not jumping straight into C/C++/Java is that a scripting language will probably let you get to fun stuff sooner. Using Tk you can throw together a little tick tack toe game in about 5 minutes once you know what you’re doing. The second advantage is that this will reduce you’re boredom in beginning CS classes where they will probably start with either Java or C++. The third advantage is that a scripting language is always useful as a go to language for a quick script to do something like text processing. Learn regular expressions, they’re useful even for everyday find/replace tasks on a decent text editor.

How to learn to program

Learning to program is a bit like learning a musical instrument. People can tell you how to do it 500 times and it won’t make you any better. You simply become a better programmer by programming. When you’re learning to use Linux, it generally screws up and you figure out how to fix it. When you move on to programming, you screw up and slowly learn from your mistakes until you see what to do and what not to. Some things might accelerate the learning path: seeing really good code, seeing really bad code, finding the built in library that does the exact thing you’ve spent 3 days programming from scratch, sitting through lectures on software design and algorithms. Overall the best way to learn to program IS to program. I absolutely can not stand reading tutorials on the syntax of languages. Learn the basics of a language and then move on to actually trying to program something. What you ask? What do people draw when they learn to paint? What do people play when they learn music? What kind of building does an architect practice design on? There’s no correct answer; be creative. If you can’t think of anything useful to make, you can always resort to classic games (tic tack toe, checkers, chess, blackack, rubik’s cube, tower defense game, etc etc). The point being it’s easier to study pages of dull documentation when you’re using that to work toward a working program rather than just trying to memorize stuff. Your program might have been programmed a hundred times before, but that won’t make it any less of an experience writing, and you could learn from other people’s implementations.

Keeping the passion and motivation

Everyone has highs and lows when it comes to interests in things. If you’ve been reading from the beginning of this you probably think that I sit around every night writing MMORPGs and hacking together Linux scripts that make my Linux box take input by voice command. The truth is that  my work ethic can best be summarized as spurts of obsessive genius followed by long stretches of laziness, and the vast majority of my nights are filled catching up on all the TV I somehow missed growing up (seen Buffy the Vampire Slayer? If not, go, watch, now). This occurs on both a daily and long term basis, and I don’t believe I’m alone in it. Something I saw in a post by Joel Spolsky resonated with me,

Sometimes I just can’t get anything done.

Sure, I come into the office, putter around, check my email every ten seconds, read the web, even do a few brainless tasks like paying the American Express bill. But getting back into the flow of writing code just doesn’t happen. These bouts of unproductiveness usually last for a day or two. But there have been times in my career as a developer when I went for weeks at a time without being able to get anything done. As they say, I’m not in flow. I’m not in the zone. I’m not anywhere.

For me, just getting started is the only hard thing. An object at rest tends to remain at rest. There’s something incredible heavy in my brain that is extremely hard to get up to speed, but once it’s rolling at full speed, it takes no effort to keep it going.

This is the same with me. Once you get in the middle of a programming project it isn’t a chore, it’s a rush, a feeling of zen that most people rarely find during their day job. However, finding the motivation to get started, especially without school or work deadlines pushing you can be the last thing you feel like doing. I don’t have any solution to this other than: think of something to program and force yourself to start. Sure, it might end up being a false start, I once tried to force myself into the mood by programming an Android time tracking application for people with type A personalities (or just plain OCD, doubt I would ever actually be able to consistently use such and application). It ended in nothing but a failed attempt to find the Ballmer Peak and a slightly more advanced version of the classic Hello World program to see if my SDK was set up.

You might find motivation in odd places too. Why did I take up exploring network security? Anger at someone who told me their page was secure after I said it was outdated and full of holes. I once programmed a puzzle solving game automation program to impress a girl (she was impressed, but in hindsight asking her out would have been a far more effective move). The IRC bot I wrote was partly inspired by another guy writing a bot and battling mine with massive kick/ban/flood wars until the IRC network banned both our IP addresses.  Good times. What you should take away from this is that programming game playing algorithms is not a good way to attract a girl.

If you manage to make it through college as a CS major without having at least one existential crisis, I’ll be amazed. At some point you’ll probably be sitting gloomily in front of your computer realizing that the last x years of your life have been focused around the perusal of degree which will enable you to spend 10x that number of years sitting in front of computers pressing buttons and making the patterns on the screen change. In fact, this was the hardest thing about college for me. It wasn’t the work, I could do the work easily if I applied myself. It was just trying to not fall into apathy, or worse, pure hate for school (keep reading and I’ll got to this).

How did I survive it without becoming a deranged alcoholic? It’s surprising how many software developers and IT people you can find in hole in the wall bars; you should be concerned I know this. There is no easy answer to this. My only advice is to find something to do, even if it isn’t programming. The worse period of my college experience was about 6-12 months ago when I simply had no motivation to touch any CS stuff outside of work and school. The classes I had were both boring and tedium filled, the capstone project I was looking forward to ended up being a huge wast of time, and I’d been both in school and at my internship long enough that absolutely nothing new or exciting was happening in my life. I managed to narrowly avoid failing Statistics for Engineers (pulled a C out of it from 2 days of cramming for the final). The only thing that pulled me out of it was the reality that this is my last semester and I really need to start doing things like planning for a career and not failing my last upper division humanity.

Thoughts on bad professors

An unfortunate fact of my college experience is that I would say the bad professors outnumbered the good professors by probably 2 to 1. For every lecture I went to, I had 2 others with a professor I found mediocre at best.  Is this conclusion because my expectations for professors are too high? Maybe: what makes a good professor?

  • Knowledge of the subject matter above and beyond the textbooks
  • Can be understood (doesn’t skip too many steps, can speak English, can explain things articulately, can write legibly)
  • Entertaining personality/ability to hold people’s attention (throwing in a joke or story instead of 75 minutes of straight monotone slide reading)
  • Fair grading scheme and tests
Once you get to upper division classes, you might be able to start picking classes from professors you know are good. I’d definitely recommend this, nothing is worse than being interested and excited by a topic and then losing all interest because you hate the class so much.

Graduating on time

College advisers always push graduating on time. I went the route of attempting a double major (in math), giving that up, and ended up being behind 1/2 to 1 year depending on how you count things. I don’t regret it at all, if you’re liking college, don’t be afraid to kill some time with interesting non-required classes. It’s easy to get internships when you’re in college that look good on a resume, and in the big scheme of things, who cares if you’re a year older when you enter the work force?

Exception: if you’re hating every moment of college, try and get out quick and not procrastinate. I put off a few classes I didn’t want to take and I would have done better on them earlier on before I lost a lot of my motivation. For those in pain, the quick bandage approach is far better than the slow procrastinating but loathing perma-college student that takes 8 years to finish their degree (I’ve seen it). But hey, 8 years if you’re having the time of your life might be okay, just depends on your situation.

Final thoughts and a link

Somewhere in the middle of college I stumbled across Joel Spolsky’s blog, Joel on Software; I highly recommend reading through his old posts. One of his posts offers some advice for computer science majors.  Go read it yourself, but here are his main points.

  • Learn how to write before graduating.
  • Learn C before graduating.
  • Learn microeconomics before graduating.
  • Don’t blow off non-CS classes just because they’re boring.
  • Take programming-intensive courses.
  • Stop worrying about all the jobs going to India.
  • No matter what you do, get a good summer internship.
A good point to end on: companies like having interns. Programming interviews are hard to properly conduct. Internships let companies have a nice trial period where they get to see what you’re capable of, and you get experience, resume fodder, and money. One problem I had was not knowing when I had enough skills to actually get an internship. Simple answer if you’re an ASU student, CSE310 (Data Structures and Algorithms) and CSE360 (Sofware Engineering/Design) will give you what you need to at least have a good change at surviving a technical interview. That doesn’t mean you couldn’t pick of the stuff you need before the classes or try to interview anyway, but in my experience interviewers focus on algorithmn (reverse a linked list, common algorithm time complexity, space complexity, hash tables, sorting) and OOP design (think through a first pass architecture of a program that does blah and scribble it on a white board) questions a lot, especially for college students that don’t really have much past experience to point to in order to show their skills.




Top 10 Gvim/Vim Commands for coding

16 05 2011

When you first start using Vim, you’ll hate it. It makes a terrible first impression. It isn’t until you think one day, “Hm, I want to skim up to the top of the file to remember what that variable name was, then jump back here,” and then proceed to type, without thinking, magg’a. That’s the day you’ll fall in love with Vim, when you start translating complicated editing actions into quick commands rather than painful trudging through files one arrow key press at a time. You tell Vim what you want to do, and it happens. It just takes a long time to learn how to tell Vim what to do.

If you had to code using just 10 Vim commands (besides edit, write, quit, etc), what would they be? Here are my favorites.

Navigating the Code

1. / text or ? text Fine next/previous occurrence of the text specified. Also highlights all matches. This is the primary way I find myself moving to the middle of a line in Vim. Rather than sitting there and scrolling right character by character or word by word, just start typing the text you want to move to. n moves to next match, N moves to last match. Using the find command may seem like an odd way to move around at first, but I find that just typing 2-3 characters will take me right where I want to go 90% of the time, and ends up taking way less keypresses than other navigation methods.

2. :xxx Jump to line number xxx.

3. ma will mark your current cursor position, ‘a will jump back to it. The a can be any letter. This is amazingly useful when you want to scroll somewhere in the code to read and remember how you did something, then jump right back to where you were editing.

Writing new Code

4. Ctrl+n in insert mode will attempt to autocomplete whatever you’re typing. Great for being able to type partial variable or function names, minimizes typos and speeds your typing up. This can be enhanced further with the intellisense plugin.

5. o in command mode will create a new blank line below your current cursor position, move your cursor to the correct indentation level, and go into insert mode.

6. % in command mode will jump to the opposite brace of the brace your cursor is at.

General cool stuff

7. ! xxx will run the command xxxx in a terminal and show you the result, then let you jump back to vim when you’re done.

8. :%s/1/2/g Replace all instances of 1 with 2 in the file. Can use regular expressions and is extremely powerful.

9. :badd/:bn/:bdel navigating multiple files at the same time is a must for a programmer.

10. y/p yank and paste (also known as copy in paste) is such a fundamental command it hardly warrants mention, but it’s used so often that it takes the number 10 spot.





The Quest for Programming Zen

23 02 2011

Every good programmer knows what it’s like to have a programming spree. For some it’s a rare but wonderful occurrence, for others it’s a daily thing. It’s those times where you stay up until 3:00am trying to perfect a piece of code, then wake up in the morning still thinking about it. It’s those times where you code for 8 hours straight at work and get yelled at by HR for skipping your lunch break. It’s those times you become so immersed in your work that your mind doesn’t wander, get tired, or get bored. It’s an illusive and spontaneous thing, impossible to force yourself into if the conditions aren’t just right.

What causes such sprees? What separates mind numbing tedium from intense programming that you love to do? And are we as software engineers alone in this feeling of zen? We’re certainly not alone, but it may be surprising that the near cousin in our quest for coffee induced super human attention spans is not another engineering discipline, but rather a form of entertainment: video games.

I was watching a video lecture the other day on 7 ways that video games reward your brain. The single most interesting thing I find about video games is their ability to engage people’s minds for long periods of time. Instead of vegetating in front of a TV, they make people actively solve problems, compete against other people, and make seemingly tedious things nearly addictive (see Farmville), but without feelings of boredom or burnout. Does programming reward our brains the same way that video games do?

1. Experience bars measuring progress

Ever since the beginning of video games, cold hard numbers have reported progress and skill in video games. It’s nearly impossible to find a video game that doesn’t contain scores, levels, or character experience counters. Programming can also provide some empirical measures of progress in the form of line numbers, file sizes, code check ins, bug counts, and requirements met. As you’re programming you have a mental road map of where you’re going, and you have some idea of how close you are. The future may be filled with unpredicted obstacles impeding your progress toward your goal, but video games are similarly unpredictable. Sometimes level 20 seems right around the corner, but you get stuck trying to defeat a group of enemies or conquer a troublesome city. The constant desire to further your progress drives you forward.

2. Multiple long and short-term aims

Video games don’t just reward the player at the completion of the game, but incrementally guide and reward them on their journey. Similarly, programming is not just about getting to the completed program. The program consists of many objects, functions, and small individual pieces that must be constructed before we get to the final integration. Each of these smaller tasks is a short term goal, a specific thing to keep your mind focused and busy on, all the while making progress toward a long term goal.

3. Rewards for efforts

Rewarding effort is a mysterious thing. On one hand, you might not think that watching crops grow and getting money for them to plant more crops would be rewarding, but the millions of people playing Farmville prove otherwise. The reward for video games usually comes in the form of unlocked weapons, levels, and character perks. In programming, the reward is the satisfaction of creating a program and having it run correctly. Programmers simply enjoy what they do, and in a zen like way, are rewarded just by doing it and doing it well. There are, of course, also financial and academic rewards associated with many programming projects.

Computer Problems (XKCD 722)

4. Rapid, frequent, clear feedback

This is something that separates software engineers from other types of engineers, and is quite possibly a reason why someone like electrical engineers don’t obtain the same zen like states that we do. An electrical engineer will take design requirements and spend the majority of their time painstakingly creating schematics for the design before they even get close to having a real device to look at and test. Software engineers on the other hand, will compile and test pieces of their code literally hundreds of times a day. Of all the engineering disciplines, software engineering is the one with the most rapid and frequent feedback.

5. An element of uncertainty

If you were playing a video game where every enemy you killed dropped the exact same items, or enemies always appeared in the same size groups and locations, the game would be far less fun. Do elements of uncertainty make programming more interesting? Your first thought is probably that you hate uncertainty when programming, and anytime something uncertain happens it’s usually some sort of frustrating bug. However, there is an element of uncertainty in program design that could equate to this in video games. If you designed a program in your head, every little detail, and then began to program it, it would be a very boring procedure of typing away at your keyboard inserting the appropriate code into the computer until done. However, that’s not even a possibility in programming. Instead, a high level view of the program is constructed in your mind, and like an artist creating a painting, the visual feedback he receives from every stroke of the brush effects the next. You don’t sit down knowing what your program will look like, but rather you build the program up from your mind in an uncertain fashion. The element of uncertainty in programming is actually a byproduct of our brains inability to predict and fashion the entire program in our head. The limited scope of our brains means we can’t see what we’re going to create in even the near future.

6. Windows of enhanced attention

A game consisting of nonstop action is tiring. They do exist, and can frankly be a lot of fun (see the open source shooter Nexiuz), but the design of the game must be different to counter the mental exhaustion. Death matches between players have to be quicker, and competition has to fuel the attention span that would otherwise wilt. A more common theme is using windows of enhanced attention. The actual size of these windows is a science and art that video game designers have been striving to perfect since the beginning of games. Finding a balance between exhausting amounts of action and giving the player too much down time to relax and let his attention wander is not a trivial challenge at all. Does programming contain windows of enhanced attention? Definitely. The size and length of these windows vary depending on the type of programming your doing, but the actual programming is the enhanced attention window, and the debugging/testing is the downtime.

7. People

Single player video games can be fun, but ultimately have very short lifespans. The games that live on for decades (World of Warcraft) are games that have a good interaction with other people, providing both competition and teamwork. Likewise, individual programming projects can be fun and hone one’s programming skills, but in the end it’s the large scale projects that will live on. Starting an Open Source project is analogous to starting a game clan. You have a goal, and you find other people to join you and help complete that goal. You also have large scale competition among companies and projects (Firefox vs Chrome, Google vs Bing).

Perhaps in looking to our video gaming cousins in computing, we learn a bit about our own psychology. Is this what the zen like programming zone is? Working and competing with others on a constant drive forward, measured by metrics of progress, and filled with uncertain challenges with both long and short term goals as we’re rewarded and given rapid feedback.





Project Euler Problem #15

20 03 2009

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

p_015

How many routes are there through a 20×20 grid?

First off, let me say I’ve never taken a combinatorics course, and before this problem had never seen the words “n choose k”. If you’ve taken a combinatorics course, you’ll probably figure out this problem in about 3 seconds, realizing it’s simply 40 choose 20 (which Google calculator will gladly output). Due to my lack of combinatorics, I was forced to take a very long route to get to the answer, but challenged myself a lot more in the process.

First off, I thought to myself, there must be some function f(n) for an n x n grid that will give me the result, and I just need to find it. In order to simplify things, I changed the grid to a set of equally spaced points in a plane. For a 2×2 grid, there would be 9 points (2+1)(2+1). Then I traced through the grid again, looking for some simple pattern. I quickly noticed that once you hit the bottom or right edge, you must go straight to the end point using a single path (along the edge). Otherwise, you have two choices (down or right). In my diagram below, I drew arrows on the points that I had a choice, and simply put a line through the points on the edges that had no choice. I also took note that for an n x n grid, there would be n movements in the right direction, n movements in the down direction, and 2n movements total.

paths2I was also on the bus at the time, so no access to a computer, which explains the badly scribbled diagrams.

The only pattern I could deduce from this, is that because there is 2n number of moves, all of which n must be down and n must be right, I could do something like this.

Down = 0

Right = 1

Paths to end in my 2×2 grid (from left to right, top to bottom in the diagram): 1100, 1001, 1010, 0011, 0101, 0110.

Nifty, but how do I make an algorithm to actually create these numbers? I could simply check using a brute force method, generating all the binary numbers from 0 to 15, and then checking if they meet the requirements. To solve the problem though, I would need to generate all the numbers from 0 to 2^(40). That’s a lot of numbers to check. 1,099,511,627,776 of them to be exact. I found the result of the 3×3 grid by hand, through painful searching. There’s 20 of them, so I don’t bother to show the result. If anyone finds an easy algorithm to use this method, I’d be interested in seeing it.

As things were, I hadn’t gotten far, and decided to take another approach. After staring at 1’s and 0’s for so long, I was ready to stare at something more graphical, and decided to represent the 3×3 grid paths as a binary tree, in the back of my mind thinking I could use a linked list in C to actually make such a structure and maybe get somewhere. First off, I put all the points into an array (in my head anyway) so I could easily keep track of them. P11, P12, P13, P21, etc for labels. Then, for a down branch, go left on the tree, and for a right branch, go right.

pathtreeThen I spent quite some time trying to make out patterns. First off, I began noting the paths from a point down to the bottom, which you can see in the small numbers on the lines and under the points. Then I noticed the tree diagrams for a 1×1 (red) and 2×2 (blue) grid were actually inside the 3×3 (green) grid. Nifty! Closer I thought I was, to finding a simple recursive function to find the answer I seek. Unfortunately, I couldn’t devise a simple function to generate the number of paths from the next tree diagram. Then, it came to me, looking at the path lengths.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

20

Eureka! It’s Pascal’s  triangle up-side-down! The result I seek for a n x n grid is the middle number of the 2*n’th row of pascal’s triangle. Not only that, but this is also the sum of the terms squared of the n’th row (one of many odd patterns in the triangle). Finally all I had to do was write a program to calculate the first 20 lines of Pascal’s triangle, and then square the terms of that last row and add them together.

to calculate the triangle,

#include 

#define ROWS 21
#define COLS 21

int main() {
        int triangle[ROWS][COLS];
        int i, j;

        for (i = 0; i < ROWS; i++) {
                for (j = 0; j <= i; j++) {
                        triangle[i][j] = 0;
                        if (i == j || j == 0) {
                                triangle[i][j] = 1;
                        } else {
                                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                        }
                        printf("%d ", triangle[i][j]);
                }
                printf("\n");
        }
}

Resulting in,

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1

Taking all the elements of the last row, squaring them, and adding them,

1^2 + 20^2 + 190^2…. = 137,846,528,820 paths to the end in a 20×20 grid. That’s a lot of paths, I’m glad I didn’t have to resort to a pure brute force approach, it would have taken quite a long time.





A Programmer’s Quest for Primes: Part 4 – Special Primes

10 03 2009

Continuing my playing with primes, I’m now up to having 1 billion of them sitting on my hard drive. That’s 11GB in a text file. It’s actually spread out between 10 files in 100 million prime blocks to load in an out of RAM easier. They were generated in only 30 minutes using the Sieve of Eratosthenes and a modified version of the prime program found here, http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm.

In this post I went through my files finding some statistics on special primes. The graphs below have groups of 1 million primes on the x-axis, and the number of special primes found within that 1 million on the y-axis.

Twin primes: prime numbers that differ by two. For example, 17 and 19. There are theories that there are an infinite number of twin primes, but looking at it as a limit as the function approaches infinity, it certainly looks like it goes to 0, if very slowly. In the first 1 billion primes, there are 58,047,180 twin primes (according to my program’s results at least), or about 5.8% of the total.

twinprimesCousin primes: prime numbers that differ by four. Interestingly, according to some number theory equations called the Hardy–Littlewood conjecture, they are supposed to have about the same distribution as twin primes. My results show it’s quite close, 58,040,262 of them in the first billion primes. The graph is about the same.

cousinprimesSexy primes: no, I didn’t come up with the name, the Latin word for 6 is sex, and the math people love to name things in Latin and use Greek symbols. Primes that differ by 6. There are 105,002,853 of them in the first billion, quite a bit more than twin or cousin primes.

sexyprimesAnswer primes: pairs of primes that differ by 42. Okay, I did make this one up. Any scifi fans out there will see the reference. There are 22,729,810 of them in the first billion primes. The graph is at least more interesting than the others due to the fact it’s a larger number. The distance between primes increases as the primes gets bigger.

answerprimesSome random facts of interest (to weird people like me anyway).

The longest distance between two primes out of the first billion (consecutive composite integers): 394. There are no prime numbers between 22367084959 and 22367085353. If you split the 1 billion primes into blocks of 1 hundred million, and then find the longest runs of composite integers in each block,

292 between 1453168141 and 1453168433
336 between 3842610773 and 3842611109
354 between 4302407359 and 4302407713
340 between 8605261447 and 8605261787
382 between 10726904659 and 10726905041
354 between 11705477863 and 11705478217
346 between 14066075347 and 14066075693
376 between 16161669787 and 16161670163
372 between 20404137779 and 20404138151
394 between 22367084959 and 22367085353

Since the distance on average between primes increases as you get bigger, you’d think the max distance would increase more clearly. Such is one of the mysteries of the primes.





Rubik’s Cube Programming: Part 3

5 11 2008

I’m still messing with the Rubik’s Cube and Java3D every now and then, so here’s an update. Instead of making the cubies actually rotate, I just decided to make them change color. And instead of bothering to keep track of all the cubies and change the colors, I instead just decided to display the cube as a BranchGraph, and then remove the BranchGraph and generate a new one when you twist a side. Result, the colors of the cubies change. Not the best way to do it probably, but it works well enough. In order to rotate a side I’d need to have cubies in more than one transform group, delays to not rotate one side until another side is done rotating, and regenerating the transform groups every twist anyway because the same cubies would no longer be on the same faces. I’ll save that for version 2…

Rubik's Cube Program Version 0.1

Rubik's Cube Program Version 0.1

At the top you have controls to reset the cube to a solved state, scramble the cube,  and display either a black Rubik’s Cube or a see through Rubik’s Cube. In the center, we have the Rubik’s Cube itself, can be rotated, moved, and zoomed using the mouse. The right is a list of text values describing the arrays, and on the bottom is an entry box which will allow values f, f’, b, b’, l, l’, r, r’, t, t’, d, d’, rotating the sides either clockwise or counterclockwise. You can either enter one value at a time or a handful of values seperated by spaces. Everything works fine and I declare it version 0.1!

Rubik's Cube Program Version 0.1You can go play with it if you download Java 3D API here,

http://java.sun.com/products/java-media/3D/download.html

And you can find the Rubik’s Cube in it’s current version here,

http://wolfhacker.jumbofx.com/cube/cube.html

Note: it will NOT work at this moment without downloading and installing the Java 3D API first. It’s a small and fast install though.

To do list:

  1. Display the sides not visable by means of some sort of mirror.
  2. Program the methods to actually solve the cube and display how.
  3. Create user entry mode so people can program in their own cube permutation to be solved.
  4. Run without the need for users to download Java 3D manually.

I’ll get right on that… after writing up an EE120 lab report, doing MAT267 homework, and finishing up homework that’s actually for my Java class… and maybe watching some TV. Stay tuned for most likely the last Rubik’s Cube programming post, part 4!