Hackathon @Google

#Hack4Humanity

This was the hashtag used by close to 100 student hackers, Googlers, and guest speakers at Google NYC’s recent Hack4Humanity hackathon! From Friday night to early Sunday morning, we coded and brainstormed with intermittent breaks for talks, food, coffee, and sometimes even sleeping.

The Google Logo

This was my first official hackathon, so I had no idea what to expect. On top of that, it was at Google, so I really did not want to embarass myself too much.

Upon arriving, and after being given an unhealthily amount of Google swag, we found our table and listened to some guest talks. They described real-life problems they have encountered and empowered us to find a solution. This hackathon was not about making something cool for yourself, or technically challenging; it was about making something useful and even life-changing to some part of the world.

Baris Yuksel (@baris_wonders), a tech lead at Google and one of the hackthon’s organizers, described it best by saying our goal was not to create a “scheduling app” or one of the other dozen ideas that people always try. “How many people in the world do you think would benefit from a website that enables you to double major?” he asked us today, right after complimenting every group on a job well done. The answer is not too many.

Everyone demoed a practical app today that could easily improve the quality of life of some people and possibly safe others.

Our app may not have won anything, but I still learned a lot and was very grateful for the opportunity. Many valuable lessons were learned, and not just on the coding side, and I hope to apply them at future hackathons.

Primes

Prime numbers.

Hopefully, by now, we know what they are. Do we, however, know an efficient way to add up every single one between 1 and 2,000,000?

This question, also known as problem 10 on Project Euler, seems pretty simple at face value. For beginners, the simplest and obvious solution is to solve it by brute force:

Exhibit A

long sumOfPrimes = 0;
boolean isPrime;

for (int x = 2; x < 2000000; x ++) {
    isPrime = true;
    for (int y = 2; y < x; y ++) {
        if (x % y == 0) {
            isPrime = false;
            break;
        }	    
    }
    if (isPrime) {
        sumOfPrimes += x;
    }
}

System.out.println(sumOfPrimes);

This way would be fine if our upper limit was not two million. Running this code works, but it takes over 10 minutes to get the answer on my Acer Aspire S7-392 Ultrabook (a great computer, but it is not Watson).

XKCD 303 - Compiling

I am pretty sure Project Euler has a one minute compiling “rule” where you should get your results in under a minute, so this solution was obviously not acceptable.

The next thing I tried was putting the numbers in an ArrayList, from two to two million. Then, I ran them through a loop that deleted the numbers from the list if they were not prime. You can imagine this was not very efficient either - in fact, it was faster to brute force. After messing around with this (very messy) code for an extended period of time, I did some research on algorithms and stumbled upon the Sieve of Eratosthenes.

Sieve of Eratosthenes

The Sieve of Eratosthenes works on the idea that, if number (n) is prime, any multiples of (n) will not be prime. So where n is prime, 2n would not be.

It took me a few tries to implement it correctly, but I believe I did it farily efficiently here:

Exhibit B

static ArrayList<Integer> primesList = new ArrayList<Integer>();

public static boolean isPrime(int testDigit) {
    for (int primeVal : primesList) {
        if (testDigit % primeVal == 0)
            return false;
    }
    return true;
}

long sumOfPrimes = 0;

for (int x = 2; x < 2000000; x ++) {
    if (isPrime(x))
        primesList.add(x);			
}

for (int primeVal : primesList) {
    sumOfPrimes += primeVal;
}

System.out.println(sumOfPrimes);

Instead of comparing each digit to every possible factor, we now only compare it to known prime numbers. Starting with 2, there are no digits in our array list of primes, so 2 is added to the prime list. The number 3 is compared to the array list of primes, which only consists of 2 - it cannot divide evenly, so 3 is added to the list of primes. When 4 is compared against the list of primes, it can divide evenly against 2, so it is not added to the list and the program breaks out since the number cannot be prime. And so on.

This, of course, makes our program take a fraction of the time to find a solution, because we are comparing each digit against a lot less numbers. When the upper limit is 2 million, the efficiency gains are much more noteworthy.

Time to find the solution in exhibit B: ~46 seconds.

Unclassifieds

Why does everything need a specific category?

Lets replace the classified advertisements with a more modern approach. I could post a wanted classified advertisement on Craigslist, or pay for one in my local newspaper, but there is no guarantee anyone will ever see those. Even if the right person does, who is to say it will be in time?

It is almost 2015: we live in an age where instant feedback is expected. We could hit refresh every 10 seconds on Craigslist but that does not seem very time efficient.

The idea (and a rough example).

Lets create a platform where people can post their requests and display them to relevant, applicable people. For example, pretend I want to play frisbee right now:

I post a request (except lets call them buzzes) saying “Looking for people to play some frisbee.” Sounds great, but this could potentially be millions of people. So lets narrow it down a bit.

In my buzz criteria, I will put “Drexel University students in a one mile range”. I can also add “able to play sometime this afternoon”.

By adding specific criteria, we can make sure not to spam random people and guarantee our buzz is seen by people who want to see it! If all went well, Drexel students currently in the area who like frisbee and are not marked as busy would see this post and be able to respond to it. If someone was really into frisbee, they could setup push notifications whenever a buzz was posted with the keyword frisbee.

That still sounds like categories.

Sure, it may seem like that example falls in the sports or frisbee category, but the point is not to limit people. What if you wanted to eat toast while skateboarding by a river while its raining?

I want to create the declassifieds, because no experience ever falls into one category. Something like playing frisbee may seem basic at face value, but it will always be a unique experience!

Buzz at 10:21pm: Looking to bake a cake; I can provide eggs, flour, and an oven. 
               	 Open to all friends of friends within a mile.
               	 This buzz will expire in one hour if not answered.

This is the first post in my new Ideas series, where I will be blogging about different ideas that come to mind.

Ideas

Everyone has ideas.

Some are better than others. Ordering a pizza at 3am on a Tuesday may seem like a good idea at the time, but you will probably regret it the next morning.

I like ideas because there are very little parameters. Ideas do not have to be a certain size, conform to a certain standard, or be executed in a specific way. The best idea in the world may be something people use everyday but do not even think about. Having a cell phone alert you by vibrating instead of playing a loud, obnoxious ringtone was a great idea.

Anyway, having ideas is a good idea. And everyone has them, all the time. That is why I want to dedicate part of my blog to discussing my own ideas! If I think of something during the day, I will blog about it. It may be a horrible idea, like using your oven to heat up bath towels in the winter, but the point is to find out what makes it so bad. (Or good. Sometimes I have good ideas too.)

Thanks for reading!

Hello Jekyll

Hello, internet.

I have decided to rebuild my website and blog using the Jekyll framework. My old site was built on Wordpress, which is a bit heavy for what I need to do. Hosting this website on my Github page allows me to do the following.

  • Securely update it from anywhere.
  • Avoid using an unncessary database.
  • Save money by using Github's hosting.

Plus, since the site is a git project, I can easily grab the latest version from whatever workstation I am using, and work offline. Over the next few weeks I plan on giving the site a facelift and adding more content, including links to my current web projects.

Stay tuned!