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
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:
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
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.