A dissection of Steve Jackson's Creature of Havoc

I recently found some old Fighting Fantasy gamebooks I remembered from my childhood. One in particular stood out as having seemed next to impossible. I never finished it. I had vague recollections of infinite loops and dead ends, of getting fed up of playing by the rules and yet still not managing to find the way through when I bookmarked pages and backtracked from untimely deaths.

For those unfamiliar with the series, these were like Choose Your Own Adventure books, but in addition to your choices, you also had to roll dice and keep track of your health and inventory throughout the book. You could die from your wounds due to bad luck as much as bad decisions, although generally with sufficiently good choices you could minimize the likelihood of such an outcome.

I've found some accounts that describe the correct path through this book (e.g. solution 1, solution 2) but I wanted to do something a bit more thorough, so I decided to diagram the entire book and have a look at what made it quite so nasty. I woefully underestimated how much work this would be, but it's done now, for better or worse. I also did a crude Monte Carlo simulation to try to figure out how hard the book is even when you know exactly what to do.

Overview

I've split the book into lettered chunks of closely related pages. Sections A through M cover your escape from the dungeon. Sections N through W cover your search for the necromancer Zharradan Marr. There's a bottleneck around the middle, but both before and after there are sections with a lot of branching.

Throughout the book, there are a number of items or abilities that you need to find to be able to make progress later on. In some cases (e.g. the elven dust), it just asks you if you've got the item and if so to turn to page X. But with most of them, the book will tell you some number or operation when you get them, possibly with instructions about when to apply it to find a new page to turn to. In this way, it's not always obvious when or if you were missing an important item. The items that you must not miss in order to complete the book (marked in gold on the diagrams) are the pendant, the club, the ability to decipher codes, the ring of holy blessing, the ability to enter the netherworld, the elven dust, the assistance of Grog, the sculliweed and the ring of truth.

During the first half of the book, there are many different ways through, but there's essentially one long correct path, and a large number of shortcuts that skip out different sections of this path, missing the opportunity to obtain essential items. There are also some dead-ends and short optional sections.

Random wandering

During the first part of the book, everything is determined by dice rolls. You have no free-will. It is entirely possible, though relatively unlikely, to die before you get to make a single decision. You get four chances to get onto the path of success, but if you get the wrong path every time you end up in a dead-end section headed for one of a variety of certain deaths. Apart from disorienting you, this section hampers an honest player from powering through with the same decisions every time they play - you need to repeat the rolls every time and might have to take a different path. Given the improbability of heading down the doomed path, you also get a nagging sense of having missed something, since until you've died down that path a lot you're never sure if there was a way through that you might have missed.

You can see that I've coloured in deadly pages as black, and I've also shaded in dark grey those pages that inevitably lead to death. Page 408 marks your certain doom as you fall onto the unlucky path that will inevitably see you die on page 99, 14 or 260.

In fact, there's really nothing of terribly great importance in these first sections. It's not until you reach section C and your choices open up that you can start screwing up of your own accord...

The power to choose

Section C branches rapidly, and provides many ways to fail. There's no backtracking to this point, so if you miss the magic pendant on page 306 (coloured gold) you will certainly die eventually. The bracelets and the coins might seem useful, but they are distractions from the pendant. Those paths which necessarily miss a vital page are coloured light grey. You can't win once you find yourself on one of these pages, but they're not as bad as the dark grey pages, because they do return to the main path, and while you can't finish the book, you may still learn something useful along these paths. In contrast, the dark grey pages are cul-de-sacs, and at best all they offer is an entertaining death.

From here, branches lead to sections D, F, G, H, I and J, but as there's no backtracking, leaving to any section other than D will miss out important discoveries and prevent you from finishing.

The pendant is one of several mechanisms that lets you turn to pages that are not listed as options. When you see the key-text "You cannot see a thing" you can subtract 20 from the current page number to find a secret. You need to use it here in section D to gain the crystal club, another essential item that is needed much later on. You get the option to use it in combat by turning to another page, but this is a trap - it destroys the club which you need towards the end of the book.

Section E yields the secret to the codes found throughout the book. This too is absolutely necessary, since some of the coded passages contain instructions to tell you to turn to another page. The code is slightly frustrating - it explains how to encode text, but the operation is slightly lossy, and you need to make some guesses in order to reverse it correctly in all cases. There are also some optional items to obtain here, but the sack seems to be useless, since the conditions to use its ability never seem to come up. It would make sense if it allowed you to collect all three kinds of plant in the swamp instead of picking just one, but there's no allowance for this in the text. The rhino's message unlocks some sections later on that can only be accessed on a doomed path, so it's a bit of a red herring. The breastplate seems like the best optional item here, but I'm not certain whether it's worth it. It makes you better at fighting but worse as skill checks. There's only one skill check on the critical path, but failing it spells doom.

Section G misses the ring in section F, but it does introduce the use of the pendant in a hard-to-miss way. There are a bunch of interlinked pages that you can wander back and forth between, one of which has the trigger-words for the pendant, and one of which kills you. If you don't have the pendant you're stuck, but if you do hopefully you'll notice the opportunity to use it as you wander around.

Section K contains the notorious misprint. The trigger-words for the pendant are missing from page 213. However, the layout here is very similar to section G and the dead-end is pretty suspicious, so it's perhaps not wholly impossible to guess what you're supposed to do here.

Section L introduces a pretty elaborate warren of dead-ends for you if you have missed the secret code or the ring of holy blessing. It will take you quite a few deaths in the mines, or fighting an endless loop of chaos warriors to discover that there is no way through here. I think the endless loop is quite cruel, and it isn't the only time the book does this to you!

Section M similarly has a large number of ways to fail, although all lead to the same end, unless you are lucky enough to be killed by the guard. This has the peculiar feature of a page that ends with "Unless you wish to try battering the door down (turn to 128), you have reached the end of your journey." This sounds like an optional death, but really it's just there to confirm that yes, this is an infinite loop, and your choices are to slowly batter yourself to death in a futile attempt to break down the door, or to put the book down and walk away.

Outside the dungeon

In section N, you are finally free from the dungeon. But rather cruelly, one of the paths here takes you right back into the dungeon, back to section K, only this time you no longer have your pendant so you are trapped with no way to escape.

Section O introduces the friendly half-orc Grog (assuming you manage to find and rescue him) with a nice little system where whenever a page number ends in "7", you can subtract a number and Grog will say or do something to help before you turn back to the page you were on.

In section Q, poor Grog meets his demise. You actually turn to a page that kills you (hence I've shaded it black), but since it ends in a "7", you can turn to another page and continue. Grog, sadly, does not get to continue. Hopefully you were paying attention when Rosalina told you that sculliweed has blue stems, otherwise you'll be taking a short and miserable trip to Dree.

Much like the end of the dungeon, if you miss the trick in section S, by not having the ring, not remembering to use it or simply not asking the right questions, you'll end up in a large dead-end section, exploring magic pools and getting lost in the forest.

The Galleykeep

Section T is the finale. Some of the critical requirements here were from far, far back at the beginning of the book, so you might get here with no idea of how to proceed. Again, most of the paths here require knowledge of secrets from earlier on, so you may not even realise that you're missing something. There's another death loop here - if you're unlucky enough to find the undead physician, you'll have to keep fighting him over and over until you die.

There are a few ways to end up in Dree, and not much to do there other than die! If you read the introductory material at the start of the book you might know not to trust anyone offering you potions there, but the knowledge won't help you much.

The training camp is another red herring. It's possible to get out of it alive with the help of your rhino friend, but you won't get far beyond it, because you won't have the ring of truth.

Simulation

I hacked up a rudimentary simulator in Python to run through the critical route. It's not optimal, because it's pretty hard to know when best to use the option to "test your luck" during combat. I also haven't experimented with trying to kill the rhino-man to steal his breastplate, which trades off skill for attack strength. But nevertheless, here's the result of running 10,000 trials:

You were mind-controlled by a wizard.                          2920
You win!                                                       2089
You were killed by dark elves.                                 1260
You drowned in the Bilgewater.                                  986
Killed by <THIEF, skill=8, stamina=6>, <WARRIOR, skill=7, stamina=7>    682
Killed by <First BLOOD ORC, skill=7, stamina=7>, <Second BLOOD ORC, skill=8, stamina=7>    440
Killed by <WARRIOR, skill=8, stamina=9>                         343
You beat yourself against a door.                               295
Killed by <CLAWBEAST, skill=9, stamina=14>                      214
Killed by <FIGHTER IN LEATHER ARMOUR, skill=7, stamina=8>       159
Killed by <First FLESH-FEEDER, skill=6, stamina=6>, <Third FLESH-FEEDER, skill=6, stamina=6>, <Second FLESH-FEEDER, skill=6, stamina=7>    158
Killed by <STRONGARM, skill=7, stamina=8>                       128
You could not control the ophidiotaur.                           83
Killed by <ARMOURED KNIGHT, skill=8, stamina=9>                  80
You were eaten by the Galleykeep crew.                           72
Killed by <MANIC BEAST, skill=7, stamina=8>                      59
A knight stabbed you in the back.                                21
Killed by <HOBBIT, skill=5, stamina=6>                            7
Killed by <Second BRIGAND, skill=8, stamina=7>, <First BRIGAND, skill=8, stamina=9>      3
Killed by <TOADMAN, skill=9, stamina=9>                           1

So it seems to work out that, if you know the path, and play by the rules, you have around a 20% chance to survive to the end. Perhaps it's a little higher if you make better decisions. That wizard right at the start is really deadly! I'm amused that the hobbit managed to kill us 0.07% of the time, and the door is really quite dangerous, killing us 2.95% of the time. I'm curious why the toadman gets so few kills, but I suspect that it's because very weak characters have already been weeded out, and you get healed shortly before the encounter. Overall this isn't quite as hard as I had thought - the difficulty of the book largely comes from all the secrets that necessitate an extremely thorough search of every corner of the book.

If you want to mess around with the code, feel free. I make no guarantees that it's actually correct! It was a quick, fun and not in any way rigorous. I've put it in a github repo along with the drawio files for the diagrams.

Here's what the description of the book looks like - all the options have been stripped away, so apart from the random bits at the start, it's a straight path all the way through.

book = {
    '1':Seq(
        Compare('1d6', '<=', 3, then=Goto('205')),
        Compare('1d6', '<=', 2, then=Goto('205')),
        Compare('1d6', '<=', 1, then=Goto('205')),
        Fight([Character('CLAWBEAST', 9, 14)]),
        Compare('1d6', '<=', 4, then=AddStat('stamina', 2)),
        Compare('1d6', '<=', 3,
                then=Die('You were killed by dark elves.')),
        Goto('205'),
    ),
    '205':Seq(
        Fight([Character('HOBBIT', 5, 6)], aggressive_luck=True),
        Compare('combat-duration', '<=', 3,
            then=TestStat('luck', on_fail=
                Die('You were mind-controlled by a wizard.')),
            otherwise=Compare('1d6', '<=', 4, then=
                Die('You were mind-controlled by a wizard.'))
        ),
        AddStat('stamina', -2, 'A knight stabbed you in the back.'),
        Fight([Character('ARMOURED KNIGHT', 8, 9)]),
        RestoreStat('stamina'),
        Compare('1d6', '<=', 2, then=AddStat('skill', -1)),
        Compare('1d6', '>=', 4, then=AddStat('stamina', -2)),
        Fight([
            Character('First FLESH-FEEDER', 6, 6),
            Character('Third FLESH-FEEDER', 6, 6),
            Character('Second FLESH-FEEDER', 6, 7),
        ]),
        AddStat('luck', 2),
        Fight([Character('STRONGARM', 7, 8)]),
        Fight([
            Character('THIEF', 8, 6),
            Character('WARRIOR', 7, 7),
        ]),
        AddStat('luck', 1),
        TestStat('luck', on_fail=
            Die('You drowned in the Bilgewater.')),
        Fight([Character('WARRIOR', 8, 9)]),
        Fight([Character('FIGHTER IN LEATHER ARMOUR', 7, 8)]),
        AddStat('luck', 1),
        Fight([
            Character('First BLOOD ORC', 7, 7),
            Character('Second BLOOD ORC', 8, 7),
        ]),
        AddStat('luck', 2),
        TestStat('luck', on_fail=
            Die('You drowned in the Bilgewater.')),
        AddStat('stamina', -1, 'You beat yourself against a door.'),
        Fight([
            Character('MANIC BEAST', 7, 8, manic=True),
        ]),
        AddStat('stamina', 4),
        RestoreStat('stamina'),
        AddStat('stamina', 8),
        AddStat('luck', 2),
        RestoreStat('skill'),
        Fight([Character('VILLAGER', 7, 8)]),
        AddStat('luck', 2),
        AddStat('stamina', 4),
        Fight([Character('TOADMAN', 9, 9)]),
        RestoreStat('luck'),
        RestoreStat('luck'),
        RestoreStat('stamina'),
        TestStat('skill', on_fail=
            Die('You could not control the ophidiotaur.')),
        Fight([
            Character('Second BRIGAND', 8, 7),
            Character('First BRIGAND', 8, 9),
        ]),
        TestStat('luck', on_fail=TestStat('luck', on_fail=
            Die('You were eaten by the Galleykeep crew.'))),
        Fight([
            Character('Second GOBLIN', 5, 5),
            Character('First GOBLIN', 6, 5),
        ]),
        Win()
    ),
} 

Conclusion

I think this book is better appreciated as a masterpiece of cruelty than as a game. It's very cleverly constructed, but I'm not sure how much you can really take that in just from playing it. I don't remember enjoying it nearly as much as other such books when I was a child. It's just overwhelming, and requires a great deal of attention and note-taking. I think the variety from random outcomes can keep things interesting for a while, but I can't imagine it still being fun by the time you've finally pieced together everything that you have to do. I wonder how many people ever finished it without cheating. I certainly was not one of them.

PS - Draw.io is really great! I started drawing the diagrams in Inkscape, but it was too slow and its connectors weren't as easy to use. Draw.io did a generally good job, although it's a bit rubbish at exporting. I had a lot of hassle because I'm using a custom font, and most of the export options end up trashing the text in one way or another.

Some programming annoyances

I write and maintain mostly C# these days. I've been accumulating a list of annoyances. Whenever I come across a piece of code that makes me groan, fills me with fear or just bothers me, I add it to the list. It helps keep me sane. Some of them are obvious and blatant; nobody should be doing those things! Some of them are subtle. Some of them are debatable. All are related to actual code I've dealt with. Some of them are things I do myself and then feel guilty about. Maybe you'll find them interesting. Maybe you'll disagree.

C#

Most of these are C# or at least .NET-specific. Some are general to object-oriented languages.

Don't lock on public objects

This exposes your implementation and invites deadlock.

Don't lock on String.Empty

Seriously. WTF. I mean, locking on strings is weird and problematic enough, but locking on String.Empty??

Don't catch Exception

There should almost always be a more specific exception to catch. If you're catching Exception you have no idea what kind of bad state your program is in and there's very little you can sensibly do. I'll concede that there may be situations where you need to bundle away the exception to rethrow later on, if you're writing some kind of remoting/scheduling framework, but really ask yourself if you need to be doing that. As soon as you catch that exception, you're making it much harder to debug, by separating the symptom from the cause in time and space.

Don't do work in a constructor

It is a horrible code-smell if you construct an object and then throw away the reference immediately, indicating that it is invoked solely for the side-effects of its constructor. Constructors should not be responsible for stitching the newly created object into an object-graph. You have something that resembles a Klein bottle. I find it hard to express exactly what's so bad about this, but it fills me with trepidation when I see it.

If you need to guarantee that some non-trivial work is done before the object is in a valid state, you should not postpone that work until after the constructor. That's worse! Instead require that it has been completed before the constructor is invoked - the prepared components should be arguments to the constructor. Perhaps you will find that you then need another object to assemble the object-graph. That's okay! Assembling a system is a different and quite unrelated task to the job the system performs! Cars, computers, bridges, houses - none of these engineered objects need to assemble themselves. The same is true of objects in programming.

Avoid "new" outside of factories

Okay, this is possibly a controversial one.

The "new" keyword should be relatively rare in your code. It's okay to new up a List or Dictionary, but you should not be constructing objects all over the codebase. This tightly couples code and makes it difficult to test separate components. It's especially bad to have a huge hierarchy of constructors called by each other. Prefer to confine construction to factories. Note that you don't need one factory per class - often it makes sense for one factory to construct a suite of related object classes.

Avoid downcasting

Sometimes it's the pragmatic choice. Most of the time it creates hidden dependencies and surprising behaviour.

Don't use "indicator" interfaces

Interfaces without members are a bad smell. Don't use interfaces which are just indicators that the object can be used in some other way, such as by casting.

One pattern that does this a lot that I don't have a great answer for, is the "interface that returns handles". Suppose you define an interface for a file-system, and an interface for the files/folders it contains. The file-system hands out instances of the file interface to represent the files it contains. The question is, how do you describe file-system operations that affect two files? Say "move this file into that folder"? How do you design this so that you can have different implementations of the file-system interface with different hidden implementation details, but still have a natural and useful API for users? I've seen a lot of systems that just take IFile as an argument, and fail if the downcast to MyFileType fails or if file belongs to a different file-system. That seems downright nasty, but I most of the alternatives I can think of are still at least a bit unpleasant.

Prefer signed integers

Unsigned integers are unusual in .NET APIs. They're not CLS compliant - other .NET languages might not have them. They also behave badly, silently wrapping when decremented below 0. It's better to take signed integers as parameters and throw an exception when a negative value is provided than to take unsigned integers and fail in weird ways when somebody accidentally decrements beyond 0. Unsigned integers should only be used when it's important to have the entire range of positive values. Also beware not to do this:

for (uint i=9; i>=0; --i) { ... }

This advice is quite specific to C#. It sometimes applies in C++, but unsigned integers are much more pervasive there, particularly size_t, so it's not such practical advice. It doesn't apply at all to languages that don't have silent wrapping.

Dispose in reverse order of creation

Objects with *similar* lifetimes should have *nested* lifetimes. Anything else is horrible to keep track of and maintain. That said, most of the worst cases of this I've seen have involved other bad practices, like massive constructors that call a million other constructors. Nothing is less fun than trying to fix an "object diposed too early" bug and finding that it's one of thirty other objects disposed by its parent in seemingly random order.

Don't have properties that modify state

It's surprising, and it will do weird stuff in the debugger. Property access should not observably modify state. (Caching an unchanging result is probably okay.)

Don't hand out "this" in a constructor

Here's another one I think might be controversial. I'd be interested in feedback on this one, and I'll try to answer questions anyone has.

See also "Don't do work in a constructor". If you pass out references to "this" (including bound methods, or closures that capture "this") you are revealing your partially constructed object and allowing it to be meddled with before it has established its invariants. This will end in tears if you have subclasses. Even if you don't have subclasses, it's hard to maintain. It becomes unclear where in the constructor the invariants have been established, and it breaks easily when someone tries to re-order the code in the constructor.

Don't throw from a Dispose method

It's too late. You don't know if your object is being disposed due to stack unwinding passing through a "using" block, in which case you will trash the useful information in its stack trace and replace it with less useful information from your own. If you're doing something in a dispose method that might fail, prefer to give users a way to do it manually before the object is Disposed, and throw at that point. I'm not 100% certain on this one. There are cases where it's a programmer error to forget to do something before disposing an object and it would be nice to flag it up.

Prefer not to expose IDisposables to clients who are not responsible for disposing them

It's just too confusing otherwise. A corollary is that you should be very careful about declaring interfaces that inherit from IDisposable. Should all clients of your interface have the power to dispose the object?

Avoid null values when possible, and document them clearly where they're necessary

Nulls are insidious, and love to get into places they're not supposed to be. Avoid them in APIs when possible.

Avoid null with the meaning "key not found"

This just invites your clients to make a mistake and forget to check if the value is null. Prefer to throw an exception, or use a TryGetValue approach, or let the client specify what to return when the key is not found. If you must, document it.

Don't repeat yourself

Do I need to say this one? Don't repeat yourself. It just gives you more places for bugs to live and more places you need to remember to fix bugs.

Prefer composition to inheritance

Inheritance exposes part of your implementation. It also tightly couples you to the base class implementation. Prefer composition as a first resort, and inheritance only when it is well-suited to the problem. If you're not going to make use of polymorphism, think very carefully about why you're using inheritance.

Don't hold references "for a friend"

Especially don't hold references solely for the purpose of passing them on to a constructor later on. See also "Avoid 'new' outside of factories".

I'm guilty of this myself. I think this tends to go hand-in-hand with Law of Demeter violations. It's probably a sign that your objects know too much about each other. However, it can take a lot of careful thought to iron out these problems. I have a feeling that a good dependency injection framework is helpful here, but sadly I've not been able to use one much lately, so I've got no first-hand evidence.

Ensure no methods on an object will be called after you enter its Dispose method

Just as a constructor shouldn't hand out references to "this", a Dispose method shouldn't be expected to defend against use of outstanding references to "this". You may choose to detect and flag up this situation, but it should be considered an error, not the intended behaviour. The same problems with sub-classes arise. Clients of the class should guarantee that all other uses of it happen-before invocation of Dispose. If the class itself manages a thread or by other mechanisms causes concurrent invocations throughout its lifetime, *those concurrent invocations should not be to the object itself*.

This goes double for C++ destructors. You are doing something extremely dodgy if any other thread is calling methods on your object after control has entered the destructor.

NUnit

My list was almost entirely general C# stuff, but there were a few items specific to unit-testing.

Avoid Debug.Assert

Use the NUnit asserts. They give better error messages.

Don't Assert.IsTrue(false)

This is perverse. Prefer more specific assertions which can give you more information about what went wrong. E.g. Assert(foobar.Counter, Is.EqualTo(5)) will tell you the actual value of foobar.Counter when it fails. Even if there is no more specific assertion, prefer Assert.Fail, which is clearer as a "we should not have gotten here" indicator than seeing "Expected true: was false".

Don't repeat yourself

Yes, this counts for tests too. Yes, I understand the irony of repeating myself in telling you not to repeat yourself.

Use of 'this' in constructors

this in constructors

Some quick C++ advice today, but I think it generalizes to C# and Java too. If you do anything with the this pointer in your constructor – apart from dereference it – your design is probably missing a class.

There are a few dangers with using the this pointer in the constructor. For a start, weird stuff will happen if it ends up in the hands of code that attempts to call a virtual method: in C++ the instance changes type as each constructor in the inheritance hierarchy gets a shot at it, meaning that the same call will invoke different code depending on where we are in the construction process. In C# and Java you get a different sort of misery – virtual methods in a subclass can be invoked before their constructor has ever had a chance to initialize the subclass fields.

But I'd say the more important general problem is that it becomes much harder to reason about the class. It's no longer clear which methods can rely on the class's invariants being intact when they start, and it's no longer clear at which point in the constructor invariants should be established.

Concurrent access in destructors

The other side of this coin is destruction. If methods on your class can be invoked concurrently with its destructor something is fishy in your class! The most common scenario I've seen this is when the class manages a thread which it attempts to join during the destructor, and where the thread is calling methods on the class itself. This isn't obviously insane – with appropriate synchronization it can work and be safe – but I'd argue that it's still a really bad idea. For one thing, it all goes a bit wrong if you create a subclass – the concurrent calls will continue while the subclass destructor runs. (I'm not 100% sure, but I think it's probably undefined behaviour to invoke a virtual method on an instance concurrently with one of its subclass destructors finishing.) Even if you avoid subclassing, it gives you a messier destructor that's harder to reason about.

You're missing a class

The good news is that there is a general solution to these problems. If you have a class A that in its constructor wants to send its this pointer to a class B (figure 1), you can almost always solve the problem by splitting A into A₁ and A₂, with A₂ a member of A₁ (figure 2). The A₁ constructor can now give B a pointer to A₂. It might be a little tricky to figure out what goes in A₁ and A₂, but I think you'll find in the end the design becomes cleaner and your constructors and destructors will become less tangled and confusing.

Figure 1 – Before, the cycle of pain

Figure 2 – After, a pleasant pyramid

Key usage coding challenge

Last week, Cedric Beust posted a new coding challenge:

We want to make multiple calls to a site that only allows to use a key 500 times every 10mn. You are given a collection of keys (strings), a max count (e.g. 500) and a time period (e.g. 10mn) and your task is to implement getNextKey()...

(Go read the article, as there's a more detailed problem statement there.)

So we have a set of K keys, and each key is valid for X uses in a rolling window of T milliseconds. My first observation (made in the comments) is that we need never re-order our keys. If we use every key X times each in any order, then the next key that will be available for use is the first key that we used, exactly T milliseconds after we first used it. Then the second key, T milliseconds after we first used it. Whatever order we pick, we can just repeat it indefinitely. We might cycle all through the keys X times, or repeat each key X times before moving on to the next. For the rest of this discussion, we'll assume we have K keys that can each be used only once in the given period, and for which we won't bother keeping track of the different key names. We can easily adapt such a solution to handle the original problem, but it will be simpler to discuss. So here's the simplified problem we'll consider:

We want to make multiple calls to a site that only allows to use a key once every 10 minutes, and we have 500 keys. At any time we might be asked for a key to be used, and we must answer whether there is one free, and if there is, to consider it used up for the next 10 minutes. Your task is to implement tryUseKey(), returning true if a key was available and false if not.

My second observation is that to provide perfect answers, we cannot avoid storing the time-stamp of every one of the last K keys used. To observe this, imagine that over the last 10 minutes we have called tryUseKey() exactly K times. To recover the timestamps of all K invocations of tryUseKey(), we can just poll getNextKey() as fast as possible over the next 10 minutes. Every time it successfully returns a key, we know the approximate timestamp of one of the original invocations: about 10 minutes ago. By polling arbitrarily fast we can can obtain an arbitrarily accurate answer. If we can reconstruct this information, then it must be encoded somehow in our object's state, so we can place a lower bound on the working memory required by the data structure that is linear in K.

It's not especially hard to write a solution that solves the problem precisely by storing K timestamps, but it would be nice if we could trade off some precision in order to use substantially less memory. For that reason, we'll look for solutions that allow false negatives in specific circumstances. A false negative is to indicate that no keys are available when in fact some keys should be available. We never allow false positives – we will never say that a key is available when it should not be.

• We might allow a false negative when all the keys have been used in the last 11 minutes (rather than the last 10 minutes). We'll call this relaxed requirement A.
• We might allow a false negative when less that 50 (of 500) keys are available. We'll call this relaxed requirement B.
• We might allow a false negative only when less than 50 keys are available and all keys have been used in the last 11 minutes. We'll call this relaxed requirement AB.

I'm going to use graphs of keys used and available over time to illustrate a number of solutions. They're all going to look similar to this:

The orange line rises whenever keys are used. The blue line rises whenever used keys have "cooled down" over 10 minutes and become available for re-use. The blue area between the two lines shows how many keys are available for use – when the red and blue lines meet all keys have been used and none are available until the blue line rises again. You can see that the shape of the blue line in the top-right of the graph replicates the shape of the orange line in the bottom-left, as the keys that were used on the left become ready again on the right.

Buckets

All the solutions I'm going to discuss involve buckets. The general idea is that as we use keys we group them up in an "active" bucket, and at some point we set the active bucket aside (and don't add any more keys to it), and use another bucket as the active one. After a bucket has been set aside for 10 minutes to "cool down", we recover all the keys from that bucket. By grouping keys into buckets, we only need to store a timestamp for the bucket. By choosing when to set the buckets aside and how many buckets to use we can try to meet our relaxed requirements.

To meet requirement A we can use 10 buckets and swap out the active bucket every minute. Here's what it might look like:

The rectangles added to the diagram show keys held in buckets. In the light blue rectangles keys are added to the active bucket, while the dark blue rectangles show keys held in a cooling down bucket. The new green line shows the number of keys we consider free. It tracks closely to the blue line, but in places it is lower, the yellow area between them reflects where our algorithm will falsely report a smaller number of keys available than is accurate. The number of keys reported available may be a lot lower than the true value, but never for very long.

To meet requirement B we can use 10 buckets and swap out the active bucket every time it has 50 keys in it. Here's what that might look like:

As before, the yellow area shows where the algorithm will falsely report a smaller number of keys available than is accurate. This time the number of keys incorrectly reported unavailable is never very high, but can remain low for a long time.

Finally, to meet requirement AB, we can set aside a bucket after it has been active for 1 minute or after it has 50 keys in it, whichever comes first. It will look something like this:

The complication here is in figuring out how many buckets we might need. I believe it's 20. This can happen if, for example, we use 451 keys very rapidly, then use just one or two keys a minute for the rest of the time. So we need more buckets, but in return we obtain very strict bounds on how wrong our answers can be.

Generalizing

So far, we've been working with a specific example where the cooldown period is 10 minutes, there are 500 keys and we have allowed a 1 minute time threshold and a 50 key threshold for false negatives. We can change these parameters. The number of buckets we'll need for solution A is based on the cooldown period divided by the time threshold, the number of buckets needed for solution B is based on the number of keys divided by the key threshold, and the number of buckets needed for solution AB is the some of both these values.

The code

Here's an example implementation in Python:

import itertools
import time
from collections import deque

class Bucket(object):
    def __init__(self, close_time):
        self.keycount = 0
        self.close_time = close_time
    def add(self, now):
        self.keycount += 1
    def has_cooled_down(self, now, cooldown):
        return self.close_time + cooldown <= now
    def will_accept(self, limit, now):
        is_full = self.keycount == limit
        is_closed = now >= self.close_time
        return not is_full and not is_closed

def divide_rounded_up(dividend, divisor):
    return (dividend + divisor - 1) // divisor

class Throttler(object):
    def __init__(
            self,
            limit, cooldown, maximum_cooldown, key_threshold):
        '''
        limit: number of key usages allowed initially.
        cooldown: time in milliseconds before a used key can be
            re-used.
        maximum_cooldown: try_use_key is only allowed to give a
            false negative when all keys have been used within this
            amount of time in the past.
        key_threshold: try_use_key is only allowed to give a false
            negative when the true number of keys is less than this
            number.
        '''
        self.buckets = deque()
        self.cooldown = cooldown
        self.open_time = maximum_cooldown - cooldown
        buckets_a = divide_rounded_up(cooldown, self.open_time)
        buckets_b = divide_rounded_up(limit, key_threshold)
        self.num_buckets = buckets_a + buckets_b
        self.bucket_size = key_threshold
        self.free = limit
    def release_expired_buckets(self, now):
        while self.buckets:
            if self.buckets[0].has_cooled_down(now, self.cooldown):
                self.free += self.buckets.popleft().keycount
            else:
                return
    def try_use_key(self, now):
        '''
        Check if any keys are available. If so, use one and return
        True. Otherwise, return False.
        May return a false negative, but only if all keys were used
        within the last (maximum_cooldown) milliseconds, and if
        fewer than key_threshold keys are actually available.
        '''
        self.release_expired_buckets(now)
        if self.free == 0:
            return False
        should_create_bucket = (
            len(self.buckets) == 0 or
            not self.buckets[-1].will_accept(
                    self.bucket_size, now))
        if should_create_bucket:
            assert len(self.buckets) < self.num_buckets
            self.buckets.append(Bucket(now + self.open_time))
        self.buckets[-1].add(now)
        self.free -= 1
        return True

def now_ms():
    '''
    Return the current time in milliseconds.
    '''
    return int(time.time() * 1000)

class SlidingWindowMap(object):
    def __init__(self,
            keys, max_count, cooldown, maximum_cooldown,
            key_threshold, now_func=now_ms):
        '''
        keys: a sequence of key names.
        max_count: the maximum number of times any key can be used.
        cooldown: the time in milliseconds before a used key can be
            re-used.
        maximum_cooldown: try_use_key is only allowed to give a
            false negative when all keys have been used within this
            amount of time in the past.
        key_threshold: try_use_key is only allowed to give a false
            negative when the true number of keys is less than this
            number.
        now_func: a function that returns the current time in
            milliseconds.
        '''
        keylist = list(keys)
        num_keys = len(keylist) * max_count
        self.keys = itertools.cycle(list(keys))
        self.now_func = now_func
        self.throttle = Throttler(
                num_keys, cooldown,
                maximum_cooldown, key_threshold)
    def get_next_key(self):
        if self.throttle.try_use_key(self.now_func()):
            return self.keys.next()
        else:
            return None

Further questions

I've not given a proof of the formula for the maximum number of buckets required for solution AB. I actually thought it should be one less, but in practice this didn't seem to be true. I haven't quite figured out why.

For a fixed number of buckets, it's not clear when it would be better to be more strict about the time or the key thresholds. It might be interesting to see what percentage of full key utilization can be achieved with different levels of "burstiness" in key requests and different choices of threshold.

Objects in Javascript and Python

I've been doing some Javascript recently (well, Coffeescript actually, but this applies equally to either, so I'll stick to Javascript for the examples) and found its approach to objects rather interesting. I think it might be instructive to compare Javascript's objects to Python's, the dynamic programming language I'm most familiar with.

First of all, take this Javascript code, which creates a factory-function called "Counter" which returns objects with "increment" and "decrement" methods:

function Counter() {
    this.value = 0
}
Counter.prototype.increment = function() {
    this.value += 1;
}
Counter.prototype.decrement = function() {
    this.value -= 1;
}
c1 = new Counter()
c2 = new Counter()
c2.increment()

When we execute it, we end with a set of objects much like this:

In our outermost scope (the identity of which I'll gloss over for now) we have three names (or keys) defined. "Counter" is a function object, while "c1" and "c2" are both generic objects. "Counter", like all functions, has an object attached to it under the key "prototype", and it's in this prototype object that we've inserted the functions increment and decrement.

Each time we invoke "new Counter()" a new object is created with its special "__proto__" key mapped to Counter.prototype, and then the Counter function is executed with "this" bound to the new object. The Counter function adds to that object, mapping "value" to the number 0. (I must say, I still don't entirely understand why "new" works like this - I can't see any value in being able to invoke the same function both with and without "new".)

Finally we invoke "c2.increment()". First Javascript looks on the c2 object for the key "increment", but there is no such key. Next, it follows the "__proto__" key and tries again with the prototype object. There it finds the increment function. The function is executed with "this" bound to the "c2" object. When it does "this.value += 1" it first looks up "value" in the same way, finding it directly on the object itself, then after adding 1 to the value it stores it back on the object. (Note that storing something doesn't involve "__proto__" traversal. It always goes straight into the object that you put it into. It's only look-ups that involve "__proto__" traversal.)

Now, let's see the same thing in Python:

class Counter(object):
    def __init__(self):
        self.value = 0
    def increment(self):
        self.value += 1
    def decrement(self):
        self.value -= 1
c1 = Counter()
c2 = Counter()
c2.increment()

At a first glance, things look pretty similar. The "__class__" attributes on the objects are much like the special "__proto__" attributes in Javascript. The "__init__" method is quite similar to the "Counter" function in Javascript. The differences are subtle.

When Python executes the class statement, the three functions "__init__", "increment" and "decrement" are defined and attached to the newly created class object.

When "Counter()" is invoked a bunch of stuff goes on behind the scenes, but importantly a new object instance is created with "__class__" pointing to the class and then the "__init__" function is invoked with the object instance as its first argument.

When "c2.increment()" is executed, first "increment" is looked up on c2. This fails, so next Python follows "__class__" and checks for "increment" on the class. However, something special happens when it finds it there. When an attribute lookup for an object finds a function on its class object, it instead returns a "bound method", which is effectively a function that takes one fewer argument then passes through to the "increment" function itself, inserting a reference to the object as the first argument. So even though the statement "c2.increment()" provides no arguments, when "increment" is actually executed, it receives c2 as its first argument.

There are, I think, two interesting differences here. One is what happens when we want to represent inheritance, which my example doesn't really cover. In Javascript, if attribute lookup fails on the prototype then the prototype's prototype is searched, and so on. In Python, if the attribute lookup fails on the class, then instead of looking at its "__class__" attribute, the base classes are searched. (And since Python allows multiple inheritance, the corner cases are a bit tangled.)

But what I think is most interesting are the different approaches to how methods know their receiving object and the unintuitive consequences of these mechanisms. In Javascript, when a function is retrieved from an object and invoked on the same expression, it triggers the binding of "this" to the object in the function. But if you take a reference to the function and invoke it separately then "this" remains "undefined". For example:

c1.increment();

is not equivalent to this:

var f = c1.increment;
f();

The former will increment c1. The latter will do nothing because increment executes with this undefined.

In Python, on the other hand, the equivalent will work as you might expect, because "c1.increment" in fact refers to a bound method. However, from this we can see that in Python "Counter.increment" is not the same entity as "c1.increment". "Counter.increment" is a function that takes one argument. "c1.increment" is a bound method that takes no arguments. In contrast, in Javascript, "Counter.prototype.increment" refers to the exact same object as "c1.increment". So Python does the magic during object attribute lookup, while Javascript does the magic when invoking an attribute as a function.

I think this is all correct, but do let me know if I've made a mistake. I'm finding Javascript a lot more pleasant than I expected, except for its cheerful silent propagation of "undefined" at every opportunity, and Coffeescript definitely rounds off some of the rough corners. In fact, I'd say I even slightly prefer Coffeescript's class notation to Python's.

I'm curious to know if there are any particular benefits of prototype-based objects. I can't see any clear advantages over class-based objects, and I particularly don't understand the benefit of being able to use any function to create an object. Is it just nice because it results in a smaller language? (Does it result in a smaller language?)

As if by magic, some maths appeared

I've not really done any programming lately, so this week there's no Minecraft. Instead there's some maths. Hurrah! Hey, where are you—

I was reading Richard Wiseman's Friday puzzle. It's very short and not at all hard, so you might want to go and solve it and come back. Go on, I'll wait.

Okay, you're back? I'll try not to state the answer outright, but it will probably become pretty obvious very quickly. Right, so this got me thinking about sums of series. The case in the question is sufficiently small that you don't even need to work out the formula for the sum of sequence in question, but I was thinking about it nonetheless.

Now, I knew the formula for the sum of an arithmetic sequence, and I knew that you could easily enough prove it by induction, but this is a very unsatisfying form of proof. It doesn't feel like something you could have figured out on your own. Imagine just picking random equations one at a time and testing them until you find one that you can prove correct with induction! I thought about it a little and came up with what I thought was a pretty compelling geometric proof, at least for the simple case where you start at 1 and increment by 1. (I have no idea if a proper mathematician would call this a proof. I am certainly not a proper mathematician.)

Is it obvious? On the left in the green we have a square with area 1, a rectangle with area 2, a rectangle with area 3, etc. The area of the whole shape must be the sum of those areas. By dividing up the space differently, we can easily see how to produce the closed form.

Great, I thought. Now lets do the same for the sum of squares. It must be just as obvious in 3D. Right?

Hmmm. Well, it gives the right answer, and it's satisfying to figure it out by hand, but it lacks the obviousness of the diagram for the arithmetic sequence sum. Perhaps there's a simpler way to do it?

As an aside, I think I'm getting the hang of Inkscape, although there are still some areas I find I much prefer Visio. Inkscape has some pretty painful and inflexible handling of arrowheads, for example. They're always black, regardless of the line colour, and then there's a special menu action just to make them change to match the line colour. The selection of arrowheads available is limited and weird, and most of them aren't resizable. I'm not sure if that's because SVG forces arrowheads to behave in strange and unintuitive ways, or that's just the way that Inkscape chooses to work.

Maybe next week there will be more programming. We shall see.

Minecraft mapping - Rotation and flipping

Last time, I discussed ambient occlusion for adding depth to the map. Today I'm going to explain how the fragment shader rotates and flips oriented blocks like minecart tracks.

As you may have noticed, there's only one block ID for regular minecart tracks. The 4-bit data value encodes the orientation of the track, from 10 possibilities - 2 orientations of straight track, 4 orientations of corner track, and 4 orientations of sloped track.

A minecraft texture pack includes only two textures for normal minecart tracks: one curved and one straight. We need to use these to make up all the other orientations. We could either do that in advance - building up a bigger texture atlas with all the orientations we need, or we can do it in the shader. By doing it in the shader we avoid the need for a much expanded texture atlas and some fiddly work to assemble textures, at the cost of extra work in the shader.

To let the shader know what orientation to use, we encode it in the blue channel of our map data texture. We use 2 bits to encode a rotation (0°, 90°, 180° 270°) and 1 bit to encode a possible flip. (I don't think we actually use the flip at the moment, but it might be useful for doors.)

The shader code isn't actually terribly exciting. I should however point out that this version treats the map texture as having normalized float values, rather than integers. For most of the earlier posts I had been updating the code to use integer textures to simplify things a bit, but I haven't gotten around to doing that with this code. That's why we multiply the sample values by 255.0 – as normalized floats they've already been rescaled from 0 to 255 to the range 0.0 to 1.0.

    float flipx = (tiles_sample.b * 255.0) >= 8.0 ? -1.0 : 1.0;
    float rotation = mod(
        tiles_sample.b * 255.0, 8.0) *
        0.5 * 3.141592653589793;
    mat2 transform = mat2(
        flipx * cos(rotation),  flipx * sin(rotation),
        -sin(rotation),         cos(rotation));

We form a rotation matrix with the rotation value of 0, 0.5π, π or 1.5π. The sines and cosines just work out as -1, 0 or +1. There's probably a cheaper way to calculate them.

This will rotate around the origin. Before we transform our texture coordinate we rescale it to the range -1..1, then adjust it back afterwards.

Some mention should be given to how we obtain the rotation values in the first place. There's no trick – there's just a great big table mapping block id and data values to texture coordinates and orientations. The same table is used to pick coloured wool values.

And here's the end result. I think I've talked about most of the things I had originally set out to cover. Next week I might touch on light levels, but there's not a lot to say there. If I find the time I'd like to do some work on cave rendering, but I'm not sure I'll both find the time to work on it and write a blog post, so next week's post may be quite short.