JtRH: Tar and Parity

A couple of levels on, and I’m once again finding myself spending a lot of my time clearing tar, not just because of those tar gates, but because clearing a room completely of tar has become a fairly common subject for Challenge scrolls. The mechanics of it are seeping into my dreaming mind, occupying my idle thoughts. Let me get some of this out in words.

Tar lies in multi-square puddles, which you can cut with your sword along any edge, except at the corners, which are vulnerable only to explosions — which is to say, invulnerable in rooms without bombs, which is most rooms. To remain stable, the puddles have to have a width of at least 2 in all places, both north-south and east-west; any square of tar that lacks a neighbor in either dimension will break off and start chasing you. Thus, the smallest stable configuration of tar is a simple 2×2 square. Since this puts all four tiles at a corner, such a square cannot be cleared. It’s the basic kernel of most unclearable tar shapes: if you can clear everything except a 2×2 square, you were doomed from the start. There are other invulnerable shapes, but they basically amount to multiple 2×2 squares stuck together by shared corners.

The basic clearable tar shape, on the other hand, is the 2×3 rectangle. Poke that in one of its vulnerable longer sides, and the remaining five squares break into monsters. This can be generalized. Given a 2xn strip, the only things you can do are cut off two rows at one end, or remove one row in the middle and split it into two pieces. If n is odd, you can cut off two rows repeatedly until it’s 2×3. If n is even, then it will still be even if you cut off two rows, and splitting it in the middle will always create one strip with an odd length and one with an even length; thus, you’re always going to wind up cutting it down to a 2×2 square at the end. So strips of this sort are solvable if their length is odd and unsolvable if their length is even. Many rooms have a checkerboard pattern on the floor, allowing you to tell odd from even at a glance.

Similar logic, which I’ll leave as an exercise for the reader, shows that a rectangle is solvable if and only if it has at least one odd side. It’s basically a matter of parity, an odd-or-even property that you can’t change with your sword, except with “odd” and “even” confusingly swapped: an odd length represents even parity and vice versa. That is, by assigning “even” to odd lengths, an nxm rectangle has even parity if either n or m has even parity, just as the product of two integers is even if either of them is even. It works out this way because of how splitting a rectangle into two pieces requires removing a row. When you split a rectangle in two, the pieces will have similar parity if the original had even parity, and opposite parity if the original was odd.

At any rate, all rectangles with even parity are solvable, but things get more complicated when we move beyond rectangles. You can have lumpy shapes with corners in inconvenient places that keep you from making the cuts you want. If you can reduce a shape to two separate 2×2 squares, it had even parity, but might still have been unsolvable. Odd parity is always unsolvable, though, no matter the shape. Assuming that Challenges are never completely impossible, it’s therefore safe to assume that the parity of any completely inert tar pool you’re supposed to clear will be even. But if there’s a Tar Mother in the room, making the tar expand at regular intervals, it’s possible for the parity to change. Thus, when you kill the Mother, it’s imperative to make sure that the remaining tar has the right parity if you intend to clear it all. I have no better way to do this for wiggly shapes than to attempt to clear it and see if it I wind up with a 2×2 square left over. But if I do, at least I know better than to keep trying from the same point.

2 Comments so far

  1. Jacob on 21 May 2017

    Have you seen the analysis here?

  2. Carl Muckenhoupt on 21 May 2017

    I had not! This is good; this takes it a few steps farther than I had gotten. In particular, much is explained by the realization that the parity isn’t on tar-filled tiles but on interior corners. Also, the checkerboard-coloring idea explains why parity isn’t everything and sometimes the best you can do with even parity is reduce it to two separate 2×2 squares or whatever.

Leave a reply