wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Let There Be Circular Light.
        
(Message started by: rloginunix on Mar 16^th, 2014, 10:45am)

Title: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 10:45am

Let There Be Circular Light.

Once upon a time Uber Puzzler woke up hearing a disembodied voice from above:

- I am a disembodied voice from above. And you, Uber Puzzler, are deep in the underground bowls of Berkeley University in the Circle of Passage. The circle consists of N identical empty rooms connected to each other via corridors. Each room has a switch connected to an unreachable but clearly visible light. Flip the switch on and the light turns on. Flip the switch off and the light turns off.

- At first there was darkness ...

- Then, using my awesome powers of randomization, I turned the lights on in some rooms in a random pattern unknown to you.

- Using only the lights and their switches tell me the number of rooms in the Circle of Passage.

Some time later Uber Puzzler obtained correct N (in an eco-friendly way).

How did (s)he do it?

[edit]
Got rid of confusing "reasonable time" and O(N) in the problem statement.
[/edit]

Title: Re: Let There Be Circular Light.
Post by gotit on Mar 16^th, 2014, 10:57am

First Pass: Turn off all the lights.
Second Pass: Turn on the lights and count the rooms until you reach a room that is already lighted.

You may ask how the Uber Puzzler knew that all the lights had been turned off. I would say (s)he did that by spending a reasonable amount of time going around the completely dark circle.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 11:16am

If you read your first sentence carefully, "First Pass: Turn off all the lights", there is one word in it that introduces a contradiction.

Which word is it?

Title: Re: Let There Be Circular Light.
Post by gotit on Mar 16^th, 2014, 11:28am

Ok...You can't be sure that you have finished the first pass until you are sure that you have turned off all the lights...So I ll put it differently..

Spend reasonable amount of time going around the circle and turning off the lights until you are reasonably sure that all the lights are turned off...

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 12:00pm

Please don't get me wrong - I'm just trying to steer you towards a correct solution.

1). The reason "reasonably sure" isn't going to work is because of the randomness of the on/off pattern which is not known ahead of time - it may very well so happen that while walking the Circle of Passage you will hit a number of dark rooms in a row that may make it look like you've turned off "all" the lights. But the algorithm is absolutely deterministic - it guarantees the room count with absolute certainty. No guessing and no luck is involved.

2). The problem statement "Some reasonable amount of time later ..." means that in a reasonable amount of time Uber Puzzler has found the algorithm first and obtained the actual N later. Sorry if I made it less clear than it should've been.

3). "All" in "all the lights are turned off" assumes the knowledge of N ahead of time, in which case there's no need to make any passes at all - just tell the disembodied voice from above the answer.

[hide]When you look at your drawings you have a bird's eye all-at-once wholesome view of the Circle of Passage and that affects your thinking. However, Uber Puzzler in the Circle of Passage doesn't have that view[/hide]. (S)he doesn't know how many rooms are there.

[edit]
I've updated the problem statement to avoid the confusion. My apologies.
[/edit

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 16^th, 2014, 12:19pm

Start walking one way and make a pattern. I would choose some really difficult pattern, but since random is random, switching all lights on is also good enough (btw. why would someone try to swith OFF all the lights, when you can switch ON all of them - much more friendly).
When you already suspect that you reached the starting point, switch one lamp off and go the other way. If after n steps you find a light switch off, it was indeed the one you switched off. If is still on, then it was a misleading repetition of pattern, so you need to continue again.
I am not sure it is O(N), but so far the best I can think of.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 12:40pm

jollytall, I think you started seeing the light ...

Again, my apologies, guys. Wording and typing problems is hard. God knows I'm trying. O(n) is not the first degree polynomial. It's just a notation. An asymptotic behavior of some yet unknown function of the number of rooms when that number is large.

jollytall, "really difficult pattern" may very well coincide with the random one chosen by the disembodied voice from above. Also, in "switching all the lights on" the word "all" is the problem. If "all" is known then just give it as the answer.

But your answer does contain a portion of the algorithm. Be more specific.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 16^th, 2014, 1:39pm

This is why I wrote all ON is as good as a complex pattern.
All means all I have visited.

e.g. I switched on 500 lamps and then I see a sequence of on more than another let`s say 1000 on then I switch one off and turn back. I should find it in more than 500 steps but less than 1500. If I need to go back more than 1500 then it is not a real finding, so I can do it again (using these 1500 steps as the starting).

Title: Re: Let There Be Circular Light.
Post by towr on Mar 16^th, 2014, 1:46pm

I don't see what the problem with Jollytall's solution is

You turn on some improbable pattern of lights (like, turn everything on that you encounter), and walk/count till you find a place that looks like the start of your pattern.
Change the (suspected) start in an identifiable way, and walk back as many lights as you've counted. If the (actual) start has changed then you've got the right count.
Otherwise, walk back to the not-actually-the-start-of-your-pattern, and continue walking/counting while continuing your pattern.
Rinse&repeat till you achieve a glossy shine.

[e]I wish I could write faster[/e]

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 2:16pm

You, guys, are getting closer and closer. I just have to guide you carefully towards the intended solution.

OK, let's see. "Improbable" still involves a degree of luck. If Uber Puzzler's plan is to turn all the encountered lights on then what if all the lights are on to begin with? Uber Puzzler doesn't know the pattern ahead of time. If the plan is to turn all the lights off then may be they are all off to begin with.

The algorithm should consist of some number of statements that work no matter what N and the initial on/off pattern is. Step 1, step 2, step 3, ...

Uber Puzzler doesn't know that, but let's assume we do. There are 5 rooms in the Circle of Passage and the lights in all of them are initially on. According to jollytall's algorithm we do 100 circles to make sure we count 500 lights that are on. What should we do next?

[edit]
Addition: "and the initial on/off pattern".
[/edit]

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 16^th, 2014, 2:48pm

why would I make 100 rounds? If after 5 rooms (where I had to switch on few) I see a sufficiently long pattern (I would go another 10) I would turn back already.
You might want to turn back immediately when you have the right to think that you are around. That is as soon as you have one unvisited on. It might be a bit zig-zaggy, why I would wait a bit more.
Interesting question if the initial state is really random, what is the optimal number of ONs before turning back.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 3:41pm

on 03/16/14 at 14:48:08, jollytall wrote:

why would I make 100 rounds?

I'm just trying to steer you towards framing your good observations into a working algorithm. Earlier you said 500 - I used 500. Now you are saying "If after 5 rooms ...". I will use 5. Say, there are 3 rooms in the Circle of Passage ... Problem is Uber Puzzler, boots on the ground, doesn't know there are 5 rooms in the Circle of Passage. (S)he needs to find it.

You are almost there. One of your sentences is dead on. You've hit the nail on the head: "[hide]You might want to turn back immediately when you have the right to think that you are around[/hide]".

Try putting your solution down as a working algorithm that we can apply to any N and any, truly random, initial distribution of lights. The actual algorithm works exactly that way - no assumptions.

So (for a hypothetical example):

Step 1. Walk 5(?) rooms in a given direction. For each room: if light is off then turn it on.
Step 2.
...

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 4:14pm

Some snippets of my search. I went through roughly the same motions as you guys (it just took me longer). When I realized nothing is working I said "forget it. Let me see if I can solve this problem if there is [hide]only 1 room in the Circle of Passage. What do I have to do to make sure that I can with absolute certainty say that yes, I am back in the room #1 and not the second room of a 2-room circle that happened to have the same state of the light? Once I cleared that up I moved on to a 2-room circle. How can I be sure that I am back in the anchor room of a 2-room circle and not the 3-rd room of a 3-room circle which happened to have the same state of the light? By the time I did that with a 4-room circle I started seeing the light[/hide].

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 16^th, 2014, 6:04pm

OK, how about this.

If we define "one step" or just "step" as a walk from one room to the next then could you express the number of such steps your algorithm takes in terms of the total number of rooms in the worst case - for consistency sake. Worst case means that all the lights are always in the least convenient state and you always have to do something with them. The algorithm should of course work in the non-worst case scenario just the same, perhaps taking less steps.

Basically, formalize your algorithm. For an arbitrary integer n come up with a worst case function S(n) which can be used to calculate (without actually walking) the number of steps for any m != n. So that when we plug an arbitrary room count into the function we get the actual worst case step count. Using totally made up, off the wall, not real numbers for demonstration purposes: S(1) = ... = 1, S(2) = ... = 2, S(3) = ... = 3, and so on.

If you try doing that I think you'll see what I mean.

[edit]
Also, guys, don't forget about the hint built into the problem statement: "(in an eco-friendly way)". [hide]When it comes to light bulbs which one of its two states is eco-friendly[/hide]?
[edit]

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 16^th, 2014, 10:51pm

I think you missed my point. You can always do the turning back "immediately" logic. E.g. go right 1 OFF, so SWITCH to ON. Next one to the right ON, so you assume you are already back, i.e. TURN OFF and go backwords. Room 1 disappointment, because still ON. Continue left. Next room (the n-th) is OFF. So now you are potentially happy (and turn ON), but not sure. Make one more to the left (n-1). DIsappointment, because that is still OFF (so turn ON again) and continue. NExt one (n-2) is ON. Now you are really happy thinking n-1=2 and n-2=1. So you turn it OFF and go backwords. And so on.
If n is really large, then you have a lot of turning back. Worst case you turn back every room (Think a ring where you are in the 1st and the sequence is (oFf and oN):
FNNNNNNNN.....NNNNNNNNF.
The total number is in the range of n²/2, what is not O(N).

This is why I wrote earlier to use a longer reassuring sequence (e.g. twice the thought - meaning first suspcted - ring length).

It is a nice question to assume the optimal length of the reassuring pattern in case of a total random starting state.

Title: Re: Let There Be Circular Light.
Post by gotit on Mar 17^th, 2014, 12:15am

on 03/16/14 at 16:14:17, rloginunix wrote:

For 1 room:
Room 1 : TURN ON if OFF.
Go To ROOM 2, which is actually ROOM 1.
TURN OFF (it will definitely be ON).
GO BACK to the previous room.
If it's on, there are more than 1 rooms. Else there is only 1 room.

For 2 Rooms.
Room 1 : TURN ON if OFF.
Go To ROOM 2.
TURN OFF if ON.
GO BACK to the previous room (ROOM 1).
It will be definitely ON. So there are at least 2 Rooms.
Go to room 3 (which is actually ROOM 1)
Turn OFF (it will definitely be on).
Go Back 2 rooms. If it is OFF, there are 2 rooms. Else there are at least 3 rooms.

Title: Re: Let There Be Circular Light.
Post by towr on Mar 17^th, 2014, 12:17am

You can avoid turning back at every room in the worst case, by doubling or tripling (or ntupling) the range of rooms you explore each iteration. (Although it's quite improbably you'd need to if the initial pattern is random.)

How about:
* go right X rooms turning the lights off
* turn the last light on
* go X rooms left (stumbling in the dark, cursing under your breath),
** if you encounter a light that's on, then you know you've gone gone a full circle, and how long that circle is.
** otherwise go 2X+1 rooms further left while turning lights off; set X=3X, swap(left,right), goto 2.

Title: Re: Let There Be Circular Light.
Post by gotit on Mar 17^th, 2014, 12:23am

In General

Turn ON Room 1.
Go ahead until you find another room with light ON. Let's say you find it after k Steps.
Turn if Off.
Go back k steps to Room 1. If it is ON, there are at least k rooms. Else there are k rooms.
Next, move ahead until you find a lighted room (say m > k).
Turn off and move back m steps to room1.
If it is off, there are m rooms. Else there are at least m rooms.
Continue till you find n

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 17^th, 2014, 12:46am

As my son has just pointed out; my above zig-zag strategy is not even the most aggressive, it already had an element of optimisation (confirmation) in it. When after 1 and 2 and turning back I reach the n-th (and find it OFF), then I might already think that that is the 2nd and without validating that n-1=1 or not, can turn it ON and going back to check number 2 (whether it became ON from the last OFF).
In the worst case scenario it is still O(n²), the only difference is that the worst pattern is:
FNNNNNN .... FFFFFFFF. (Right the token lamp is ON, left it is OFF).

Regarding the optimal solution, I still think that the immediate turn back is far from optimal. The zig-zag is essentially walking one suspected ring and as soon as it can be a ring (without any more confirmation) turn back and validate the ring.
My recent one had at least one more confirming step (to n-1) in it, filtering out when n-1 was also OFF.
My gut feel tells me that at least one confirming ring would make sense. If it is finally the real ring then I make n extra steps (i.e. the last steps are not n+n, but n+N+n), but save a lot of zig-zaging. Imagine a 100 long ring. In the zig-zag logic, I would make randomly about 50 turn backs (n²/4 steps), worst case n²/2. In the new logic, even if the original distribution is the worst possible, I make steps about 1+3+7+15+31+...+100+100+100 bringing the total number of steps down to O(N) (about 3*N).
The real question to me now, whether one full or only half or (as I originally suggested) two full confirming cycles are used in the optimal case if the initial distribution is random and n is large. As N turns large, we might reduce the confirmation ring to less than a full ring. E.g. In case of N=100, we might turn back after let's say 20 confirmation steps, leaving a one per million chance that we made it early.
The same question for the worst initial distribution.

Edit: I started to write like an hour earlier, but could not push "Post". So sorry for some elements of duplication.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 7:13am

Good morning, guys. I just woke up and need to go buy some milk for my coffee so that I can think straight.

You basically got it. Didn't have the time (but I will) to analyze your latest answers in all the details but I feel that "gotit" got it closest to what I had in mind. I would put the algorithm thus:


Step 1. Pick a room, any room.
 Call it a Marker room.
 If the light in the Marker room is off then turn it on.
 Pick a direction, any direction - say, clockwise.
 Set RoomsVisited = 0.

Step 2. Go clockwise into the next room.

Step 3. Got there.
 Increment RoomsVisited by 1.

Step 4. If the light in that room is on then
{
  turn it off and 
  walk back RoomsVisited corridors (steps).
  This will put you back into the Marker room.
  If the light in the Marker room is off then
  {
    you turned it off RoomsVisited steps ago
    which means you've made full circle and
    You are done: RoomsVisited is the answer.
  }
  else
   /* Didn't make the full circle yet. Start all over again. */
   Set RoomsVisited = 0
   go to step 2. 
}
else
{
  /* The light in the current room is off - keep going. */
 go to Step 2.
}

Sorry for the small text. I'm going blind trying to read it myself. Not sure how to make it bigger.

Anyway, above algorithm works for any however random initial distribution of light states.

By the end of this procedure all the lights will be off which is eco-friendly. The process is symmetrical in reference to the state of the light - you will get the same answer if you flip the states to their opposites in the algorithm above. If you keep the light in the Marker room off then in the next room you will turn the light on if it's off. By the end of this process all the lights will be on. Not very eco-friendly.

To come up with a formula for the worst case scenario we can do some small number of pen and paper calculations for 1, 2, 3, and 4-room circles. I numbered the rooms in the clockwise fashion. Marker room is always at 12 o'clock and I numbered it as 1. The number in parenthesis is the number of times that room is visited:

1-room circle: 1(2) = 2
2-room circle: 1(3) + 2(3) = 3 + 3 = 1 + 2 + 3 = (1 + 3 ) + 2 = 6
3-room circle: 1(4) + 2(5) + 3(3) = 4 + 5 + 3 = 1 + 3 + 5 + 3 = (1 + 3 + 5) + 3
4-room circle: 1(5) + 2(7) + 3(5) + 4(3) = 5 + 7 + 5 + 3 = (1 + 3 + 5 + 7 ) + 4

You can see that the pattern emerges: S(N) = N^2 + N = N*(N + 1) since the sum of first N odd integers is N^2. Then we get worst case O(n) = N^2.

Please let me go do my morning routine and I will be back to think about towr's and jollytall's replies in depth.

[edit]
Made the algorithm's text size bigger. Thank you, towr.
[/edit]

Title: Re: Let There Be Circular Light.
Post by towr on Mar 17^th, 2014, 8:51am

on 03/17/14 at 07:13:06, rloginunix wrote:

Sorry for the small text. I'm going blind trying to read it myself. Not sure how to make it bigger.

 You can use the size tag.

Quote:

You can see that the pattern emerges: S(N) = N^2 + N = N*(N + 1) since the sum of first N odd integers is N^2. Then we get worst case O(n) = N^2.

That's rather inefficient. You can get a linear run-time.
And I don't quite understand the way you're using O(n); big-O notation (http://en.wikipedia.org/wiki/Big_O_notation) has a meaning that doesn't fit your usage.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 10:43am

Want to clear one thing up real quick. I hope I didn't offend anyone with my replies. I've never done this before and I'm not trying to torture anyone. The goal of my replies is to make sure you derive the same pleasure from your deductions as I do. If you don't like something in my style - let me know, I will adapt.

on 03/17/14 at 08:51:48, towr wrote:

And I don't quite understand the way you're using O(n); big-O notation (http://en.wikipedia.org/wiki/Big_O_notation) has a meaning that doesn't fit your usage.

Yes, I'm an idiot. I confused myself and everyone else. Problem is I'm not sure what to put down as a question: "find the big oh", "find the asymptotic behavior of your function when the argument tends to positive infinity"? What's the best short and sweet that will not confuse anyone and convey the correct meaning?

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 10:44am

jollytall, I've looked at your algorithm. I think all in all it's almost the same but I have a couple of questions.

on 03/16/14 at 22:51:18, jollytall wrote:

Trying to put it in an algorithmic way for, say, a 3-room circle. Stars are rooms with the room numbers next to them:

*1
*3 *2

When you say "go right" - right relative to what? I'm assuming a marker room. What is the state of light in the marker room? I'm assuming you make sure it's off. Step right once - we are in room 2. If light in room 2 is off - switch it on and move on. Step right once more - we are in room 3. If light in room 3 is on then turn it off and step back once - we are in room 2, light is on. Step back once more - we are in the marker room, room 1. Light is off here. Turn it back on. Done. Now the state of lights is: 1 - on, 2 - on, 3 - off. Next. Step left once - we are in room 3. Light is off here. Turn it on. State: 1 - on, 2 - on, 3 - on. Step left (?) once - we in room 2. Light is on here. Turn it off ...

I see what you are trying to do. All in all you are correct but I think you are overshooting once you reach the marker room and trying to step left. At what point do we stop?

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 10:46am

towr, I've looked at your suggestion:

on 03/17/14 at 00:17:50, towr wrote:

How about:
* go right X rooms turning the lights off
* turn the last light on
* go X rooms left (stumbling in the dark, cursing under your breath),
** if you encounter a light that's on, then you know you've gone gone a full circle, and how long that circle is.
** otherwise go 2X+1 rooms further left while turning lights off; set X=3X, swap(left,right), goto 2.

Your overall idea is also correct. But I think turning the light on in the X-th room will make it difficult distinguishing it from the marker room.

Using a 5-room configuration let's fix X at 2. From the marker room we step right once - turn the light off in room 2, step right once more - we are in room 3. Turn the light on in room 3. Step back twice - we are in the marker room where the light is on or off? Not sure. Let's say it's on. If I read your algorithm correctly you're saying we've made full circle if that light is on but we've visited only 3 rooms so far. Also, how do we choose the value of X?

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 11:42am

Here is how I did my worst case counts. 3-room circle. Initially all the lights are on (worst case for this scheme):

In the marker room, light is on. Step right once. Room 2, turn light off, set visits = 1. Step back once. Marker room, set visits = 1. Light is on - not done yet.

Step right once. Room 2, light is off, visits = 2. Step right once. Room 3, turn light off, visits = 1. Step back once. Room 2, visits = 3. Step back once. Marker room, visits = 2. Light is on - not done yet.

Step right once. Room 2, visits = 4. Step right once. Room 3, visits = 2. Step right once. Marker room, turn light off, visits = 3. Step left once. Room 3, visits = 3. Step left once. Room 2, visits = 5. Step left once. Marker room, visits = 4. Light is off - we are done. Total number of visits (or steps):

S(3) = 1(4) + 2(5) + 3(3) = 12

It's tedious but you see exactly what's going on with the steps or visits to each room as the count progresses.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 17^th, 2014, 12:16pm

rloginunix:
There are quite a number of solutions on the table.

1. Your solution
for i=1 to n do
Go right (or clockwise, whichever you prefer) i steps. Turn all lights from 1 to i-1 into A state (e.g. OFF). If the last is A then turn it into B state (in the example ON), otherwise just go on to i=i+1.
If you change the i-th from A to B, then go back to the first room. If it is in B state then n=i solution found.
Otherwise continue with the next i.
As towr pointed out and I also mentioned in my quoted post, it is a very inefficient solution with O(n²).

2. My real turning back immediately solution (after my son's comment)
It is similar to yours with one important change. In the loop I choose the next i. I go right i steps. If it is in B state, then turn it into A and go to the next room. If it is in A state then turn it into B and go back to the marker room as you call it. If it changed from A to B, then i=n, job done.
Now is the change compared to your solution. Now I redefine the marker room from the 1st room to the i-th room, and instead of going "right" or clockwise, I go left, i.e. counter-clockwise. I also change the definition of the states, so A and B states swap (marker room initial state is now B, not A).
With this logic I can cut the walking half, it is still O(N²), but only the half of yours.
The worst case login is xAAAAA.....BBBBBBB (small letter indicates the original first room, its status is irrelevant at the beginning).
After the first step I have aAAAA... so I make aBAAA... and turn back. Sine the original marker room is still A, so n>1. Now I go left and find
BBBaBAAA. I am happy to think the B is the new marker. I make it A: BBAaBAAA, hoping that the first to the right will now be A. Etc.

3. My original turning back immediately.
It is the same as solution 2, but by mistake I did not turn back immediately, but made one more step. That is a sort-of reassuring step. If - as per the solution 2 - I think I found the marker room, I make one more step, thus making more certain. That can help avoiding a lot of fake turning back (statistically every second). This brings down the expected number of steps to about n²/4. I mentioned in the Post you quoted that this is still O(n²), with about n²/2 worst case.

4. My original solution
Similar to the above, but if in the i-th step the i-th is in state A, I do not turn back immediately, not even from the next room, but made 2*i more steps into the same direction. This is really reassuring. I can exclude statistically all fake turning backs. If during the 3*i steps I realised that I am not around yet, then I choose a larger i where the pattern is still OK. With very limited turning back (this is why I would choose a random pattern instead of all ON, so there is no easily a matching pattern generating a false turning back), I will have slightly more than 4*n steps (3*n forward, 1*n backwards). This is O(n).

5. towr solution
It is also a kind of doubling logic. It does not check the status of the lamps in the room it goes into, it only mechanically turns them. That is sub-optimal compared to solution 4, because it turns back after X steps even if it is sure that it cannot be a circle yet (e.g. all the lights are on. It switches X OFF, last one ON. But it cannot be a circle, becuase the lamp would be OFF. Being all ON means that there was not around yet, so it is better to go on. Nonetheless 1+3+9+... and the last +n backwards also O(n).

6. My thinking on the optimal number of extra rooms. In solution 1 and 2 these are 0, in solution 3 it is 1 and in solution 4 it is 2*i. The question where is the optimum? If the number of reassuring steps is less than i (let it be j), then when I realise that it is not a real curcle yet (that is when I go back from i+j to j and j-th did not change), it is still better to continue "left" because that end is closer. If j>i and I got disappointed, then I can actually go again right, since that end is closer than the other.
I can choose j as a fix number (0 or 1 in the above examples), as a multiplier of i (e.g. 2*i in my solution), or towr's logic of fixed i+j, or it can be a smart logic: for small i-s use j=2*i, for larger i-s start to reduce j-s far below i (e.g if we choose at one point j=20 that gives a 1/1M chance of a false turn back). With basically eliminating false turnbacks we can go down to 2*i+j+ a little for the false turnbacks. I would assume we can do statistically between 2*n and 3*n steps.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 17^th, 2014, 12:38pm

And a bonus question. What if it is not circular?

Let there be an underground shelter with rooms and corridors connecting the rooms. To make it easier, all rooms have a flat surface and doors are on the perimeter of the rooms. Every room has a switch and a lamp. No other sign, etc. Can you map the shelter?

Title: Re: Let There Be Circular Light.
Post by towr on Mar 17^th, 2014, 1:57pm

on 03/17/14 at 10:46:24, rloginunix wrote:

Using a 5-room configuration let's fix X at 2. From the marker room we step right once - turn the light off in room 2, step right once more - we are in room 3. Turn the light on in room 3. Step back twice - we are in the marker room where the light is on or off? Not sure. Let's say it's on. If I read your algorithm correctly you're saying we've made full circle if that light is on but we've visited only 3 rooms so far. Also, how do we choose the value of X?

You're right that there's an error there. But that's easily fix by using only the 'should-be-off' rooms to check for the circle (so not the "marker" room).
The value of X doesn't particularly matters, what matter is that you pick some maximum ring-size to check, check it, and if the check fails choose a sufficiently larger size to check so it offsets the work you've already done; keeping the solution linear.
And as jollytall says, that can easily be optimized further.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 17^th, 2014, 6:35pm

OK, guys. The linear solutions, that you have found, are hands down better than what I came up with. Interesting thing mental inertia. I found one solution and a small improvement to it and thought that was it. I've got stuck with this fixed marker room idea. Live and learn. At least It's a good thing I've put Uber Puzzler in charge of the problem.

For completeness sake my small optimization can be called "right-left flip-flop" and is only somewhat similar to jollytall's #2 solution even though it's not a good fit of course.

Say it's a 5-room circle. Start with a marker room 1 and turn the light on. Step right once. If in room 2 light is on - turn it off and go back to the marker room, at which point instead of stepping right twice step left once. If the light in room 5 is on - turn it off and go back to the marker room, at which point instead of stepping left twice step right twice and so on.

If, going in either direction, you come into a room where the light is off - keep going. This is almost the same as my original algorithm but instead of always going clockwise this one flips the direction to the opposite every other iteration in the worst case.

This cuts the number of steps somewhat but for large Ns it is still of course an inefficient O(N^2).

Title: Re: Let There Be Circular Light.
Post by rmsgrey on Mar 18^th, 2014, 7:25am

on 03/17/14 at 18:35:06, rloginunix wrote:

When you go to room 5, you know it's room N and that N is at least 2, so if you find the light on there, you know that it isn't room 2 (where the light is off) so N must be at least 3...

The most generic solution:

State 1: Exploration
Keep going in one direction, leaving a known pattern behind you (either because you've seen it or because you're setting it up). When you encounter a room that could be the start room of the pattern, change to State 2.

State 2: Suspicion
Keep going in the same direction, still leaving a known pattern behind you, until either you check a certain number of rooms (dependent on the length of the potential loop) or you find a room that doesn't fit the earlier pattern.
If you find an anomaly, then check whether any of the rooms you visited in State 2 could be the start room of the pattern; if so, continue in State 2 as though you'd entered State 2 in the earliest room that could still be the start room. If none of the rooms could be the start room, return to State 1
If you visit the allotted number of rooms without finding an anomaly, change to State 3

State 3: Verification
Change the light in the last room visited, then turn around and backtrack until either you find an anomaly, or you've retraced the entire known pattern.
If you find an anomaly, you're done - either it matches the change you made and you've gone round one loop since entering State 3, or it doesn't match the change you made, and the task is impossible.
If you retrace the entire known pattern, then reverse the pattern and change to State 1, continuing into unknown territory from the new endpoint.

No matter what pattern, P(i), you choose, there's the same chance that, for some n, the initial room state, R(i), satisfies R(n+i)=P(i) for i in [1,k(n)] where k(n) is the number of rooms you visit to confirm a suspected loop of length n, so, in that respect, it doesn't matter what pattern you choose - turning everything off is as good a pattern as any other, assuming you can keep count accurately.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 18^th, 2014, 2:45pm

Isn't it the same as the above #4? I do not see the difference.

1 Go and make or leave a pattern. (if the original pattern is not random but left intentionally, then making a random pattern is definitely better than leaving the original, otherwise a misleading pattern with lots of false suspicions can be generated).
1 Start to suspect if you find what is the first room status left, but go on to get sufficient confidence.
3 If during that confidence part it fails then choose a larger number where you can suspect (worst case where you are). If you have enough confidence then make a change and go back the suspected distance.
4 If that is indeed changed then solved. If not then you need to work on. Depending on how long the reassuring phase (more or less than the suspected i) was, you either should go again the original direction or go the opposite.

The qusetion to me is still how long the reassuring phase should be. Should it be a function of the suspected i lenght (e.g. 2*i or 1*i or even log(i)) or should it be a fixed number (e.g. 20).

Title: Re: Let There Be Circular Light.
Post by rmsgrey on Mar 19^th, 2014, 5:44am

on 03/18/14 at 14:45:58, jollytall wrote:

4 If that is indeed changed then solved. If not then you need to work on. Depending on how long the reassuring phase (more or less than the suspected i) was, you either should go again the original direction or go the opposite.

Okay, I suppose there are cases where you only have the one candidate loop to check, and gone several times its length as reassurance - I was only thinking of the cases where you have multiple candidate loops going and one pass checks them all...

And, yeah, it's not a novel solution - more of an attempt to formalise the family of plausible solutions.

Title: Re: Let There Be Circular Light.
Post by rloginunix on Mar 19^th, 2014, 8:31am

on 03/18/14 at 14:45:58, jollytall wrote:

The qusetion to me is still how long the reassuring phase should be. Should it be a function of the suspected i lenght (e.g. 2*i or 1*i or even log(i)) or should it be a fixed number (e.g. 20).

When TCP/IP writes the packet it's first confirmation timer is tight. If it didn't get confirmed quickly then the timer interval is increased. If that one expires then the next one becomes even longer and so on. Don't hold me to this but if memory serves me right IP timers are exponential - they have to deal with a difficult issue - using one parameter only - time - decide if the other host is dead (or some such). Wait 5 hours and kill the connection only to see the other host becoming available 5 hours and 1 nanosecond later. Too bad. If you've missed the train by 1 minute - you've missed the train.

Here the situation is similar - we have only one parameter - number of times our suspicion went unconfirmed so far - to decide on the number of reassurance steps. Similarly, it could be a one-room circle or one million-room circle. So the gist of this function is "I'll start kinda low but then, as more suspicions go unconfirmed, become reasonably more aggressive".

So towr's f(X) = 2X + 1 can be made reasonably more aggressive as f(X) = 2*X*S + 1, where S is the number of suspicions that didn't pan out so far. Of course Uber Puzzler must keep track of this variable.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 19^th, 2014, 1:30pm

on 03/19/14 at 05:44:31, rmsgrey wrote:

I was only thinking of the cases where you have multiple candidate loops going and one pass checks them all...

Now I see your point. Let's say I made 20 steps where I noticed that repetition started. I make 20 reassuring more steps and change the 40th. Checking the whole 40 pattern, I also find that after 30, the remaining 10 is also a repetition of the first 10 and also the last 3 are the repetition of the first 3 and the last one is the repetition of the last one.
My solution ws to change the 40th and go back 20. If that is not the changed one, either go forward or backwards (20+20 is the border where forward and backward is the same). Your logic is that it might still be a 30 or 37 or 39 long loop, so it is much better to continue backwards rather then forward. If no change till the first room then you can still continue in the same direction, using the changed room as the starting point.
I think it is a great observation.

Title: Re: Let There Be Circular Light.
Post by jollytall on Mar 19^th, 2014, 1:39pm

on 03/19/14 at 08:31:23, rloginunix wrote:

So towr's f(X) = 2X + 1 can be made reasonably more aggressive as f(X) = 2*X*S + 1, where S is the number of suspicions that didn't pan out so far. Of course Uber Puzzler must keep track of this variable.

I am not sure it is smart. By the time S reaches e.g. 3, probably i is already e.g. 50 (guessing). It would mean that you take a 300 long reassurance. If it is random (you made the first 50 such) then the chance of 300 elements being right is 1/2^300. Far too low to worth the effort.
I would rather go the other direction. If i is already large (e.g. 1000) then it might be enough to take 10 reassuring step to get a 1/1000 chance of making a 1000 step back. If we take 20 reassuring steps then we have a 1/1M chance to go back 1000 step. I would rather take that (1 extra step expected value) then walk 2000-6000 more steps (2000-6000 expected value). This is why I suggested some log2(i) like reassurance.

Title: Re: Let There Be Circular Light.
Post by rmsgrey on Mar 20^th, 2014, 8:25am

on 03/19/14 at 13:39:24, jollytall wrote:

I've not calculated it, but my immediate intuition is that having a sublinear reassurance will make the asymptotic worst-case time superlinear...

Mind you, once you're going 1000 steps, you'll be wanting supplies even if there are no false leads and no reassurance steps...