Art Gallery Problem

I was looking through Wikipedia's list of NP-complete problems to try to come up with an idea for a game. A few of the problems on the list have already been made into games. I thought the art gallery problem might make an interesting game. My research on Google suggests that it has never been adapted into a game before. I spent the day implementing the game and have posted it online here. So far I have only made four levels but I plan on adding more soon.

Google Offer

I just accepted a job offer from Google! The position is Software Engineer. After I finish my master's degree, I will be moving to Mountain View, California.

ACM Eligibility

During the last two weekends I competed in tryouts to be part of the UBC programming team. I did well enough to qualify for the first team. However, yesterday I noticed on the 2010 ACM eligibility chart that I am ineligible because I am slightly too old (by four months). We tried emailing the ICPC manager but she verified that I can not compete :(

Happy Petrov Day!

Thank you Stanislav Petrov for saving the world on September 26, 1983.

Sri Lanka

Last week I finished my internship at Google. I have been in Sri Lanka for about a day now. Cathay Pacific managed to lose both of my suitcases on the way here. So far I like Sri Lanka. It seems to be similar to India except better in a number of ways.

Homework

Translation courtesy of reddit user thelifan:

My life here is terrible. Work environment is not great and benefits are little. But don't worry, everyday only about 10 people are seriously injured and I'm very careful. We opened a small shop, business isn't bad. Although I don't understand very much English, but I can still understand what white men say. Hopefully we can become successful, I will work hard and take care of myself.

Are you guys well? Miss you very much, hope to see you again.

Skydiving!

This morning I went skydiving from 15,000 feet. It was an incredible experience. The free-fall lasted for about one minute and parachuting lasted five minutes. The "falling" sensation only lasted for a few seconds after leaving the plane. Once reaching terminal velocity, the free-fall was quite comfortable (and surreal). My instructor let me control the parachute for part of the descent. We also performed a fun maneuver spinning the parachute around in a tight spiral. A few years ago I went bungee jumping. I think making the jump was probably scarier for bungee jumping than skydiving. However, I enjoyed everything about skydiving a lot more than bungee jumping.

Skydiving!

Next week I am planning to go skydiving with some Google interns. Should be fun!

YouTube Easter Egg

For YouTube videos with the new layout style, performing the following steps will start up a game of Snake:

1) Click on the video to give it keyboard focus
2) Hold the left arrow key

Here is a YouTube video that it will work on. Discovered via Reddit.

Body Invaders

[YouTube link]


[YouTube link]


[YouTube link]

National Geographic

New Camera!

I am now the proud owner of a Panasonic Lumix DMC-ZS7. Today I took some photos with it around the Google campus. One of my favorite features of the camera is that it tags pictures with GPS coordinates. Picasa Web Albums automatically creates a Google Map with the photo locations.

Demon's Souls

Today I finally beat Demon's Souls. I am pretty proud of this accomplishment given how ridiculously hard the game is. It is the best PS3 game I have played.

RoboCup 2010

I am currently in Singapore attending RoboCup 2010. UBC Thunderbots is competing in the small size league. We played four games and did not advance to the semi-finals. We lost three games and won one game. The Thunderbots website has lots of pictures, videos, and a blog. I will be in Singapore for one week.

TopCoder Open

Today I discovered that TopCoder is hosting an interesting marathon match over the next month. The problem is pretty simple:

Input: list of edges
Output: vertex locations
Goal: minimize number of edge intersections

There is an online scoreboard which shows your ranking after each submission. I was in last place after my first submission. My second submission was quite an improvement and put me in second place =)

siarco

I just released an open source version of the arithmetic coder I discussed in my previous post. The project is hosted at http://code.google.com/p/siarco/.

Nice Weather

[link]

Arithmetic Coding

This week I wrote a program to perform arithmetic coding. Arithmetic coding is useful for data compression. This summer I plan to release an open source lossless data compression algorithm which uses the coder.

The program to do the arithmetic coding is only around 150 lines of Java code. For a while I had a really annoying bug related to precision errors with floating point numbers. The vast majority of the time I spent developing the program was trying to fix this bug. Today I finally figured out a great solution to the precision problem which has almost no computational overhead and is theoretically guaranteed to always be correct.

Wikipedia claims "every programmatic implementation of arithmetic encoding has a different compression ratio and performance." I find this statement surprising because I think I can construct a proof showing that my program encodes the input with exactly the minimal number of bits. If the number of bits is not divisible by 8, my program uses a few extra bits in order to store the resulting bytes to disk. As far as I know it is impossible for another arithmetic coder to achieve a better compression ratio. I tried testing the program on several files and it achieved a compression ratio extremely close to the theoretical cross entropy limit.

In terms of performance my algorithm also has nice properties. The time and space complexity are both linear in terms of the number of input characters (which is optimal). The code only performs basic arithmetic operations on primitive data types, so it should also be very efficient. The code works with any input alphabet size. I plan to convert the program to optimized C code and compare its performance to other arithmetic coders. Since I am already confident that its compression ratio can not be beaten, if it turns out to be faster than other arithmetic coders as well, then my algorithm could be an important contribution =)

Googleplex

I really enjoyed my first week at Google. So far I have mostly been doing training. The food at the Googleplex is amazing. I will be eating breakfast, lunch, and dinner there, so I will only have to cook for myself on weekends. I have been trying to go to a different café for every meal. My apartment is about a 30 minute bike ride from the campus, so that exercise might help counteract the abundance of free food. Google gave me a nice bike to use over the summer.

Yesterday I bought a new monitor so that I can play my PS3. I also bought a game called Demon's Souls. I tried getting Demon's Souls at three different places in Vancouver but they were all sold out. In Mountain View I tried checking Best Buy and Toys Я Us but they were also sold out. Finally, I found a copy at Game Stop (which turned out to be their last copy). The ridiculous thing is that this game was released over half a year ago. The gameplay is incredibly addicting (and incredibly difficult). It is the best PS3 game I have played.

Suitcase Computer

I recently discovered that traveling with a desktop computer in a suitcase is a bad idea. When I was packing for my trip to Mountain View I spontaneously decided to bring my desktop computer since I had lots of extra room in my suitcases. I have traveled with a desktop computer before without any problems.

The first annoyance was that both my suitcases were way over the weight limit, so I was charged expensive overweight fees. I would have been under the weight limit without the computer. When I arrived in Mountain View and started unpacking the computer, I noticed a horrible rattling sound when I moved it. A rattling sound indicating loose components in the case.

The CPU heatsink had somehow become detached and was bouncing around inside the case the entire trip. Today I bought some thermal grease and reattached the heatsink. When I tried to boot the computer it started making beeping sounds and immediately shutdown. It is most likely the motherboard which was damaged. I wish I had just left the computer in Vancouver.