Just for fun, the 100 door problem on several different systems
By Michael Doornbos
- 6 minutes read - 1099 wordsWhat’s the 100 door problem?
It’s a just for fun problem in “beginning” math and computer courses. The idea is simple:
There are 100 closed doors in a row.
You walk past the doors 100 times (100 passes)
The first time, visit every door. If the door is closed, open it. If it is open, close it. In programming, you’d probably call this toggling the door so let’s call it that.
The second time, ONLY visit every 2nd door and toggle it. (door 2, 4, 6, etc)
The third time, ONLY visit every 3rd door and toggle it. (door 3, 6, 9, etc)
Keep going through this loop over and over until you get to the loop where there’s only the last door.
Which doors are open? Can you guess before we solve it?
Let’s break this down in a program
We could do this as a quick loop and get the answer.
10 DIM D(100)
20 FOR I=1 TO 100
30 FOR J=I TO 100 STEP I
40 D(J) = NOT D(J)
50 NEXT J
60 NEXT I
70 FOR I=1 TO 100
80 IF D(I) THEN PRINT I,
90 NEXT I
But this isn’t terribly fun.
My favorite way to solve this problem is on an old computer where you can directly use screen locations. If you think about it, you can use those locations to store data AND visualize what’s happening.
This is WAY more FUN
The Commodore VIC-20 is a perfect candidate for this. On an unexpanded VIC, you are also making good use of screen memory that’s already allocated to the screen but not being used for anything else. Those 3585 Free Bytes get used up quickly sometimes.
There are two built-in characters on Commodore computers that work pretty well for this. You’re free to use whatever you want, including creating a couple of characters if you REALLY want them to look like doors.
Characters 81 and 87 are closed circle and open circle. They look a little like LED lights that are on and off. We’ll be using these.
1 REM 100 DOOR PROBLEM USING SCREEN MEMORY
5 TI$="000000":PRINT CHR$(147)
10 FORI=38796-5*22TO38911:POKEI,0:NEXTI
20 D=8185-5*22:FORI=1TO100:POKED+I,81:NEXTI
30 FORI=1TO100
40 FORJ=ITO100STEPI
50 IFPEEK(D+J)=87THENPOKED+J,81:GOTO70
60 POKED+J,87
70 NEXT J
80 NEXT I
85 PRINT"JIFFIES:"TI
90 FOR I=1TO100
100 IF PEEK(D+I)=87 THEN PRINT I,
110 NEXT I
Other Commodores
On Commodore 64 and 128, you only need to change lines 10 and 20.
Change lines 10 and 20 to:
10 FORI=56296-3*40TO56296:POKEI,1:NEXTI
20 D=2023-3*40:FORI=1TO100:POKED+I,81:NEXTI
On the Commodore PET you can remove line 10 since it doesn’t have color and change line 20 to:
20 D=33767-3*40:FORI=1TO100:POKED+I,81:NEXTI
Atari BASIC
There aren’t the same characters on the Atari, but I think 128 and 96 work pretty well. The program is basically the same. Clearing the screen is 125 rather than 147, and the default screen location starts a 40000 decimal.
1 REM 100 DOOR PROBLEM USING SCREEN MEMORY
5 PRINT CHR$(125)
20 D=40839:FOR I=1 TO 100:POKE D+I,128:NEXT I
30 FOR I=1 TO 100
40 FOR J=I TO 100 STEP I
50 IF PEEK(D+J)=128 THEN POKE D+J,96:GOTO 70
60 POKE D+J,128
70 NEXT J
80 NEXT I
90 FOR I=1TO100
100 IF PEEK(D+I)=96 THEN PRINT I," "
110 NEXT I
Color Maximite 2
This one is a little more tricky to port. On the Maximite, the screen locations aren’t really locations like they are in the previous examples, and the dialect of BASIC is quite different. Here’s what I came up with. Can you think of a better way?
MODE 4
DIM doors(100)
for pass = 1 TO 199
for door = pass TO 100 step pass
doors(door) = NOT doors(door)
for d = 1 to 100
if d<50 then
h=0
o=0
else
h=9
o=392
endif
if doors(d) then text d*8-o,h,chr$(130)
if not doors(d) then text d*8-o,h,chr$(128)
for x=1 to 100
next x
next d
next door
next pass
print
FOR door =1 to 100
if doors(door) then print door;
next door
for w = 1 to 10000000
next w
Extra Credit
You almost certainly don’t have a CERBERUS 2080, but it’s an interesting machine. It’s about as pure of a 6502 Assembly environment as I can think of that’s not a complete pain to use. There are no Kernal routines for printing, etc., so we need to do EVERYTHING manually.
I don’t know if this is the most efficient way to do this. Luckily, since we’re going for the visual effect, we need it to be slow and add a TON of slowness.
Charloop 1 and 2 create some new characters. Delay is where we waste a ton of time to slow it down.
The decimal conversion routine is almost a direct copy of Garth Wilson’s.
org $0202
ldx #$00
lda #32
clearsc
sta $f800,x
sta $f900,x
sta $fa00,x
sta $fb00,x
sta $fc00,x
inx
bne clearsc
ldx #0
lda #$ff
charloop1
sta $f000,x
inx
cpx #8
bcc charloop1
ldx #0
lda #$81
charloop2
sta $f008,x
inx
cpx #8
bcc charloop2
lda #$ff
sta $f008
sta $f00f
lda #00
ldx #0
loop1
stx $fb
jsr delay
ldx $fb
sta $fc37,X
inx
cpx #100
bne loop1
sta $fc37,X
ldy #01
loop2
cpy #101
bcs done4
tya
loop3
;;;;;;;;;;
sty $fc
jsr delay
ldy $fc
;;;;;;;;;;
cmp #101
bcs done3
tax
pha
lda $fc37,x
eor #$01
sta $fc37,x ; Toggle door
pla
sty $fc
adc $fc
bcc loop3
done3
iny
bne loop2
done4
ldx #0
loop4
stx $fb
stx lobyte
lda $fc37,x
beq skip
jsr conv
ldx $fb
lda result+2
cmp #$30
beq skipz1
sta $f800,x
skipz1
lda result+3
cpx #99
bcs over
cmp #$30
beq skipz
over
sta $f800+1,x
skipz
lda result+4
sta $f800+2,x
skip
inx
cpx #101
bne loop4
lda #32
sta $fc37
rts
;--------
delay
ldy #$18
loopdx
ldx #$ff
loopd
dex
bne loopd
dey
bne loopdx
rts
;--------------------------------------------
conv
lda #$30
ldy #$04
clear
sta result,y
dey
bne clear
ldx #$4f
loop9
clc
rol lobyte
rol hibyte
bcs calculate
txa
sec
sbc #$05
tax
bpl loop9
end
rts
calculate
clc
ldy #$04
loop10
lda table,x
adc #$00
beq zero
adc result,y
cmp #$3a
bcc notten
sbc #$0a
notten
sta result,y
zero
dex
dey
bpl loop10
jmp loop9
table
.byte 0,0,0,0,1
.byte 0,0,0,0,2
.byte 0,0,0,0,4
.byte 0,0,0,0,8
.byte 0,0,0,1,6
.byte 0,0,0,3,2
.byte 0,0,0,6,4
.byte 0,0,1,2,8
.byte 0,0,2,5,6
.byte 0,0,5,1,2
.byte 0,1,0,2,4
.byte 0,2,0,4,8
.byte 0,4,0,9,6
.byte 0,8,1,9,2
.byte 1,6,3,8,4
.byte 3,2,7,6,8
result .byte 0,0,0,0,0
lobyte .byte $00
hibyte .byte $00
All Together Now
“So what?” You might ask.
Well to me what’s interesting is that for 100 doors, all of the remaining doors that are open are all of the perfect squares.