How many rooms are there in the tower?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

vicariggio
Posts: 3
Joined: Mon Jan 24, 2011 10:32 pm UTC

How many rooms are there in the tower?

Postby vicariggio » Fri Oct 02, 2015 11:49 am UTC

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 non-trivial 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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How many rooms are there in the tower?

Postby jaap » Fri Oct 02, 2015 12:30 pm UTC

Spoiler:
This reminds me of a technique I used to use occasionally in a painting program. If there was an area that had been dithered (i.e. was coloured in some pattern using two distinct colours) and I wanted it to be just one colour, I would alternate floodfilling it with one colour and then the other. Each time the area getting filled is joined by pre-existing pixels of the same colour, so a larger and larger area would be filled, until the boundary is reached.

For this puzzle you do something very similar.
To begin with, choose a direction you will travel in. For ease of description, I'll assume the current light is on.

Move in the chosen direction, switching lights off as you go, and counting how many lights you switch off. Continue until you reach a room with a light that is already off.
Turn around to go in the other direction, switching the lights on as you go, and counting how many lights you switch on. Continue until you reach a room with a light that is already on.
Reverse again, switching lights off, etc.

Each time the string of lights you switch off/on gets longer, until it encompasses all the rooms on the whole floor. When the number you count remains the same, you have your answer.

vicariggio
Posts: 3
Joined: Mon Jan 24, 2011 10:32 pm UTC

Re: How many rooms are there in the tower?

Postby vicariggio » Fri Oct 02, 2015 2:46 pm UTC

jaap wrote:
Spoiler:
This reminds me of a technique I used to use occasionally in a painting program. If there was an area that had been dithered (i.e. was coloured in some pattern using two distinct colours) and I wanted it to be just one colour, I would alternate floodfilling it with one colour and then the other. Each time the area getting filled is joined by pre-existing pixels of the same colour, so a larger and larger area would be filled, until the boundary is reached.

For this puzzle you do something very similar.
To begin with, choose a direction you will travel in. For ease of description, I'll assume the current light is on.

Move in the chosen direction, switching lights off as you go, and counting how many lights you switch off. Continue until you reach a room with a light that is already off.
Turn around to go in the other direction, switching the lights on as you go, and counting how many lights you switch on. Continue until you reach a room with a light that is already on.
Reverse again, switching lights off, etc.

Each time the string of lights you switch off/on gets longer, until it encompasses all the rooms on the whole floor. When the number you count remains the same, you have your answer.

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:
My idea is to check for each number N (in an increasing order) whether the tower has N rooms, until one of those checks succeed. To check whether it has N rooms for a particular value of N:
1. Switch on the light in your starting room.
2. Go forward N rooms in the same direction.
3. Switch off the light in the Nth room (assuming that the light is on).
4. Go back N rooms, thus arriving to your starting room.
5. Now if you find the light switched off, the tower has N rooms.

If at step 3 the light is not switched on in the Nth room, you can immediately reject the current hypothesis, move forward until you find a room where the light is on, e.g. room N+k, and test that hypothesis without going back to your starting room (saving k 'rounds').

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:
I mean, in both of these solutions we have to do some backtracking (each time longer and longer), and both are based on verifying a current hypothesis or rejecting it and coming up with a new hypothesis in which the number of rooms increases. (In your solution, every time the string of lights you switch on/off gets longer, you try to verify that amount by seeing if it remains the same in the other direction.) I wonder if there's a solution which does not utilize some variant of this.

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 (not-really-well-defined) view, too.

mward
Posts: 123
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: How many rooms are there in the tower?

Postby mward » Fri Oct 02, 2015 3:27 pm UTC

Spoiler:
The solution assumes incandescent lights, or at least, less then perfectly efficient lights:

Turn on the light in the starting room (if it is currently off) and wait a minute or two for it to warm up. Turn it off. Go through and count the rooms one by one until you find a room where the light is off but the bulb is still warm. Now you know you are back at the starting room.

User avatar
emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

Re: How many rooms are there in the tower?

Postby emlightened » Fri Oct 02, 2015 4:02 pm UTC

mward wrote:
Spoiler:
The solution assumes incandescent lights, or at least, less then perfectly efficient lights:

Turn on the light in the starting room (if it is currently off) and wait a minute or two for it to warm up. Turn it off. Go through and count the rooms one by one until you find a room where the light is off but the bulb is still warm. Now you know you are back at the starting room.


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:
My idea is to check for each number N (in an increasing order) whether the tower has N rooms, until one of those checks succeed. To check whether it has N rooms for a particular value of N:
1. Switch on the light in your starting room.
2. Go forward N rooms in the same direction.
3. Switch off the light in the Nth room (assuming that the light is on).
4. Go back N rooms, thus arriving to your starting room.
5. Now if you find the light switched off, the tower has N rooms.

If at step 3 the light is not switched on in the Nth room, you can immediately reject the current hypothesis, move forward until you find a room where the light is on, e.g. room N+k, and test that hypothesis without going back to your starting room (saving k 'rounds').


Sort of going in the exact opposite direction from what they want, but a more efficient implementation is:

Spoiler:
  1. Flick the current room's light on.
  2. Let R=0 be the index of your current room.
  3. Set N=1
  4. Flick all of the lights from rooms R=N to R=2N-1 inclusive off.
  5. Go to R=0. If the light is off, go to step 7.
  6. Double L, then go to step 4.
  7. Turn the light back on. Now the only room with a light on is R=0
  8. Add 1 to R. Repeat while the light is off.
  9. If the light is on, then you have discovered how many rooms there are, namely the current value of R.


He doesn't sound like the sort of person who would like to hear that the efficiency has been increased from O(n2) 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."

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Sat Oct 03, 2015 6:33 am UTC

Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:
Spoiler:
  1. Declare M, N, and i as integer variables whose initial values are all set to 0; arbitrarily define one door of the starting room as leading "forward" and the other as leading "backward". If the light is off: turn it on. Proceed to Step 2.
  2. If i<N: move forward one room; increment i; repeat Step 2. Else: set i to 0; proceed to Step 3.
  3. Move forward one room; increment N. If the light is off: increment i; repeat Step 3. Else: turn the light off; proceed to Step 4.
  4. If i<M: set i to 0; go back to Step 3. Else: set i to N; swap "forward" and "backward"; proceed to Step 5.
  5. If i>0: move forward one room; decrement i; repeat Step 5. Else: proceed to Step 6.
  6. If the light is off: halt, returning N as the answer. Else: swap M and N; go back to Step 2.

User avatar
SirGabriel
Posts: 42
Joined: Wed Jul 16, 2014 11:54 pm UTC

Re: How many rooms are there in the tower?

Postby SirGabriel » Sat Oct 03, 2015 12:49 pm UTC

ThirdParty wrote:Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:
Spoiler:
  1. Declare M, N, and i as integer variables whose initial values are all set to 0; arbitrarily define one door of the starting room as leading "forward" and the other as leading "backward". If the light is off: turn it on. Proceed to Step 2.
  2. If i<N: move forward one room; increment i; repeat Step 2. Else: set i to 0; proceed to Step 3.
  3. Move forward one room; increment N. If the light is off: increment i; repeat Step 3. Else: turn the light off; proceed to Step 4.
  4. If i<M: set i to 0; go back to Step 3. Else: set i to N; swap "forward" and "backward"; proceed to Step 5.
  5. If i>0: move forward one room; decrement i; repeat Step 5. Else: proceed to Step 6.
  6. If the light is off: halt, returning N as the answer. Else: swap M and N; go back to Step 2.

Please explain why that works.

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Sat Oct 03, 2015 2:27 pm UTC

SirGabriel wrote:
ThirdParty wrote:Here's a solution that's significantly more efficient than jaap's and significantly more elegant than emlightened's:
Spoiler:
  1. Declare M, N, and i as integer variables whose initial values are all set to 0; arbitrarily define one door of the starting room as leading "forward" and the other as leading "backward". If the light is off: turn it on. Proceed to Step 2.
  2. If i<N: move forward one room; increment i; repeat Step 2. Else: set i to 0; proceed to Step 3.
  3. Move forward one room; increment N. If the light is off: increment i; repeat Step 3. Else: turn the light off; proceed to Step 4.
  4. If i<M: set i to 0; go back to Step 3. Else: set i to N; swap "forward" and "backward"; proceed to Step 5.
  5. If i>0: move forward one room; decrement i; repeat Step 5. Else: proceed to Step 6.
  6. If the light is off: halt, returning N as the answer. Else: swap M and N; go back to Step 2.

Please explain why that works.
Spoiler:
I'm searching out from the starting room in alternating directions, checking for the pattern that I know exists on the other end (i.e. a long run of "off"s unpunctuated by "on"s).

The worst-case-scenario is that I do a kind of fibonacci sequence search: I start at Room 0; go to Room 1, mistake it for Room 0, and return home; then I go to Room -2, mistake it for Room 0 (after mistaking Room -1 for Room 1), and return home; then I go to Room 4, mistake it for Room 0 (after mistaking Rooms 2 to 3 for Rooms -2 to -1), and return home; then I go to Room -7, mistake it for Room 0 (after mistaking Rooms -3 to -6 for Rooms 4 to 1), and return home; then I go to Room 12; then I go to Room -20, and so on.

User avatar
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?

Postby Vytron » Sun Oct 04, 2015 7:21 pm UTC

Spoiler:
jaap wrote:This reminds me of a technique I used to use occasionally in a painting program. If there was an area that had been dithered (i.e. was coloured in some pattern using two distinct colours) and I wanted it to be just one colour, I would alternate floodfilling it with one colour and then the other. Each time the area getting filled is joined by pre-existing pixels of the same colour, so a larger and larger area would be filled, until the boundary is reached.


Ah, yes, I used to do that a lot with Mario Paint :mrgreen: - I'd even play "mini-games" where I'd erase some parts of the picture in that manner.

Anyway, I don't get what ThirdParty is doing...

But I think my solution is different from everyone else, because, from the starting room, you never visit the "backdoor":

1-From the starting room, define "back" as the door in one direction, and "forward" as the other one.
2-Leave the switch of this room ON.
3-Move forward, room after room, until you find a light ON, and turn it off.
4-Go back to the starting room to check the status of the light:
---If it's ON, go to step 3.
---If it's OFF, the number of rooms is "number of times in a row you had to open a backdoor".

At least, I think this is better than the OP's solution, as if, say, there's 15 OFF rooms forward, you instantly check if there's 15 rooms (i.e. each room you visit lets you know there's at least n+1 rooms.)

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Mon Oct 05, 2015 1:00 am UTC

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:
Spoiler:
Turn on the light in the starting room (call it Room 0). Pick a direction and travel thataway, naming the rooms (Room 1, Room 2, etc.) as you go. When you hit a room (call it Room N) with a light that's on, stop, turn the light off, and return to Room 0 to see if you're done. If you're not done, start going in the other direction: Room -1, Room -2, etc. Continue until you've observed a sequence of at least N rooms in a row with the lights off, followed by a room with the light on (call it Room -M). Turn it off, and return to Room 0 (turning off any other lights you pass along the way) to see if you're done. If you're not done, return to Room N, and then go forward from there until you observe a sequence of at least M rooms in a row with lights off, followed by a room with lights on. This is the new Room N. Turn the light off and return to Room 0 (turning off any other lights you pass along the way) to see if you're done. etc.

Like jaap's solution, I'm exploring in both directions at once. Like emlightened's, my strategy finishes in linearithmic time (if I turn around at Room N once, then the next time I'm exploring in that direction I definitely won't turn around again until room 2N+2 at the earliest). Unlike everyone else's solution, I'm using information about how I left the light in rooms other than the one I started in.
I did a simulation of a hundred-room 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 worst-case scenario for each strategy. vicariggio's worst 100-room tower takes him 10100 steps; jaap's takes 5251 steps; emlightened's takes 594 steps; and mine takes 500 steps.

User avatar
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?

Postby Vytron » Mon Oct 05, 2015 3:00 am UTC

Spoiler:
ThirdParty wrote:Vytron: your solution appears to be identical to vicariggio's in all details. Maybe you misread his.


Oh, right, I missed this:

If at step 3 the light is not switched on in the Nth room, you can immediately reject the current hypothesis, move forward until you find a room where the light is on, e.g. room N+k, and test that hypothesis without going back to your starting room (saving k 'rounds').


At least I can say I found it before reading his.

Thanks for elaborating on your solution, I had no idea what you were doing at first. Basically, you no longer rely on just the original room being switched off, and having to go back to it every time, you rely on that, for randomly starting configurations, all lights off in several rooms in a row is unlikely, so you only need to have a check when you find as many as you know there are, so at some point you never go back (because you don't find as many in a row - say, if you know there are 200 off in a row, then with 1000000 rooms you can basically just go ahead until you find them again, and then go back, and as 200 in a row happening naturally is unlikely, you're most likely not wasting time) until you find all of them, and you know you're done once you get back (minimizing the "perhaps I'm done already" moments.)

User avatar
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?

Postby jestingrabbit » Mon Oct 05, 2015 8:34 am UTC

ThirdParty wrote:I did a simulation of a hundred-room 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 worst-case scenario for each strategy. vicariggio's worst 100-room 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.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: How many rooms are there in the tower?

Postby Cauchy » Mon Oct 05, 2015 8:44 am UTC

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:
For each integer N in sequence, starting from 1:
Note the current state of the room you're in. Walk in one direction N rooms, toggle the switch there, and then go back N rooms. If the room has switched states, then the tower has N rooms. Otherwise, it doesn't; try the next N.


Spoiler:
Fundamentally, the only way to know for sure that you've got the size of the tower is to have visited every room, and the only way to know you've done that is to flip a switch and know it's caused a change some number of rooms away by visiting that room and observing the change, so that you know you've gone all the way around the tower; otherwise, it's possible that the initial state of the tower is just fooling you into thinking you've visited everything based on coincidences. Every solution, then, must involve some amount of backtracking, since you have to backtrack to previously visited rooms to observe the change. And since you don't ever know while exploring new rooms whether you've looped around or are just finding coincidentally similar initial setups, the solution has to be of the form "do some exploration, then head back to see if anything's changed; if so, you're done, and if not, keep exploring". This seems to me to be the heart of the "algorithmic" feel of the solution, and it's unavoidable.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: How many rooms are there in the tower?

Postby PeteP » Mon Oct 05, 2015 1:13 pm UTC

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:
Serious answer: I will label the first room room 1 and pick a direction and number the rooms in increasing order (I will use k for the current room number.). Then I switch the light of rooms 1-10 of and set N=10. Afterwards I will continue walking in the direction and if a light is on I turn it off and set N=k. I stop when I reach a dark room where 2*N=k, turn the light on and check if an of the rooms I have visited have light again. Otherwise I return and turn the light off and set N=k and begin again.

I don't really think there is a particularly elegant answer, without an upped bound for the room number every pattern you find could be coincidence so your only choice is to check back from time to time. So the only question is how often do you check back. If no room has light my pattern just doubles the distance each time. However if the distribution of on/off is relatively random then it is likely that I will find a room with light before reaching 2*N which will increase my N, if I haven't reached rooms that I already visited.

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Mon Oct 05, 2015 1:23 pm UTC

jestingrabbit wrote:
ThirdParty wrote:I did a simulation of a hundred-room 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 worst-case scenario for each strategy. vicariggio's worst 100-room 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.
emlightened's solution ignores the initial configuration of lights, and so always achieves its worst-case scenario. (By the way, for some tower sizes--1023 rooms, for example--his time is better than my worst-case time. The main virtue of my algorithm is that it usually does far better than its worst case.)

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 tiny-tower hypotheses, it reached a point where it started charging through the rest of the tower non-stop.

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.
Wouldn't it be easier to just unscrew it rather than trying to burn it out? Or are you too short?

PeteP wrote:Serious answer:
Spoiler:
I will label the first room room 1 and pick a direction and number the rooms in increasing order (I will use k for the current room number.). Then I switch the light of rooms 1-10 of and set N=10. Afterwards I will continue walking in the direction and if a light is on I turn it off and set N=k. I stop when I reach a dark room where 2*N=k, turn the light on and check if an of the rooms I have visited have light again.
I like this one! Easier to explain than mine, and also reaches a "charge through" point.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: How many rooms are there in the tower?

Postby PeteP » Mon Oct 05, 2015 3:37 pm UTC

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.

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Tue Oct 06, 2015 3:38 am UTC

Here's a solution that's approaching maximum efficiency (albeit low elegance):
Spoiler:
  1. Turn the first light on, pick a direction, and travel in that direction, turning other lights off, until we become confident (see below) that we've looped around the tower.
  2. Then turn the last light on, and then go back to verify the loop. If the loop doesn't check out, go the nearest unexplored room (turning off the light in the last explored room as we pass it), and then travel in that direction, turning other lights off, until we become confident that we've looped. Rinse and repeat.
  3. To decide if we're confident enough to turn back, compare the cost of wrongly turning back (times the estimated probability that we'd be wrong to turn back) with the cost of taking an unnecessary extra step forward. Note: you may not turn back until you've seen at least two rooms that you think you may have seen before.

Example:
  • We turn the first light on. Current state: 1.
  • We step right, finding the light on. It's possible that we're in a %1 tower, but we're not allowed to turn around yet, so we turn the light off and keep going. Current state: ?0.
  • We step right again, finding the light off. The %1 tower is still possible. The probability of seeing this configuration if we're wrong about it being a %1 tower is 1/4. The cost of wrongly doubling back is 3 steps (1 to test the hypothesis, 2 more to get back to unexplored territory). We decide to double back, so we turn the light on. Current state: ??1.
  • We step left, finding the light off. %1 tower disproven. Unexplored territory is equally distant in both directions, so we decide to head right. Current state: 101.
  • We step right twice (turning off the light in the second-to-last room as we pass it), finding the light off. Current state: 1000.
  • We step right again, finding the light on. %4 tower possible. We turn the light off. Current state: ?0000.
  • We step right again, finding the light off. %4 tower still possible. The probability of seeing this configuration if we're wrong about it being a %4 tower is 1/4. The cost of wrongly doubling back is 6 steps (4 to disprove hypothesis, 2 to get back to unexplored territory). We decide not to double back yet. Current state: ?00000.
  • We step right again, finding the light off. %4 tower still possible. Probability of this situation if we're wrong is 1/8. Cost of being wrong is 7. We decide to turn back. We turn the light on. Current state: ?0?0001.
  • We step left four times, finding the light off. %4 tower disproven. Nearest unexplored territory is to the left. Current state: 1000001.
  • We step left three times (turning off the light in the second-to-last room), finding the light on. %7 tower possible. We turn the light off. Current state: 0000000?.
  • We step left again, finding the light on. %7 tower disproven. %8 tower possible. We turn the light off. Current state: 00000000?.
  • We step left again, finding the light off. %8 tower possible but not likely enough. Current state: 000000000?.
  • We step left again, finding the light off. %8 tower still possible. Probability of being wrong is 1/8. Cost of being wrong is 11. Current state: 0000000000?.
  • We step left again, finding the light on. %8 tower disproven. %11 tower possible. We turn the light off. Current state: 00000000000?.
  • We step left again, finding the light off. %11 tower possible but not likely enough. Current state: 000000000000?.
  • We step left again, finding the light off. %11 tower possible but not likely enough. Current state: 0000000000000?.
  • We step left again, finding the light off. %11 tower still possible. Probability of being wrong is 1/16. Cost of being wrong is 15. We decide to turn back. We turn the light on. Current state: 10000000000?00?.
  • We step right eleven times, finding the light on. %11 tower proven. We halt. Final state: 100000000001000.

Comments:
  • Like jaap and unlike everyone else, I'm willing to explore in both directions rather than just one. Because there's no good reason not to.
  • I'm leaving the edge light on and all other lights off, rather than making them all homogenous like PeteP and jaap do. This is so that I never have to entertain more than one active "I may have looped" hypothesis at once.
  • I'm tending to turn back sooner than PeteP or even my previous strategy (but still much later than vicariggio or jaap). This makes the algorithm better for small towers and worse for large towers.
  • We could, and probably should, complicate things immensely by forming hypotheses about the relative probabilities of different initial configurations of lights and different tower sizes, and updating our credences in those hypotheses as we gain information. For example, if we begin to suspect that we might be in a very large tower, we should become more reluctant to double back to test small-tower hypotheses. If we begin to suspect that rooms were initially more likely to be unlit than lit, we should switch to using "unlit" to mark the edge of explored territory and "lit" to mark the interior. If we begin to suspect that an evil djinn foresaw our strategy and arranged the initial lit/unlit pattern to mess with us, we should begin randomizing the conditions that we leave explored rooms in rather than using a pattern (or partially randomizing, since we still prefer to avoid self-similar sequences; the math could get very complicated here). etc.

User avatar
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?

Postby Elvish Pillager » Mon Oct 12, 2015 3:01 am UTC

I have a simple solution that is O(n).

Spoiler:
1. set N = 2
2. Turn off the first N-1 rooms, then turn on the Nth room.
3. Go back to the first room. On your way, as soon as you see a light at room R, there are a total of (N-R-1) rooms and you're done. If you never see a light, double N and go to 2.

This is O(n) worst-case. Specifically, it takes no more than 4n moves.

EDIT: Incidentally, this is the first solution I came up with, before looking at the other answers.

EDIT: You could save about a quarter of the moves by extending the "all off" block of rooms back in the opposite direction each time, instead of repeating the turn-off operations from the previous cycle. That would be more complicated, though.

EDIT: got the number wrong by a bit. It takes up to 7n moves initially, 5n moves with the optimization.
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(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

User avatar
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?

Postby Vytron » Mon Oct 12, 2015 11:34 am UTC

Spoiler:
Okay, so here's this idea that would work for large number of rooms:

-Leave the light of your room ON, and advance 99 rooms forward, ignoring any bulbs on that you find, and turning ON any ones you find OFF. Now, move forward a room

-IF after doing this you find the next room is ON, then, start a counter that counts how many bulbs in a row are on. If 99 in a row are on, turn the last one OFF, and go back to previous rooms. If you find a light off in the previous 198 rooms, then the tower has 198 rooms or less, and they were the number of lighted on bulbs you saw in a row, plus 1. If you don't, then you're back in the starting room. Try the strategy again switching 99 for 199 and switching "forwards" and "backwards".

-ELSE IF you find at least one light off in the next 99 rooms, keep going forward increasing your counter until you find 99 lighted ON rooms in a row. Turn off the last one, and go back to the last one you turned on to see if it's off and it's over (the number of rooms is 99 plus the rooms on your counter). Otherwise, keep going back until you pass the starting room, and you find 99 rooms in a row when going back, not stopping until you see the reverse pattern of the bulbs on your counter, followed by 99 bulbs. Turn off the last one, and then go forward to see if this was the starting room, and so on.

This is bad if the rooms are less than 200, but should be good if there's, say 10000000 rooms, as you only need to visit 20000000 and you're done, unless by chance there were 99 lighted on bulbs in a row that screws you up...

User avatar
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?

Postby Elvish Pillager » Mon Oct 12, 2015 3:19 pm UTC

More optimizations, possible fastest solution?
Spoiler:
tl;dr: I think I can do it in 3.83n moves, and I'm not sure it can be done in less.



In order to finish, the player has to observe that a specific light changes when they change a light n rooms away. Since they don't know its initial state, they must observe it before doing that. So the minimum possible time is 2n – walk n rooms, flip the switch, walk back.

So, 2n is a lower bound. Since I solved it in 5n above, 5n is an upper bound. The perfect answer must be somewhere between those.

Since we need to optimize for very large n…

OBSERVATION: wandering around in previously visited rooms gives the player NO information that can be used to rule out larger possible answers. The player has visited some number of rooms R, which are all in a contiguous block. Under the assumption that (R<n), the player knows state of the lights in all of those rooms. Therefore, returning to any of those rooms gives no new information.

This suggests a solution concept: keep walking forward into new rooms, without going back to check anything. At some point, go back n rooms to confirm that there are exactly that many rooms. The only question is how to check promptly after reaching the actual n, without checking too many times erroneously.

SOLUTION:
1. Start walking forwards, leaving a distinctive but non-repeating pattern. (I suggest one room on, 2 rooms off, 3 on, 4 off, 5 on, and so on.) The important thing about this pattern is that, although you might run into fake repetitions of the pattern, they can only fake one specific value of n at a time. For instance, if the pattern was "alternate on and off," and you saw that the lights were already alternating for 100 rooms, you wouldn't know whether the period was 2, or 4, or 6, or any other even number. With a non-repeating pattern, whatever you observe pinpoints exactly one period.
2. For some constant X (let's say 2), keep walking into all there exists an N for which all the following are true:
– your observations are consistent with the conjecture (n=N), and
– you are at least XN rooms away from your starting point.
At this point, switch the light in the current room, and go back N rooms to check whether the conjecture is true. If it isn't, return to where you left off and continue walking forwards instead.

Ideally, condition 2 does not trigger until you are and exactly Xn rooms away from the starting point, so the process would take exactly (Xn+n) moves. However, a malicious initial state would try to trigger the condition as much as possible. With the chosen pattern, it can't trigger spuriously very much* after room n. If we erroneously check starting at room n, that has a move cost of 2*(n/X). In general, if the initial conditions cause an erroneous check at room XR, they can't have done so again at any point closer than room R. So the total possible wasted moves is the infinite sequence:

2*(n/X) + 2*(n/X^2) + 2*(n/X^3) + …

whose sum is 2n/(X-1). So the total cost, (ideal time + wastage), is n*(X+2/(X-1)).

The best value for X is (1+sqrt(2)), giving a total cost of (1+2*sqrt(2))n, or approximately 3.8n moves.

For a practical algorithm, spurious checks would almost never occur, so it would be efficient to use much lower value for X. The average case performance is essentially just the ideal case, (Xn+n). Choosing X=1.1 would give an average case of 2.1n moves, while still having a reasonable worst-case bound of 21.1n moves.

I keep trying to come up with a more rigorous proof for any of the claims in this post, but I haven't managed it, so there might be a clever trick that I'm missing.


*The pattern would distinguish it, but only after enough of the pattern repeats to tell the difference. Thankfully, "enough" becomes very small compared to n as n becomes very large.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

User avatar
ThirdParty
Posts: 351
Joined: Wed Sep 19, 2012 3:53 pm UTC
Location: USA

Re: How many rooms are there in the tower?

Postby ThirdParty » Tue Oct 13, 2015 12:06 am UTC

Elvish Pillager wrote:More optimizations, possible fastest solution?
Spoiler:
tl;dr: I think I can do it in 3.83n moves, and I'm not sure it can be done in less.



In order to finish, the player has to observe that a specific light changes when they change a light n rooms away. Since they don't know its initial state, they must observe it before doing that. So the minimum possible time is 2n – walk n rooms, flip the switch, walk back.

So, 2n is a lower bound. Since I solved it in 5n above, 5n is an upper bound. The perfect answer must be somewhere between those.

Since we need to optimize for very large n…

OBSERVATION: wandering around in previously visited rooms gives the player NO information that can be used to rule out larger possible answers. The player has visited some number of rooms R, which are all in a contiguous block. Under the assumption that (R<n), the player knows state of the lights in all of those rooms. Therefore, returning to any of those rooms gives no new information.

This suggests a solution concept: keep walking forward into new rooms, without going back to check anything. At some point, go back n rooms to confirm that there are exactly that many rooms. The only question is how to check promptly after reaching the actual n, without checking too many times erroneously.

SOLUTION:
1. Start walking forwards, leaving a distinctive but non-repeating pattern. (I suggest one room on, 2 rooms off, 3 on, 4 off, 5 on, and so on.) The important thing about this pattern is that, although you might run into fake repetitions of the pattern, they can only fake one specific value of n at a time. For instance, if the pattern was "alternate on and off," and you saw that the lights were already alternating for 100 rooms, you wouldn't know whether the period was 2, or 4, or 6, or any other even number. With a non-repeating pattern, whatever you observe pinpoints exactly one period.
2. For some constant X (let's say 2), keep walking into all there exists an N for which all the following are true:
– your observations are consistent with the conjecture (n=N), and
– you are at least XN rooms away from your starting point.
At this point, switch the light in the current room, and go back N rooms to check whether the conjecture is true. If it isn't, return to where you left off and continue walking forwards instead.

Ideally, condition 2 does not trigger until you are and exactly Xn rooms away from the starting point, so the process would take exactly (Xn+n) moves. However, a malicious initial state would try to trigger the condition as much as possible. With the chosen pattern, it can't trigger spuriously very much* after room n. If we erroneously check starting at room n, that has a move cost of 2*(n/X). In general, if the initial conditions cause an erroneous check at room XR, they can't have done so again at any point closer than room R. So the total possible wasted moves is the infinite sequence:

2*(n/X) + 2*(n/X^2) + 2*(n/X^3) + …

whose sum is 2n/(X-1). So the total cost, (ideal time + wastage), is n*(X+2/(X-1)).

The best value for X is (1+sqrt(2)), giving a total cost of (1+2*sqrt(2))n, or approximately 3.8n moves.

For a practical algorithm, spurious checks would almost never occur, so it would be efficient to use much lower value for X. The average case performance is essentially just the ideal case, (Xn+n). Choosing X=1.1 would give an average case of 2.1n moves, while still having a reasonable worst-case bound of 21.1n moves.

I keep trying to come up with a more rigorous proof for any of the claims in this post, but I haven't managed it, so there might be a clever trick that I'm missing.


*The pattern would distinguish it, but only after enough of the pattern repeats to tell the difference. Thankfully, "enough" becomes very small compared to n as n becomes very large.
Good analysis, and definitely in sympathy with the kinds of approach I've been pushing. However, I have a couple of notes:
Spoiler:
1. How did you add (Xn+n) to (2n/(X-1)) and get n(X+2/(X-1))? When I add them I get n(X+1+2/(X-1)). In which case the worst-case scenario for your algorithm is 4.8n moves rather than 3.8n moves.

2. I still like the "1000000000..." pattern I advocated in my previous post better than your "1001110000..." pattern. For one thing, it saves electricity. More importantly, it fulfills the "can only fake one specific value of n at a time" condition better than yours does: whereas the worst-case scenario with your pattern is that we'll perform an erroneous check at room n+2, after a previous erroneous check at room (n+2)/X+2, and so on, the worst-case scenario with my pattern is that we'll perform an erroneous check at room n-1, after a previous erroneous check at room (n-1)/X-1, and so on.

User avatar
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?

Postby Elvish Pillager » Tue Oct 13, 2015 12:18 am UTC

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(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

User avatar
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?

Postby Vytron » Tue Oct 13, 2015 12:37 am UTC

Philosophical offtopic comment?
Spoiler:
I don't like the term "malicious" when talking about an initial state. It's like, you're on a magical tower, that has N rooms, and some configuration of bulbs on and off, that will make whatever strategy you come up with return the worst case scenario?

I don't think the tower should change shape to screw you over. In my mind the best course of action will be that one that would work the best against an intelligent designer that has, previously put the bulbs in some configuration and has put as many rooms so as to make most strategies behave as worse as possible, but that doesn't know in advance what you will do.

Not necessarily the best that works on random towers.

I even wonder if this would work as a game (all players of the game would send a tower and a strategy to follow on other people's towers. The winners would be those that build the hardest towers to solve, and the best strategies for others' towers, as measured in (number of steps taken to solve)/(number of rooms).)

User avatar
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?

Postby Elvish Pillager » Tue Oct 13, 2015 1:05 am UTC

Spoiler:
It's just a way of thinking about the worst-case bounds. It's a common term when thinking about computer algorithms, even when no actual malice is involved.

I also don't like your suggestion because it would make the puzzle much, MUCH more complicated. To even begin thinking about the best strategy for either player, we would have to agree upon some things that aren't specified in the puzzle. Either we have to agree on a probability distribution for the initial number of rooms, or – if the designer chooses the number of rooms – we have to agree upon a way to compare scores across different numbers of rooms. Neither of those has an obvious answer. And if the designer chooses the number of rooms, there might also be some issues about the infinite collection of choices (there might not be any Nash equilibrium even with mixed strategies).

Sure, we could settle on a set of rules, and then it would be interesting as a game. I don't think it would be interesting as a puzzle, though, in the same way that "solve Chess" isn't a good puzzle.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: How many rooms are there in the tower?

Postby Cradarc » Tue Oct 13, 2015 4:28 am UTC

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:
Spoiler:
Let P(n,k) be a symmetric pattern of length n, with ID number k that uniquely identifies it.
Pick one direction to be clockwise = CW and another to be counterclockwise = CC

1. Find or artificially construct some pattern P(n,0).
2. Create a buffer with size n initialized to 0. The buffer has the property that every time you push a bit in, the oldest element gets dropped. Start your room counter.
3. Step CW, pushing the data of every room into the buffer. When you leave a room, set it to 0 (ie, make the lights be off).
4. Immediately before leaving every room, check if your buffer contains P(n,0).
5. Let's say this happens after m rooms. After making note of this, you reset your room counter
6. Define a new pattern P((2n+m),0) such that the last n values and the first n values are P(n,1). P(n,1) is distinct from P(n,0) by definition.
7. Walk CC and write over your path with the new pattern. When you are done, your buffer should contain either P(n,1) or P(n,0).
8. Since the buffer data is pushed before you make changes to each room, it should contain data that occurred prior to your overwrite. If it contains P(n,1), you know it must have been overwritten from m rooms before. This means the total number of rooms is m+n.
9. If the buffer contains P(n,0), you must continue in the CC direction. However, you must now flush your buffer and expand it to size 2n+m.

10. Your situation is now very similar to the situation at the beginning of step 3!
11. Repeat the same process, updating your buffer upon entering a room, and zeroing out every room when you leave.
12. When you find P((2n+m),0), change directions and overwrite with a new symmetric pattern, P((2n+m),1).
13. Once you get back to where you were at the end of step 5, you can check your buffer to see if it contains P((2n+m),1) or P((2n+m),0).
etc.

Because the marker pattern (at minimum) doubles in size every time you backtrack, you exponentially decrease your chances of encountering a match that isn't the exact same rooms.

Large N Time Analysis
Let some initial point on the circle be S0. If you construct a pattern, p1, of length n, it will span S0:S(n-1).
In the worst case scenario, the next detected copy of p1 will span Sn:S(2n-1).
This will trigger a change in direction, and construction of a new pattern, p2, of length 2n. spanning S(2n-1):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 +...2k-1n = n(2k-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 2k-1n 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:
2k-1n > N/2
k > log2(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) = 2N-1. The verification bit adds some number between 1.5N and 2N. Thus, for the worst case scenario, we have 3.5N-1 as the minimum bound and 4N-1 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 > log2(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.

User avatar
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?

Postby Vytron » Wed Oct 14, 2015 10:27 pm UTC

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.)

User avatar
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?

Postby Elvish Pillager » Wed Oct 14, 2015 11:41 pm UTC

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.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: measure and 7 guests