A bit in bottles
Francois Grieu
Green or Red, then turns it "off".
Our procedure can be interrupted abruptly at *ANY* time [picture a
microprocessor which power can disappear without warning], then
restarted [with most information about what was going on earlier lost].
Before each (re)start, the light gets turned "off" automatically. When
our procedure is executed without interruption, it must turn "on" the
light at least once per minute, for at least 1 second, with no color
change during that "on" time.
Between a (re)start and the next interruption, the "on" color used must
alternate between Green and Red.
If an interruption occurs while the light is "on" in some color, then
the next time the light is turned "on", it must be with the same color
[thus at least one bit of information must be kept about past history to
decide that color].
The only method to store information across interruptions is the amount
of water in 10 identical bottles initially empty. We can order to
"Empty" a designated bottle; or to "Pour" enough water in a designated
bottle to fill an empty bottle [water is recycled to and pumped from the
sea]. Each such order is dutifully executed when we ask, and lasts 1
second. Our "Pour" orders must never cause a bottle to overflow. Only
our orders have the effect of changing the amount of water in a bottle,
and do so one bottle at a time.
On (re)start, our procedure is given input about each bottle, either 0
for "not full" or 1 for "not empty" [this gives no information for a
bottle neither empty nor full, which can occur e.g. if an interruption
occurs while we pour into that bottle; for such a bottle, the input can
vary from one restart to another even if the amount of water in the
bottle did not change].
Assume everything (computation, decision, action on the light..) is
instantaneous except "Empty", "Pour", and explicit delay.
Does a correct procedure exist [one that never breaks any of the "must"
or asks for something of unclear feasibility or effect]?
If yes, try to optimize the rate of color changes per time unit under
some odds of interrupt per second; else, try to optimize the mean time
between failures [the best procedures may depend slightly on some
additional assumptions].
I'm the author of this puzzle. It is based on a real engineering issue
[occurring in Smart Cards, which are subject to random or adversarial
power loss or reset, and store information by injecting electrical
charges into memory cells, then read it as the charge level].
Francois Grieu
Francois Grieu
Green or Red, then turns it "off".
Our procedure can be interrupted abruptly at *ANY* time [picture a
microprocessor which power can disappear without warning], then
restarted [with most information about what was going on earlier lost].
Before each (re)start, the light gets turned "off" automatically. When
our procedure is executed without interruption, it must turn "on" the
light at least once per minute, for at least 1 second, with no color
change during that "on" time.
Between a (re)start and the next interruption, the "on" color used must
alternate between Green and Red.
If an interruption occurs while the light is "on" in some color, then
the next time the light is turned "on", it must be with the same color
[thus at least one bit of information must be kept about past history to
decide that color].
The only method to store information across interruptions is the amount
of water in 10 identical bottles initially empty. We can order to
"Empty" a designated bottle; or to "Pour" enough water into a designated
bottle to fill an empty bottle [water is recycled to and pumped from the
sea]. Each such order is dutifully executed when we ask, and lasts 1
second. Our "Pour" orders must never cause a bottle to overflow. Only
our orders have the effect of changing the amount of water in a bottle,
and do so one bottle at a time.
On (re)start, our procedure is given input about each bottle, either 0
for "not full" or 1 for "not empty" [this gives no information for a
bottle neither empty nor full, which can occur e.g. if an interruption
occurs while we pour into that bottle; for such a bottle, the input can
vary from one restart to another even if the amount of water in the
bottle did not change].
Assume everything (computation, decision, action on the light..) is
instantaneous except "Empty", "Pour", and explicit delay.
Does a correct procedure exist [one that never breaks any of the "must"
or asks for something of unclear feasibility or effect]?
If yes, try to optimize the rate of color changes per time unit under
some odds of interrupt per second; else, try to optimize the mean time
between failures [the best procedures may depend slightly on some
additional assumptions].
I'm the author of this puzzle. It is based on a real engineering issue
[occurring in Smart Cards, which are subject to random or adversarial
power loss or reset, and store information by injecting electrical
charges into memory cells, then read it as the charge level].
Francois Grieu
[reposted due to usenet propagation issues]
James Dow Allen
> [snipped lengthy puzzle description]
No one's tackled this, so I'll sacrifice myself to keep the
thread alive. I've probably misunderstood the problem, missolved
what I did understand, or both....
(BTW, one reason for lack of response may be length and apparent
complexity of the puzzle. Another good puzzle *might* be to
find a way to restate OP more concisely!)
> The only method to store information across
> interruptions is the amount of water in 10
> identical bottles initially empty.
I'll "think aloud", hoping I understand the problem.
I want to set the bottle configuration to one of two known
states; turn on the appropriate light color; turn it off;
change the bottles to the alternate configuration; and so on.
Which two configs to use? I'll try OOFF and FFOO
with six bottles unused. (O=empty, F=full)
Empty, empty, fill, fill does the trick when running
(the order of empty/fill may matter - exercise!);
from now on we consider only error-restart.
What makes things tricky is the 'F' readings.
They're unreliable; to convert 'F' to reliable 'F'
you must first Empty the bottle, then refill it
(filling a non-empty bottle can destroy it permanently);
problem may arise when an error-restart during this
unreliable F -> O -> reliable F
transition makes the bottle 'O'.
If after restart the state is OOxx, we do empty #1,
empty #2, empty #3, empty #4, fill #3, fill #4.
This also handles the "initial" all-empty state
mentioned by OP.
If instead the state is FxOO, we do empty #3,
empty #4, empty #2, fill #2, empty #1, fill #1.
Finally, if the state is OFOO we just do empty #1, fill #1.
The concern is that FFOO can end up looking like OOxx;
I've *tried* to prevent that.
Why did OP give me six extra bottles I didn't need?
Did I do something wrong? For that matter, did I even
need all 4 bottles I *did* use?
> I'm the author of this puzzle.
> It is based on a real engineering issue ...
> Does a correct procedure exist [?]
> If yes, ... else ...
This is phrased as though *you* might not know the answer!
If that's true, and someone here solves it, I hope you'll
send them a consulting stipend.... :-)
> Francois Grieu
Too bad about the extra 'i'. You could have had
one of those rare names with each vowel occurring
just once!
Jumes Dow Allin
Francois Grieu
> On Jan 28, 7:58 am, Francois Grieu wrote:
>> [snipped lengthy puzzle description]
>
> No one's tackled this, so I'll sacrifice myself to keep the
> thread alive. I've probably misunderstood the problem, missolved
> what I did understand, or both....
>
> (BTW, one reason for lack of response may be length and apparent
> complexity of the puzzle. Another good puzzle *might* be to
> find a way to restate OP more concisely!)
(That would be welcome! I tried. The statement has to be precise.)
>> The only method to store information across
>> interruptions is the amount of water in 10
>> identical bottles initially empty.
>
> I'll "think aloud", hoping I understand the problem.
>
> I want to set the bottle configuration to one of two known
> states; turn on the appropriate light color; turn it off;
> change the bottles to the alternate configuration; and so on.
Yes.
> Which two configs to use? I'll try OOFF and FFOO
> with six bottles unused. (O=empty, F=full)
>
> Empty, empty, fill, fill does the trick when running
> (the order of empty/fill may matter - exercise!);
> from now on we consider only error-restart.
>
> What makes things tricky is the 'F' readings.
> They're unreliable; to convert 'F' to reliable 'F'
> you must first Empty the bottle, then refill it
> (filling a non-empty bottle can destroy it permanently);
> problem may arise when an error-restart during this
> unreliable F -> O -> reliable F
> transition makes the bottle 'O'.
Yes. The input for bottles left in some intermediary state
during Empty or Pour (or Fill as you call it) is
indistinguishable from input for empty or full bottles.
> If after restart the state is OOxx, we do empty #1,
> empty #2, empty #3, empty #4, fill #3, fill #4.
> This also handles the "initial" all-empty state
> mentioned by OP.
>
> If instead the state is FxOO, we do empty #3,
> empty #4, empty #2, fill #2, empty #1, fill #1.
You are interrupted during fill #1. Next state is ?F00.
You get input FF00. You redo the above, and get interrupted
during empty #2. Next state is ??00. You get input 0000,
and are not interrupted. You end up at 00FF, which was
clearly against your intend.
Your procedure seems to fail regardless of how you handle
the change of state (which you have not described).
> Finally, if the state is OFOO we just do empty #1, fill #1.
>
> The concern is that FFOO can end up looking like OOxx;
> I've *tried* to prevent that.
The nice thing is that you have understood the essence of
the puzzle, if not found a correct solution.
> Why did OP give me six extra bottles I didn't need?
(snip)
>
>> I'm the author of this puzzle.
>> It is based on a real engineering issue ...
>> Does a correct procedure exist [?]
>> If yes, ... else ...
>
> This is phrased as though *you* might not know the answer!
> If that's true, and someone here solves it, I hope you'll
> send them a consulting stipend.... :-)
I and a co-worker have worked on the problem (in spare time)
for several days, alternating between "solutions" with increasingly
many bottles, that got busted, and inconclusive demonstrations
of impossibility that gave rise to new "solutions".
The feasibility is now conclusively settled. I plan to release
the cryptographic hash of a text on that, hopefully during the
next week-end (I must polish that text). I'll release the text
when the group has stabilized on the feasibility (or gave up,
which is unlikely), and anyone can then verify the hash. I've
done that before, see http server with my name followed by dot com.
I'll probably re-state the problem will "Empty"/"Fill" and
the E/F notation for input and E/?/F notation for bottle state
used in the present post, even if that breaks the similarity with
"Erase"/"Program" and reading of EEPROM in my original engineering
problem.
>> Francois Grieu
>
> Too bad about the extra 'i'. You could have had
> one of those rare names with each vowel occurring
> just once!
>
> Jumes Dow Allin
Thanks for the interest!
Francois Grieu
Nick Wedd
<fgr...@gmail.com> writes
>We must define a procedure which repeatedly turns "on" a light either
>Green or Red, then turns it "off".
Conjecture: the light has three states, "off", "green", and "red". the
procedure can set it to any of these states whenever we choose.
>Our procedure can be interrupted abruptly at *ANY* time [picture a
>microprocessor which power can disappear without warning], then
>restarted [with most information about what was going on earlier lost].
>Before each (re)start, the light gets turned "off" automatically. When
>our procedure is executed without interruption, it must turn "on" the
>light at least once per minute, for at least 1 second, with no color
>change during that "on" time.
>
>Between a (re)start and the next interruption, the "on" color used must
>alternate between Green and Red.
Conjecture: When we start, it has no history, so our first "on" state
can be red, or green, without risk of breaking the alternation.
>If an interruption occurs while the light is "on" in some color, then
>the next time the light is turned "on", it must be with the same color
>[thus at least one bit of information must be kept about past history
>to decide that color].
>
>The only method to store information across interruptions is the amount
>of water in 10 identical bottles initially empty. We can order to
>"Empty" a designated bottle; or to "Pour" enough water in a designated
>bottle to fill an empty bottle [water is recycled to and pumped from
>the sea]. Each such order is dutifully executed when we ask, and lasts
>1 second. Our "Pour" orders must never cause a bottle to overflow. Only
>our orders have the effect of changing the amount of water in a bottle,
>and do so one bottle at a time.
so if a bottle is in an unknown state, our next action on it must be to
empty it, right?
>On (re)start, our procedure is given input about each bottle, either 0
>for "not full" or 1 for "not empty" [this gives no information for a
>bottle neither empty nor full, which can occur e.g. if an interruption
>occurs while we pour into that bottle; for such a bottle, the input can
>vary from one restart to another even if the amount of water in the
>bottle did not change].
Suppose I have an empty bottle and I order it to be filled. Then an
interrupt happens. When I wake up, it is labelled "?". Before I do
anything with it, another interrupt happens. When I next wake up, will
it still be "?"? Or may it have resolved itself to "0" or "1"?
>Assume everything (computation, decision, action on the light..) is
>instantaneous except "Empty", "Pour", and explicit delay.
>
>Does a correct procedure exist [one that never breaks any of the "must"
>or asks for something of unclear feasibility or effect]?
>
>If yes, try to optimize the rate of color changes per time unit under
>some odds of interrupt per second; else, try to optimize the mean time
>between failures [the best procedures may depend slightly on some
>additional assumptions].
It seems to me that the task is impossible, with any finite number of
bottles. But I have probably misunderstood the problem.
Nick
>I'm the author of this puzzle. It is based on a real engineering issue
>[occurring in Smart Cards, which are subject to random or adversarial
>power loss or reset, and store information by injecting electrical
>charges into memory cells, then read it as the charge level].
>
> Francois Grieu
--
Nick Wedd ni...@maproom.co.uk
Francois Grieu
> In message <4b60e11f$0$23534$426a...@news.free.fr>, Francois Grieu
> <fgr...@gmail.com> writes
>> We must define a procedure which repeatedly turns "on" a light either
>> Green or Red, then turns it "off".
>
> Conjecture: the light has three states, "off", "green", and "red". the
> procedure can set it to any of these states whenever we choose.
Yes.
>> Our procedure can be interrupted abruptly at *ANY* time [picture a
>> microprocessor which power can disappear without warning], then
>> restarted [with most information about what was going on earlier
>> lost]. Before each (re)start, the light gets turned "off"
>> automatically. When our procedure is executed without interruption, it
>> must turn "on" the light at least once per minute, for at least 1
>> second, with no color change during that "on" time.
>>
>> Between a (re)start and the next interruption, the "on" color used
>> must alternate between Green and Red.
>
> Conjecture: When we start, it has no history, so our first "on" state
> can be red, or green, without risk of breaking the alternation.
Yes. [It seems possible to turn an hypothetical fully correct procedure
into one that starts Green: first remove randomness in any choice
made, then exchange colors in the definition of the modified procedure
if it starts Red]
>> If an interruption occurs while the light is "on" in some color, then
>> the next time the light is turned "on", it must be with the same color
>> [thus at least one bit of information must be kept about past history
>> to decide that color].
>>
>> The only method to store information across interruptions is the
>> amount of water in 10 identical bottles initially empty. We can order
>> to "Empty" a designated bottle; or to "Pour" enough water into a
>> designated bottle to fill an empty bottle [water is recycled to and
>> pumped from the sea]. Each such order is dutifully executed when we
>> ask, and lasts 1 second. Our "Pour" orders must never cause a bottle
>> to overflow. Only our orders have the effect of changing the amount of
>> water in a bottle, and do so one bottle at a time.
>
> so if a bottle is in an unknown state, our next action on it must be to
> empty it, right?
Yes.
>> On (re)start, our procedure is given input about each bottle, either 0
>> for "not full" or 1 for "not empty" [this gives no information for a
>> bottle neither empty nor full, which can occur e.g. if an interruption
>> occurs while we pour into that bottle; for such a bottle, the input
>> can vary from one restart to another even if the amount of water in
>> the bottle did not change].
>
> Suppose I have an empty bottle and I order it to be filled. Then an
> interrupt happens. When I wake up, it is labelled "?". Before I do
> anything with it, another interrupt happens. When I next wake up, will
> it still be "?"? Or may it have resolved itself to "0" or "1"?
It is still neither empty nor full, or equivalently "?". That was
supposed to be specified by "Only our orders have the effect of
changing the amount of water in a bottle".
>> Assume everything (computation, decision, action on the light..) is
>> instantaneous except "Empty", "Pour", and explicit delay.
>>
>> Does a correct procedure exist [one that never breaks any of the
>> "must" or asks for something of unclear feasibility or effect]?
>>
>> If yes, try to optimize the rate of color changes per time unit under
>> some odds of interrupt per second; else, try to optimize the mean time
>> between failures [the best procedures may depend slightly on some
>> additional assumptions].
>
> It seems to me that the task is impossible, with any finite number of
> bottles. But I have probably misunderstood the problem.
We have an assertion of impossibility without proof here, and an
incorrect solution there. This repeats what happened in my workplace.
Typically, persons exposed to the problem change their mind on the
feasibility at least one time if they work at it hard enough.
Revealing that bit of information too soon spoils all the fun.
James Dow Allen
> James Dow Allen wrote :
> > [snip]
> Your procedure seems to fail regardless of how you handle
> the change of state (which you have not described).
Well, I figured a wrong solution would be better for
the thread and for newsgroup morale than a correct solution. :-)
> I'll probably re-state the problem will "Empty"/"Fill" and
> the E/F notation for input
Minor orthographic nit:
I started with E/F, but decided the letters are visually
too similar. I switched to O/X but noticed I was using
x also for don't care. That's how I settled on O/F.
> > Jumes Dow Allin
To send me e-mail, Gmail me at my 13-character name, first
correcting the vowels.
Richard Heathfield
> Well, I figured a wrong solution would be better for
> the thread and for newsgroup morale than a correct solution. :-)
Beautifully put. I'll remember that for next time. :-p
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
Nick Wedd
I am not going to put much effort into attacking the problem until I am
sure I have understood it. So here is my next question:
Can we order two empty bottles to be filled simultaneously?
If we can, and we do, and then an interrupt happens, which of the
following sets of states are possible when we wake up?
F F yes
? ? yes
F ?
? F
E F
F E
E ?
? E
Nick
>
>> Nick
>>
>>> I'm the author of this puzzle. It is based on a real engineering
>>>issue [occurring in Smart Cards, which are subject to random or
>>>adversarial power loss or reset, and store information by injecting
>>>electrical charges into memory cells, then read it as the charge level].
>
> Francois Grieu
--
Nick Wedd ni...@maproom.co.uk
Francois Grieu
> (..) here is my next question:
>
> Can we order two empty bottles to be filled simultaneously?
The problem statement includes "our orders have the effect of
changing the amount of water in a bottle (..) one bottle at a time".
Therefore it seems immaterial that we can make simultaneous
orders or not. Just assume things are executed sequentially in
the order specified.
[Ambiguous orders like "fill all bottles" may be disqualifying, or
interpreted implicitly as "in any arbitrary order", at the jury's
will]
Francois Grieu
Nick Wedd
<fgr...@gmail.com> writes
>Nick Wedd wrote:
>
>> (..) here is my next question:
>> Can we order two empty bottles to be filled simultaneously?
>
>The problem statement includes "our orders have the effect of
>changing the amount of water in a bottle (..) one bottle at a time".
You are right about the mind-changing.
How's this for a procedure:
We just use the first two bottles and ignore the rest.
What we see What we do
Light is on Wait a second then switch it off.
EE Fill 1.
?E Empty 1.
FE Fill 2. The instant it is full, green on.
F? Empty 2.
FF Empty 1.
?F Empty 1.
EF Empty 2. The instant it is empty, red on.
E? Empty 2. The instant it is empty, red on.
?? Can't happen.
Nick
--
Nick Wedd ni...@maproom.co.uk
Daniel Giaimo
Remember that you can't tell the difference between E? and EE, so
your procedure is indeterminate when the bottles are read to be in
state EE.
--
Dan G
Daniel Giaimo
> We must define a procedure which repeatedly turns "on" a light either
> Green or Red, then turns it "off".
>
> Our procedure can be interrupted abruptly at *ANY* time [picture a
> microprocessor which power can disappear without warning], then
> restarted [with most information about what was going on earlier lost].
> Before each (re)start, the light gets turned "off" automatically. When
> our procedure is executed without interruption, it must turn "on" the
> light at least once per minute, for at least 1 second, with no color
> change during that "on" time.
>
> Between a (re)start and the next interruption, the "on" color used must
> alternate between Green and Red.
>
Does this mean that once the light is on, that it can't be turned off
again? If so, then the problem is trivially unsolvable. I have a
fairly convincing argument (not sure if it is a full proof, though)
that in order for any solution to work the light must alternate:
off -> green -> off -> red -> off -> green -> etc...
This is a very tricky problem. After looking at it a while I have the
strong feeling that it is unsolvable as stated, but I can't quite pin
down a proof. I do have a sketch of a solution that appears to work
provided the restarts occur no more often than once every six or so
seconds.
--
Dan G
Francois Grieu
> How's this for a procedure:
> We just use the first two bottles and ignore the rest.
>
> What we see What we do
>
> Light is on Wait a second then switch it off.
Or equivalently turn the light off 1 second after switching
it on. OK for that.
> EE Fill 1.
> ?E Empty 1. (snip)
I do not get your notation. We never get to *see* "?",
or to see the bottles whatsoever.
If the bottle is neither empty nor full (I assume: "?")
we *get* information that is *either* "E" or "F" ("0" or "1"
in the original statement) and plain worthless.
Information about bottles is given at (re)start and we get no
more information. For the sake of simplicity we can assume
that we update this info when we give orders, though.
We could also maintain an independent variable for each
bottle, initially "?", and changed to "E" or "F" after we get
certainty either by orders (e.g. after "Empty" we can set the
variable to "E"), or by reasoning about what's possible given
what our procedure does (e.g. if we never order anything about
a bottle, it is bound to remain empty).
Back to your proposed procedure: if starting from the initial
state you are interrupted during "fill 1" resulting from your
first rule, bottle 1 could become half full. On restart, the
information you get about it might be "E" ("0") for "not full"
in which case you are back to your first rule and order "fill 1",
and (unless an interruption occurs) this will cause overflow.
The first line of your proposed procedure makes it incorrect.
This, or I do not get your thinking.
Francois Grieu
Francois Grieu
> On 1/27/2010 7:58 PM, Francois Grieu wrote:
>> We must define a procedure which repeatedly turns "on" a light either
>> Green or Red, then turns it "off".
>>
>> Our procedure can be interrupted abruptly at *ANY* time [picture a
>> microprocessor which power can disappear without warning], then
>> restarted [with most information about what was going on earlier lost].
>> Before each (re)start, the light gets turned "off" automatically. When
>> our procedure is executed without interruption, it must turn "on" the
>> light at least once per minute, for at least 1 second, with no color
>> change during that "on" time.
>>
>> Between a (re)start and the next interruption, the "on" color used must
>> alternate between Green and Red.
>>
>
> Does this mean that once the light is on, that it can't be turned off
> again? If so, then the problem is trivially unsolvable.
No. You can order the light to be Green, Red, or Off.
> I have a
> fairly convincing argument (not sure if it is a full proof, though)
> that in order for any solution to work the light must alternate:
>
> off -> green -> off -> red -> off -> green -> etc...
I won't contradict you on that one.
Excellent state of mind. Try to make a proof, and the counterexample
to your proof must be a solution. Or vice versa.
> I do have a sketch of a solution that appears to work
> provided the restarts occur no more often than once every six or so
> seconds.
You can't assume that.
>
> --
> Dan G
Francois Grieu
Daniel Giaimo
> Daniel Giaimo a �crit :
<snip>
>> I do have a sketch of a solution that appears to work
>> provided the restarts occur no more often than once every six or so
>> seconds.
>
> You can't assume that.
Ok. I think I may have actually modified my solution into one that
always works. Moreover, I believe you only need 8 bottles. For
the solution I assume that you start with all the bottles empty.
The basic idea is then to go through the following state changes
where o indicates an empty bottle and x indicates a full one.:
oooooooo
xooooooo
xxoooooo
xxxooooo
xxxxoooo
(loop)
(turn green light on)
xxxxxooo
oxxxxooo
oxxxxxoo
ooxxxxoo
(turn green light off)
ooxxxxxo
oooxxxxo
oooxxxxx
ooooxxxx
(turn red light on)
xoooxxxx
xooooxxx
xxoooxxx
xxooooxx
(turn red light off)
xxxoooxx
xxxoooox
xxxxooox
xxxxoooo
(goto loop)
The only thing to determine now is what to do if we get interrupted.
On the first pass through there are 7 (8 after the second restart)
isomorphism classes of states we could get after restarting : (In the
following, letters indicate unknown bottles)
1) oooooooo
In this case we know that we are in the following case:
aooooooo
In this case we first empty a. If we are interrupted in this emptying
we will restart in either case 1) or case 2). We are now back in a
known state.
2) xooooooo
In this case we know that we are in the following case:
aboooooo
In this case we first empty b. If we are interrupted, we will restart
in either case 1), case 2), or case 3). After emptying b we empty a.
If we are interrupted we will restart in either case 1) or case 2). We
are now back in a known state.
3) xxoooooo
In this case we know that we are in the following case:
xabooooo
In this case we first empty b. If we are interrupted, we will restart
in either case 2), case 3), or case 4). After emptying b we empty a.
If we are interrupted we will restart in either case 2) or case 3). We
are now back in a known state.
4) xxxooooo
In this case we know that we are in the following case:
xxaboooo
In this case we first empty b. If we are interrupted, we will restart
in either case 3), case 4), or case 5). After emptying b we empty a.
If we are interrupted we will restart in either case 3) or case 4). We
are now back in a known state.
5) xxxxoooo
In this case we know that we are in the following case:
xxxabooc
In this case we first empty c. If we are interrupted, we will restart
in either case 4), case 5), or case 7). Next we empty b. If we are
interrupted, we will restart in either case 4), case 5), or case 7).
Next we empty a. If we are interrupted we will restart in either case
4) or case 5). We are now back in a known state.
6) ooxxxxoo
In this case we know that we are in the following case:
ocxxxabo
In this case we first empty c. If we are interrupted, we will restart
in either case 6), case 7), or case 8). Next we empty b. If we are
interrupted, we will restart in either case 6), case 7), or case 8).
Next we empty a. If we are interrupted we will restart in either case
6) or case 8). Lastly we fill a. If we are interrupted we will
restart in either case 6) or case 8). We are now back in a known state.
7) ooxxxxxo
In this case we know that we are in the following case:
oobxxxao
In this case we first empty b. If we are interrupted, we will restart
in either case 6), case 7), or case 8). Lastly we empty a. If we are
interrupted we will restart in either case 6) or case 8). We are now
back in a known state.
8) ooxxxooo
In this case we know that we are in the following case:
oooxxxaoo
In this case we empty a. If we are interrupted, we will restart in
either case 6) or case 8). We now fill a. If we are interrupted, we
will restart in either case 6) or case 8). We are now back in a known
state.
Once we are back in a known state as described above we determine the
location of the cyclically-leftmost filled bottle. If there are at
least four bottles filled, and the leftmost filled bottle is one of the
first three bottles, then we turn the green light on, however if it is
the third bottle we immediately turn it off again. If it is the fourth
bottle, we leave the light off. If it is one of the next three, we
turn the red light on, however if it is the seventh bottle we
immediately turn the light off again. If it is the last bottle, we
leave the light off. If there are not at least four bottles filled,
then we leave the light off. In any case, things then proceed as
described in the diagram above.
--
Dan G
Francois Grieu
> Ok. I think I may have actually modified my solution into one that
> always works.
That's one change of mind. I had several.
I'll eventually comment...
Francois Grieu
James Dow Allen
> Your procedure seems to fail regardless....
Can I try again?
As a building block, I'll use two bottles as a
flip-flop, normally in either state FO (on) or OF (off).
I'll use 4 flipflops (8 bottles total) called
D1, D2, D3, V1. D1=D2=D3=on will be the Red state;
D1=D2=D3=off the Green state; V1 represents whether
alteration is permitted on D1. Of the four states
of V1 (OF, OO, FO, FF) only OF will mean D1
alteration is permitted. Otherwise V1 will be
driven to FO, but may be intermediate due to error.
D1/D2/D3 use 6 bits to provide one of two messages; this
is like a ECC problem: we need demonstrate that at most
2 bits (bottles) will go bad.
If the 2-error maximum condition holds, we will always
be able to select the correct Red/Green state upon
restart. The only problem is driving the 8 bottles
to their correct and reliable values.
Restart procedure: Determine the desired Red/Green state.
If V1 is set to "D1 alteration", drive V1 to that state
reliably, and alter D1 correctly.
In either case we now continue by driving V1 to the
non-alter state and altering D2 correctly. We then
correct D3 and normal operation is restored. To prove
this works all we need show is that at most 2 of the
6 bits constituting D1/D2/D3 can be in error. Note
that the three 'O' bits will be emptied first thing,
so no new errors can be introduced there; we need only
show that at least one of the 'F' bits will be correct.
The key idea is that the V1/D1 operation means we don't
alter D2 or D3 until D1 has been permanently fixed.
(V1 never gets a double-bit error because we always
empty the O before doing empty/pour on the F.)
D2 and D3 might *bot* go bad, but only if D1 has been
made secure.
I give myself a 45% chance that this works, and perhaps
3% chance that eight bottles is minimal.
James Dow Allen
Willem
) Remember that you can't tell the difference between E? and EE, so
) your procedure is indeterminate when the bottles are read to be in
) state EE.
In that case I conjecture that after any start, each of the bottles must
first be emptied, regardless of its state, since you don't know if it is
empty or not. Or did I misunderstand something about the problem ?
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
Willem
) We must define a procedure which repeatedly turns "on" a light either
) Green or Red, then turns it "off".
)
) Our procedure can be interrupted abruptly at *ANY* time [picture a
) microprocessor which power can disappear without warning], then
) restarted [with most information about what was going on earlier lost].
) Before each (re)start, the light gets turned "off" automatically. When
) our procedure is executed without interruption, it must turn "on" the
) light at least once per minute, for at least 1 second, with no color
) change during that "on" time.
)
) Between a (re)start and the next interruption, the "on" color used must
) alternate between Green and Red.
)
) If an interruption occurs while the light is "on" in some color, then
) the next time the light is turned "on", it must be with the same color
) [thus at least one bit of information must be kept about past history to
) decide that color].
)
) The only method to store information across interruptions is the amount
) of water in 10 identical bottles initially empty. We can order to
) "Empty" a designated bottle; or to "Pour" enough water into a designated
) bottle to fill an empty bottle [water is recycled to and pumped from the
) sea]. Each such order is dutifully executed when we ask, and lasts 1
) second. Our "Pour" orders must never cause a bottle to overflow. Only
) our orders have the effect of changing the amount of water in a bottle,
) and do so one bottle at a time.
)
) On (re)start, our procedure is given input about each bottle, either 0
) for "not full" or 1 for "not empty" [this gives no information for a
) bottle neither empty nor full, which can occur e.g. if an interruption
) occurs while we pour into that bottle; for such a bottle, the input can
) vary from one restart to another even if the amount of water in the
) bottle did not change].
)
) Assume everything (computation, decision, action on the light..) is
) instantaneous except "Empty", "Pour", and explicit delay.
)
) Does a correct procedure exist [one that never breaks any of the "must"
) or asks for something of unclear feasibility or effect]?
)
) If yes, try to optimize the rate of color changes per time unit under
) some odds of interrupt per second; else, try to optimize the mean time
) between failures [the best procedures may depend slightly on some
) additional assumptions].
I must not understand the problem:
My procedure:
Start: - If bottle 1 is 'F', remember 'red'
Otherwise remember 'green'
- Empty bottle 1
- If we remembered 'red', go to RED:
GREEN: - Turn light green
- Wait 1 second
- Turn light off
RED: - Fill bottle 1
- Turn light red
- Wait 1 second
- Turn light off
- Empty bottle 1
- go to GREEN:
How it works:
The red light is only turned on when we're sure the bottle is full, and the
green light is only turned on when we're sure the bottle is empty.
The only real requirement is for the light to be the same colour as last
time, when the light was turned on. So by only turning on the light when
we are sure of the state of the bottle, we can use the state of the bottle
as an indicator of which colour to pick. If we were interrupted during a
pour or empty, the light was off, and it doesn't matter what colour we
pick.
So what did I miss ?
(I first assumed that the light was required to alternate, even between
interruptions, but when I reread I saw that was not the case).
Daniel Giaimo
Here's one problem with your solution:
Suppose the bottle is empty to start with.
You read that empty to start with and turn the green light on.
You wait for a second and turn the light off.
You then start filling the bottle.
You are interrupted halfway through.
You restart and read the bottle as empty.
You turn the green light on.
You wait for a second and turn the light off.
You then start filling the bottle.
You overflow because the bottle was not empty. //
--
Dan G
Daniel Giaimo
> Daniel Giaimo wrote:
> ) Remember that you can't tell the difference between E? and EE, so
> ) your procedure is indeterminate when the bottles are read to be in
> ) state EE.
>
> In that case I conjecture that after any start, each of the bottles must
> first be emptied, regardless of its state, since you don't know if it is
> empty or not. Or did I misunderstand something about the problem ?
Not quite. For example, suppose your strategy is to start at the left
and fill the bottles one by one until you reach the end. (This of
course tells you nothing, and for the problem is a stupid strategy, but
go with it for now.) Suppose you are interrupted halfway through and
on restart you read the following as the state of the bottles where x
means full and o means empty:
xxxxxooooo
Then you know for a fact that the first four bottles are full and the
last four bottles are empty. You do not, however, know the state of
the middle two bottles as you can't tell which you were filling when you
restarted. The only safe thing you can do with those two bottles is
empty them.
--
Dan G
Nick Wedd
<fgr...@gmail.com> writes
>Nick Wedd wrote :
>> How's this for a procedure:
>> We just use the first two bottles and ignore the rest.
>> What we see What we do
>> Light is on Wait a second then switch it off.
>
>Or equivalently turn the light off 1 second after switching
>it on. OK for that.
>
>> EE Fill 1.
>> ?E Empty 1. (snip)
>
>I do not get your notation. We never get to *see* "?",
>or to see the bottles whatsoever.
>
>If the bottle is neither empty nor full (I assume: "?")
>we *get* information that is *either* "E" or "F" ("0" or "1"
>in the original statement) and plain worthless.
>Information about bottles is given at (re)start and we get no
>more information. For the sake of simplicity we can assume
>that we update this info when we give orders, though.
I must have misunderstood the problem.
Forget what I wrote above. I now assume that if an interrupt occurs
while a bottle is filling or emptying, we get told that it is full, or
that it is empty, arbitrarily. When we wake up, we are told either
"full" or "empty" for every bottle; we should always suspect that one of
them is part-way through a transition; and if our strategy is good, we
should be able to deduce which one.
Have I got this right now?
Nick
>We could also maintain an independent variable for each
>bottle, initially "?", and changed to "E" or "F" after we get
>certainty either by orders (e.g. after "Empty" we can set the
>variable to "E"), or by reasoning about what's possible given
>what our procedure does (e.g. if we never order anything about
>a bottle, it is bound to remain empty).
>
>
>Back to your proposed procedure: if starting from the initial
>state you are interrupted during "fill 1" resulting from your
>first rule, bottle 1 could become half full. On restart, the
>information you get about it might be "E" ("0") for "not full"
>in which case you are back to your first rule and order "fill 1",
>and (unless an interruption occurs) this will cause overflow.
>The first line of your proposed procedure makes it incorrect.
>This, or I do not get your thinking.
>
>
> Francois Grieu
--
Nick Wedd ni...@maproom.co.uk
Willem
) On 1/29/2010 2:31 PM, Willem wrote:
)> My procedure:
)>
)> Start: - If bottle 1 is 'F', remember 'red'
)> Otherwise remember 'green'
)> - Empty bottle 1
)> - If we remembered 'red', go to RED:
)> GREEN: - Turn light green
)> - Wait 1 second
)> - Turn light off
)> RED: - Fill bottle 1
)> - Turn light red
)> - Wait 1 second
)> - Turn light off
)> - Empty bottle 1
)> - go to GREEN:
)>
)> How it works:
)> The red light is only turned on when we're sure the bottle is full, and the
)> green light is only turned on when we're sure the bottle is empty.
)>
)> The only real requirement is for the light to be the same colour as last
)> time, when the light was turned on. So by only turning on the light when
)> we are sure of the state of the bottle, we can use the state of the bottle
)> as an indicator of which colour to pick. If we were interrupted during a
)> pour or empty, the light was off, and it doesn't matter what colour we
)> pick.
)>
)> So what did I miss ?
)>
)> (I first assumed that the light was required to alternate, even between
)> interruptions, but when I reread I saw that was not the case).
)
) Here's one problem with your solution:
) Suppose the bottle is empty to start with.
) You read that empty to start with and turn the green light on.
) You wait for a second and turn the light off.
) You then start filling the bottle.
) You are interrupted halfway through.
) You restart and read the bottle as empty.
) You turn the green light on.
) You wait for a second and turn the light off.
) You then start filling the bottle.
) You overflow because the bottle was not empty. //
Nope, that is not the problem with my solution.
After a restart, the bottle is always emptied first.
A possible problem with my solution is when you get
two interruptions within a second:
First interruption is when the light is red. After the restart, the bottle
will be emptied, but we get another interruption. Next restart, the bottle
reads as empty, so we proceed to empty it and then turn on the green light.
But it should have been red, because the last time it was turned on it was
red (even though there were two interruptions between then and now.)
Francois Grieu
We must define a procedure which, if executed without interruption,
repeatedly: turns "on" a light either "Green" or "Red", turns it
"Off", turns it "on" again in the other color ["Red" or "Green"],
turns it "off".
Our procedure can be interrupted abruptly at *ANY* time [picture a
microprocessor which power can disappear without warning], then
restarted [most information about what was going on earlier is lost].
Before each (re)start, the light gets turned off automatically.
If an interruption occurs while the light is "on" in some color, then
the next time that the light is turned "on", it must be with the same
color [thus one bit of information must be kept about past history to
decide that color].
The only method to store information across interruptions is the
amount of water in 10 identical bottles, initially empty, that we
never get to see.
On (re)start, our procedure is given input about each bottle, either 0
for "not full" or 1 for "not empty" [this gives no information for a
bottle neither empty nor full; for such a bottle, the input can vary
arbitrarily from one restart to another even if the amount of water in
the bottle did not change].
We can order to "Empty" a designated bottle [it's content is recycled
to the sea]; or to "Fill" it, which must be ordered only on an empty
bottle [this avoid overflow while enough water to fill an empty
bottle is pumped from the sea]. Each of these "Empty" or "Fill"
lasts 1 second, unless an interruption occurs, which may leave the
designated bottle neither empty nor full. Bottles are emptied and
filled one at at time. Nothing but our orders changes the amount of
water in the bottles.
Assume everything [computation, decision, actions on the light..] is
instantaneous except "Empty", "Fill", and any explicit "Wait" we may
request. In the absence of interruption, the delay from (re)start or
"Off" to "on" transition to the next such transition must not exceed
1 minute [the procedure must not stall], and each "on" state of the
light must last at least 1 second with no color change [allowing
inspection].
Does a correct procedure exist [one that never breaks any of the
"must" or asks for something of unclear feasibility or effect]?
If yes, try to optimize the rate of color changes per time unit under
some odds of interrupt per second; else, try to optimize the mean time
between failures [the best procedures may depend slightly on some
additional assumptions].
I'm the author of this puzzle. It is based on a real engineering issue
[occurring in Smart Cards, which are subject to random or adversarial
power loss or reset, and store information by injecting electrical
charges into memory cells, then read it as the charge level].
I have conclusively determined if a correct procedure exists or not.
Revealing that bit of information removes a lot of fun to the puzzle:
my experience is that typically, one changes mind at least once about
existence if trying the puzzle hard enough. I'd like the rec.puzzles
group to come to it's own consensus on that.
Francois Grieu
These hashes commit a text file with my statement and proof:
MD5: 7E006F96EF35C2E1F10EBE6B338D09C6
SHA1: B314FEDF2214D11E725F0C3CCA1C181D9929B844
Francois Grieu
> I now assume that if an interrupt occurs
> while a bottle is filling or emptying, we get told that it is full, or
> that it is empty, arbitrarily. When we wake up, we are told either
> "full" or "empty" for every bottle; we should always suspect that one of
> them is part-way through a transition; and if our strategy is good, we
> should be able to deduce which one.
>
> Have I got this right now?
Yes, though I prefer to state: we are told either "not empty" or "not
full" for every bottle.
Francois Grieu
Francois Grieu
> I think I may have actually modified my solution into one that
> always works. Moreover, I believe you only need 8 bottles. For
> the solution I assume that you start with all the bottles empty.
> The basic idea is then to go through the following state changes
> where o indicates an empty bottle and x indicates a full one.:
>
> oooooooo
> xooooooo
> xxoooooo
> xxxooooo
> xxxxoooo
> (loop)
> (turn green light on)
> xxxxxooo
> oxxxxooo
> oxxxxxoo
> ooxxxxoo
> (turn green light off)
> ooxxxxxo
> oooxxxxo
> oooxxxxx
> ooooxxxx
> (turn red light on)
Assume an interruption occurs here [say, to simplify, with the
left bottle still empty]
I assume that following the above interruption, we are in this case,
just shifted by half a turn.
> In this case we know that we are in the following case:
>
> xxxabooc
>
> In this case we first empty c. If we are interrupted, we will restart
> in either case 4), case 5), or case 7). Next we empty b. If we are
> interrupted, we will restart in either case 4), case 5), or case 7).
> Next we empty a. If we are interrupted we will restart in either case
> 4) or case 5). We are now back in a known state.
After two empty, we are back at ooooxxxo. Interrupt, this is case 4.
After two empty, we are back at ooooxxoo. Interrupt, this is case 3.
After two erase, we are back at ooooxooo. Interrupt, this is case 2.
After two erase, we are back at oooooooo. Interrupt, this is
indistinguishable from the initial state, and if there is no interrupt
we'll turn the light on green after a few steps, which makes the
procedure invalid.
Likely I misunderstood your wording, but at what point ?
>
> 6) ooxxxxoo
[I do not quite get how this is different from 5 shifted by a quarter
of a turn; however the actions defined below up to "Lastly we fill a"
seem the same as for 5; so I simply assume that we are interrupted
with "a" fully empty].
Good thinking!
Francois Grieu
Daniel Giaimo
You have misunderstood. The difference between case 5 and case 6 is
that case 5 only occurs if the cyclically left-most filled bottle is
the actual left-most bottle. The only reason these cases are
distinguished is because of the ramp-up at the beginning of getting the
bottles to a state where at least four bottles are filled at any one
time. Try your analysis again starting with state 6. You will find
that after two empty you get sent to case 8, not case 4. You will find
that you cannot end up in state ooooxxoo and hence your argument falls
apart.
--
Dan G
Nick Wedd
<fgr...@gmail.com> writes
Right. So when we wake up after an interrupt, there is a bottle that we
don't know what state it is in, _and_ we don't know which bottle it is.
We had better empty it (and possibly then fill it) before we do much
else.
I have three more questions:
1.) When we wake up after an interrupt, do we know this? Or do we
think we are doing whatever it was we were last doing?
2.) Suppose are doing something with a bottle when an interrupt
happens. When we wake up, that bottle is shown as empty. We order it
to be emptied, and another interrupt immediately occurs. Is there a
possibility that when we next wake up, that bottle will be shown as
full?
3.) Suppose we were doing something with bottle A when an interrupt
happens. When we wake up, bottle A is shown as in state X. We decide
to empty bottle B; and another interrupt immediately occurs. When we
wake up again, is there a possibility that bottle A will be shown in the
other state than X?
Nick Wedd
<fgr...@gmail.com> writes
>[polished statement]
>
>We must define a procedure which, if executed without interruption,
>repeatedly: turns "on" a light either "Green" or "Red", turns it
>"Off", turns it "on" again in the other color ["Red" or "Green"],
>turns it "off".
>
>Our procedure can be interrupted abruptly at *ANY* time [picture a
>microprocessor which power can disappear without warning], then
>restarted [most information about what was going on earlier is lost].
>Before each (re)start, the light gets turned off automatically.
>
>If an interruption occurs while the light is "on" in some color, then
>the next time that the light is turned "on", it must be with the same
>color [thus one bit of information must be kept about past history to
>decide that color].
>
>The only method to store information across interruptions is the
>amount of water in 10 identical bottles, initially empty, that we
>never get to see.
The word "identical" is misleading here. The bottles are
distinguishable, and might as well be labelled with small integers. It
would not affect the problem if no. 1 were a beer bottle, no. 2 a milk
bottle, etc.
>
>On (re)start, our procedure is given input about each bottle, either 0
>for "not full" or 1 for "not empty" [this gives no information for a
>bottle neither empty nor full; for such a bottle, the input can vary
>arbitrarily from one restart to another even if the amount of water in
>the bottle did not change].
I think I know what this means, but I find the statement above confusing
(though I can now see that it is technically correct). We are not given
"no information" about a bottle neither empty nor full, we are given
inaccurate information.
Here is my first attempt at rewriting it:
On (re)start, our procedure is given input about each bottle, either
"empty" or "full". For a bottle that was being filled or emptied when
the interruption occurred, this information will be given arbitrarily,
and can vary arbitrarily from one restart to another even if the amount
of water in the bottle did not change.
Nick
--
Nick Wedd ni...@maproom.co.uk
Nick Wedd
<ni...@maproom.co.uk> writes
>In message <4b661eac$0$2052$426a...@news.free.fr>, Francois Grieu
><fgr...@gmail.com> writes
>>Nick Wedd wrote:
>>> I now assume that if an interrupt occurs while a bottle is filling
>>>or emptying, we get told that it is full, or that it is empty,
>>>arbitrarily. When we wake up, we are told either "full" or "empty"
>>>for every bottle; we should always suspect that one of them is
>>>part-way through a transition; and if our strategy is good, we
>>>should be able to deduce which one.
>>> Have I got this right now?
>>
>>Yes, though I prefer to state: we are told either "not empty" or "not
>>full" for every bottle.
>
>Right. So when we wake up after an interrupt, there is a bottle that
>we don't know what state it is in, _and_ we don't know which bottle it
>is. We had better empty it (and possibly then fill it) before we do
>much else.
>
>I have three more questions:
>
>1.) When we wake up after an interrupt, do we know this? Or do we
>think we are doing whatever it was we were last doing?
Please ignore the next two questions, I see you have answered them (both
"yes" in another thread.
Francois Grieu
> In message <4b661eac$0$2052$426a...@news.free.fr>, Francois Grieu
> <fgr...@gmail.com> writes
>> Nick Wedd wrote:
>>> I now assume that if an interrupt occurs while a bottle is filling
>>> or emptying, we get told that it is full, or that it is empty,
>>> arbitrarily. When we wake up, we are told either "full" or "empty"
>>> for every bottle; we should always suspect that one of them is
>>> part-way through a transition; and if our strategy is good, we
>>> should be able to deduce which one.
>>> Have I got this right now?
>>
>> Yes, though I prefer to state: we are told either "not empty" or "not
>> full" for every bottle.
>
> Right. So when we wake up after an interrupt, there is a bottle that we
> don't know what state it is in,
Who said *A* bottle? It can grow to several, e.g. if after an
interruption we select to empty another bottle that was full,
and an interrupt comes whiles doing that.
> _and_ we don't know which bottle it is.
> We had better empty it (and possibly then fill it) before we do much else.
Yes, we'd better do just that, if we can.
> I have three more questions:
>
> 1.) When we wake up after an interrupt, do we know this? Or do we
> think we are doing whatever it was we were last doing?
We do not know we have been interrupted doing something with
a bottle or something else, and must assume either is a
possibility (except for a strategy with all bottles left empty,
but we do not get far with this one). And we have no clue of what
bottle that was (except if our strategy leaves all bottles empty
except one; try that first).
The only memory we have of past things is by the information we
get on bottles on restart, which in the case of a bottle neither
empty or full is worthless. Picture a microprocessor turned off
then on, with all RAM and registers lost. Or, if you have seen
it, the movie "Groundhog Day" with Bill Murray magically knowing
the content of bottles on wakeup (though with that info possibly
misleading for bottles neither empty nor full).
Francois Grieu
Francois Grieu
> On Jan 29, 5:37 pm, Francois Grieu <fgr...@gmail.com> wrote:
>> James Dow Allen wrote :
>>> ...
>> Your procedure seems to fail regardless....
>
> Can I try again?
>
> As a building block, I'll use two bottles as a
> flip-flop, normally in either state FO (on) or OF (off).
It would help if you'd detail how one flipflop works,
in particular how you move from FO (on) to OF (off)
and vice versa. Is it thru 00 or FF? If on restart you
see either, what are your next orders?
Then, explain your moves on restart as a function of
information available on restart for each flipflop.
More generally, analyzing the strategies proposed requires
a precise description.
I suggest a general sketch: if you use M bottles out of 10,
there are at most 2 to the M different informations you
can get on restart (some may be impossible). Just state
unambiguously what are your actions on bottles and lights
in any case that can happen.
Have fun.
Francois Grieu
Francois Grieu
> In message <4b661c25$0$10143$426a...@news.free.fr>, Francois Grieu
> <fgr...@gmail.com> writes
>> [polished statement]
>>
>> We must define a procedure which, if executed without interruption,
>> repeatedly: turns "on" a light either "Green" or "Red", turns it
>> "Off", turns it "on" again in the other color ["Red" or "Green"],
>> turns it "off".
>>
>> Our procedure can be interrupted abruptly at *ANY* time [picture a
>> microprocessor which power can disappear without warning], then
>> restarted [most information about what was going on earlier is lost].
>> Before each (re)start, the light gets turned off automatically.
>>
>> If an interruption occurs while the light is "on" in some color, then
>> the next time that the light is turned "on", it must be with the same
>> color [thus one bit of information must be kept about past history to
>> decide that color].
>>
>> The only method to store information across interruptions is the
>> amount of water in 10 identical bottles, initially empty, that we
>> never get to see.
>
> The word "identical" is misleading here. The bottles are
> distinguishable, and might as well be labelled with small integers. It
> would not affect the problem if no. 1 were a beer bottle, no. 2 a milk
> bottle, etc.
Agreed. I said "identical" so that the amount of water poured in a
bottle does not depend on the bottle, but we are better without that
"identical" adjective, and yet another wording: "Fill (..) must be
ordered only on an empty bottle [this avoid overflow while this bottle's
worth of water is pumped into it from the sea]"; or rather we can
dispense with the [] and leave rationale unstated.
>> On (re)start, our procedure is given input about each bottle, either 0
>> for "not full" or 1 for "not empty" [this gives no information for a
>> bottle neither empty nor full; for such a bottle, the input can vary
>> arbitrarily from one restart to another even if the amount of water in
>> the bottle did not change].
>
> I think I know what this means, but I find the statement above confusing
> (though I can now see that it is technically correct). We are not given
> "no information" about a bottle neither empty nor full, we are given
> inaccurate information.
I can't see how "not empty" or "not full" is "inaccurate information"
about a bottle that is half-full, or otherwise neither empty nor full.
> Here is my first attempt at rewriting it:
>
> On (re)start, our procedure is given input about each bottle, either
> "empty" or "full". For a bottle that was being filled or emptied when
> the interruption occurred, this information will be given arbitrarily,
> and can vary arbitrarily from one restart to another even if the amount
> of water in the bottle did not change.
I have two problems with that (the second is minor)
- "the interruption" suggest the last interruption, when it can be any
past interruption;
- "empty" or "full" is inaccurate in some cases such as a bottle
left "half full", and the reader thus as a reason to wonder if the
information "empty" or "full" obtained about bottles that are empty
or full could be inaccurate too.
Francois Grieu
James Dow Allen
> .
> > As a building block, I'll use two bottles as a
> > flip-flop, normally in either state FO (on) or OF (off).
> It would help if you'd detail how one flipflop works,
> in particular how you move from FO (on) to OF (off)
> and vice versa.
To change OF to FO, do Empty 1, Empty 2, Pour 1.
(The initial Empty 1 is just restart thoroughness.)
Note that FF can never arise.
The six information bits should be FOFOFO or OFOFOF,
so on restart I assume whichever state means double-bit error
or better, driving them to a zero-error state as described in
previous post. (If there's a triple bit error, we were
definitely transiting *between* Red and Green and, if I
understood the rules correctly, it doesn't matter whether I
drive the bottles towards zero-error Red or zero-error Green.)
The V1 latch (bottle pair) is assumed to be in the
Disallow-Alteration-of-D1 state *unless* it is FO specifically.
That is, only one V1 state allows D1 alteration.
If on restart V1 is Disallow, you drive it to reliable
Disallow. In that case, I guess you already know a
correct Red/Green state before you even inspect D2 or D3!
If on restart V1 is Allow, you drive it to reliable Allow
(obviously emptying the O before the F !), drive D1 to
the state that conforms with D2/D3, drive V2 to disallow,
and continue on to make D2 and D3 correct and reliable.
> Have fun.
Admit it! My 8-bottle solution works! Any prize for
a 7-bottle solution? :-)
James Dow Allen
James Dow Allen
> We must define a procedure which repeatedly turns "on" a light either
> Green or Red, then turns it "off".
(Your latest message makes me wonder if I misunderstood the
problem all along. If not, the following *may* work.)
I think I have a six-bottle solution. It's related
to my earlier 8-bottle solution, but uses erstwhile
unused latch states to avoid the need for the
"validity" latch.
If it really does work, it seems like overkill and
might lead to a similar 5-bottle solution.
But perhaps there's a mistake: we've seen these
things are fragile. I've thought of writing
a piece of software to verify these things but
*that* would be overkill given all the other
projects I'm procrastinating on! :-)
In this six-bottle solution,
a bottle pair will read out in one of four states
OO -- called O
FO -- called R
OF -- called G
FF -- called Y
The idea is that the third latch will always be
R or G and can then be relied on unless the other
two latches are both in state Y.
Normal operation looks like
R R R --> Y R R --> Y Y R --> Y Y O
then
Y Y O --> Y Y G --> Y G G --> G G G
Transitions after restart are:
O/R O/R R --> O O/R R --> R O/R R -->
Y O/R R --> Y O R --> Y R R --> R R R
Y O/R R --> R O/R R --> as above
O/R Y R --> O/R R R --> as above
and similarly, with G instead of R:
O/G O/G G --> O O/G G --> G O/G G -->
Y O/G G --> Y O G --> Y G G --> G G G
Y O/G G --> G O/G G --> as above
O/G Y G --> O/G G G --> as above
The transitions just shown are all we need
to restore the Red or Green state. We need
now deal only with intermediate or invalid
states. But for this scheme, since neither
Y Y any
nor
any any O
can occur after a correct Red or Green state,
handling the other invalid states is easy.
(Start by emptying both bottles of D3):
any any any --> any any O
--> Y Y O --> normal operation
Francois: Does this work?
James Dow Allen
Francois Grieu
> On Jan 28, 3:13 pm, Francois Grieu <fgr...@gmail.com> wrote:
>> We must define a procedure which repeatedly turns "on" a light either
>> Green or Red, then turns it "off".
>
> (Your latest message makes me wonder if I misunderstood the
> problem all along. If not, the following *may* work.)
>
> I think I have a six-bottle solution. It's related
> to my earlier 8-bottle solution, but uses erstwhile
> unused latch states to avoid the need for the
> "validity" latch.
>
> If it really does work, it seems like overkill and
> might lead to a similar 5-bottle solution.
> But perhaps there's a mistake: we've seen these
> things are fragile. I've thought of writing
> a piece of software to verify these things but
> *that* would be overkill given all the other
> projects I'm procrastinating on! :-)
I've had the very same thought and decided NOT to do it. Until I finish
my current work assignment. Or..
> In this six-bottle solution,
> a bottle pair will read out in one of four states
> OO -- called O
> FO -- called R
> OF -- called G
> FF -- called Y
> The idea is that the third latch will always be
> R or G and can then be relied on unless the other
> two latches are both in state Y.
>
> Normal operation looks like
> R R R --> Y R R --> Y Y R --> Y Y O
> then
> Y Y O --> Y Y G --> Y G G --> G G G
Can I assume that
- transition back from GGG to RRR is thru the opposite path.
- after reaching RRR or GGG the light is lit accordingly and a 1 second
delay occurs
> Transitions after restart are:
>
> O/R O/R R --> O O/R R --> R O/R R -->
> Y O/R R --> Y O R --> Y R R --> R R R
>
> Y O/R R --> R O/R R --> as above
> O/R Y R --> O/R R R --> as above
>
> and similarly, with G instead of R:
>
> O/G O/G G --> O O/G G --> G O/G G -->
> Y O/G G --> Y O G --> Y G G --> G G G
>
> Y O/G G --> G O/G G --> as above
> O/G Y G --> O/G G G --> as above
>
> The transitions just shown are all we need
> to restore the Red or Green state. We need
> now deal only with intermediate or invalid
> states. But for this scheme, since neither
> Y Y any
> nor
> any any O
> can occur after a correct Red or Green state,
> handling the other invalid states is easy.
> (Start by emptying both bottles of D3):
> any any any --> any any O
Just to be sure, let me add:
--> any O O --> O O O -> O Y O
> --> Y Y O --> normal operation
>
> Francois: Does this work?
I see no glitch; but can we be sure without the aforementioned testbed?
Assuming I did not miss something, that's the third correct procedure on
rec.puzzles, and the one with the least bottles. Daniel Giamo had the
first, and is also the second person with a solution, and first to
change mind only once.
IMHO, it looks like time to go after the minimum number of bottles (this
greatly ease verification!); then:
- minimizing the maximum (re)start to on time (reading time);
- maximizing flashing rate assuming no restarts (toggle rate);
- maximizing flashing rate assuming odds p of interrupt each second,
assuming info on bottles neither empty nor full is assigned by coin
toss, with particular interest for p->0 and p->1.
Francois Grieu
Francois Grieu
With David Giaimo's clarification that on restart
oooooooo is case 0;
xooooooo is case 1;
xxoooooo is case 2;
xxxooooo is case 3;
xxxooooo is case 4, other rotations of that are case 8;
xxxxoooo is case 5, other rotations of that are case 6;
xxxxxooo and rotations of that are case 7;
and the actions that David Giaimo describes, I see no loophole.
Congratulations! IMHO David Giaimo was the first rec.puzzler to solve
this, and did that with only one public change of mind, and no incorrect
solution publicly proposed (not my case unless public excludes
coworkers!). He might be the first person to solve the puzzle if, who
knows, my procedures turn out to be wrong. David's procedure is
radically different from my first (hopefully) correct one.
James Dow Allen also posted two procedures that are correct unless I
err, including one with 6 bottles. Therefore, it looks like time to go
after the minimum number of bottles (this greatly ease verification!);
then trying to:
- minimize the maximum (re)start to on time;
- maximize flashing rate assuming no restarts;
- maximize flashing rate assuming odds p of interrupt each second, and
info on bottles neither empty nor full is assigned by coin toss, with
particular interest for p->0 and p->1.
Note: Here is a consise statement of the problem, with provable
equivalence of feasibility, minimum number of bottles, and maximum
(re)start to on time.
http://groups.google.com/group/rec.puzzles/msg/60d29d3a40a57f7e
Francois Grieu
Nick Wedd
writes
If this is a solution, I must still be misunderstanding the puzzle.
Suppose, sometime while we are going round the loop, we order a bottle
to be filled, there is an interrupt, and the bottle ends up shown as
"not empty". So we carry on - and every subsequent time we order a
bottle to be filled, there is an another interrupt, and the bottle again
ends up shown as "not empty". Thereafter we have three or four bottles
which are really empty, and five or four which are "not empty" but are
in fact part full. Then there is another interrupt, after which all
eight are shown as "not full".
It is claimed above that
>>>> In this case we know that we are in the following case:
>>>> aooooooo
I am not sure what this means - nor how we can know which light should
go on next.
James Dow Allen
> >>> Daniel Giaimo wrote:
> >>>> [snip]
> >>>> 2) xooooooo
> >>>> In this case we know that we are in the following case:
> >>>> aboooooo
> >>>> In this case we first empty b.
> >>>> After emptying b we empty a.
> .
> If this is a solution, I must still be misunderstanding the puzzle.
> .
> Suppose, sometime while we are going round the loop, we order a bottle
> to be filled, there is an interrupt, and the bottle ends up shown as
Whenever there's doubt about non-empty bottles upon restart,
the first (or almost first) thing you do is empty them!
Daniel's detailed description seems to make this quite clear,
as in the excerpt above.
James
Francois Grieu
http://groups.google.com/group/rec.puzzles/msg/64868b56d7d8804b
Nick Wedd wrote :
> If this is a solution, I must still be misunderstanding the puzzle.
You get the puzzle, that's for sure! You misunderstood the solution.
> Suppose, sometime while we are going round the loop, we order a bottle
> to be filled, there is an interrupt, and the bottle ends up shown as
> "not empty". So we carry on
No. On restart state reported is matched against 8 cases. What you
describe falls into case 6 if the "worm" was growing from 4 to 5 at the
time of interrupt. Quoting Daniel Giaimo in his post linked above:
>>> 6) ooxxxxoo
>>> In this case we know that we are in the following case:
>>> ocxxxabo
>>> In this case we first empty c. If we are interrupted, we will
>>> restart in either case 6), case 7), or case 8). Next we empty b.
>>> If we are interrupted, we will restart in either case 6), case 7),
>>> or case 8).
>>> Next we empty a. If we are interrupted we will restart in either
>>> case 6) or case 8). Lastly we fill a. If we are interrupted we
>>> will restart in either case 6) or case 8). We are now back in a
>>> known state.
Otherwise stated: if on restart we see a worm of 4 consecutive x/1/"not
empty"/"full-like" when considering the 8 bottles as a circular track,
then we empty one bottle on the left, one bottle on the right [this is
the one left neither empty nor full in the case that you are
considering], and the rightmost x, which we then fill [worm growing from
3 to 4], and we are back with all bottles in known state and the worm
ready to grow from 4 to 5 again. There is a special case when the worm
is on the left and down to size 3, but it occurs only while the light is
off. IMHO David's procedure works.
(snip)
All this shows that given unlimited time the Best Thing would be to
define a syntax to express a strategy and write an automatic randomized
tester, or/and a deterministic checker. This is left as an exercise to
the reader with no deadlines.
I hope that it will become less necessary as rec.puzzle reduces the
number of bottles in the solutions proposed.
Francois Grieu
Nick Wedd
<06e484bc-55ba-4c01...@g8g2000pri.googlegroups.com>,
James Dow Allen <jdall...@yahoo.com> writes
But you don't know there's been a restart, unless a light was on when it
happened. From another posting to this thread:
In message <4b66c6b4$0$23541$426a...@news.free.fr>, Francois Grieu
<fgr...@gmail.com> writes
>Nick Wedd wrote:
>>When we wake up after an interrupt, do we know this? Or do we think
>>we are doing whatever it was we were last doing?
>
>We do not know we have been interrupted doing something with
>a bottle or something else, and must assume either is a
>possibility (except for a strategy with all bottles left empty,
>but we do not get far with this one). And we have no clue of what
>bottle that was (except if our strategy leaves all bottles empty
>except one; try that first).
So if we order a bottle to be filled, we can never be sure we have
succeeded.
Or maybe Francois' reply means that we _do_ know we have been
interrupted, we just don't know what we were doing at the time.
Willem
) But you don't know there's been a restart, unless a light was on when it
) happened. From another posting to this thread:
)
) ...
)
) So if we order a bottle to be filled, we can never be sure we have
) succeeded.
)
) Or maybe Francois' reply means that we _do_ know we have been
) interrupted, we just don't know what we were doing at the time.
When you're interrupted, your program is started from the beginning.
Francois Grieu
> But you don't know there's been a restart, unless a light was on when it
> happened.
My view of my puzzle is that you do know when there has been a restart.
For a programmer, the analogy with a microprocessor makes it clear. "Our
procedure can be interrupted abruptly (..) then restarted" was meant to
imply that on restart, the procedure starts again from the start, but I
(now) realize this must be made explicit!
Francois Grieu
Charles Bryant
Daniel Giaimo <dgi...@gmail.com> wrote:
..
}where o indicates an empty bottle and x indicates a full one.:
}
}oooooooo
}xooooooo
}xxoooooo
}xxxooooo
}xxxxoooo
}(loop)
}(turn green light on)
}xxxxxooo
}oxxxxooo
}oxxxxxoo
}ooxxxxoo
}(turn green light off)
}ooxxxxxo
}oooxxxxo
}oooxxxxx
}ooooxxxx
}(turn red light on)
}xooooxxx
}xxoooxxx
}xxooooxx
}(turn red light off)
}xxxoooxx
}xxxoooox
}xxxxooox
}xxxxoooo
}(goto loop)
}
}The only thing to determine now is what to do if we get interrupted.
}On the first pass through there are 7 (8 after the second restart)
}isomorphism classes of states we could get after restarting : (In the
}following, letters indicate unknown bottles)
}
}1) oooooooo
}
}
}In this case we first empty a.
}2) xooooooo
}In this case we know that we are in the following case:
}
}aboooooo
}
}In this case we first empty b. ... After emptying b we empty a.
}3) xxoooooo
}In this case we know that we are in the following case:
}
}xabooooo
}
}In this case we first empty b. ... After emptying b we empty a.
}4) xxxooooo
}In this case we know that we are in the following case:
}
}xxaboooo
}
}In this case we first empty b. ... After emptying b we empty a.
}5) xxxxoooo
}In this case we know that we are in the following case:
}
}xxxabooc
}
}In this case we first empty c. ... Next we empty b. ... Next we empty a.
}6) ooxxxxoo
}In this case we know that we are in the following case:
}
}ocxxxabo
}
}In this case we first empty c. ... Next we empty b. ... Next we empty a.
} Lastly we fill a.
}7) ooxxxxxo
}In this case we know that we are in the following case:
}
}oobxxxao
}
}In this case we first empty b. ... Lastly we empty a.
}8) ooxxxooo
}In this case we know that we are in the following case:
}
}oooxxxaoo
}
}In this case we empty a. ... We now fill a.
After each:
}... We are now back in a known state.
}Once we are back in a known state as described above we determine the
}location of the cyclically-leftmost filled bottle. If there are at
}least four bottles filled, and the leftmost filled bottle is one of the
}first three bottles, then we turn the green light on, however if it is
}the third bottle we immediately turn it off again. If it is the fourth
}bottle, we leave the light off. If it is one of the next three, we
}turn the red light on, however if it is the seventh bottle we
}immediately turn the light off again. If it is the last bottle, we
}leave the light off. If there are not at least four bottles filled,
}then we leave the light off. In any case, things then proceed as
}described in the diagram above.
I'm not sure if I understand correctly what you mean by "We are now back
in a known state". I'm taking it to mean that all bottles are either
full or empty with no part-filled ones. If so, I think there is a
flaw.
Run the main sequence until the gree light dfirst comes on:
state step
01234567
-------- ----
XXXXoooo fill 4
XXXXpooo reset - read as XXXXXeee - case 7 empty 0
pXXXpooo reset - read as XXXXeeee - case 5 empty 7
pXXXpooo empty 4
pXXXeooo empty 3
pXXeeooo "we are in a known state"
This ends with bottle 0 part filled. An immediate reset after which the
bottles read eXXeeeee is an unhandled state, so I assume a known state
shouldn't have any part-filled bottles.
Daniel Giaimo
<snip description of proposed solution>
> I'm not sure if I understand correctly what you mean by "We are now back
> in a known state". I'm taking it to mean that all bottles are either
> full or empty with no part-filled ones. If so, I think there is a
> flaw.
>
> Run the main sequence until the gree light dfirst comes on:
> state step
> 01234567
> -------- ----
> XXXXoooo fill 4
> XXXXpooo reset - read as XXXXXeee - case 7 empty 0
> pXXXpooo reset - read as XXXXeeee - case 5 empty 7
> pXXXpooo empty 4
> pXXXeooo empty 3
> pXXeeooo "we are in a known state"
>
> This ends with bottle 0 part filled. An immediate reset after which the
> bottles read eXXeeeee is an unhandled state, so I assume a known state
> shouldn't have any part-filled bottles.
Yes. You're right, though I think this solution can definitely be
modified to handle this case. It should just involve a few more
potentially indeterminate bottles. I'll need to think about it a
bit before I give a corrected solution.
--
Dan Giaimo
Francois Grieu
A remark that I think helps in this case: when one is after correctness
rather than performance, it never impairs correctness to first empty
each bottle reported as "not full" on (re)start.
Also: my best (hopefully) correct procedure uses less bottles, this is
easier to check.
Francois Grieu
Daniel Giaimo
Looks like I spoke too soon. From what I can tell at this point, this
solution is fundamentally flawed. Back to the drawing board...
--
Dan G