Author |
Topic: Let There Be Circular Light. (Read 2989 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
Re: Let There Be Circular Light.
« Reply #25 on: Mar 17th, 2014, 12:16pm » |
 Quote  Modify
|
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(n2).
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(N2), 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 n2/4. I mentioned in the Post you quoted that this is still O(n2), with about n2/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.
|
|
 IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #26 on: Mar 17th, 2014, 12:38pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Let There Be Circular Light.
« Reply #27 on: Mar 17th, 2014, 1:57pm » |
Quote Modify
|
on Mar 17th, 2014, 10:46am, 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.
|
| « Last Edit: Mar 17th, 2014, 1:58pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #28 on: Mar 17th, 2014, 6:35pm » |
Quote Modify
|
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).
|
| « Last Edit: Mar 17th, 2014, 10:04pm by rloginunix » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: Let There Be Circular Light.
« Reply #29 on: Mar 18th, 2014, 7:25am » |
Quote Modify
|
on Mar 17th, 2014, 6:35pm, rloginunix wrote: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). |
|
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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #30 on: Mar 18th, 2014, 2:45pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Let There Be Circular Light.
« Reply #31 on: Mar 19th, 2014, 5:44am » |
Quote Modify
|
on Mar 18th, 2014, 2:45pm, 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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Let There Be Circular Light.
« Reply #32 on: Mar 19th, 2014, 8:31am » |
Quote Modify
|
on Mar 18th, 2014, 2:45pm, 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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #33 on: Mar 19th, 2014, 1:30pm » |
Quote Modify
|
on Mar 19th, 2014, 5:44am, 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.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Let There Be Circular Light.
« Reply #34 on: Mar 19th, 2014, 1:39pm » |
Quote Modify
|
on Mar 19th, 2014, 8:31am, 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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: Let There Be Circular Light.
« Reply #35 on: Mar 20th, 2014, 8:25am » |
Quote Modify
|
on Mar 19th, 2014, 1:39pm, jollytall wrote:
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. |
|
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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print