Emacs Keyboard Macro Counter to the Rescue
So, I have to admit, I've been doing a lot of manual numbering/indexing in a particularly large auto generated Scala file. An example of what I've been doing is parameterizing hardcoded values to be populated from a list.
val a = 2.0
val b = 10.0
val c = 1.7
val d = 8.2
…
val x = 1.2
val y = 10.5
val z = 1.1
Essentially what I was doing using emacs at this point was creating a macro which would template out the list that I would be pulling elements from.
val a = a(0)
val b = a(0)
val c = a(0)
val d = a(0)
…
val x = a(0)
val y = a(0)
val z = a(0)
The problem with this is that I still have to go back and manually change each of these values to be 1, 2, 3, and so on. So in one of the cases I was working on, there was a number of values that was too large for me to get by with this technique, enter the keyboard macro counter. The keyboard macro counter can be accessed when you are defining your macro using <F3> and everytime it is called the value is incremented. This essentially solves my problem since I am just trying to number things.
The macro I would create now would be, C-s "=", right arrow key, C-k, "a(", <F3>, ")", down arrow key, C-a. Repeating this macro would go down the list and produce val b = a(1), val c = a(2), … until the end which is what I wanted.
What I've explained here is just what I needed to solve my problem, you can find more information on how to use the keyboard macro counter in the documentation at http://www.gnu.org/software/emacs/manual/html_node/emacs/Keyboard-Macro-Counter.html.
Maximum Cost Path down a Number Triangle
Posted by stphung in Personal, Programming on May 15, 2010
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.
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!
QuickMark 3 Released
Posted by stphung in Gaming, Programming on April 25, 2010
For those who have stuck to using QuickMark, I salute you for I was stuck on how to extend this addon further before that was growing to be more and more unmaintainable as time went on. The most I have been doing as of lately has been updating the version number and ensuring nothing was broken.
QuickMark has been long overdue for a rewrite, I am now using the Ace3 Framework. The effect of this hopefully is a more maintainable addon that I can add features to easily and quickly. To start this off right, I have added a highly requested feature which has been locking and unlocking of the user interface. I am truly excited to see what direction this addon takes off in, I will sincerely consider each and every one of your feature requests in a democratic manner.
Thank you,
Steven
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.
Early lessons learned in Starcraft 2
Some lessons I learned from playing my placement matches in the Starcraft 2 beta:
- The game as a whole seems to be faster paced.
- Zerg have a worker rally point and a unit rally point, make sure you use them to full effect.
- Zerg can nydus at long range due to overlord’s creep generation ability.
- Nydus canals are different in Starcraft 2, a nydus canal can create many nydus worms, units can be loaded into any of these structures and unloaded at any of them. This is more powerful but less automatic compared to the nydus canal from Starcraft.
- Overlords are not detectors, they can be morphed into overseers which are detectors which requires you to have the lair upgrade.
- Zerg have the ability to kill scouting overlords early in the game now with the introduction of the Queen, be careful.
- Queens can cast a spell which creates larva at a hatchery.
- Roaches can be used to harass a base without detection due to their high health regeneration rate and mobility underground, you must scout for this.
- Hydralisks are much stronger and the hydralisk den has been upgraded to an advanced building, getting the lair upgrade is now essential if you want anti air units.
- Burrow is cheap and effective primarily when defending against attacks against your mineral line.
- Units move out of the way for you when you are building a structure.
- Minerals are mined away fairly quickly, expansion and containment are issues earlier in the game.
- Reapers kill buildings… really… fast.
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.
Single Responsibility Principle
Posted by stphung in Uncategorized on September 30, 2009
I created a screencast which explains the single responsibility principle introduced by Robert Martin in Principles of Object Oriented Design. The single responsibility principle is about keeping your classes focused and only having one reason to change them. If you are interested, you can find the screencast here (right click and download).
Using Java’s new style for-loop
Posted by stphung in Personal, Programming on September 23, 2009
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).
Where’s my hashCode?
Posted by stphung in Programming on June 22, 2009
Every now and then we run into code where the what is written does not reflect the author’s intent, that’s a bad thing. Here’s an example of Java code that does not reflect the author’s intent most of the time.
pubic class Foo {
private int[] myInts;
// Constructors...
// Methods...
public int hashCode() {
return this.myInts.hashCode();
}
}
What’s the problem? The catch here is that invoking hashCode() on an array does not take into consideration the data that resides inside the array and is the same as invoking System.identityCode(…). This could lead to potential problems when using hash code dependent structures such as HashSet or HashMap. If you run the following code you will find that both printouts are identical.
public class Test {
public static void main ( String[] args ) {
int[] a = new int[1];
a[0] = 1;
System.out.println(a.hashCode()); // A value
a[0] = 5000;
System.out.println(a.hashCode()); // That value again
}
}
What do we do then? The fix for this is to use the Arrays.hashCode(…) method which is overloaded for all of the primitive arrays and Object array as well. The usage of Arrays.hashCode(…) is shown below.
public class Test {
public static void main ( String[] args ) {
int[] a = new int[1];
a[0] = 1;
System.out.println(Arrays.hashCode(a)); // A value
a[0] = 5000;
System.out.println(Arrays.hashCode(a)); // Another value
}
}
Be careful when using methods, be absolutely certain about the behavior of the methods you invoke. If you are a developer and recognize that you are doing something that might look questionable then document defensively for fear that another developer may come along and fix your “mistake” which was actually what you intended.
Twitter- Could not connect to Twitter