Registration is now open 🙂
Lucky I hadn’t booked my plane tickets yet… I was planning to be on a plane when the qualification round was starting. Hopefully I can still organise to be around for it.
No local finals this year, ’tis a shame because the probability of me making it into the top 25 is pretty tiny. Hopefully I can still get a t-shirt 🙂
Guess I better get back to working on TMD.Algo (and brushing up on a few hundred problems).
I was recently asked to write a simple algorithm using recursion. I immediately baulked because the algorithm was so trivial and recursion was such a bad choice.
But for novelty sake i wrote it up on the whiteboard. It was wrong, I didn’t put the termination condition in, but I don’t program whiteboards anyway and the fact that the problem was so stupid to solve as recursion had me befuddled.
But it has made me think. Think about how bad the solution I wrote up was. I was asked to write a recursive solution, to a linear single loop problem, so I wrote it thinking like I was solving a problem which was best solved by recursion. Solution ran n^2, I knew it, was the biggest reason why I thought writing the algorithm with recursion was stupid.
Later I was thinking, it wouldn’t be that hard to make the recursion linear, its still a terrible way to solve the problem but at least its still linear.
But it was only just now that the obvious truth hit me, you can turn any loop into a recursion trivially without changing the asymptotic performance (your performance will likely drop, and you’ll probably stack overflow, but the O notation won’t change). I had been so focused on the request for recursion that I didn’t do what I should have done, which is solve the problem the right way, and then make that fit the requirements. (Not that that is a good motto for general development…)
I feel the probability of this challenge being met is low, but I felt the urge to post it.
Someone out there, go to a magic show where the guy asks you to write down a number between 1 and 100.
On the paper write e^pi – pi. Or Ceil(e^pi – pi) if you are concerned about possible implicit integer definition in original request.
Come back and tell me what happens.
I feel like writing another blog post, has been a while. But I don’t have anything interesting about .Net to put up today.
So, to a completely different topic. I play LOTRO, in fact maybe that is why I haven’t had much to blog about recently… One of the developers ‘Orion’ has been posting a blog in which he details his daily work on reworking an existing area of the game. This blog has received a lot of comments, and I think that the general idea is good for player relations.
However in his latest blog post he decided to take some time out to respond to one of the comments claiming that devs ignore the players. As a personal time game developer for an old text based MMORPG, I have been exposed to a lot of player requests, and seen this complaint plenty of times. But Orion’s response surprised me in some ways. Specifically I don’t think he put enough emphasis on what I think is the most important part of being a game developer, which is interpretation.
When a player complains ‘a’ is too hard. That may be a decent complaint, although there are a bunch of people who aren’t complaining because they don’t find it too hard… But the problem can be solved to satisfy both parties. (Sort of… More on that later…) However player complaints can often be more like ‘you should change this to be like that’, they go further than just identifying the issue and start offering solutions. The problem now is that if you don’t do exactly what they say you aren’t listening to the playerbase, in their eyes. As a game developer you may receive 18 ways to address an issue – they will often be conflicting with each other, they will often result in there being no actual challenge left in the game. This last point I think is one which is very important, players often ask for stuff without realising that if they get given it, the net result will be a game which will bore them. It is a game developers job to interpret all of these factors and try to come up with compromises and solutions which keep the masses both feeling respected and entertained. This is really quite a challenging job and I think Orion should have made a bigger deal of it. The customer is not always right, but the customer does always have a point…
One of the ways in which LOTRO attempted to produce a compromise which produced a lot of negative feedback in public forums (although ultimately public forums are often the vocal minority…) is the concept of having two ways to do a piece of game play, one as an ‘easy’ mode and another as a ‘hard’ mode. Although they are trying to rename those as normal and challenge, I imagine the initial naming will be hard to get rid of in peoples minds.
I think that this is a pretty good idea – certainly has the potential to be divisive, but in general the concept is sound. The problems come in the rewards. There is a decent section of the playerbase of a MMORPG which is equipment centric, and if you make it so the only way to get a certain piece of gear (which is above normal standards) is through a challenge mode, you have caused a problem. Because the section of the playerbase which is gear centric and the section of the playerbase which is very good at playing, are not the same. So in the process of trying to satisfy the high end and average groups separately, you’ve take a section of the average group and failed to solve the problem for them.
So the trick here comes in working out what rewards you can give out without causing community division. I am thinking bragging right rewards (titles, housing items – useless in all ways except for bragging), and items which are obtainable from other locations. But if the items are obtainable from other locations why would you ever do the challenge mode more than the number of times required to get your bragging rights. I think the answer here lies in the quantity of the rewards (as opposed to the quality). If you make doing challenge tasks give out frequently used consumables in quantities which give a significant benefit in terms of time taken vs amount required compared to other non-challenge task options – people will keep doing them. Or if you make rare drops noticibly more common when challenge mode is completed. Letting people save time by doing things the hard way is the traditional rpg trade off, and I think should be perceived as generally acceptable.
When book 8 first dropped one of the bugs which many people noticed was that ‘normal’ mode was dropping the tokens for the good gear – and initially I thought yeap that’s a bug, because it didn’t match with their previous gear drop strategy of being only from ‘hard’ mode. Now I think this bug is actually the first step on the right way to do things. They just need to significantly improve the quantity of hard mode rewards, since they are currently very very boring.
(Hopefully none of my fellow ‘hardcore’ raiding kinship members read this, because they’re more likely to be in the small minority of players which think there should be truely awesome equipment which is only obtainable by being elite players – heh even I think that, I just don’t think its the right way to run the game… ahh self inconsistency…)
In other news one of my fellow workmates came up to me the other day and said ‘you’re famous’. I instantly had to wonder why – had I broken some code in some spectacular way… Or had he found me on the internet… why would he have found me on the internet was the next idea in my head – there are a number of avenues which can result in finding me on the internet (physics competitions/programming competitions/game development/my university web page/open source mailing list archives…). But no, he had just done a google search for WindowsIdentity and IDisposable and this blog was the top result.
WindowsIdentity is IDisposable.
Recently I went on a quest to dispose of IDisposable objects wherever I could find them, since many types are IDisposable but people are not aware of this fact. (Suggestion for VS2010, shade types which are IDisposable a different color in the IDE.)
WindowsIdentity.GetCurrent() returns an instance which you should dispose, otherwise you temporarily leak a user handle. (Its a safehandle so its not a huge deal).
Infact, most times you use WindowsIdentity it is good to dispose of the item. Except for one case.
If you call Impersonate() on a WindowsIdentity instance, disposing it will cause hard to diagnose crashes.
It took me a while to work out why, so I thought I would write this up, maybe it’ll save someone else out there the trouble once.
Reflecting through windows identity related code, tokens get duplicated and new WindowsIdentity instances get created all over the place, so it would seem that you were safe to dispose.
However, when you call Impersonate, the WindowsIdentity instance, and its internal safe handle, get stuffed into the current security context, without being copied or duplicated. I don’t know whether that security context disposes the instance later (looks like it doesn’t), but it effectively takes ownership of it, so you can’t.
If you do dispose of it, and you start a timer or queue a work item before the impersonation is undone, when that timer or work item is executed, the .net framework attempts to set up the security context by impersonating again, but the safe handle is already disposed.
As a bonus, you can disable security support in the .Net runtime, in which case the newly corrected code temporarily leaks handles without the runtime being responsible for the leak.
So I have had a chance to look at the CTP briefly and I’ve found a few things of interest
I haven’t really played arround with c# 4 yet, so I haven’t discovered any cool new syntax. (Although I’ve heard about dynamic, and generic variance.)
Also i’ve really only looked at mscorlib and system. System.Core was a brief eyeball in reflector, everything else I’ve not had a chance to examine.
Thought I would post something, since it has been a while.
Looking forward to .Net 4/c# 4 news next week with the PDC. Session notes make it sound like BigInteger will be going mainstream so I can remove my dodgy reflection hack from TMD.Algo in the future.
Been doing some code cleanup at work for a couple of days as a change of pace and learnt a thing or two about fxcop – finally discovered what Gendarme is. (I’ve seen it mentioned on the mono mailing lists but I never really paid attention.)
I also discovered MoonWalker, which sounds excellent if it has an acceptible running speed and can be applied to real apps. (Although it would be extra cool if it had inner knowledge of SQL database lock acquisition which is caused by .Net code so it could diagnose mutual .Net/SQL deadlocks. I can always dream.) I haven’t tried it out yet.
Applying fxcop rules to old code is somewhat of an exercise in frustration, so many style issues are recognized which you can’t fix because they are breaking changes. And other rules fail so often you just don’t have the time to fix them all. Anything to do with naming has alot of false positives so we can throw those out quickly, and there are a few rules which are very dubious (Avoid unneeded assignments I am looking at you), but even after you pull all those away there is still usually way more than you can fix in a reasonable timespan.
FxCop 1.36 is definitely an improvement over 1.35 – much lower false positive rate. But there are a few rules which have gone away (admitedly false positive causing ones) which were really nice. Validate arguments to public functions is a really good rule, if only it didn’t give false positives everywhere. Another one which is gone is Dispose of objects before they leave scope. I haven’t seen many false positives from it but it is gone, along with ensure base.Dispose is called.
Rules for implementing dispose correctly are quite numerous so you get to learn them well and I think they are mostly pretty good – however I have run in to a fairly common scenario where my friends and I think they are wrong.
If you have a class which is only used as a singleton instance exposed via an Instance property, and that class maintains disposable objects, the rules state that the class needs to implement IDisposable. However if you implement IDisposable, you tempt users of your Instance property to call Dispose, which is bad. Additionally, Dispose will never be called because singleton is never torn down.
If the singleton manages unmanaged resources, then you need a finalizer, but you still don’t need Dispose.
An alternative in many cases is to have written the class as a static class in the first place, rather than go with the singleton pattern. But thats a whole different argument right there.
Globalization rules also crop up pretty frequently, and at first I thought fixing them in old code was way too high a cost to benifit ratio. But then I actually started to run in to scenarios which would have been caught by fixing the issues raised by these rules. Things like times in Itallian using . instead of : as the time separator.
But one thing which came to my attention is how frequently string.Format is used instead of string.Concat, in scenarios where string.Concat is really the better option. If you are joining strings which are localized, string.Format is the way because the grammar in each language is different, but if you are joining togeather strings for some custom logging, or in those cases where dynamic sql/javascript can’t be avoided, you often aren’t really formating, just concating.
One final thing – DataTable/DataSet.Locale – a property I never knew existed or would have thought to even look for if it wasn’t for FxCop. Now that I know it exists, I begin to think that maybe I will find a whole lot more places which should have a locale property if I go and look for them.
Anyway, thats all I have on the top of my head for tonight.
Shame the ISP connection dropped out.
I have 3 UPS for 4 computers, 2 monitors, a switch and an adsl modem (and a phone).
The alarms woke me up just after 4 this morning, although it appears that one of the UPS had already failed before I was awake.
I run a text based online role playing game server on one of the computers (which was connected to a UPS which hadn’t failed), so I logged in to warn everyone that the power was out, but no one was there because the adsl connection had been out for 2 minutes.
Shut everything down, but in the dark I couldn’t see where to turn the main UPS off.
Went back to sleep and an bit more than an hour later, the main UPS alarm was still going. It was light enough to see a bit then, so I could finally turn it off.
7am, power was still out so I went to work. Guess my text based MORPG won’t be back up online until I get home this afternoon. Looking at an 11 hour outage, which I think is as long as all outages combined since I last moved house.
Finalized results are out – 139th for me.
The third question would of gotten me 87th and finally 37 points was above the cut off.
In a moment of inspiration, I realised that my solution to the 3rd problem would have solved both the small and the hard, which would have gotten me through.
However, it fails to produce the correct result, even though it runs in time. I guess there is another bug in my ternary search.
I came 143rd (out of 180 in the APAC).
With 2 minutes to go I started running my code for a test case which if it had passed, would have gotten me ~80th. However I was running debug code, with the debugger attached!
A couple of minutes after the comp finished, my code finished running.
Additionally, I was about a couple of minutes of coding away from getting out the first problem, which would have gotten me ~38th position. Which was close to the cutoff for 36th. Poor concentration during the early part of the comp on my part explains why I failed to see the last little bit until just after the competition.
However, I plan to keep working on TMD.Algo (which was practically no help in todays competition, of course) and hopefully next year I’ll get to those finals. (Although my best is still 2005, I’m not getting any younger…)