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.

Reflections on my progress and plans

Currently Listening to:
Galaxy - Highlight Diver
Dan Pound - Esoterica (Part Eight)

So tomorrow is POSSCON. My team left today right after our ACM talk to go setup the booth for the event. I didn't sleep last night because of my impending fear that I won't get all the work done in time for POSSCON. I think I should have let sleep take over my body seeing as how I don't feel my section of the presentation was lacking in every way. I had to present a demo in front of everyone at the meeting, and my mind was going in a hundred different directions by the time I finished my part of the presentation. The team left after our talk and I stayed in the conference room to finish up more bug fixes and documentation issues. I feel like I let some members of the team down because of my performance today, but I can take solace in the fact that normally I strive under giving talks in front of people (See: BarCamp). Today was just not my day.

I finished my documentation that I wanted to get done and submitted the final diff to Hunter for a bug that I wanted fixed before we debut at POSSCON and proceeded to take a nap. Currently Obsidian is the only thing that I have been working on, and I have been mostly neglecting my other work in other classes. So while the progress has been great on the front of releasing an open source project I feel that on a personal level I should step back and not try to bite off more than I can chew. Currently I want to be on par with the inner workings of Obsidian as Hunter is currently, but that will take more time seeing as how he has a 2 year headstart.

I think the whole team was feeling the stress for the past few days. Sleepless nights of work for the past week have taken its toll on the whole team. I know that looking back on this in hindsight is going to be a great experience, but for next semesters 462 class I will warn the people who want to make their own community that it is a lot of hard work and sleepless nights to make it good.

Oh, and Happy birthday to me. My birthday was this past Sunday which I forced myself to take a break and have dinner with my family. It was fun. I'm most likely going to be buying that mechanical keyboard that I have wanted for a while now with the money I received.


Time for bed so I can wake up early tomorrow to drive up to POSSCON. Wish me luck.

Preparing for POSSCON

Currently listening to: 
Kettel - Boekebaas 
Bassic - Daydreamer

Adding a currently listening to. I think I'll start adding that to my blog posts from now on seeing as how some of my friends ask me for new music to listen to all the time, I might as well give them a easy way of finding new songs ;)

Finally the blog where I get to pick the speakers I'll be going to attend during POSSCON. A few of my friends are actually going to be presenting at the event and I have been asked to attend their talks, but I'll list the talks that I'll be attending for the sake of the class instead.

The first talk that I want to attend is one that I already signed up to do with my current boss Clay. There is a special workshop held on the second day where SparkFun is going to be teaching us how to solder, and then later in the day teach us how to program our newly made simon says game. The class is going to be held by a few people from SparkFun and should make an interesting second day to POSSCON (that and I get to annoy Clay on the ride back by playing simon says the ENTIRE ride back to Charleston. I'm sure he would love that).

The second talk that I want to attend is actually a SparkFun employee who is giving a talk on how to teach STEM in schools. Lindsay Craig will be leading the session. I have already talked about my wanting to work in education here, here, here, and here. So I feel like this is a class that is almost required of me to attend. Hopefully he talks about motivational techniques like gamification and other types of external and internal motivators that we can instil in the younger generation.

The third talk that I want to attend is "Javascript: the language every developer should know" by Tom Wilson from Jack Russell Software. Seeing as how I have met Tom a few times (BarCamp, Code workshops for test driven development, Hack-a-thons) I feel like I should trust him with a title that has an absolute, "Everyone should know". The abstract for the talk indicates that Javascript has matured to the point of being something beyond just a scripting language, and I feel like I should look into it more than I have in the past.

Other than attending the talks my job during POSSCON will be to sit at the Obsidian booth giving out stickers and showing off the functionality of the project. I can't wait to see if there is any hype or feedback from them. Besides, I'll be keeper of the stickers that everyone in our class wants so bad >:D

Release Early and Often

Release Early, Release Often! Back to my favorite conglomerate of papers written by Eric S. Raymond. This segment talks about the development model of the Linux kernel, as well as a common development model for most open source projects.

Back in the early days of software development it was common to work with the Cathedral building development, this way your early buggy versions do not disgruntle users or even change their workflow. The idea that the objective was for users to run into the least amount of bugs kept this perpetual cycle of one leader programming and slow patching schedules going for a while. It wasn't until Linux started gaining momentum that another way of developing code seemed to work better. Linus treated his users as co-developers, bug hunters, and documentarians.

His use of leveraging users to let them collaborate allowed him to pick ideas and incorporate them (if the user didn't already incorporate it themselves). This turnaround sometimes lead to releasing a kernel update more than once a day. This helped motivate the co-developers, either from their sense of the gift culture that open source is now known for, or for the ego satisfying love that hackers have when their name is on a project. This lead to better code with the idea that "given enough eyeballs, all bugs are shallow" otherwise known as "Linus's Law". If the project dev group is large enough a bug will be caught faster, and bugs will have a higher probability of having a quick and obvious fix to someone who might have seen that type of problem before.

Releasing early and releasing often is most likely going to be the development model for Obsidian. Hopefully builds will be twice a month at first, and when the project becomes more stable the ability to refactor parts that we know we want to change (like the methodMap) can come later. We just need to find a collection of developers that like our project and will continue to use it even if we are not developing it anymore. I hope the original team will continue to work on it, but the open source community is already used to people moving on and new people taking over, we just need to find our developers first.

Speaking of Obsidian, we have a week to go before POSSCON and our release of the code to the public. The poster now has cool graphics to show how each pattern works. The wiki is tentatively declared done, but as it is a wiki it will never be done. Something will always need to be changed, something else will always need to be updated, it is just the name of the game when it comes to an evolving project. The documentation needs to change to keep up.

Lets just hope it doesn't need to be changed that much.

The Doc is in!

The exercise this week was all about documentation. Seeing as how we are in the middle of writing all the documentation for Obsidian I decided just to keep at it and continue working on the Obsidian documentation. My feelings on documentation were described in a earlier post, but I feel like Jeff Atwood describes the best methods of commenting on his blog Coding Horror. If the complexity of the code is high enough for you to write a dissertation in the method, you might want to reconsider refactoring it to be separated out a little bit more. 

One of the exercises was to write a wiki page of developer documentation for each program. Seeing as how I took hold of the "How to Contribute" page I decided just to finish it up with some common coding standards as well as modifying the build instructions for the source code. Other then that most of the documentation is almost finished, we are just working on the documentation for the poster. 

The team's meeting recently has been about the layout and wording of the poster. We tried making the sections understandable without being too much, but to fully explain parts of the project we had to write full paragraphs. An example of some of the poster documentation:

Overview:

Obsidian has four different patterns for tests that are determined by two factors: whether the function has parameters and whether the function throws exceptions. With the usage of these patterns Obsidian can create a test implementation for different types of methods. 

And an example of one of the patterns:

Call:

The CALL pattern, the simplest pattern, is generated on functions that do not have parameters and do not throw exceptions. All Obsidian can do in this case is call the method, and generate the assert statements. This is the basic building block of Obsidian, and is used in all of the other patterns.

I'm really excited to see how it turns out. I'm just sad that I will not be there the night before to help setup. I have a test the night that the rest of the team will be driving up, so I will not be at the welcoming party. This is good news in a way, seeing as how the stickers should be arriving the day that everyone else is heading up, so I'll be bringing them with me the next day (the first day of POSSCON). 

After the break...

During the break I told myself that I was going to get a bunch of homework done on the first few days, and while this is true I also said that I wanted to work on Obsidian for a few days after, this is not so true. I did work on what I had to finish but the break allowed me to recharge my batteries which I desperately needed. Especially because I got sick halfway through the break.

So after the break the team got together to see what we needed to finish. The documentation had a good "first pass" where everything had a little bit of information, be that bullet points or just setup of the page. During the next week the main focus will be documentation seeing as how most of the bugs and enhancements/features are now completed and fixed over the weekend. There are refactoring things we want to do, but currently we want to have the documentation in place so people can help contribute.

One of the side items that I have been working on is to try and figure out how I would want to implement Global Equality Methods. These methods are there to allow the programmer/test engineer how each object that is in the project is equal to another object of the same type. The problem that we know exists is one of how to address the objects. Our code styling for the Package and Class level of the Equality Methods just use the name of the class. One of the projects that we use contains two classes with the same names in different namespaces, so we have a problem with ambiguity between the classes with the same name. It seems like we are going to have to use fully qualified names when we create the areEqual methods (example: areEqual(com.foo.bar x, com.foo.bar y) instead of importing com.foo.bar and using areEqual(bar x, bar y)).

 Other then that the team is going to start meeting on Friday nights, bringing the total time working together 3 days a week. We figured that while writing the documentation it is easier to just ask everyone at the table what the wording should be, or what should go on what page instead of emailing everyone to wait for a response. Hopefully the Friday meetings are going to allow us to work on the project to get it out there faster and decrease the amount of stress that the group has been feeling. That plus the pop quizzes Hunter has been giving us (to test our knowledge of Obsidian) are sure to help ease everyone's nerves about the upcoming booth unveiling at POSSCON.