calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

OK, something I've been thinking about. And I've come up with a question. Take the following assumptions.

You have a DROD room with a single entrance. (it can be more than 1 square wide if needed)
There are no secret rooms attached, the room has a single way in or out - nothing else
No NPCs or scripted characters are allowed to be present.
Exception: You may have Halph and/or the 39th Slayer present, but no special scripts.

Thus... what room configuration would give rise to the longest possible DROD room? As in the room which cannot be solved in less than N moves, where N is the maximum possible. What elements would be useful in making the room longer than any other?

My current hypothesis is that the longest possible room would involve a stupidly long chain of doors and orbs, in such a way that it's mechanically identical to a Tower of Hanoi and having to shift it back and forth multiple times - each time extracting a single monster from inside it. If you could get say... 30 doors in the configuration, and you have to make at least 5 moves to make a move... you're looking at a *minimum* of 5368709120 moves to unlock the structure already, to say nothing of doing it multiple times.

Discuss. Go

EDIT: I know that DROD (without scripted characters) is a Turing-complete system, but that's only for an infinitely large room. It's not possible to make a room that requires infinitely many moves to solve - there is an absolute limit.

____________________________
My Holds

---

[Last edited by calamarain at 06-22-2007 08:39 PM]

jbluestein
Level: Smitemaster

Rank Points: 1670
Registered: 12-23-2005
IP: Logged

I believe that there was a contest about this at one point. It gave rise to such rooms as Caverns of Animus: The Long Ascent: 2N2E. Of course, if you're trying to be gratuitously long, you could just reverse the force arrows on that room and change the algorithm to be more complex. Right now each door just opens the next door in line.

(The best demo for this room as it currently stands is about 66K moves, and it's only the second-longest #1 demo out there.)

Josh

____________________________
"Rings and knots of joy and grief, all interlaced and locking." --William Buck

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

jbluestein wrote:
I believe that there was a contest about this at one point. It gave rise to such rooms as Caverns of Animus: The Long Ascent: 2N2E. Of course, if you're trying to be gratuitously long, you could just reverse the force arrows on that room and change the algorithm to be more complex. Right now each door just opens the next door in line.

(The best demo for this room as it currently stands is about 66K moves, and it's only the second-longest #1 demo out there.)

Josh

Yeah, but 66k moves is only the start. I'm not interested in putting such rooms into holds... this is just a curiosity thing As I said before - tower of hanoi structure and you're already into the multibillions of moves.

____________________________
My Holds

Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged

Hmm. There was a contest to make the longest DROD:AE room. But I can't find the link.

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator

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

This is the current record for the longest room.

Ezlo
Level: Smitemaster

Rank Points: 1224
Registered: 01-08-2006
IP: Logged

What's so long about it? I can't tell from the picture.

Dolan42
Level: Master Delver

Rank Points: 195
Registered: 04-14-2006
IP: Logged

Well, Doctor E. Will's Mega Complex : Happiness Is a State of Mind : 2 South, 2 East shows what you can do with snakes. Eliminate the southern entrance, add more seeps and protect them better and you're at 105,675,570 moves before you can even enter the snake area. Add more snakes of length prime*2 and you've got a room that takes possibly over a trillion moves.

____________________________
-D
"To understand recursion you must first understand recursion."

Doom
Level: Smitemaster

Rank Points: 3260
Registered: 07-05-2004
IP: Logged

This is probably what you're looking for...

Edit:

coppro wrote:
This is the current record for the longest room.

I don't think that qualifies... Currently, Rabscuttle is the only person who has a score for the room, and it looks a lot like he's just purposefully lenghtened it to get the first place on the longest rooms list.

I played the original, slightly easier version when it was a contest entry for the hardest imaginable room, and it was clearable well under 5000 moves. It can't have changed that much.

Hmm... I think I need to play a little DROD right now

---

[Last edited by Doom at 06-22-2007 09:12 PM]

jbluestein
Level: Smitemaster

Rank Points: 1670
Registered: 12-23-2005
IP: Logged

Doom wrote:
This is probably what you're looking for...

Edit:

coppro wrote:
This is the current record for the longest room.

I don't think that qualifies... Currently, Rabscuttle is the only person who has a score for the room, and it looks a lot like he's just purposefully lenghtened it to get the first place on the longest rooms list.

I know that michthro had a demo for it after the hold was originally released, and then Rabscuttle made a modification to remove an unintended solution.

That said, I haven't a clue why it takes so long to finish -- I'm guessing it requires some serious synchronization of tar growth or something. I have played around in the room briefly, but never enough to get a sense of how it was supposed to be solved.

Josh

____________________________
"Rings and knots of joy and grief, all interlaced and locking." --William Buck

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

Yeah, I definitely remember the thread Doom mentioned. The longest room from that thread is 1327844982041917746723970516381171568323982794317579807998610345501008899 6521306068479062556630732141722233237156162525383664483441317680985237999 4691646837985957817708848304757932033 moves long.

I wonder if TCB can have more?

RoboBob3000
Level: Smitemaster

Rank Points: 1980
Registered: 10-23-2003
IP: Logged

TripleM wrote:
I wonder if TCB can have more?

Pressure plates alone should be able to tighten up the Hanoi implementation.

That was a cool thread. It was some of my first real exposure to the forum.

____________________________
http://beepsandbloops.wordpress.com/

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

RoboBob3000 wrote:

TripleM wrote:
I wonder if TCB can have more?

Pressure plates alone should be able to tighten up the Hanoi implementation.

That was a cool thread. It was some of my first real exposure to the forum.

Yeah. Pressure plates would be a huge help. Plus, a tower of hanoi with n "rings" takes 2^n - 1 moves to complete, so it's got exponential growth at least. However, with the finite size of a room, not sure if you'd be able to beat the previous one in time.

____________________________
My Holds

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

TripleM wrote:
Yeah, I definitely remember the thread Doom mentioned. The longest room from that thread is 1327844982041917746723970516381171568323982794317579807998610345501008899 6521306068479062556630732141722233237156162525383664483441317680985237999 4691646837985957817708848304757932033 moves long.

I wonder if TCB can have more?

I believe that particular one required scripting though?

____________________________
My Holds

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

Also, just a thought. Tower of Hanoi seemed to be the best one in terms of simplicity, it grows in the power 2^x...

Are there any classical mathematical puzzles which grow proportional to a higher power? e.g. 4^X. If one of them could be included then we could get even higher...

____________________________
My Holds

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

It is definitely possible to do more with scripting, even without TCB, and even keeping the scripts simple. I just checked out the record over in that thread, set by Schep, and found a minor change to Schep's script that allows you to fill every square with characters instead of every other one, resulting in double the density. This raises the numer of moves from 2^605+1 to around 2^1309+1, perhaps give or take a power of two.

Even better, with a few more simple additions to the script, you can indeed change the base of the exponent! The simplest expansion results in 4^1309+1 moves, and you can make the base of exponent as large as you want, limited only by how many lines are allowed in one character's script.

By the way, what is the maximum number of lines are allowed in one script? Or is there no maximum except the limitations of filesize/memory? If I knew the limit, I could work out a value for the movecount astronomically greater than anything posted so far.

Posting a demonstration hold shortly...

____________________________
Complexity is the source of Life.

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

Yes, the limit is based on available memory.

However, with variables available, you can easily rank the maximum amount far into oblivion. You can easily make a theoretically infinite room with enough variables. Just think of each variable as a single digit base 4 294 967 296.

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

Skylancer64 wrote:
It is definitely possible to do more with scripting, even without TCB, and even keeping the scripts simple. I just checked out the record over in that thread, set by Schep, and found a minor change to Schep's script that allows you to fill every square with characters instead of every other one, resulting in double the density. This raises the numer of moves from 2^605+1 to around 2^1309+1, perhaps give or take a power of two.

Even better, with a few more simple additions to the script, you can indeed change the base of the exponent! The simplest expansion results in 4^1309+1 moves, and you can make the base of exponent as large as you want, limited only by how many lines are allowed in one character's script.

By the way, what is the maximum number of lines are allowed in one script? Or is there no maximum except the limitations of filesize/memory? If I knew the limit, I could work out a value for the movecount astronomically greater than anything posted so far.

Posting a demonstration hold shortly...

Yeah, but I'm trying to see what the maximum is without scripting. With the new scripting commands in TCB, you can make a hold arbitrarily long - just have a script that increments a variable by 1 each time something happens, and wait until that variable reaches X where X is some high number.

You can nest this by say... every time X reaches a billion (or whatever), reduce it back to zero and increment Y by one. Y tthen must reach a billion before it resets back to zero... incremementing Z by one. etc etc. If you're restricted to JtRH scripting, then it's less.

EDIT: Bah, coppro beat me to it

____________________________
My Holds

---

[Last edited by calamarain at 06-23-2007 03:01 AM]

Banjooie
Level: Smitemaster

Rank Points: 1645
Registered: 12-12-2004
IP: Logged

also consider briefly you could make it so the variable has to hit its max...then its minimum again. And repeat this.

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

Banjooie wrote:
also consider briefly you could make it so the variable has to hit its max...then its minimum again. And repeat this.

Basically, if you can have TCB scripting, you can reach arbitrarily high amounts.

With JtRH scripting... not so sure.

____________________________
My Holds

Rabscuttle
Level: Smitemaster

Rank Points: 2486
Registered: 09-10-2004
IP: Logged

jbluestein wrote:

Doom wrote:
This is probably what you're looking for...

Edit:

coppro wrote:
This is the current record for the longest room.

I don't think that qualifies... Currently, Rabscuttle is the only person who has a score for the room, and it looks a lot like he's just purposefully lenghtened it to get the first place on the longest rooms list.

I know that michthro had a demo for it after the hold was originally released, and then Rabscuttle made a modification to remove an unintended solution.

That said, I haven't a clue why it takes so long to finish -- I'm guessing it requires some serious synchronization of tar growth or something. I have played around in the room briefly, but never enough to get a sense of how it was supposed to be solved.

That was the last room I got a high score for the first time I had a score for all rooms. I'd wager it is currently the least optimised room. It should belong near the bottom of page 1. Probably page 2 with some work.

Kwakstur
Level: Smiter

Rank Points: 385
Registered: 05-05-2006
IP: Logged

Okay, looks like I play the role of the n00b, once again.

What is Hanoi?

____________________________
Also known as ExpHP everywhere else.

Rabscuttle
Level: Smitemaster

Rank Points: 2486
Registered: 09-10-2004
IP: Logged

http://en.wikipedia.org/wiki/Towers_of_hanoi

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape.

The objective of the game is to move the entire stack to another peg, obeying the following rules:

* Only one disk may be moved at a time.
* Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg.
* No disk may be placed on top of a smaller disk.

Here is an example (in Pelcho's Puzzles)

---

[Last edited by Rabscuttle at 06-23-2007 03:31 AM]

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

File: Etnernal-er Script.hold (17.9 KB)
Downloaded 43 times.
License: Public Domain

Heh. I haven't been keeping up with the new TCB scripting features, and just recently got back to playing. But I'm pretty sure that "Wait for..." and "Wait while..." are available in JTRH, which did not have variables. No variables used at all here.

Demonstration attached, with lengths of (2*2^1211 + 1) and (2*4^1211 + 1) featured. Increasing the exponent base simply requires adding more "Wait for..." and "Wait while..." statements. If there is no maximum scripting limit, then apparently JTRH scripting allows arbitrarily high values as well.

Only the first 20 or so characters are actually implemented, plus the one next to the orb, since I was not insane enough to set scripts for a over a thousand characters.

I'm fairly sure that there is no better way to make use of the space in a room with JTRH scrpting, and that this method is the best for maximizing move count, aside from the small multipliers you can get by adding Wait... statements, and packing a few more characters in the spaces adjacent to Beethro with invulnerability flags.

As for the non-scripting TCB limit...
That remains interesting.

*Edit*
I don't think you can get much better than "Eternity 3" from the other thread though (page 4 I think). According to the posts there, it has 162 orbs, and implements a binary-counting method using them all, so the movecount should be in the range of 2^162. Implementing towers of hanoi is too complicated. The best method is probably going to come from this sort of binary counting and optimizing the packing of the orbs and doors.

____________________________
Complexity is the source of Life.

---

[Last edited by Skylancer64 at 06-23-2007 03:48 AM]

calamarain
Level: Smitemaster

Rank Points: 933
Registered: 03-25-2007
IP: Logged

Skylancer64 wrote:
As for the non-scripting TCB limit...
That remains interesting.

*Edit*
I don't think you can get much better than "Eternity 3" from the other thread though (page 4 I think). According to the posts there, it has 162 orbs, and implements a binary-counting method.

2^X might be the limit of growth (in unscripted systems), because we only seem to have binary states. The only means of "data storage" we have are 2-state. e.g. monster is present, or monster is not. Door is open or door is closed. There doesn't appear to be any means of storing more than a 1 or a 0 in any one square.

____________________________
My Holds

---

[Last edited by calamarain at 06-23-2007 03:50 AM]

Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged

So without scripting I think you do better in TCB. The idea is to build a binary counter. It would work like so:

.   .
    ^
X   |

P-> D

(the .'s are empty, P is a pressure plate that toggles door D, and we have force arrows as shown). Hooking a lot of these up, we get a binary counter. Given that they are 2*3, and that the map is 30*36, we can fit roughly 180 binary counters. Since they must be counted in binary we get about

2^180 turns.

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

File: BinaryCounter.gif (28.3 KB)
Downloaded 85 times.
License: Public Domain

How's this for a compact binary counter? (See image)

Every pressure plate is set to toggle the door to its immediate right. Counting the wall, each binary bit takes only a 1x3 space. (Note that it is not 1x4 since adjacent rows of bits will share walls).

We can expect about 38 * 32 / 3 = 405.3 bits to fit in a room. (A bit less if we insist on the border of the room beings surrounded by walls). Of course, not quite that much since we need space for possible inefficiencies involving room size and turning around when we run into the edge. But this gives in the range of 2^(350 to 400) pressure plate toggles required. Anyone want to cook up a room using this, or can anyone do better?

____________________________
Complexity is the source of Life.

---

[Last edited by Skylancer64 at 06-23-2007 05:04 AM]

RoboBob3000
Level: Smitemaster

Rank Points: 1980
Registered: 10-23-2003
IP: Logged

Wow, that looks efficient! Have you worked up a way to take corners? I wonder if a tunnel approach to cornering could save you some space...

____________________________
http://beepsandbloops.wordpress.com/

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

File: BinaryCounterCorner.gif (222.1 KB)
Downloaded 60 times.
License: Public Domain

RoboBob3000 wrote:
Have you worked up a way to take corners? I wonder if a tunnel approach to cornering could save you some space...

Excellent idea! I wasn't considering tunnels, but your suggestion allows slightly more efficiency. I found two methods of cornering.

The first is a 90 degree turn. Each turn wastes a 2x2 space.

The second method uses tunnels to gain an extra bit per 180 degree turn, but appears to be 180 degree only. These are depicted in the attached image.

I'm not sure, but it might be possible to do better than these corners, although I can't find a way to make the force arrows work out. Also, a big problem is getting the plates and doors to line up. There are plenty of corners that don't work because there are more doors than plates, or vice versa.

Interestingly enough, it is possible to "get stuck" in these corners if you proceed through the arrows around the turn before the next door has opened. This can be prevented by shifting the door in the next row back a force arrow or two, but then the corner loses its visual symmetry.



____________________________
Complexity is the source of Life.

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

File: BinaryCount.hold (4.7 KB)
Downloaded 46 times.
License: Public Domain

Anyways, here is the hold featuring two rooms of this stuff.

The version with properly-bordered walls contains 343 doors. The version without them contains 397 doors. The actual movecount should be somewhat higher than 2^343 or 2^397 because there is a great deal of walking involved between each binary configuration.

Unfortunately, for the wall-bordered room, there is a wasted row at the bottom. I think it is possible to take up some of that extra space by introducing the slightly less efficient 90-degree turn to add vertical columns of bits for the counter rather than making it run only horizontally. At the moment though, I don't really care to try.

____________________________
Complexity is the source of Life.

Skylancer64
Level: Delver
Rank Points: 62
Registered: 10-25-2003
IP: Logged

File: BetterCorners.gif (32.2 KB)
Downloaded 59 times.
License: Public Domain

And a small improvement to the corners. By twisting a few of the arrows, the player can no longer get stuck (I think).

____________________________
Complexity is the source of Life.