AVL Trees Turn 50

I am teaching 600.226: Data Structures as a summer session course right now, and we covered AVL Trees yesterday. As I was ranting about them I suddenly realized that they were first published in 1962, and here I am in 2012 still teaching them to my eager (and somewhat perplexed) students.

So blame my brain: I have never been able to develop a good intuition about red-black trees (which I gather is what "respectable" schools are supposed to teach). My favorite balanced trees are treaps anyway, because they take so little code yet perform so well. But I feel that I "owe" my students at least one deterministic balanced search tree, and 2-3(-4) trees are just so messy to implement. Hence AVL!

I started to wonder: Since AVL trees were published in 1962, were they the first efficient data structure for ordered sets or maps? So I did some checking, and here is what I found:

AVL Trees 1962
B-Trees 1970
Symmetric Binary B-Trees 1972
Finger Trees 1977
Red-Black Trees 1978
Splay Trees 1985
Treaps 1989

If we losen things up a bit and include things that either demand more of the data or provide fewer general operations, we could consider these as well:

Tries 1960
Heaps 1964

So as far as I can tell after a quick search, AVL Trees are indeed the oldest efficient way to maintain a dynamic ordered set or map. And since students still have some trouble implementing them today, I guess that means we either haven't made a lot of progress, or we should take our proverbial hats off and nod a quiet "Thanks!" to Adelson-Velskii and Landis for figuring out how balanced search trees should work before most of us were even born.

One or two rolls in D&D-variants?

Let's look at how (simple) combat works in (classic) D&D variants. There's an attacker of a certain level and a defender with a certain armor class. The attacker makes a roll, modified to take into account the attacker's physical capabilities as well as the situation the attack is made in. If the attacker hits, the attacker rolls damage which the defender subtracts from hit points. Not very complicated, is it?

Note that there's one roll for the attack and one roll for damage if the attack succeeds, that's it. Specifically, the defender does not make a roll to see if the successful attack can be evaded somehow. (And neither is there a roll to avoid some of the damage.)

Now let's look at how (simple) spells work in (classic) D&D variants. There's a caster of a certain level and a target of a certain level. (There are spells in which one or the other level doesn't matter, but that's besides the point.) Provided the caster doesn't get distracted while casting, the spell will be cast successfully. Now the target gets to make a saving throw against the spell. If the saving throw fails, the full spell effect applies to the target; if the saving throw succeeds, only some or none of the effects apply to the target.

Note that there's again one roll, but this time the roll tells us whether the defense was successful. (There may also be a roll for damage made by the caster, ignore that.) Specifically, the caster does not make a roll to see if the spell worked or fizzled somehow.

But now look at surprise. Surprise! There is both a chance to be surprised and a chance to surprise someone else. Details vary by which version of D&D you're looking at, but they all seem to maintain that both sides get to roll for both things. Having both sides roll dice in this situation but not in the other two situations seems rather odd. (I have no problem with the fact that the first two use a d20 and the third uses a d6, that's not the point.)

There are other places where a "let's use two rolls" mechanic has crept into D&D, for example when trying to disarm someone: You have to hit, but then the defender gets a saving throw to avoid dropping their weapon. There are also places where two rolls actually make sense in a way, for example for spells that require touching the target with a successful attack.

Now some people may just not care and some may say "different mechanism for different tasks are a-okay" or something close to that. But for myself, I would prefer a clear line throughout the whole system: Either use two rolls consistently, or use a single roll consistently, but don't jump back and forth. Opinions?

History of Greyhawk Wars PDF

It's difficult to explain exactly why I've done this, but in any case: I grabbed the old "Official History of the Greyhawk Wars" document that TSR posted on AOL in 1995 and converted it to LaTeX. I am probably not the first to do this, but I couldn't find another version anywhere, only RTF and HTML versions. I think my PDF looks great and reads better than the other versions I've seen. I made one tiny change compared to the original: I moved a paragraph from one section to another to get a more decent layout. Let me know what you think!

Spell Progressions in D&D-variants

I've been reading some interesting stuff related to D&D-type roleplaying games recently. One thing I came across is spell progression: How do you translate from the wizard or cleric level to the number of spells of each spell level the character can cast? Apparently different incarnations of D&D used somewhat different tables over the years.

All of this reminded me that I never liked the spell progressions in D&D-type games: I never "got" them in the sense that they always seemed way too random to me. What was the unifying mechanic behind all these numbers? Hard to figure out, go ahead, try.

I use the following simple progression: 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 and so on and so forth. Read: You start spell level x with 1 spell, after one more level you gain a second spell, after two more levels you gain a third, after three more you gain a fourth, etc. And I use this for each spell level. Both wizards and clerics gain a new spell level every 2 class levels, and done: One simple rule explains it all.

Yes, there is some “fluctuation” in terms of which character levels get the most new spell levels, but it’s really not too bad to say “look, level 18 is really powerful because that’s where you realize the most about how the multiverse really works". And yes, there are certain levels where you gain absolutely nothing, especially as a cleric, but those are really high and I wouldn’t normally play there anyway.

Comments?

Browsing man pages in vim

So I've been playing around a lot with my .vimrc lately, and this is one of the more useful things I've added. I have forgotten where it came from exactly, but here it is:

let $GROFF_NO_SGR=1
source $VIMRUNTIME/ftplugin/man.vim
nmap K :Man <cword><CR>

What's it good for? The default key binding for K (that's "shift-k" I guess) in vim is to look up the word under the cursor using the man command. The sad thing about this process is that vim gets replaced by less (or whatever pager you happen to be using), and that once you're done reading the page, you have to press "Enter" one additional time to get back into vim and back to whatever you were doing. Kinda breaks your flow, you know?

Once you've added the three lines above to your .vimrc things are quite different. When you hit K, the man page opens as a new split window inside of vim so you're staying in the same environment. All the usual binds for switching between windows work, so you can keep the man page open while going back to your code. Better yet, the man page will be "syntax highlighted" using different colors for headings, text, and (you guessed it) references to other man pages. And the best thing? You can browse man pages the same way you browse tags: use "ctrl-]" to open another man page and use "ctrl-t" to "go back" to the previous one.

Now that's how man pages were supposed to be integrated with your editor. Very nice indeed... :-D

There's one small problem that I have not been able to work around yet: The original K could be preceded by the section number to look in, but this won't work in the replacement above. I am not enough of a vim hacker yet to add that capability. Shame on me?

Update: Actually, I forced myself to learn just enough of vimscript to cobble together something ugly for section numbers:

" experimental hack to get section numbers to work as well

function ManWrapper(n, w)
  if a:n > 0
    let cnt = a:n-line(".")+1
    execute "Man" cnt a:w
  else
    execute "Man" a:w 
  endif
endfunction 

com -count=0 -nargs=+ CMan :call ManWrapper(<count>, <f-args>)
nmap X :CMan <cword><cr>

Yes, I know, it's quite horrific! If you know this dreadful language better, please tell me how to rewrite this cleanly.

Random Design Patterns, Part 1

I have no special reason to start writing these, except that I've been re-reading some patterns stuff recently. And while they are "warm" in my brain, I might as well try to write them down as that always seems to help me "solidify" things. None of the patterns I'll write about are new in any way, so feel free to skip these posts you pattern gurus!

First pattern, simple as can be: Null Object. Say you have some operation that returns a Sprite object that you then do something to. What if there is no sprite? You could return NULL or nil or None or whatever your language of choice calls the thing. But then you have to check the returned value:

sprite = some_operation()
if sprite:
    sprite.do_something()

If instead you return a Sprite instance that simply doesn't do anything, your code becomes a little more straightforward:

sprite = some_operation()
sprite.do_something()

Not exactly a big deal, but of course it could add up to something more significant if you were using this in a more complicated way.

It's certainly not a good idea to always ignore the fact that you didn't find the sprite in question, for example you don't want to keep inserting NullSprite objects into a list over and over. So when you do care, you need a way of telling that it's a real sprite. One way is to guarantee that only a single NullSprite is ever created and to make that one globally accessible. Then, in places where you care, you can say this:

sprite = some_operation()
if sprite is not Sprite.NULL:
    sprite.do_something()

Whether Null Object is particularly useful therefore depends on how often you care versus how often you don't care (but still have to check if you use the language's builtin version of "no such object"). As with all design patterns: Think before you apply the pattern!

Sets of Dictionaries in Python

I may come to regret this post in the future, we'll see. So I was hacking on some sysadmin tool that collects data. Each item is a dictionary of various things, and I had all those dictionaries in a list. Wait! What if I parse another piece of data that results in an identical dictionary? I don't want to keep growing the list to infinity with duplicates, do I? So without much thought I replaced the list with a set, but that doesn't work:

>>> set([{}])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'dict'

Of course this makes sense: Python implements sets as dictionaries and dictionaries as hash tables and you cannot use something mutable as a key in a hash table. (If you don't see why that's so, think harder.) But sensible or not, what I certainly don't want to do is search my list of dictionaries for duplicates before every single insertion! So I came up with a little hack to make dictionaries hashable:

def hash_string_dict(obj):
    """
    Return a unique-ish string for a dictionary mapping
    string-ish things to string-ish things.
    """
    import hashlib
    k = "".join(sorted(str(obj.keys())))
    v = "".join(sorted(str(obj.values())))
    digest = hashlib.sha1(k+v).hexdigest()
    return digest

Alright, so the dictionaries are not really hashable, instead I produce a hashable digest of a dictionary's contents. You can now give me a lecture on how this is not very efficient, and some part of me would agree. However, given a long enough list of dictionaries, the time I spend on computing these digests will be less than looking through the whole list for a duplicate.

So instead of a list of dictionaries or a set of dictionaries, I end up with a dictionary of dictionaries: The key in the outer dictionary is the digest of the inner dictionary. If a duplicate comes along it'll produce an identical digest and I can forget about it after one (expected!) constant time lookup.

Of course all of this depends crucially on my dictionaries being immutable as far as my application is concerned. Python itself doesn't have the luxury of wondering about this, it has to "worst-case" it and assume all dictionaries are mutable, period. I wonder: Should I package this as a container class? :-D

Update: Note that it's sort of important that the keys and values you have in that dictionary produce "useful" string representations. In other words, don't apply this trick without thinking through the kind of data you're pushing around and whether the digest has a reasonable chance of being accurate enough for duplicate detection.