On the (Ab)Use of Tarstuff (By Martin Jacobsen).

The dangers of tarstuff are well known. In rooms containing mothers, you must often be careful to avoid being overwhelmed by the growth. But what about blobs of tarstuff lying around without any mothers? What puzzles can they be used for, and how do you handle such puzzles?

This article is intended to explain two questions related to this: When can a blob of tar be removed completely, and how many babies can you get from a single blob?

Stability

Before getting started on the actual removal of tarstuff, it's interesting to know what shapes it can form. It turns out that the rule for this is the same for both tar and mud, and it's quite simple: every square of tarstuff must be part of a 2x2 blob. This leads to an alternative way of describing any blob of tarstuff.

Consider the point right between four squares in DROD. I'll call such a point a corner. If the corner is completely surrounded by tarstuff (that is, all the four squares next to it contain tarstuff of the same kind), I'll call it an enclosed corner. Since every square of tarstuff is next to an enclosed corner, you can describe a blob completely by stating which corners it encloses.

Note that if there is no tarstuff in a room, the room contains no enclosed corners. Also, because of the stability rules, there will be no tarstuff in a room containing no enclosed corners.

Treatment of Tar

Consider the question: When can a blob of tar be removed completely? In order to figure this out, it's necessary to figure out what happens when you cut into the blob. So suppose that a square of tar (call it X) is cuttable. This means that it is an edge square. Suppose further that the edge is on the south side of the square. This implies that the square just S of X does not contain tar. Further, the squares just W, NW, N, NE, and E of X must contain tar. The squares SW and SE of X may or may not contain tar.

In total, this means that the SW and the SE corners of X will not be enclosed by tar, but the NW and NE corners will be. More importantly, if Beethro cuts square X, the NW and NE corners will no longer be enclosed, but no other corners will be affected by the cutting. (If they are enclosed, they will stay that way.) In other words, the number of enclosed corners in the blob is decreased by 2. Similar things happens if the edge of square X is on the west, north or east side.

The above can be summarised as: Whenever Beethro cuts a square of tar, the number of enclosed corners is decreased by 2. This implies that the parity of the number of enclosed corners is invariant. (For those unfamiliar with the terms: "Parity" means whether a number is even or odd. "Is invariant" is a fancy way of saying "does not change") Since a room with no tar has no enclosed corners, a tar blob containing an odd number of enclosed corners cannot be removed! This is the reason that rectangular tar blobs with sides of even length cannot be removed; they contain an odd number of enclosed corners.

Now consider what happens when you checkerboard-color the corners. This means that every corner is assigned one of two colors (I'll just use black and white) in such a way that any two adjacent corners have different colors. (It's just the same as the way the floor squares in any DROD room is colored.) As was observed above, every time Beethro cuts tar, two corners enclosed by tar will no longer be enclosed. Now observe that the two corners must be adjacent, meaning that they will have different colors. So every time Beethro cuts tar, one black and one white corner will no longer be enclosed. This implies that the number of enclosed white corners minus the number of enclosed black corners is invariant! This number can be called the value of a tar blob. It should be noted that the number of corners enclosed by a tar blob can be reduced no further than its value (or minus its value, if the value is negative).

As an example of what this is good for, take a look at the room below. The distribution of trapdoors is the same on the two platforms, so all you need to do is to remove enough of the tar to uncover all of them. Coloring the enclosed corners tells you that the tar blob has a value of four, so you'll need to leave (at least) four white corners enclosed. On the other platform, I've marked those corners which can be left enclosed without covering any trapdoors. Note that although there are ten such corners, only four of them are white. These are the four corners that should be left enclosed on the other platform. Any other distribution of tar will make some trapdoors unreachable.

Creating Babies from Tar

This approach also makes it possible to calculate how many tar babies you can create from a given tar blob. After cutting a tar blob down to the smallest possible size, one of three things will have happened to every square of tar: (1) it has been stabbed as part of the cutting process, (2) it has become a tar baby, or (3) it has been become impossible to remove and is therefore still part of a tar blob. Hence, you can figure out how many babies will be formed by taking the number of squares covered by tar at first, and subtracting the number of squares covered afterwards and the number of times you have to cut the blob. In general, these numbers are somewhat difficult to calculate, but in the case of a rectangular tar blob, the calculations are more manageable.

Consider a rectangular tar blob of size m by n squares. The total number of squares covered is obviously mn. The number of enclosed corners in the blob is (m-1)(n-1). Because of the checkerboard pattern, the tar blob has a value of one (or minus one) if both m and n are even, and zero otherwise. Hence, the number of stabs neccesary is ((m-1)(n-1)-1)/2 if m and n are even, and ((m-1)(n-1))/2 otherwise. Finally, if m and n are even, you'll have to leave a 2x2 blob behind, hence leaving 4 squares covered, but in all other cases the blob can be removed completely. Putting this together gives these formulas for the number of tar babies:
mn - ((m-1)(n-1)-1)/2 - 4 (m and n both even)
mn - ((m-1)(n-1))/2 (otherwise)

These formulas can be simplified, and a bit of algebraic manipulation yields this simpler version:
((m+1)(n+1)-9)/2 (m and n both even)
((m+1)(n+1)-2)/2 (otherwise)

Manipulation of Mud

With mud, the situation is somewhat simpler. Unlike tar, mud has no stable forms, since all blobs contain at least one corner. "Hence, the only way to make a blob of mud impossible to remove is to use walls or pits to prevent Beethro from reaching any of the blob's corners. For now, I'll ignore this possibility." An analysis much like the one made for tar will show that every time you cut into a mud blob, you'll remove exactly one enclosed corner. So the number of cuts necessary to remove a mud blob is equal to the number of enclosed corners.

This makes it simple to determine the number of mud babies that can be made from a general mud blob. As with tar, the number can be found by taking the number of squares covered by mud, and subtracting the number of squares covered afterwards and the number of times you have to cut the blob. However, since the blob can be removed completely, the second term is equal to zero and can be removed. Hence, you just take the number of squares covered and subtract the number of enclosed corners.

To further simplify this, you might count the enclosed corners in an unusual way. Instead of counting the actual corners, count the squares just southeast of the corners. This way, you have to count all squares whose northwest corner is enclosed. So the formula becomes the number of mud squares minus the number of mud squares whose northeast corner is enclosed. Or, in other words, simply the number of mud squares whose northeast corner isn't enclosed. The image below shows some examples. In each blob, the counting the opaque squares will tell you how many mud babies the blob can produce.

Exceptions

Throughout the above analysis, I've assumed that cutting tarstuff with Beethro's sword is the only way of changing its shape. What happens when this is not the case?

The most obvious exception is the presence of mothers. In this case, the entire analysis breaks down. With a mother in the room, you can generally produce any number of babies. In addition, expansion of tar doesn't respect the invariant mentioned above, so it will often be possible to clear a room of tar if it contains a tar mother.

Mimics are another important exception. They can make it possible to remove an otherwise unremovable tar blob. If Beethro and a mimic (or two mimics, for that matter) cut two squares of tar that share a corner, the cutting will remove 3 enclosed corners, thus changing the parity of the blob. Further, the corners removed will be either 2 white and 1 black, or 1 white and 2 black, thus changing the value as well. Therefore, neither the parity nor the value of a tar blob are invariant if a mimic is employed carefully. This is why it can be necessary to use a mimic in order to remove a tar blob.

Finally, bombs cause an exception. A well-placed bomb can increase the number of babies that can be generated from a mud blob, and it may change the value of a tar blob.

Guidance of Gel

Version 3.0 of DROD added one new kind of tarstuff, the Forbidden Gel, and the tarstuff switchers. I'll discuss gel first.

The Forbidden Gel has the same stability rules as the two other kinds of tarstuff, so the "enclosed corner" analysis can still be used. However, the stabbing rules are new: gel can only be stabbed at inside corners. This gives rise to two basic removal possibilities, shown below.

The first shape is by far the most common when dealing with a large area of gel, whereas the second one crops up near thin areas of the gel. Neither of these shapes are particularly easy to deal with, so determining whether a blob of gel can be removed is difficult by this method. However, there is another analysis that can provide some insight. Instead of looking at the enclosed corners, I'll look at the cuttable squares. I'll also need to use the usual checkerboard coloring, which divide the squares into "light" and "dark" squares.

Cutting a single square of gel can create up to three new cuttable squares, as shown below.

Note that the newly cuttable squares have the same color as the square that was just cut. This implies that if you have a blob of gel where all cuttable squares have the same color, then you will only ever be able to cut squares of that color in the blob. This has some interesting implications. Take a look at the enclosed corner below.

To remove it, you have to cut one of the four squares surrounding it. However, one is a corner square and two are edge squares, so they can never become cuttable. That leaves only one square. In this picture, it is a light square, meaning that in order to remove this enclosed corner, you must be able to cut a light square. If you cannot do this, the corner will remain enclosed, and the four squares around it will remain as stable gel.

Combining these two results can give you a lot of information. For example, in the room shown below, no amount of cutting will ever uncover any of the twenty pressure plates.

A few other results can also be derived. An example is shown in the room below.

To uncover the pressure plate in the northeast corner, you must cut a light square. Initially, the only cuttable light square is in the southwest corner, so you must start in this corner and carve a path across the blob to the northeast corner. Similarly, to uncover the southeast plate, you must start in the northwest corner and carve a path across. However, these two paths cannot cross each other. This means that you can uncover either pressure plate, but not both.

Double-stabbing is not particularly interesting in the case of gel. It allows you to cut two adjacent squares, which can be necessary in some situations, but it doesn't change the above results in any way.

Finally, a word on the creation of gel babies. The picture below shows two apparently cuttable blobs of gel.

However, attacking either blob is fatal. The only way to cut the gel is from the central square, from which it is difficult to move away. Cutting the northeastern blob leads to the creation of gel babies to the east and north, making it necessary to retreat in order to survive. However, the other blob blocks the retreat, making it impossible to escape. So even though the blobs appear cuttable, you still need assistance (such as a mimic, a speed potion, or a clone) in order to deal with them. This situation can also crop up when dealing with a single blob of gel, such as in the picture below, where it is impossible to cut northeast or southwest from the square Beethro stands on.

Tarstuff switchers

There's not too much to say about the switchers. Obviously, having access to a switcher can only make it easier to deal with a blob of tarstuff. In particular, if you can turn the blob into mud, you can remove it. If you're only able to switch between tar and gel, the blob may not be removable, but a fairly large blob probably will be. For this reason, switchers are most interesting when the blob is largely surrounded by walls, a situation I won't try to analyze here.

One interesting aspect of switchers is the way they interact with double-stabbing. Double-stabbing is allowed even if you hit a switcher in between the two stabs. The basic situation is shown in the pictures below. The eastern mimic moves first.