By Dr. Peter Wayne
My old college chum, Chad Paperwaite, was on the cell phone. "For Pete's sake, Pete, you've got to help me out," he sputtered. "You know I'm the supervisor of elections here in Jambalaya County, and we're having a devil of a time invalidating, I mean counting, Democratic ballots. I need every man Jack I can recruit. Can I count on you?" The November weather in New York being what it is, I was flown on a wave of nostalgia (Nostalgia Airlines, that is) into Okeefenokee Airport and limo'd into the Jambalaya County Courthouse, where Chad and I sat for hours on end, holding paper ballots up to 40 watt bulbs and discarding Democratic votes in the interests of a fair and free election and lower estate taxes for estates over $600,000.
So there we were one evening, burping contentedly on Chad's veranda after a heart-healthy meal of chicken wings fried in bacon fat, when Chad, ever a fount of election lore, spoke up. "Do you know," he belched, " ballot supervisors the world around owe their inspiration to Josephus Flavius?"
"Josephus who?," replied your present correspondent.
"Josephus Flavius. He was a Jewish historian of the first century who wrote about the Jewish-Roman wars. And a expert on invalidating ballots."
"Please explain, Chad." - my curiosity was piqued.
Chad was so excited, he accidentally flicked some cigar ash into his mint julep. Or maybe it was my mint julep - we were both pretty bleary-eyed at that point.
"The legend is that old Joe was stuck in a cave with 40 Jewish soldiers, surrounded by hostile Roman troops", continued Chad. "The Jewish partisans - fanatics to the core - decided on suicide rather than surrender. They formed a circle, and beginning with the first soldier, counted down by 3's. Every 3rd soldier would impale himself on his sword, and the counting continued. Eventually, of course, only one soldier would be left, and he would be the last to kill himself. Except that Joe knew that the world would be interested in his writings, so in a lightning calculation he insinuated himself in the circle so that he would be the last survivor. At that point, he just hid himself in the back of the cave until the Romans had gone."
"I think I see," I replied. "Let's say there were only 5 soldiers: Adam, Bobby, Chuckie, Dave, and Eddie. If we count by 3's, then Chuckie is the first one down, followed by Adam. That leaves only Bobby, Dave, and Eddie, so Eddie is the next one out. We then count Bobby, Dave, and Bobby again, so it's Bobby's turn to eat his sword. That leaves Dave."
"You've got it," congratulated Chad. "But can you solve the problem for a circle of 41 soldiers?"
Well, I have no idea how Josephus Flavius managed it, but with the help of Alpha Five I designed 2 ways of solving what has become known in computing circles as the Josephus Problem.
In the first method, I created a table of soldiers, with a single field, "soldier_num", defined as Numeric, width 4, 0 decimal points:
Fig. 1. Structure of soldier.dbf
I also decided I wanted to see the review the order in which the soldiers are removed from the circle, so I created a second table, "josephus.dbf", with the same structure. As soldiers are removed from soldier.dbf they are entered into josephus.dbf.
I then wrote a short script to fill soldier.dbf and then to delete every 3rd record. When I come to the last record, of course, I have to resume counting at the beginning:
nsoldiers=val(ui_get_number("How many soldiers in the circle?","","41"))
if nsoldiers=0 then
end
end if
interval=val(ui_get_number("Count how many before removing one?","","3"))
if interval=0 then
end
end if
josephus=table.open("josephus",file_rw_exclusive)
josephus.zap(.t.)
josephus.fetch_first()
t1=toseconds(time())
soldier=table.open("soldier",file_rw_exclusive)
soldier.zap(.t.)
soldier.fetch_first()
' fill up soldier table
for i=1 to NSOLDIERS
soldier.enter_begin()
soldier.soldier_num=i
soldier.enter_end(.t.)
next
soldier.close()
soldier=table.open("soldier",file_rw_shared)
soldier.fetch_first()
ndeletes=0
while ndeletes<NSOLDIERS-1
for i=1 to interval-1
soldier.fetch_next()
if soldier.fetch_eof() then
soldier.fetch_first()
end if
next
josephus.enter_begin()
josephus.soldier_num=soldier.soldier_num
josephus.enter_end(.t.)
soldier.change_begin()
soldier.delete()
soldier.change_end(.t.)
if soldier.fetch_eof() .or. soldier.is_deleted() then
soldier.fetch_first()
end if
ndeletes=ndeletes+1
end while
t2=toseconds(time())
ui_msg_box("last soldier remaining",str(soldier.soldier_num))
soldier.close()
josephus.close()
ui_msg_box("time elapsed",str(t2-t1)+ " seconds")
' show a list of soldiers as they are removed from circle
Browse.View("Default Browse for josephus@josephus.dbf")
Script 1.
If there's one thing I learned from Chad, it's that there's always more than one way to count. This first method gets rather slow as the circle gets larger and larger - it takes quite some time to create and delete records, and for a circle of 2000 soldiers, it takes about 6 minutes on my computer. If all the work is done with records in memory, then most of the overhead is gone. Instead of using a table, then, I created an array of soldiers. Each member of the array is a pointer variable, and each pointer variable has an element, "next", that lists the number of the next soldier in the circle. As soldiers are deleted, the "next" elements are updated to bypass the dead soldiers. For example, if we start with:
| Soldier | "Next" |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |
| 4 | 5 |
| 5 | 1 |
After soldier 3 is killed, the array looks like this:
| Soldier | "Next" |
| 1 | 2 |
| 2 | 4 |
| 3 | 4 |
| 4 | 5 |
| 5 | 1 |
As we walk through the array, we skip directly from soldier 2 to soldier 4, bypassing soldier 3, who is, alas!, no longer with us.
The array-based script follows:
nsoldiers=val(ui_get_number("How many soldiers in the circle?",""))
if nsoldiers=0 then
end
end if
interval=val(ui_get_number("Count how many before removing one?",""))
if interval=0 then
end
end if
josephus=table.open("josephus",file_rw_exclusive)
josephus.zap(.t.)
josephus.fetch_first()
t1=toseconds(time())
dim soldier[nsoldiers] as p
for i=1 to nsoldiers-1
soldier[i].next=i+1
next
soldier[nsoldiers].next=1
ndeletes=0
j=0
while ndeletes<NSOLDIERS-1
for i=1 to interval
last=j
if j>0 then
j=soldier[j].next
else
j=1
end if
next
josephus.enter_begin()
josephus.soldier_num=j
josephus.enter_end(.t.)
soldier[last].next=soldier[j].next
ndeletes=ndeletes+1
end while
t2=toseconds(time())
ui_msg_box("last soldier remaining",str(last))
josephus.close()
ui_msg_box("time elapsed",str(t2-t1))
Browse.View("Default Browse for josephus@josephus.dbf")
Script 2.
The array-based method operates many times faster than the table-based method.
A word of caution: in Script 1, it is absolutely necessary that soldier.dbf be closed and then reopened in shared mode. If the deletions are performed in exclusive access mode, then a subtle bug in A5v4 will surface and some records marked for deletion may not, in fact, get deleted. This bug should be fixed by the time A5v5 appears. Josephus, of course, did not have to worry about computer glitches. Indeed, Josephus' most famous quote is "When my life depends on it, I'll take a hand count every time."
11/19/00
Don't forget, we need your feedback to make this site better!