How many rooms are there in the tower?
Moderators: jestingrabbit, Moderators General, Prelates

 Posts: 3
 Joined: Mon Jan 24, 2011 10:32 pm UTC
How many rooms are there in the tower?
Imagine a cylindrical tower with an unknown number of identical, windowless, empty rooms, which form a ring around a central (inaccessible) circular area. (So, basically, the layout so far is similar to the one in this puzzle: viewtopic.php?f=3&t=70558.) Each room has two doors, both leading to the next room in either direction. Furthermore, each room has a light switch which can turn on/off the light in the same room.
One day you find yourself in one of the rooms, with knowledge of the above paragraph. Your goal is to find out how many rooms are there. You can go from room to room and turn on/off lights. You have no other means to interact with the world (you can not mark anything, or leave any of your belongings in a room, etc.). You can not rely on observing anything other than the current state of the light in the room you are currently in (you can't measure the curvature of the walls, you can't leave doors open to let light from other rooms remain visible, you can not touch light bulbs to see if they are warm, etc.). Oh, and of course you can not assume anything about the initial condition of the light switches in any room.
I have come up with a solution, but I'm interested in others. A little bit of context: a teacher friend told me this puzzle. Not knowing a solution himself, he was only fascinated by the problem statement, mentioning how 'beautiful' and 'elegant' it was in its simplicity, yet capable of defining such a nontrivial puzzle. Therefore, he was convinced that a solution must share the same properties (being 'beautiful' and causing the same kind of fascination), because that's what he always experienced during his career as a teacher. When I discussed my solution with him (the first working solution he heard), he was disappointed, and stated that this must not be *the* solution, because he found it too 'mechanical' and algorithmic. He felt that my solution was not worthy of the beauty of the problem statement. We have not found any other solution so far (only variants and optimizations), and I'm curios whether there's any, especially one that could please him.
One day you find yourself in one of the rooms, with knowledge of the above paragraph. Your goal is to find out how many rooms are there. You can go from room to room and turn on/off lights. You have no other means to interact with the world (you can not mark anything, or leave any of your belongings in a room, etc.). You can not rely on observing anything other than the current state of the light in the room you are currently in (you can't measure the curvature of the walls, you can't leave doors open to let light from other rooms remain visible, you can not touch light bulbs to see if they are warm, etc.). Oh, and of course you can not assume anything about the initial condition of the light switches in any room.
I have come up with a solution, but I'm interested in others. A little bit of context: a teacher friend told me this puzzle. Not knowing a solution himself, he was only fascinated by the problem statement, mentioning how 'beautiful' and 'elegant' it was in its simplicity, yet capable of defining such a nontrivial puzzle. Therefore, he was convinced that a solution must share the same properties (being 'beautiful' and causing the same kind of fascination), because that's what he always experienced during his career as a teacher. When I discussed my solution with him (the first working solution he heard), he was disappointed, and stated that this must not be *the* solution, because he found it too 'mechanical' and algorithmic. He felt that my solution was not worthy of the beauty of the problem statement. We have not found any other solution so far (only variants and optimizations), and I'm curios whether there's any, especially one that could please him.

 Posts: 3
 Joined: Mon Jan 24, 2011 10:32 pm UTC
Re: How many rooms are there in the tower?
jaap wrote:Spoiler:
Nice one! I like the parallel with the painting technique. For me, personally, the idea of applying it to this puzzle certainly qualifies this solution as being elegant. Let's see if my friend agrees.
It is quite different from my solution:
Spoiler:
Still, I have a feeling (though I have trouble expressing it precisely) that in their core all these solutions share the same qualities that make them too algorithmic for my friend's taste. (And I suspect that all possible solutions are like this, only I can't prove this to him, and he won't accept it.)
Spoiler:
Either way, thanks for your solution! Also, if anyone has yet another solution, I'm eager to hear it. I still would like to find out whether my friend is right in thinking that there must be some solution which is elegant in his (notreallywelldefined) view, too.
 emlightened
 Posts: 42
 Joined: Sat Sep 26, 2015 9:35 pm UTC
 Location: Somewhere cosy.
Re: How many rooms are there in the tower?
mward wrote:Spoiler:
This fails if there are thousands of rooms, and it should go on arbitrarily high.
vicariggio wrote:It is quite different from my solution:Spoiler:
Sort of going in the exact opposite direction from what they want, but a more efficient implementation is:
Spoiler:
He doesn't sound like the sort of person who would like to hear that the efficiency has been increased from O(n^{2}) rooms visited to O(n*log(n)) (worst case), but he's not a programmer.
As for an 'elegant' solution?
You can't continue indefinitely in a single direction, as the rooms could just happen to be laid out that way. No matter the method, you are guaranteed to need to go back at least N rooms if there are N rooms total. If that's 'inelegant', then everything that works is.
██████████████████████████████████████████████████████████████████████████████████████████████████████
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:
Spoiler:
 SirGabriel
 Posts: 42
 Joined: Wed Jul 16, 2014 11:54 pm UTC
Re: How many rooms are there in the tower?
ThirdParty wrote:Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:Spoiler:
Please explain why that works.
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
SirGabriel wrote:ThirdParty wrote:Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:Spoiler:
Please explain why that works.
Spoiler:
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
Vytron: your solution appears to be identical to vicariggio's in all details. Maybe you misread his.
I'm a little disappointed that people haven't yet acknowledged the brilliance of my solution. Maybe if I explain it in words rather than algorithmically. The following isn't quite identical to the algorithm I posted, but uses the same idea and takes the same amount of time:I did a simulation of a hundredroom tower with random initial lighting. vicariggio's algorithm solved it in 4518 steps; jaap's solved it in 3033 steps; emlightened's solved it in 594 steps; and mine solved it in 216 steps.
I also calculated the theoretical worstcase scenario for each strategy. vicariggio's worst 100room tower takes him 10100 steps; jaap's takes 5251 steps; emlightened's takes 594 steps; and mine takes 500 steps.
I'm a little disappointed that people haven't yet acknowledged the brilliance of my solution. Maybe if I explain it in words rather than algorithmically. The following isn't quite identical to the algorithm I posted, but uses the same idea and takes the same amount of time:
Spoiler:
I also calculated the theoretical worstcase scenario for each strategy. vicariggio's worst 100room tower takes him 10100 steps; jaap's takes 5251 steps; emlightened's takes 594 steps; and mine takes 500 steps.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: How many rooms are there in the tower?
ThirdParty wrote:I did a simulation of a hundredroom tower with random initial lighting. vicariggio's algorithm solved it in 4518 steps; jaap's solved it in 3033 steps; emlightened's solved it in 594 steps; and mine solved it in 216 steps.
I also calculated the theoretical worstcase scenario for each strategy. vicariggio's worst 100room tower takes him 10100 steps; jaap's takes 5251 steps; emlightened's takes 594 steps; and mine takes 500 steps.
What I notice here, apart from the fact that the best performer is your own algorithm, is that emlightened's worst case was achieved randomly, which is interesting.
Out of curiosity, did you get your programs to report the perceived length after executing? Just for rigor.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: How many rooms are there in the tower?
I find all the weird case analysis to speed up the algorithm rather inelegant. My preferred solution is cleanly stated, even if it's slow.
Spoiler:
Spoiler:
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: How many rooms are there in the tower?
Do the lights use a normal light bulb? Then I turn the one in the first room repeatedly on and off and hope that that causes the light to fail faster so that I can just search for the burnt out bulb.
Spoiler:
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
emlightened's solution ignores the initial configuration of lights, and so always achieves its worstcase scenario. (By the way, for some tower sizes1023 rooms, for examplehis time is better than my worstcase time. The main virtue of my algorithm is that it usually does far better than its worst case.)jestingrabbit wrote:What I notice here, apart from the fact that the best performer is your own algorithm, is that emlightened's worst case was achieved randomly, which is interesting.ThirdParty wrote:I did a simulation of a hundredroom tower with random initial lighting. vicariggio's algorithm solved it in 4518 steps; jaap's solved it in 3033 steps; emlightened's solved it in 594 steps; and mine solved it in 216 steps.
I also calculated the theoretical worstcase scenario for each strategy. vicariggio's worst 100room tower takes him 10100 steps; jaap's takes 5251 steps; emlightened's takes 594 steps; and mine takes 500 steps.
Out of curiosity, did you get your programs to report the perceived length after executing? Just for rigor.
As for the simulation: I'm afraid I did it by hand rather than writing a program. So, yes, I can confirm that all the algorithms worked, but I can't guarantee that I didn't miscount their steps.
Doing it by hand did give me a new appreciation for how each algorithm works. jaap's turned out to be sillier than I'd realized, because of a parity issue. And mine is spooky to watch: after a bit of fiddling around at the beginning while it was ruling out tinytower hypotheses, it reached a point where it started charging through the rest of the tower nonstop.
Wouldn't it be easier to just unscrew it rather than trying to burn it out? Or are you too short?PeteP wrote:Do the lights use a normal light bulb? Then I turn the one in the first room repeatedly on and off and hope that that causes the light to fail faster so that I can just search for the burnt out bulb.
I like this one! Easier to explain than mine, and also reaches a "charge through" point.PeteP wrote:Serious answer:Spoiler:
Re: How many rooms are there in the tower?
It would be easier, but I can apparently only turn the lights on and off and nothing else in the room so I thought it might be a work around.
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
Here's a solution that's approaching maximum efficiency (albeit low elegance):
Spoiler:
 Elvish Pillager
 Posts: 1009
 Joined: Mon Aug 04, 2008 9:58 pm UTC
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
Re: How many rooms are there in the tower?
I have a simple solution that is O(n).
Spoiler:
Last edited by Elvish Pillager on Mon Oct 12, 2015 1:47 pm UTC, edited 1 time in total.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
 Elvish Pillager
 Posts: 1009
 Joined: Mon Aug 04, 2008 9:58 pm UTC
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
Re: How many rooms are there in the tower?
More optimizations, possible fastest solution?
Spoiler:
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
 ThirdParty
 Posts: 351
 Joined: Wed Sep 19, 2012 3:53 pm UTC
 Location: USA
Re: How many rooms are there in the tower?
Good analysis, and definitely in sympathy with the kinds of approach I've been pushing. However, I have a couple of notes:Elvish Pillager wrote:More optimizations, possible fastest solution?Spoiler:
Spoiler:
 Elvish Pillager
 Posts: 1009
 Joined: Mon Aug 04, 2008 9:58 pm UTC
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
Re: How many rooms are there in the tower?
I think you're correct on both points.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: How many rooms are there in the tower?
Philosophical offtopic comment?
Spoiler:
 Elvish Pillager
 Posts: 1009
 Joined: Mon Aug 04, 2008 9:58 pm UTC
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
Re: How many rooms are there in the tower?
Spoiler:
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
Re: How many rooms are there in the tower?
I think there's an optimization people haven't mentioned yet:
Backtracking is necessary, but it is a waste of time if it turns out your guess is false. To make it useful, you can use your backtrack as a way to set a new marker of larger size.
You start with zero information so you set a pattern to look for.
The next time you see the pattern, you will have a guess for the number of rooms.You check your guess backtracking.
If it's not correct, then you only have knowledge of a "contiguous fragment" of the tower.
At this point, define a new pattern as the fragment of the tower that you have knowledge of.
This larger pattern lets you traverse farther (statistically speaking) before being forced to backtrack. If you traversed farther, your knowledge fragment will grow. A larger knowledge fragment leads to a larger pattern. This snowballs until the knowledge fragment is 100%.
Here's how it could be implemented:
Large N Time Analysis
Let some initial point on the circle be S_{0}. If you construct a pattern, p_{1}, of length n, it will span S_{0}:S_{(n1)}.
In the worst case scenario, the next detected copy of p_{1} will span S_{n}:S_{(2n1)}.
This will trigger a change in direction, and construction of a new pattern, p_{2}, of length 2n. spanning S_{(2n1)}:S_{(0)}.
If we consider worst case scenarios all the time, this process will iterate. So given an initial pattern of length n, the number of room transitions will grow like:
2n + 4n + 8n + 16n +...2^{k1}n = n(2^{k}1) for a iterations
(Traverse two consecutive patterns of size n, followed by two patterns of size 2n, etc., where each pattern "upgrade" doubles back upon itself.)
The iterations will terminate only when 2^{k1}n is more than half the rooms in the tower. Once this occurs, an extra number equal to the the total number of rooms plus the length of the pattern will need to be walked to verify.
Given N rooms in the tower:
2^{k1}n > N/2
k > log_{2}(N/n)
This means for the worse case scenario, the number of room transitions in the iteration process is bounded by n(2^{(log2(N/n) + 1)}1) = 2N1. The verification bit adds some number between 1.5N and 2N. Thus, for the worst case scenario, we have 3.5N1 as the minimum bound and 4N1 as the maximum bound.
The worst case scenario requires a series of highly unlikely events. Namely, you choose the exact patterns needed to force backtrack in the minimum number of moves, for every single one of k > log_{2}(N/n) iterations. As the pattern length increases, the likelihood of you picking an unfavorable one drops very quickly.
Backtracking is necessary, but it is a waste of time if it turns out your guess is false. To make it useful, you can use your backtrack as a way to set a new marker of larger size.
You start with zero information so you set a pattern to look for.
The next time you see the pattern, you will have a guess for the number of rooms.You check your guess backtracking.
If it's not correct, then you only have knowledge of a "contiguous fragment" of the tower.
At this point, define a new pattern as the fragment of the tower that you have knowledge of.
This larger pattern lets you traverse farther (statistically speaking) before being forced to backtrack. If you traversed farther, your knowledge fragment will grow. A larger knowledge fragment leads to a larger pattern. This snowballs until the knowledge fragment is 100%.
Here's how it could be implemented:
Spoiler:
Large N Time Analysis
Let some initial point on the circle be S_{0}. If you construct a pattern, p_{1}, of length n, it will span S_{0}:S_{(n1)}.
In the worst case scenario, the next detected copy of p_{1} will span S_{n}:S_{(2n1)}.
This will trigger a change in direction, and construction of a new pattern, p_{2}, of length 2n. spanning S_{(2n1)}:S_{(0)}.
If we consider worst case scenarios all the time, this process will iterate. So given an initial pattern of length n, the number of room transitions will grow like:
2n + 4n + 8n + 16n +...2^{k1}n = n(2^{k}1) for a iterations
(Traverse two consecutive patterns of size n, followed by two patterns of size 2n, etc., where each pattern "upgrade" doubles back upon itself.)
The iterations will terminate only when 2^{k1}n is more than half the rooms in the tower. Once this occurs, an extra number equal to the the total number of rooms plus the length of the pattern will need to be walked to verify.
Given N rooms in the tower:
2^{k1}n > N/2
k > log_{2}(N/n)
This means for the worse case scenario, the number of room transitions in the iteration process is bounded by n(2^{(log2(N/n) + 1)}1) = 2N1. The verification bit adds some number between 1.5N and 2N. Thus, for the worst case scenario, we have 3.5N1 as the minimum bound and 4N1 as the maximum bound.
The worst case scenario requires a series of highly unlikely events. Namely, you choose the exact patterns needed to force backtrack in the minimum number of moves, for every single one of k > log_{2}(N/n) iterations. As the pattern length increases, the likelihood of you picking an unfavorable one drops very quickly.
This is a block of text that can be added to posts you make. There is a 300 character limit.
 Vytron
 Posts: 432
 Joined: Mon Oct 19, 2009 10:11 am UTC
 Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P
Re: How many rooms are there in the tower?
Can you do even better if you don't care about the worst case scenario?
I wonder if there's some optimal solution for when you visit the tower, only once, so it's very unlikely it contains the worst case, and another for the case where you solve many, many towers in succession, so eventually you're basically guaranteed to find the worst case scenario (and, say, lose everything you won on the other towers.)
I wonder if there's some optimal solution for when you visit the tower, only once, so it's very unlikely it contains the worst case, and another for the case where you solve many, many towers in succession, so eventually you're basically guaranteed to find the worst case scenario (and, say, lose everything you won on the other towers.)
 Elvish Pillager
 Posts: 1009
 Joined: Mon Aug 04, 2008 9:58 pm UTC
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
Re: How many rooms are there in the tower?
You could, at least if you define the probability of each initial state.
Suppose we assume that N is very large, and that each light has an independent 50% chance of being on initially. If you don't mind a 10^100 chance of taking lots of extra time, you can do it in barely more than 2N time (say, 2N + 1.01 log_2(N) + a constant). If you don't mind a 10^100 chance of giving the wrong answer, you can even do it in barely more than N time (say, N + 1.01 log_2(N) + a constant).
(Actually, even if the initial state is chosen maliciously, the player can still achieve these solutions as long as the player has an unlimited source of entropy.)
You could even use stochastic methods like these on extremely large numbers of towers if you're allowed to add a log(number of towers checked) term to your cost.
Optimizing for small values of N is more complicated, and more specific to the distribution of possible values of N.
Suppose we assume that N is very large, and that each light has an independent 50% chance of being on initially. If you don't mind a 10^100 chance of taking lots of extra time, you can do it in barely more than 2N time (say, 2N + 1.01 log_2(N) + a constant). If you don't mind a 10^100 chance of giving the wrong answer, you can even do it in barely more than N time (say, N + 1.01 log_2(N) + a constant).
(Actually, even if the initial state is chosen maliciously, the player can still achieve these solutions as long as the player has an unlimited source of entropy.)
You could even use stochastic methods like these on extremely large numbers of towers if you're allowed to add a log(number of towers checked) term to your cost.
Optimizing for small values of N is more complicated, and more specific to the distribution of possible values of N.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
GENERATION A(g_{64}, g_{64}): Social experiment. Take the busy beaver function of the generation number and add it to your signature.
Who is online
Users browsing this forum: No registered users and 14 guests