Google Code Jam Problem B.

Currently Listening to:
KOAN Sound - Sly Fox
Funkanomics - The Goonies Island

CSCI 462 has no more required blog posts. Now it is time to start blogging about specific problems I have been having as well as observations that I have.

Last weekend I participated in the Google Code Jam. This online programming competition is open to students and professionals alike. Out of the 4 problems I solved 2 of them with small and large datasets, and one of them with just a small dataset bringing my score for the competition to 80 (you only need 35 to qualify for the next round). My favorite problem to solve from a critical thinking standpoint was problem B, the lawnmower problem. 

The problem stated that if you have a patch of grass and a lawnmower that can only cut in straight (horizontal and vertical) lines, would it be possible to create the given pattern. Originally I was going to solve the problem by just checking to see if the rows and columns had a valid line, but this misses test cases. 

Eventually I got to the point where I figured that if you remove the smallest valid line that the lawnmower made (i.e. the last pass chronologically that the lawnmower made) and remove that line, you can work your way back in time until you have the original lawn. For the sake of simplicity I just removed the line out of my list completely and if I had a list of nothing it at the end of the loop was a valid lawn, otherwise if I still had stuff in the list something went wrong and it wasn't a valid cut. The method for checking is to find the smallest value in the list and checking to see if either the horizontal or vertical line was filled with the same values. So this is what a lawn looked like as it ran through the code:

2 1 2

1 1 1

2 1 2

(bold and underline is the smallest)

changed to:

2 2

1 1

2 2

which changed to:

2 2

2 2

which eventually turned into an empty list. That meant that it was a valid lawn. If at any point both the horizontal and the vertical check failed it would break out of the loop, which caused the "isEmpty" to be called and a judgement of the lawn set. My problem B solution can be found here.

POSSCON Report

Currently Listening to:
Hol Baumann - Endless Park
Can't Stop Won't Stop - Toys for Boys

I can't stress enough how comfy the bed was at POSSCON, just throwing it out there that I passed out early and woke up before my alarm.

I have been to POSSCON before but this is the first one that they held at the IT-oLogy building. I do like the facilities, but the space seems cramped in comparison to the locations of years past. During the first day I spent most of my time running the demo of Obsidian, not trusting myself to speak very much and let the code do all the talking after what I consider a mess up at the ACM meeting. We did talk to a bunch of people interested in the project. It seems like a lot of people want to extend Obsidian to work with .Net and C#. In reality it doesn't matter what language Obsidian is because the project is more about the design patterns which are just that, a pattern. Any language that has something akin to the Reflection library in Java could potentially create an Obsidian package to work with it. I know one of the people from the local LUG in Charleston caught up with me and asked if I'll try making it for Perl (Could be fun).

Right before lunch I caught up with +Eric Wages and had a fun conversation about what we have both been up to since the last time we both saw each other (must have been right after the last BarCampCHS). While talking Christian Heilmann from Mozilla showed up in our corner of the room. We all proceeded to talk about the new Mozilla Phone and how to target a niche audience. Eric had to leave to give a talk a little bit later so I got lunch at got back to the booth to do another shift.

After the first day of POSSCON there was the GitHub Drinkup. It was fun seeing old friends that I have made over the years hanging out. After catching up with a lot of people I hung out with the rest of the CofC crowd. It was fun to finally let loose after all the tension leading up to POSSCON finally let go. One of the conversations we had over drinks was +Tyler Sawyer's app idea with +Reece Long. Talking to Tyler about how he could make the app more modular in design to make more than one app was a good conversation. He could use the framework he should build *cough cough* (get on it Tyler) to create different apps for different customers. After the Drinkup a bunch of the students went out to get dinner at a local restaurant. The night was filled with stories and triumphs of the day, all concluding to the best bed in the world for my sleepless body.

The second day was more fun than the first. I got back into soldering and learned a bit about programming an Arduino (which I played Simon Says on for the rest of the day). Other than the Arduino class I spent my time on the Obsidian booth. Talked with more potential co-developers of Obsidian and got more feedback for it (moving to GitHub as I write this). During the wrap up of POSSCON Dr. Bowring and the rest of the CofC gang was called out for being at every POSSCON since the beginning and always being active participants in the talks. Obsidian was also acknowledged for being a student run project out of our department at CofC. It felt awesome for being acknowledged for being active members of POSSCON. Hopefully we will be able to send more and more students every year (one of the ideas thrown around by a few students was the ability for people about to take 462 to attend POSSCON, and then attend again while they are in 462 so they have the perspective of open source before they get involved and again while they are invested).

There was a dinner after POSSCON was over. I had a chance to chat with a professor, his recently retired wife, and a open source advocate for Microsoft. The four of us talked about everything from GIS, Remote Sensing, Open Source licensing, our favorite talks, my budding career in open source (I had to talk about Obsidian, remember, trying to get users), plans for after college, and why CSCI 462 at the school is one of the best ideas they have heard of in a long time. They all wished that their colleges had something similar. This shows me that CofC is onto something here with making a class requirement to contribute to a team project in open source.

Maybe other colleges will start trying to emulate that.