Archive for category Personal

Maximum Cost Path down a Number Triangle

My solution of problem number 18 and 67 from projecteuler.net.  I highly recommend tackling some of the problems there, they are fun and challenging.

 

The Problem

The problem at hand is from projecteuler.net, problem number 18 or 67 which can be found at http://projecteuler.net/index.php?section=problems&id=18 and http://projecteuler.net/index.php?section=problems&id=67.  The difference between problem 18 and 67 is the input size.  The problem summarized is, starting at the top of a triangle structure of numbers where a number can move to adjacent numbers on the row below, find the maximum cost path to the base.  In the example given on projecteuler, this triangle made up using four rows of numbers the maximum sum is 3+7+4+9=23.

3

7 4

2 4 6

8 5 9 3

Brute Force Feasibility

The problem that is asked for us to solve is to find the maximum cost path down a triangle of 15 rows.  The feasibility of testing every case for 15 rows isn't bad.  By observation, the number of paths in a triangle with 1 row is 1, 2 rows is 2, 3 rows is 4, so for the general case we have for n rows 2n-1 distinct paths.  For n=15 we only have 215-1=16,384 distinct path which is definitely possible to brute force but the number of distinct paths increases exponentially with n which would make for an algorithm with O(2n) runtime.  Problem 67 however is not possible to brute force since there are 100 rows which equates to 2100-1 distinct paths.

 

Using Optimal Substructure

Looking at simpler problems where n is small such as n=1 or n=2 the problem feels like it should have some optimal substructure since the maximum path from one level can probably be used somehow to compute the maximum path to the next level.

If n=1 the maximum cost path is the cost of that single number since there is only one choice, in this case, a.

a

 

If n=2 there are two distinct paths down the triangle which are, choose the single number in row 1, then either choose the first number or the second number in row 2.  In this particular triangle the paths would be ab or ac.  The values a+b and a+c here would represent the maximum cost path down triangle such that you end up at b or c respectively.  The answer to the question in this case is max(a+b, a+c).

a

b c

 

If n=3 there are now four distinct paths down the triangle.

 

a

b c

d e f

Optimal substructure becomes most apparent for this value of n in my opinion.  If we had precomputed values to the n=2 case which were the maximum cost path to get to b and c then we could easily compute the maximum cost path to get to d, e, and f.  The maximum cost path to get to a node k will be denoted mk.  Using this structure produced by solving n=2 it is intuitive how to solve n=3.

 

ma

mb mc

d e f

 

Looking at d, there is only one option,b , which makes sense since there are no paths that can get to d that also contain c which means md = (mb+d).  

Looking at e, there are complications here since it is an interior node that can be traversed to by b or c.  The maximum cost path to reach e would be computed as me = max(mb+e, mc+e).  

Looking at f, this is a case which is similar to computing md since f is not an interior node which can be traversed to by two nodes, mf=(mc+f).

After these solving n=3 we have the following structure.

 

ma

mb mc

md me mf

 

The solution to the problem for n=3 is max(md, me, mf) since the maximum cost path to get to the bottom of the triangle is going to be the maximum cost path to get to one of the nodes at the bottom of the triangle.  

 

Generalizing

Computing the maximum cost paths for row n+1 given the maximum cost paths from row n is easy.  The intuition here is that after computing the maximum cost paths for row n there are only a few choices for maximum cost paths for row n+1.  As a generalization, the solution for a triangle of n rows is to compute the the maximum cost paths for for row k using the maximum cost paths from row k-1 starting at row 2 until k=n then taking the reduction using the max operator on the maximum cost paths in row n.  Building the triangle top down we now have an algorithm which runs in O(n2/2) which is definitely faster than O(2n) for large values of n.

 

The approach taken here can basically be classified as modified Dijkstra which relaxes edges if the weights are higher rather than lower, the graph structure is emulated using a grid structure in my implementation.

2 Comments

Placeholder defeats the Lich King

Placeholder has defeated the Lich King, the major boss of the Wrath of the Lich King expansion.  After the content became available I was very excited to see that everyone reunited to pull together and finish our journey as a guild together in this expansion.  I am glad we were able to accomplish this, there were many times where I was disappointed at the fact that we didn’t finish the content similar to Burning Crusade.  I have always been proud of everyone individually though, the effort, time, and dedication that is put into our raiding.  I honestly can’t be more happy to know that each one of these individuals has set aside countless hours of their would be free time to raid, with us.

I have met many great players who have become great friends.  I have also met many people who have come and gone.  What we have left though is a group of very talented, dedicated, and friendly individuals.  I have known most of these great people for about a year now and I think we will be sticking together for a long time to come.  I think as a guild we are mostly relieved that we had what it took to defeat the Lich King.  The first time we reached him we did not have as much time as we wanted to work on him.  One month later the opportunity came up again and we won.

As for being the guild leader for this group of people yet again, for the most part it has been nothing but an honor.  I’ve read many articles about running a guild, just in case there was something I was missing or doing wrong.  What I have noticed though is that many of the issues that people have just don’t ever come up in our guild.  Issues such as loot distribution, politics, and promotions.  I think we have graduated from being a guild to being a family.

We are currently still playing and will be moving on to Heroic Icecrown Citadel and also going back to tie up a few loose ends but I think we have met our goal.  Congratulations, Kingslayers!

No Comments

Placeholder Resurrection

After contacting people for awhile everyone has come back and is ready to begin raiding yet again.  I am glad we could reunite.  We have had some level brand new characters and have been running heroics to prepare them for Icecrown Citadel.  Others have been running heroics with us just to help us out.  Overall, we have been having a great time socially just as we did before, it is a great feeling to be with these people again.  I think we’ll have a good chance at finishing this expansion by defeating the Lich King, this should be interesting.

No Comments

My Adventure in Wrath of the Lich King

First things first, I would like to congratulate Blizzard on creating such a sensational second expansion for World of Warcraft.  I have played it with my wife extensively and the game has been very memorable for us.

Prologue

Originally I was an Alliance player on Stonemaul for Burning Crusade.  I came from a hardcore 25 man raiding guild named Foebane, raiding for two days a week for ten hours each day.  The reason we only raided those days was because we were a mixed group of Australian and US players so only Fridays and Saturdays were suitable for us.  Rynuff, our guild leader was the role model for our guild, he respected members , was skilled, organized, and very professional in his attitude.  Rynuff was a very strict leader and I respect him highly for that.  Overall, everyone had fun during raiding times, this was a good group of intelligent people.

I joined the guild as Nevaa the gnome mage.  When I first joined it was only permitted to be talented as a fire mage, but for one reason or another I did not want to, I wanted to be different.  Eventually, I grew to be the top DPS player in the guild, scoring consistently the highest damage on most bosses.  Not only did I do top DPS but I was known for my competence in leading the mage team and was eventually promoted to be an officer of the guild.  As an officer, I contributed strategy discussion for each new boss we encountered and loved every minute of it.

Eventually, the off tank of the guild became undependable in terms of attendance.  It was at this moment that I leveled a Warrior named Evaa to 70.  I geared out my character in all of two weeks and tanked for the first kill of Kael’thas Sunstrider of Tempest Keep which our guild had been working on for two months.  Being a player who thought playing DPS was as easy as it is for the most part, I found tanking to my liking in terms of difficulty.  I was not as vocal as I would have liked to be, I was shy for the most part and did not speak on voice chat even though I needed to be.  As time went on with my position as off tank and eventually leading up to main tank we ran into a situation where we just did not have the attendance to keep the guild going.  Foebane was only three bosses away from finishing the Burning Crusade expansion.  After weeks of this, the officers took a vote to determine if we should continue this and the decision was a unanimous no.  Everyone went their separate ways, some to other servers to join other guilds in hopes of defeating the final boss, some stayed and joined other guilds on our existing server, and others like myself who stopped playing altogether.

Burning Crusade was a disappointing time in terms of what was not accomplished.  The gaming experience of cooperating with a group of 25 people consistently for months is something that cannot be easily replicated.  The amount that I had learned about strategy, persistence, and politics from this expansion was enormous.  These lessons don’t only apply to this game, some even to real life.

After a significant amount of time and working for awhile after college my coworkers would end up playing World of Warcraft, all because of a “I’ll go if you go” commitment.  We started on Azuremyst, one of them was named Kellion(Undead Warlock) and the other Zapan(Undead Rogue), my character was Evaa(Tauren Warrior), and my wife’s was Niena(Blood Elf Priest).  We eventually transferred to Silvermoon for a higher population server.  During the transfer Kellion changed his name to Dvorak.  We leveled to 70 and eventually joined a guild named Final Fantasy as a raid leader with some hesitation on my part being the elitist I was from my previous guild.  Many of our moments spent together were running heroics and killing the Hallowed Horseman(every day during the event!).  We then awaited the Wrath of the Lich King expansion.

Wrath of the Lich King

I lined up with my wife, Dvorak, and Zapan at our local Gamestop to grab our copies of the expansion.  With the release of the expansion it was a race to 80, I was hesitant on leveling my warrior to 80 which was the new level cap since the Death Knight class was so much fun after trying it for awhile.  On the first night of playing the Death Knight I remember leveling him from his starting level, 55 to 58 and ready for Outlands.  During that weekend I would achieve level 70 and we would all eventually reach level 80.

As our guild, Final Fantasy, had more and more members reaching the level cap we began to form into two groups of 10 man raids for Naxxramas.  Group 2 at this time was still unable to get off the ground, most of the time we would be able to get into a group 1 raid only if one of the guild leader’s friends was not online.  After three months of this went on, we slowly gathered enough members to split into two equal raiding groups, and I would also go on to level my Warrior, Evaa, to 80 with my dissatisfaction of Death Knight tanking.

The raiding groups were hardly split up equally, the guild leader had taken all of his closest friends, the best players, and left group 2 with nothing which would become our group.  As the raid leader for this group, I had scheduled  the first group 2 raids to be on Saturday and Sunday.  On our first weekend in Naxxramas, the competency of the group was immediate with my unsure and nervous mutterings of boss explanations.  We had performed better than anything I had ever imagined could happen on our first night in there.  We had run into the same boss that group 1 had on the first night of our raiding and had trouble which was Grobbulus.  On the second day, we killed Grobbulus which in terms of progress put us in front of group 1 in less than two days what they took three months to achieve.  We then ran into Sapphiron and wiped over and over since we did not have the frost gear that would make the fight much easier on us.  We scheduled a raid on Monday which seemed sketchy in attempts to finish Naxxramas since after Sapphiron was Kel’thuzad, the final boss.  In addition, we also asked everyone to make frost gear and bring it to the raid.  On Monday, I was a very surprised person as everyone had showed up and brought frost gear.  We moved on to kill Sapphiron and Kel’thuzad and with what seemed like nothing became the first group within the guild to clear the zone.

With more time, we would find the new instance Ulduar be released.  This was a very exciting time for our group, I felt that at this time we were a very focused and organized team.  With our group’s first step into Ulduar we moved farther and faster than 90% of the 10 man raiding groups on the server.  Eventually, leader of the guild which was also the leader of the group 1 raiding team became bitter.

I ran a few exploratory 25 man raids on Sundays which were up and down in terms of attendance.  On a particular day, such a raid was not scheduled to occur so I took the opportunity to schedule a 10 man raid for my group.  People logged on and expected to be running a 25 man raid, the officers gave me a lot of trouble and I stood my ground that we had not planned for it.  Ventrilo would eventually be disabled in retaliation and I would ask all of those who wanted to follow me to form a new guild to leave before I did so myself.

We formed the guild with a name intended to be replaced in the future which was, Placeholder.  We continued our excellent performance in 10 man raiding.  We eventually did clear Ulduar and would continue to grind to gear up until Trial of the Crusader was released along with its heroic version.  We then walked into Trial of the Crusader which only allowed us to move one boss further each week during progression times and we cleared it with ease.  Of the many times we attempted Trial of the Crusader on heroic mode we failed terribly.  We then would eventually walk back into Ulduar to complete various achievements in an effort to defeat Algalon.

Today, with one achievement left to do and the Lich King instance yet to be released our guild is losing steam and players are getting bored.  I am sad to say that, our run may be coming to an end which is earlier then I had hoped.  The heroic mode for Trial of the Crusader on the face of it seems like content that would keep us busy for awhile.  The high level of difficulty and the fact that it does not seem very necessary to do that mode to experience the entire game makes it difficult to push our guild members through the content.  All is not lost though, it is still possible for us to bring it together when the Lich King is released to defeat him, I hope that is the case.

Retrospective

Our guild members are by no means elite, but rather, they are intelligent, skilled, and social.  The culture of our guild was something that was priceless.  Practices such as being courteous, being friendly, mentoring newer players, being calm about loot, and getting involved were common trends to see.  It is my pleasure to be one of the many leaders of this guild, everyone was a leader having something meaningful to say at one time and another.

Being as committed as a guild leader and dealing with needs and desires over time becomes very taxing on your lifestyle as it was on mine.  When I first started leading our group of people from the very beginning even before we created our own guild in our first Naxxramas run, I had a choice to make, which was how I wanted to lead people.  I had a few experiences leading group 1 prior and felt like I had something to prove coming from Rynuff’s leadership.  My choice was not to lead in quite exactly that fashion though, I did not want a strict environment where everyone felt like they had to be on top of everything at every moment.  Instead, what I wanted was an environment where people could have fun, enjoy themselves, and socialize.  I would say that overall, people did enjoy themselves and I am happy about that.

Coming from an elite guild and into this one which right in the middle with players not being elite but rather more personable, I would have to say that I had more fun here.  I now have relationships with real people and share memories with them that I will never forget.  For all of the things we could not accomplish, I hope everyone who was involved will be able to relax and remember all of what we have accomplished.

2 Comments

Using Java’s new style for-loop

I felt like making a screencast today, so I did.  I will be making more of these in the future so I figured I’d talk about a topic I think I know half decent so I decided on talking about using Java’s new style for-loop.  This discusses the semantics of the new style for-loop along with how to roll your own data types which are able to be used together with it.

You can find the screencast here (right-click and download).

1 Comment

Return from JavaOne

It’s been a week since JavaOne and I finally have the time to at least talk about what I thought about it.  The core of JavaOne in my opinion is that it is an eye opening experience, there are people all over doing very cool things with Java.  What you get out of going is incredible if you can process a small fraction of it, what you learn does come in useful in your day to day work.  I know my coding practices will change as a result of going to JavaOne this year.

I thought it was very cool how all of the rockstar figures are just roaming about like regular people, you can essentially walk up to them and have a conversation as many did.  Some of the most notable technical talks for me came from Joshua Bloch, Bill Pugh, and William Ernst.

JavaOne was very interesting and helpful, it is a must if you are a Java developer.  I hope to be there again next year!

No Comments

One-Time Program Servers

Created a video presentation for my graduate course at North Carolina State University, CSC574 “Introduction to Computer and Network Security”.  The paper of choice was “One-Time Programs” by Goldwasser, Kalai, and Rothblum.  This video describes at a high level what one-time programs are, the concept of their creation, applications, and insight to the benefits and drawbacks of using them.

An idea I use the term “One-Time Program Servers” for is also presented at a high level describing a method for abstracting away the hardware component from developers and users of one-time programs.  The aim of one-time program servers is to make the transition for creating and using one-time programs seamless.

Download the video presentation

No Comments

Enter the MacBook

I bought the top end MacBook today, I’m going to continue exploring on it now.

No Comments

BlizzCon Day 1 + 2

Day 1 of BlizzCon was pretty exciting. First we went to the opening ceremony where Mike Morhaime mentioned the new playable class for Diablo III, the Wizard. I was genuinely expecting a big announcement of some type as per usual at all Blizzard events but none was given, somewhat of a disappointment.

Throughout the day we attended most of the main panels such as World of Warcraft Class Discussion, Starcraft II Gameplay, Diablo III Gameplay, and the BlizzCon contests. StarCraft II was announced to be released as a trilogy with the Terran campaign being released first, the crowd went wild.

Notable were the BlizzCon contests, Jay Mohr was very entertaining as the host of the events. I feel that given the superior number of people this year compared to the year before at BlizzCon 2007, the contest submissions as a whole were not as well done. Another thing that irks me is the fact that they did not at all show any of the content for the original song, machinima, and motivational poster contests. This was also unusual since we were not at all running short on time. I suppose that they had probably come up with a plan that expected us to take more time than we did and were not prepared to show any of the submissions for the other contests.

During Day 2 of BlizzCon we went to the World of Warcraft PvP and World of Warcraft Dungeons and Raids panels. After these panels we gave up our front row seats and went to the store to pick up our BlizzCon swag and then headed over to watch the Starcraft finals. Following the Starcraft finals was a Starcraft II exhibition match between Yellow(a Starcraft player) and a Warcraft III player. Yellow really showed his micro-management skills during this match up and needless to say, he won against the Warcraft III player.

We then went to attempt to get seats for the closing ceremony about half an hour before it was starting and we ended up sitting on the floor. There was a stand-up comedy session by Kyle and Patton which was sub-par compared to Jay Mohr’s hosting entertainment. After that was a concert by Level 80 Elite Tauren Chieftain which was quite loud but entertaining. Then came the Video Games Live session where an orchestra played various pieces of music from the Blizzard games. There was a special appearance by the Blind Pianist who played Mario Brothers blind which was quite exciting, they had him play a Warcraft II piece.

Overall I felt this year’s BlizzCon was not as exciting as last year’s but that I suspect is due to BlizzCon 2007 being my first. The content of this year’s BlizzCon was excellent, a lot of new content was shown to the attendees from Starcraft II, Diablo III, and Wrath of the Lich King. Aside from having no big announcement this year, BlizzCon rocked.

No Comments

BlizzCon Day 0

Just went to pick up the BlizzCon swag for the guys and myself where they ended up giving me a box to walk out with. Got some dirty looks from some people thinking I was one of the evil ebay profiteers, not a good feeling. Looking at the program it appears that they will indeed have Diablo III playable at BlizzCon. Some of the notable items in the “goodie bag” are Starcraft wrist guards, Diablo III mints, World of Warcraft TCG Starter Deck, Blizzard Authenticator, and a packet of tissues with “QQ n00b” printed on the back(got a real kick out of that one).

No Comments