Just for fun, the 100 door problem on several different systems

Just for fun, the 100 door problem on several different systems
Photo by Filip Kominik / Unsplash

What'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.