Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

File: Invariants Demo.hold (1 KB)
Downloaded 185 times.
License: Other
From: Unspecified

One thing that I'm sure you will all know, is that some tar blobs cannot be removed entirely, but always leave something behind. The simplest example is of course the 2x2 tar blob, which is uncuttable, but there are other examples. One such example is any rectangular tar blob with an even number of squares along both sides. Such a blob can be reduced no further than to a 2x2 blob.

This post is intended to explain why this happens, and to provide a more general method for determining whether a tar blob can be removed entirely.

Attached is a one room hold, which I designed by using the ideas explained here. It's provided as an example of what you can use this for.

Now, I'll only consider what happens when Beethro cuts tar. In other words, I'll be looking only at tar blobs in rooms without tar mothers. Tar babies will also be ignored; if any tar babies are formed during cutting, the relevant squares of tar are simply considered to have disappeared. Also, I'll ignore the possibility of "double-stabbing" by Beethro and a mimic for now. Finally, it's possible to cut a tar blob into two separate blobs; in this case, the two new blobs will be considered part of the same blob.

Now consider the point right between four squares in DROD. I'll call such a point a corner. A corner is considered to be enclosed by tar if all the four squares next to it contain tar. Note that if there is no tar in a room, the room contains 0 enclosed corners. Also, since all tar squares must be adjacent to at least on enclosed corner (this is just a different way of stating the tar baby formation rules), there will be no tar in a room containing 0 enclosed corners.

Now 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 any case, all 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. Even more important, if Beethro cuts square X, the NW and NE corners will no longer be enclosed. Further, 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 0 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, 2 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).

Now, about mimics. In most cases, it doesn't matter that Beethro and a mimic cut tar simultaneously. However, if Beethro and the 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. 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.

Yeah, this was rather long, but I hope that some of you can use it for something.

____________________________
Today the refrigerator, tomorrow the world!

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

I have one question: Since Beethro moves, and then the mimic moves, how could they both cut tar in the way you suggest at the same time? Once Beethro has affected the tar, it's already been changed, and then the Mimic will interact with it as if it were Beethro on a second move.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Schik
Level: Legendary Smitemaster

Rank Points: 5454
Registered: 02-04-2003
IP: Logged

This is handled as a special case in the code, just to allow simultaneous stabbing.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Cool, you learn something new every day. Thanks for the new knowledge.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

TripleM
Level: Smitemaster
Rank Points: 1379
Registered: 02-05-2003
IP: Logged

Woah, thats brilliant work.. I think that may really help me with a couple of rooms in Ricky's Dungeon

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Yeah, this is an amazing breakthrough! It'll come in really helpful when (if) we get Black Gates!

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

TripleM
Level: Smitemaster
Rank Points: 1379
Registered: 02-05-2003
IP: Logged

Any chance you can post the logic of working out your example room? That might make it a bit clearer how you're meant to exactly solve a room like that.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

File: Demo Explanation.JPG (28.4 KB)
Downloaded 333 times.
License: Other
From: Unspecified

TripleM wrote:
Any chance you can post the logic of working out your example room? That might make it a bit clearer how you're meant to exactly solve a room like that.

Sure thing. Take a look at the attached picture, which shows part of the room. All the corners enclosed by the tar blob have been marked with dots. If you count them, you'll find that the blob has a value of 4, meaning that there are 4 extra white corners. Therefore, whatever you do, there must be 4 enclosed white corners left on the platform. Obviously, these corners cannot be adjacent to a trapdoor square, since the 2x2 tar blob would block off this square. On the other platform, I've marked the 4 white corners that are not adjacent to any trapdoor square. You need to leave 2x2 tar blobs around those corners, and no others. I've also marked off the 6 black corners that are not adjacent to any trapdoor square. These are red herrings, as leaving a 2x2 tar blob around them will force you to keep an extra white corner enclosed.

____________________________
Today the refrigerator, tomorrow the world!

masonjason
Level: Smiter

Rank Points: 349
Registered: 12-29-2003
IP: Logged

This approach can also be used to solve a little problem I've been wondering about for a while: that is, how many tar babies can be made from an m * n rectangle of tar?
The number of tar babies made is obviously
a - b - c,
where a = area of the rectangle = mn,
b = number of cuts you need to make,
c = area of any uncuttable tar left over at the end.
In a rectangle of dimensions m * n, there are (m - 1)(n - 1) enclosed corners. Every time you make a cut in the tar, exactly two enclosed corners are freed, but tar is only converted completely into tar babies when there are no enclosed corners left. Thus, the number of cuts you need to make is equal to half the number of enclosed corners, i.e. b = (1/2)(m - 1)(n - 1). This is an integer as long as not both of m and n are even. I will consider the case where m and n are both even shortly. There will be no uncuttable tar left, so c = 0 and a - b - c = mn - (1/2)(m - 1)(n - 1).
However, if m and n are both even, then the number of enclosed corners is odd and there will be one enclosed corner that cannot be cut. In other words, the number of cuts that can be made is b = (1/2)((m - 1)(n - 1) - 1). Also, there will be 4 uncuttable tar squares left, so c = 4. So in this case, the number of tar babies = a - b - c = mn - (1/2)((m - 1)(n - 1) - 1) - 4.
In summary, the number of tar babies that can be created from a rectangle of tar of dimensions m * n is
mn - (1/2)((m - 1)(n - 1) - 1) - 4 (m and n both even)
mn - (1/2)(m - 1)(n - 1) (otherwise).




____________________________
Eighty people came to the bazaar.

Drizzo
Level: Master Delver

Rank Points: 179
Registered: 03-03-2004
IP: Logged

Interesting... I wonder how easy it would be to figure out how many you can keep alive as you carve this block of tar up... an interesting puzzle where you need to make ALL the tar babies possible from a block of tar survive, in order to kill a snake or something... hmmm... Although I guess with the proper room features they all could live, but I'm picturing a room where Beethro has to be constantly one step ahead of these tar babies as he carefully eliminates this tar block, as opposed to one where he can just put them in storage somewhere...

____________________________
"Disbelief in magic can force a poor soul into believing in government
and business." - Tom Robbins

swann_88
Level: Delver

Rank Points: 87
Registered: 06-29-2003
IP: Logged

maybe I am missing something
does this cover the case where beethro stabs the middle of a row of 3? xyx y is stabbed both x become tarbabies

masonjason
Level: Smiter

Rank Points: 349
Registered: 12-29-2003
IP: Logged

swann_88 wrote:
maybe I am missing something
does this cover the case where beethro stabs the middle of a row of 3? xyx y is stabbed both x become tarbabies

Yes, it does, but a row of 3 tar squares cannot exist on its own. Apply the formula to a 3 * 1 rectangle and you get
3 * 1 - 1/2(2 * 0) = 3
and 3 tar babies is what a 3 * 1 rectangle of tar basically is.

____________________________
Eighty people came to the bazaar.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Very nice work, masonjason. Just one quick comment:

masonjason wrote:
In summary, the number of tar babies that can be created from a rectangle of tar of dimensions m * n is
mn - (1/2)((m - 1)(n - 1) - 1) - 4 (m and n both even)
mn - (1/2)(m - 1)(n - 1) (otherwise).

These two formulas can be simplified to
((m + 1)(n + 1) - 9)/2 (m and n both even)
((m + 1)(n + 1) - 2)/2 (otherwise)

____________________________
Today the refrigerator, tomorrow the world!

masonjason
Level: Smiter

Rank Points: 349
Registered: 12-29-2003
IP: Logged

Cool, I didn't bother to check whether they could be simplified. Thanks.

____________________________
Eighty people came to the bazaar.

silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged

bit of a thread necromancy here, but:

I find sometimes with big chunks of randomly shaped tar, it's hard to compute the parity. so I wrote the little script I've attached. it's perl, so it should run for linux and mac osX people for free, and windows people if they have cygwin or ActiveState perl or similar.

edit: removed attachment, see my next reply.

(only secreted because it's long):



____________________________

---

[Last edited by silver at 09-16-2006 07:05 AM]

Tahnan
Level: Smitemaster

Rank Points: 2460
Registered: 11-14-2005
IP: Logged

Wow. And to think I just go into the editor, select a test hold of my own, and recreate the tar there. :-)

silver
Level: Smitemaster
Rank Points: 915
Registered: 01-18-2005
IP: Logged

File: tar_check.pl (7.5 KB)
Downloaded 64 times.
License: Public Domain

this is a more full-featured version. it detects tar clusters and removes impossible tar, and it computes the 'tar number' as it relates to solubility.

my computation of "tar number" is probably a little off from the description above, as I just sum the coordinates and call evens "white" and odds "black", and always do white-black as number. which means a blob with a tar number of 2 will have a tar number of -2 if you shift it left or right. but other than white/black being fixed outside of the tar, it's pretty much the same thing. Especially in that for this program, my only real concern is that the tar number is 0 - due to the demonstration in the first post that every tar cut removes one white and one black.

(only secreted because it's long):



____________________________

---

[Last edited by silver at 09-16-2006 09:38 PM]

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

Basically to figure out if a tar blob is cuttable or not is the same as deciding if an "blob" of unit squares may be tiled with 1x2 dominoes.

There is a very interesting application of homotopy theory and combinatorial group theory.
It is easy to decide if a simply connected region consisting of unit squares in Z^2 is cuttable (may be tiled with dominoes) or not:

Link

Caution: Don't read unless you are a mathematician.

adS

Edit: Of course, the set of enclosed corners must be tileable by dominoes.

____________________________
pauca sed matura

---

[Last edited by adS at 05-14-2014 10:37 PM]

Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged

adS wrote:
Link
Caution: Don't read unless you are a mathematician.

As a homotopical group theorist, I thank you highly for posting that link.
I now find myself thinking about domino-tiling/tar-cutting when I should be preparing a talk for next week.

____________________________
95th Skywatcher

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

You should also have a look at this.

adS

____________________________
pauca sed matura

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

adS wrote:
There is a very interesting application of homotopy theory and combinatorial group theory.
It is easy to decide if a simply connected region consisting of unit squares in Z^2 is cuttable (may be tiled with dominoes) or not:

Link

Hm, interesting. So the approach here is to regard the underlying grid as the Cayley graph of a group, which you can then write as F/R where F is a free group and R is a subgroup generated by some relations. Then a path along the edges in the grid can be regarded as an element of F, and it is a loop if and only if it is contained in R. In the case of a square grid, F is generated by two elements a and b, and R is generated by the element aba^(-1)b^(-1) and all its conjugates.

Given a set of tiles, you can then define a subgroup T of R by letting T be generated by the boundaries of your tiles (and their conjugates in F). Then for any region that can actually be tiled by your set, its boundary must lie in T. In the case of dominoes, you have two essentially different generators in T: a^2ba^(-2)b^(-1) for the horizontal dominoes, and ab^2a^(-1)b^(-2) for the vertical ones. I fiddled with the groups for a bit, and found that R/T is then an infinite cyclic group, generated by the element aba^(-1)b^(-1). So we can think of it as the group of integers, Z. With a bit more work, I found out that for any closed bounded region in the plane, the image of its boundary in R/T is actually the difference between the number of white squares and the number of black squares in the region. So that gets you back the value invariant I described in the first post.

I'm rather intrigued by the algorithm for constructing a domino tiling, provided that one exists. In effect, it seems to iteratively pick out spots where you can put down a domino, but I don't really understand why it can't lead you into a dead end.

____________________________
Today the refrigerator, tomorrow the world!

TripleM
Level: Smitemaster
Rank Points: 1379
Registered: 02-05-2003
IP: Logged

I don't have access to that article, but a maximum-bipartite-matching approach is one method of construction.

Namely, start from any unmatched square and perform any depth/breadth first search. Move to any adjacent square; if already part of a domino, move to other half of the domino. When you reach another unmatched square (and you will always be able to, given it is tileable), the whole path you've travelled along can be tiled with dominoes, replacing any already there. You've now added one more domino. Repeat.

Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged

I believe I have convinced myself:
First of all, Thurston's method only works for simply-connected/contracible regions, i.e. regions without interior "holes".

If we have a region R that we try to tile, then we make a directed graph on the edges in R where the edges around a black square is oriented counter-clockwise and the edges around white squares are oriented clockwise.
For the vertices v and w of the graph, we then have a distance function d(v,w) measuring the distance from v to w following the direction of the oriented edges.
The goal of Thurston's algorithm is then to construct a height function on all vertices/corners in R such that h(w) - h(v) <= d(v,w) for all vertex pairs v and w. (Note: The inequality sign in Thurston's paper is wrong at this spot.)

The height function is fixed (up to a constant) on the boundary of R by the requirement that it can only increase or decrease by 1 at each step. This corresponds to the fact that each edge on the boundary has to be a boundary edge of a domino. That the total change of height around the boundary is zero, is equivalent to the number of white and black squares being equal, as Watcher pointed out.
The additional claim is that the requirement h(w) - h(v) <= d(v,w) for v,w on the boundary is equivalent to the existence of a domino-tiling of R. The inequality has to be true if there is a domino-tiling of R.
Thurston then extends the function h to the interior vertices of R step by step along the oriented edges. If ever the height increases by more than 1 along an edge, the inequality h(w) - h(v) <= d(v,w) fails, and by tracing a path back to the boundary of R, the inequality must have failed already for the boundary vertices! (This is the critical point of why the algorithm doesn't break down.)

Once h has been extended to all vertices of R, it must satisfy h(w) - h(v) <= d(v,w) for all v,w in R, since otherwise the algorithm would have found an edge with an increase of more than 1. (Not entirely obvious but true.)
Applied to each square of R, h(w) - h(v) <= d(v,w) implies that each oriented edge either changes h by 1 or -3. Furthermore, each square has exactly 1 edge where the change is -3. Hence if we then delete the edges with -3, we have a tiling of R with dominoes.

The secret lies in the inequality h(w) - h(v) <= d(v,w) (which Thurston sadly wrote with >= instead of <=).

____________________________
95th Skywatcher

---

[Last edited by Kargaros at 05-17-2014 12:14 AM]

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

Regarding the non-simply connected case see here.

adS

____________________________
pauca sed matura

coppro
Level: Smitemaster
Rank Points: 1309
Registered: 11-24-2005
IP: Logged

But the real question is: can we analyze gel?

adS
Level: Master Delver

Rank Points: 214
Registered: 05-02-2010
IP: Logged

coppro wrote:
But the real question is: can we analyze gel?

Well, somebody would have to analyze the tilings with

  X          X
  XX   and  X

adS

____________________________
pauca sed matura

Pinnacle
Level: Smitemaster

Rank Points: 1137
Registered: 06-10-2004
IP: Logged

Does gel actually reduce to L-tromino tiling on the enclosed corners? From a bit of experimentation, it looks like it does, and we know that Golomb's proof applies to gel. The most basic cuttable tar shape fits a single domino, and the most basic cuttable gel shape fits a single L-tromino.

____________________________
Once (adv.): Enough.
Twice (adv.): Once too often.
~Ambrose Bierce, The Devil's Dictionary

The spitemaster
Level: Smiter
Rank Points: 354
Registered: 06-09-2005
IP: Logged

The problem is that the shape of gel is non-trivial. For instance:

__XXX
__XXX
XXXXX
XXXXX
XXXXX

While this shape can be completely destroyed, it is impossible to cut without outside assistance.

____________________________
Last night upon a stair
I met a man that wasn't there
He wasn't there again today
I wish that man would stay away

---

[Last edited by The spitemaster at 05-17-2014 05:00 PM]

tempestadept
Level: Master Delver
Rank Points: 150
Registered: 12-23-2010
IP: Logged

Pinnacle wrote:
Does gel actually reduce to L-tromino tiling on the enclosed corners? From a bit of experimentation, it looks like it does, and we know that Golomb's proof applies to gel. The most basic cuttable tar shape fits a single domino, and the most basic cuttable gel shape fits a single L-tromino.

Tiling itself tells nothing about reachability of cutting points. E.g. 2x3 rectangle is a union of two L-triominoes, but that doesn't correspond to a cutting sequence.

Kargaros
Level: Delver
Rank Points: 58
Registered: 04-06-2010
IP: Logged

Asking whether a Gel blob is removable, is more than just a tiling problem for L-shapes -- even when ignoring the Gel babies that form.

The following Gel blob

XXXX
XXXX
XXXX

has enclosed corners forming the shape

XXX
XXX

This shape can be tiled by two L's, but the original blob cannot be cut at all. The problem is that each L-shape is only cuttable at the interior corner, and in the given configuration the interior corner for each L is unreachable.

Tar does not have the same problem, because the domino shape is cuttable from both sides. Hence we are always able to cut at least one exterior domino.

Edit: Ahh, beat to it

____________________________
95th Skywatcher

---

[Last edited by Kargaros at 05-17-2014 05:28 PM]