UPCAT 2010 Results (University of the Philippines College Admission Test) were released earlier today, January 18, 2010 both online and offline.

The new official results page is now non-searchable, I wonder why. But that’s not a problem because I made a searchable version of the one’s in the UP website.

I also made a super lightweight web app that checks if your 2010 counterpart passed UPCAT or not. In my case, 201041437 either didn’t pass, still has deficiences or a pending case. His or her name was not on the list.

Aside from this, I also made another one last night which is not related to UPCAT. It’s a searchable database of UP student numbers. I got those student numbers from various sources from the Internet, including past UPCAT results. Hahaha.

I really missed scripting. All those stuff above are hosted on my laptop therefore they’ll be down whenever my laptop is sleeping. LOL.

Several hours ago was the 2009 ACM-ICPC Asia Regionals Manila Site hosted by the Ateneo de Manila University. ACM-ICPC is a programming contests in which college students are to solve a certain number of problems in a limited number of time, in yesterday’s contest ten problems in five hours.

UP Diliman had ten teams in total, seven SOGO teams from the University of the Philippines Programming Guild and three teams from the UPD Department of Computer Science. I was a member of one of the SOGO teams, the SOGO Virgins.

Results, results and results!!

Our team only ranked 26th out of the 55 teams, which was quite disappointing. Among the 10 problems given, we only had three accepted solutions out of the five problems we attempted.

The champion was from our guild (UPPG), the Mga SOGO ni E.T.. They solved all 10 problems in 1 hour and 59 minutes. They will be competing for the World Finals this February 1 to 6, 2009 at Harbin University in China. Other teams who solved all 10 problems sorted by time were teams from Ho Chi Minh City University of Science, National University of Singapore, Hong Kong University of Science and Technology and another team from UP Programming Guild, SOGOng Long Ong Moy Poso. The freshie team (2 Young 2 SOGO) from our guild beat us as they solved 5 problems in all. Woot! For more detailed results, you may check out the contest director’s blog.

Problems encountered!

Experience is the best teacher. We encountered problems on some problems.

Problem A. Given three points on a parabola, get the maximum height of the parabola. Since we don’t have a mathematician in the team, we had a hard time finding an equation with degree one for all variables. We had to force one of our teammate (out of 3) to squeeze all his knowledge on parabolas. When he found one, I immediately coded Gaussian Elimination Method for two variables and two equations. Gladly, our solution was correct thus accepted by the judges.

On the summation problem, we got correct answers for the sample inputs but it was too slow that testing it on borderline cases (worst case scenarios) won’t yield a result in a reasonable amount of time. Since no one in our team was a mathematician, we had trouble limiting our search space. Our program was so inefficient but right that we were not able to have our solution accepted.

The other problem we attempted was the A(H1N1) problem. Given a set of N people in a community with their locations and radius of contact and a person infected by A(H1N1), we had to compute the number of levels of transmission until the virus is contained. We recognized that it was a graph problem; people as nodes then connect an edge to nodes within the radius of contact of an infected person. We just have to perform a BFS (Breadth-First Search) on the graph and find the  level distance from the root to find the maximum level of transmission.

The algorithm above was correct but I made a mistake in coding BFS. I colored the node after dequeuing it from the queue instead of coloring it while putting it on the queue as seen in my code below.

Damn. I admit that it was my fault, not anyone else’s. Hmmmmf. Waaaaaa. What a shame. On the other side, it still yielded the correct answer for the sample input.

Lessons Learned

• Never spend too much time on a single problem. We spent too much time debugging the A(H1N1) problem.
• A team needs a mathematician. There were quite a number of Math problems. We were only able to solve one out of all the Math problems.

Random Stuff

Even though we did not rank well, I was still happy of the outcome. Because of this contest, I will never forget BFS anymore! Hahahaha.

I am looking forward to joining the same contest for the next years if fate will permit.

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.

Waaaaaaaaaa!

Lately, I’ve been busy finishing our research project with the great help of Kuya Franz. Our graduation is over but still I lack some requirements which I need to get my high school diploma.

During the process of finishing it, I started to love microcontrollers, again, for the second time in my life. It was a really fun experience; especially the learning process. I learned a lot of things from kuya Franz; from Hi-Tech C (a C compiler for embedded systems) to active pull-ups and pull-downs, to Proteus VSM and a lot more.

Before, I only knew programming PICs and 8051s using assembly language; now I can do it in C (in just three days; but I’m still not that good at it). I found it lot easier to do it in C rather than doing it in assembly because there’s no need to worry on 16-bit to 32-bit operations, no need to assign variables to RAM addresses. It’s also a lot better ’cause it saves you a lot of your previous development time (that’s the best thing in programming microcontrollers with C).

It was also my first time to see an oscilloscope work. I was amazed of its function and how it measured the period of the signal’s transition from high to low and vice versa brought by the counting of the microcontroller’s internal timer. We (kuya Franz and I) were able to make the timer accurate (not precise) up to the fourth-decimal-place (0.0001) as attested by the Philips oscilloscope.

I also learned how NOT to make a spaghetti circuit in a breadboard. I was able to put some stuff in the breadboard in a much neater way than I used to. (in the picture, kuya Franz cleaned up some of my dirty connections).

I also saw an In-Circuit Serial Programming (ICSP) programmer, again for the first time in my life. It was a nifty useful. With ICSP, there’s no need to remove the microcontroller from the circuit to program it thus reducing the risks of microcontroller breakdown. I also saw a Zilog development board; which according to kuya Franz costed approximately PhP 90,000.00 when it was still out in the market (fortunately he got one for free courtesy of Zilog).

I also found a PIC Simulator alternative; it’s called Proteus. Proteus is a package of ISIS (circuit designer and simulator) and ARIES (circuit [the real one] CAD). With Proteus, you can test a lot of microcontrollers. It also gives you the freedom to simulate your own circuit. It has a wide library of microcontrollers, resistors, transistors, power sources, LCDs and other electronic components. It’s the best simulator and circuit design tool I’ve ever met in my entire lifetime.

I got a lot more jargon to say, I warn you. Another thing, I used to be familiar only with Atmel products specifically its 8051 line. But our research study forced me to learn PICs. I studied its white-paper thoroughly just to get familiar with its SFRs or special function registers. I’m amazed cause I learned that PIC products’ timer0’s don’t have a timer run bit. It’s a free-run timer and runs all the time. I also learned that their operating voltage ranges from about 4.5 to 5.5 volts. Amazing!

I also loved the way we ate our merienda. Yesterday, we ate our merienda with a calculator. We discussed on what prescaler to use for timer0. We ended NOT using prescaler so we had to set a bit to a particular logic just to realign the prescaler to the WDT (watchdog timer). It was a nerdo moment!

Hahaha. I really learned a lot from kuya Franz, and it was a nice experience. He told me that I can go to their house if I want to learn something new from his projects. He encouraged me to continue learning embedded systems; which is a part of my plan for this summer. Weeeee, microcontrollers are the best.

That’s all for now!

Hey guys, I found this nifty piece of PHP file. It contains a PHP function for checking Google Pagerank. I had a hard time finding for a good code. I saw some working codes but too bad they were PHP classes which I’m not very familiar with.

The PHP file’s homepage can be found here.

Anyway, please don’t abuse the use of this Google Pagerank check PHP function. It has been reported that Google bans I.P. addresses of abusive servers.

Have fun with the code!

Graphs, graphs and graphs.

Isn’t it lovely to see the Philippine Stock Exchange Index rise and fall? How about making one for blogs? Let me call it the Blog Readership Index.

Yes, again I’m starting a new project. I’ve coded the backend’s core, frontend’s not finished.

Overview/Specifications

Blog Readership Index aims to be a good measure of blog readership. It also aims to track growth or decline in blog readership levels.

Here’s the project’s homepage.

I named 33 HTML tags in 5 minutes. Not bad, too good. I think I deserve it cause I’ve been HTMLing since Grade 3 (when I was 9)!

Here’s my badge:

33

100% Free Personals from JustSayHi

Take it too.

My sister just arrived home from Manila this morning, that means faster internet (we have two hotspots at home; one from my aunt and another from my uncle) and a camera phone. Anyway, we’re going to a white sand beach resort in Glan, Sarangani Province. The picture on my header is also taken from another resort in Glan.

Got to post the pictures later when I arrive home.