THE PUZZLET PAGE

PUZZLET 054 - THE SOLUTION
Here's a program, written in IBasic, which will solve the Puzzlet. A detailed description and explanation follow below it.

' Puzzlet #054
' 1,000 bottles are empty.  Every 2nd bottle
' is now filled with water.  Now every 3rd
' bottle is examined.  If it's empty, it has
' to be filled.  If it already contained
' water, it has to be emptied.  This process
' is repeated for every 4th bottle, then
' every 5th, and so on up to the 1,000th.
' At the end of the process, what bottles,
' if any, will be empty?
' By Dave Ellis.

declare InitialiseArray()
declare InvertStates(s: int)
declare PrintResult()
def BottleArray[1001]: int
def i: int
openconsole
print "Counting ...": print

InitialiseArray()
for i = 2 to 1000
    InvertStates(i)
next i
PrintResult()

 print: print "Press any key to exit ... ",
do: until inkey$ <> ""
closeconsole
end

sub InitialiseArray
' sets all bottles to empty state
def it: int
for it = 1 to 1000
    BottleArray[it] = -1: 'empty bottle
next it
return

sub InvertStates(s)
' fills empty bottle, empties full bottles
def p: int
p = s: ' p points to current bottle
do
    BottleArray[p] = -1 *BottleArray[p]
    p = p + s
until p > 1000
return

sub PrintResult
' pretty printer
def it, psn: int
print
print "The following bottles are empty:"
print
it = 1
psn = 0: 'used to control position on screen
do
    if BottleArray[it] = -1: 'is bottle empty?
        psn = psn + 1
        print using ("####", it),
        if psn > 7
            print
            psn = 0
        endif
    endif
    it = it + 1
until it > 1000
print
return

PROGRAM NOTES

Now we need to think carefully about the algorithm we're going to use.  I've made a simple flowchart of it to help me describe it.

We begin by creating an array to hold and represent the 1,000 bottles, BottleArray[].  I have created the convention that a full bottle is represented by loading its field in the array with a digital 1, and an empty bottle is represented by a digital -1. You'll see the reason for this shortly. The program automatically comes up with all the "bottles" loaded with a digital 0, so the subroutine InitialiseArray() is called to set all the bottles to empty before doing anything else.

 Puzzlet 054 FlowChart

This problem is very simple to code.  Using variable i as a bottle pointer, we can run through the array emptying and filling bottles as necessary from the value of i. We start with pointer i set to 2.  The algorithm calls for the code to ask whether the bottle is full or empty at this time. The code implements this requirement by calling subroutine InvertStates(i). Note that pointer i is used to tell the subroutine whereabouts to start inverting states.  When you look at the code of InvertStates(), you can see how it inverts the state, using the line BottleArry[p] = -1*BottleArray[p]. Multiplying by -1 always does this, which is why the values -1 and 1 were chosen to represent the states. It means we don't even have to check the values - the process always inverts them regardless of their existing values. The table shows why it works.
Current State
 Multiplier
 New State
 1
 -1
 -1
-1
 -1
  1

InvertStates() continues to be a core subroutine here.  It takes as argument the value passed in variable i (used as a pointer, you'll recall), using the local variable name s (for step).  It uses s to step through the whole of BottleArray[] s cells at a time, as required in the specification, emptying any full bottles it encounters along the way, and filling any empty bottles.  When all the bottles have been processed in this way, control is returned to main routine.

The main routine then continues the process by incrementing pointer i, and thus the step size s which will be used next time InvertStates[] runs through all the bottles again.  You can clearly see this algorithm in the flowchart.  I didn't show it in the flowchart, but the process ends after the pointer has been set to 1,000.

At the end of the process, PrintResult[] runs through the array of bottles. Whenever it finds an empty one, it prints its number in the array to the screen.  Remarkably, it turns out that all the square numbers are there - and nothing else!  This is, in fact, a well-known result, and has been a subject of interest to mathematicians for many years.


When you run the code, it generates the screen shown inset.  As shown in the program notes, only the bottles having square numbers are filled when the process is complete.
Counting ...

The following bottles are empty:

     1     4     9    16   25    36   49   64
   81 100 121 144 169 196 225 256
 289 324 361 400 441 484 529 576
 625 676 729 784 841 900 961

Press any key to exit ...
Site design/maintenance: Dave Ellis E-mail me!
 Last Updated: November 24th, 2009.