I admit that I am bitter with the results of the Mensa IQ Challenge I took sometime last month. It was a BIG slap on my face, after self-proclaiming myself as a geek. I don’t believe you have to pass Mensa to be a full-pledged full-fledged (as corrected by Aldrin, point well taken) geek. Hahaha. Here’s something geekier than Mensa.

After two sessions of training on our new “programming guild”, I’ve encountered tons of intellectually challenging programming problems. The spectrum of problems were very wide; from counting descendants of a person in a family tree, to beating a greedy opponent on a game, to getting the height of a rocket model using three ground observers using a theodolite, and the list goes on and on.

I admit those problems were new to me and I think it was the best answer for my hunger for knowledge. Those problems squeezed my neurons to the highest level, thus greasing up my brain. Those were the problems that made me realize I still have a lot lot lot more to learn. I mean, A LOT!

To all other geeks out there who have a background on any programming language (preferably C or Java), I dare you to solve the problems on real ACM International Collegiate Programming Competition (ACM-ICPC). There are a lot of problems available there from ACM-ICPC contests around the globe.

So far, I have only solved four ACM-ICPC problems. My goal is to solve at least one per night. Good luck to me and have fun with those problems.

DISCLAIMER: For those who are not interested in PHP, you better not bore yourself with this post.

It was ages ago since I made posted some really geek stuff. I think I had to live up with my blog title, Build that Geek — and so I had to rebuild the geek inside me.

Overview

An hour ago, a brilliant idea was distracting my sleepy brain (it was around 4am). The idea was shining so much that my eyes were blinded by it (my pair of eye was facing the inside of my head). At first, I was hesitant to do it by I eventually gave in.

The idea was to create a PHP program that would notify me thru SMS and email every time a PRC Board Exam result is released. The program would ran every five minutes by means of creating a cron job that would execute it.

The program flow are as follows:

• START
• The program, thru the PHP server would contact an external source requesting information.
• The external source would feed the requested information back to the PHP server.
• The program would parse the data in a PHP-readable format.
• The parsed data will be filtered (non-PRC related stuff would be dropped).
• CONDITIONAL: Was the parsed data previously been sent:
  • if yes: END.
  • if no, continue.
• The program will notify me regarding the PRC Board Exam result release thru SMS [thru an SMS Gateway] and email [thru PHP's mail function]
• END

The Search for Source of Information

I strolled around the Internet. The most reliable source I could have is the PRC Official Website. I visited the website and tried to search for an RSS or a well-organized XML file. Too bad there weren’t any. I thought of extacting information from the website the dirty way (using eregi, str_replace, and other string manipulation functions) but it was too much for my tired brain.

The next one was Philippine Daily Inquirer’s inquirer.net. I immediately searsuched their site and poof, there’s this XML feed. I thought it was all fine but when I checked it, it was pretty outdated. If I’d use it, the program would defeat the purpose of informing me really fast of the latest news.

Next was ABS-CBN News. In their Public Service area, they served PRC Board Exam result news. They supplied an RSS feed, but sadly it was blank. It contained no information.

The last one who successfully won me was GMANews.tv. I checked their site and they were also serving PRC Board Exam result news. I learned that they publish it on-the-go on their Nation section. Their top stories section had a usable RSS feed, woot. Finally, I’ve got it.

Data Parsing and Extraction

The next thing to do was to extract the data. How could I parse the RSS feed in such a way PHP would understand it well. Since Google is my friend, I tried googling my problem. Google (search engine) introduced to me Magpie RSS, the program I was looking. Just feed an RSS feed to Magpie RSS and it would break the individual feed items into arrays.

Implementation of Magpie RSS to the program was easy since they have posted a simple how-to on their website.

Filtering the Data

Since it was a Nation section feed, not all items on the feed were regarding PRC. There was a need to filter it out. The easiest way that came into my mind was to match either one of the following string “prc” or “professional” to the feed descriptions. If the feed description contained the said strings in a non-case-sensitive way, then retain the information; else drop them. What I used in this part was the eregi function.

Notification and all sorts of stuff

The next thing to worry about was on how to notify me. I also realized that previously sent news did not need to be sent from time to time. For this, I made a MySQL database that would save previously sent information. If the information about to be sent is not on the database, then send it; otherwise, don’t.

The email notification was easy. Gladly, PHP has this easy-to-use mail function. For the SMS notification, I used a free SMS gateway.

Keep it running, indefinitely

Since the program needs to run from time to time, I made a cron entry that would command the server to run it from time-to-time.

Conclusion

The idea was possible. Barely 30 minutes were spent doing it. Source code may be requested by contacting me thru my contact page (accessible in the header and footer).

All images and questions from Google Treasure Hunt 2008.

Question:

A robot is located at the top-left corner of a 58 x 64 grid (marked).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’).

How many possible unique paths are there?

The image is not drawn to scale. For illustration purposes only.

Solution

Since I love PHP, I will be attempting the solve the problem in PHP.

Here’s how I am gonna do it.

Since it is a 58×64 grid, to reach the 1,1 location the robot needs to go down 57 times and go to the right 63 times yielding a total of exactly 120 steps to reach its location.

So the rule is:
Number of times to go down = Y coordinate origin of robot – 1 = numdown
Number of times to go right = X coordinate origin of robot – 1 = numright
Number of steps to reach location = Number of times to go down + Number of times to go right = maxnum

The Plan

Generate

Generate strings maxnum length using two characters of my own choice which will be 0 and 1. 0 will represent movement to the right while 1 will be movement downwards.

I will generate the strings 0000…001, 0000…010 to 1111…111. All must be of length maxnum or in my case 120.

Screening

On the course of generation, one conditional with two arguments will be made.

These are, if the number of 0s and 1s in the string being generated exceed the number of allowable 0s and 1s (numright and numdown), then throw the string and proceed to the other.

Increment the Counter

If it passes the screening, then increment the counter. After the generation of possible combinations, echo or print the number in the counter. The number represents the number of possible movements.

Optimization

The code to be used could be optimized by:

• screening should be done every after generation of a complete maxnum length string instead of screening the string while generating it character-by-character.

My head is already aching! Waaaa, I wanna solve it during the week. I won’t stop until I solve this. Amf!!

Try to play it here.