100 doors

From Rosetta Code

Problem: You have 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, you visit every door and toggle the door (if the door is closed, you open it; if it is open, you close it). The second time you only visit every 2nd door (door #2, #4, #6, ...). The third time, every 3rd door (door #3, #6, #9, ...), etc, until you only visit the 100th door.

Question: What state are the doors in after the last pass? Which are open, which are closed? [1]

Alternate: As noted in this page's discussion page, the only doors that remain open are whose numbers are perfect squares of integers. Opening only those doors is an optimization that may also be expressed.

Contents 1 Ada 1.1 unoptimized 1.2 optimized 2 ALGOL 68 2.1 unoptimized 2.2 optimized 3 BASIC 3.1 unoptimized 3.2 optimized 4 C 4.1 unoptimized 4.2 optimized 5 C++ 5.1 unoptimized 5.2 optimized 6 D 6.1 unoptimized 6.2 optimized 7 Forth 8 Fortran 8.1 unoptimized 8.2 optimized 9 Haskell 9.1 unoptimized 9.2 optimized 10 J 10.1 unoptimized 10.2 optimized 11 Java 11.1 unoptimized 11.2 optimized 12 MAXScript 12.1 unoptimized 12.2 optimized 13 OCaml 13.1 unoptimized 13.2 optimized 14 Perl 14.1 unoptimized 14.2 optimized 15 Pop11 15.1 unoptimized 15.2 optimized 16 Python 16.1 unoptimized 16.2 optimized 17 R 17.1 unoptimized 17.2 optimized 18 Ruby 18.1 unoptimized 18.2 optimized 19 Scheme 19.1 unoptimized 19.2 optimized 20 Visual Basic .NET 20.1 unoptimized 20.2 optimized

[edit] Ada

[edit] unoptimized

with Ada.Text_Io; use Ada.Text_Io;
 
 procedure Doors is
    type Door_State is (Closed, Open);
    type Door_List is array(Positive range 1..100) of Door_State;
    The_Doors : Door_List := (others => Closed);
 begin
    for I in 1..100 loop
       for J in The_Doors'range loop
          if J mod I = 0 then
             if The_Doors(J) = Closed then
                 The_Doors(J) := Open;
             else
                The_Doors(J) := Closed;
             end if;
          end if;
       end loop;
    end loop;
    for I in The_Doors'range loop
       Put_Line(Integer'Image(I) & " is " & Door_State'Image(The_Doors(I)));
    end loop;
 end Doors;

[edit] optimized

with Ada.Text_Io; use Ada.Text_Io;
 with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions;
 
 procedure Doors_Optimized is
    Num : Float;
 begin
    for I in 1..100 loop
       Num := Sqrt(Float(I));
       Put(Integer'Image(I) & " is ");
       if Float'Floor(Num) = Num then
          Put_Line("Opened");
       else
          Put_Line("Closed");
       end if;
    end loop;
 end Doors_Optimized;

[edit] ALGOL 68

[edit] unoptimized

# declare some constants #
INT limit = 100;

PROC doors = VOID:
(
  MODE DOORSTATE = BOOL;
  BOOL closed = FALSE;
  BOOL open = NOT closed;
  MODE DOORLIST = [limit]DOORSTATE;

  DOORLIST the doors;
  FOR i FROM LWB the doors TO UPB the doors DO the doors[i]:=closed OD;

  FOR i FROM LWB the doors TO UPB the doors DO
    FOR j FROM LWB the doors TO UPB the doors DO
      IF j MOD i = 0 THEN
        the doors[j] :=  NOT the doors[j]
      FI
    OD
  OD;
  FOR i FROM LWB the doors TO UPB the doors DO
    printf(($g" is "gl$,i,(the doors[i]|"opened"|"closed")))
  OD
);
doors;

[edit] optimized

PROC doors optimised = ( INT limit )VOID:
  FOR i TO limit DO
    REAL num := sqrt(i);
    printf(($g" is "gl$,i,(ENTIER num = num |"opened"|"closed") ))
  OD
;
doors optimised(limit)

[edit] BASIC

Works with: QuickBasic version 4.5

[edit] unoptimized

DIM doors(0 TO 99)
FOR pass = 0 TO 99
	FOR door = pass TO 99 STEP pass + 1
		PRINT doors(door)
		PRINT NOT doors(door)
		doors(door) = NOT doors(door)
	NEXT door
NEXT pass
FOR i = 0 TO 99
	PRINT "Door #"; i + 1; " is ";
	IF NOT doors(i) THEN
		PRINT "closed"
	ELSE
		PRINT "open"
	END IF
NEXT i

[edit] optimized

DIM doors(0 TO 99)
FOR door = 0 TO 99
	IF INT(SQR(door)) = SQR(door) THEN doors(door) = -1
NEXT door
FOR i = 0 TO 99
	PRINT "Door #"; i + 1; " is ";
	IF NOT doors(i) THEN
		PRINT "closed"
	ELSE
		PRINT "open"
	END IF
NEXT i

[edit] C

[edit] unoptimized

#include <stdio.h>

int main()
{
  char is_open[100] = { 0 };
  int pass, door;

  // do the 100 passes
  for (pass = 0; pass < 100; ++pass)
    for (door = pass; door < 100; door += pass+1)
      is_open[door] = !is_open[door];

  // output the result
  for (door = 0; door < 100; ++door)
    printf("door #%d is %s.\n", door+1, (is_open[door]? "open" : "closed"));

  return 0;
}

[edit] optimized

This optimized version makes use of the fact that finally only the doors with square index are open, as well as the fact that <math>n^2 = 1 + 3 + 5 + \ldots + (2n+1)</math>.

#include <stdio.h>

int main()
{
  int square = 1, increment = 3, door;
  for (door = 1; door <= 100; ++door)
  {
    printf("door #%d", door);
    if (door == square)
    {
      printf(" is open.\n");
      square += increment;
      increment += 2;
    }
    else
      printf(" is closed.\n");
  }
  return 0;
}

The following ultra-short optimized version demonstrates the flexibility of C loops, but isn't really considered good C style:

#include <stdio.h>

int main()
{
  int door, square, increment;
  for (door = 1, square = 1, increment = 1; door <= 100; door++ == square && (square += increment += 2))
    printf("door #%d is %s.\n", door, (door == square? "open" : "closed"));
  return 0;
}

[edit] C++

Works with: GCC version 4.1.2 20061115 (prerelease) (SUSE Linux)

[edit] unoptimized

#include <iostream>

int main()
{
  bool is_open[100] = { false };

  // do the 100 passes
  for (int pass = 0; pass < 100; ++pass)
    for (int door = pass; door < 100; door += pass+1)
      is_open[door] = !is_open[door];

  // output the result
  for (int door = 0; door < 100; ++door)
    std::cout << "door #" << door+1 << (is_open[door]? " is open." : " is closed.") << std::endl;
  return 0;
}

[edit] optimized

This optimized version makes use of the fact that finally only the doors with square index are open, as well as the fact that <math>n^2 = 1 + 3 + 5 + \ldots + (2n+1)</math>.

#include <iostream>

int main()
{
  int square = 1, increment = 3;
  for (int door = 1; door <= 100; ++door)
  {
    std::cout << "door #" << door;
    if (door == square)
    {
      std::cout << " is open." << std::endl;
      square += increment;
      increment += 2;
    }
    else
      std::cout << " is closed." << std::endl;
  }
  return 0;
}

The following ultra-short optimized version demonstrates the flexibility of C++ loops, but isn't really considered good C++ style:

#include <iostream>

int main()
{
  for (int door = 1, square = 1, increment = 1; door <= 100; door++ == square && (square += increment += 2))
    std::cout << "door #" << door << (door == square? " is open." : " is closed.") << std::endl;
  return 0;
}

[edit] D

module l00door ;
import std.stdio ;

alias char[] DOOR ;       // or alias bool[] DOOR
const char OPEN = 'O' ;   // then OPEN = true
const char CLOSE = 'x' ;  //      CLOSE = false 

[edit] unoptimized

DOOR flip_u(inout DOOR d) {
  d[] = CLOSE ;
  for(int i= 0 ; i < d.length ; i++)
    for(int j = i ; j < d.length ; j += i + 1)
      if (d[j] == OPEN)
        d[j] = CLOSE ;
      else
        d[j] = OPEN ;
  return d ;  
}

[edit] optimized

DOOR flip_o(inout DOOR d) {
  d[] = CLOSE ;
  for(int i= 1 ; i*i <= d.length  ; i++)
    d[i*i-1] = OPEN ;
  return d ;  
}

test program:

void main() {
  DOOR d ;
  d.length = 100 ;
  writefln(d.flip_u()) ;
  writefln(d.flip_o()) ;  
}

[edit] Forth

: doors ( n -- )
  here over erase         \ open all doors
  dup 0 do
    here over + here i + do
      i c@  1 xor  i c!   \ toggle
    j 1+ +loop
  loop
  ." Closed doors: "
  ( n ) 0 do
    here i + c@ if i 1+ . then
  loop cr ;

100 doors

[edit] Fortran

Works with: Fortran version ISO 90 and later

[edit] unoptimized

PROGRAM DOORS

  INTEGER, PARAMETER :: n = 100    ! Number of doors
  INTEGER :: i, j
  LOGICAL :: door(n) = .TRUE.      ! Initially closed
 
  DO i = 1, n
    DO j = i, n, i
      door(j) = .NOT. door(j)
    END DO
  END DO 

  DO i = 1, n
    WRITE(*,"(A,I3,A)", ADVANCE="NO") "Door ", i, " is "
    IF (door(i)) THEN
      WRITE(*,"(A)") "closed"
    ELSE
      WRITE(*,"(A)") "open"
    END IF
  END DO
 
END PROGRAM DOORS

[edit] optimized

PROGRAM DOORS

  INTEGER, PARAMETER :: n = 100    ! Number of doors
  INTEGER :: i
  LOGICAL :: door(n) = .TRUE.      ! Initially closed
 
  DO i = 1, SQRT(REAL(n))
    door(i*i) = .FALSE.
  END DO  
 
  DO i = 1, n
    WRITE(*,"(A,I3,A)", ADVANCE="NO") "Door ", i, " is "
    IF (door(i)) THEN
      WRITE(*,"(A)") "closed"
    ELSE
      WRITE(*,"(A)") "open"
    END IF
  END DO
 
END PROGRAM DOORS

[edit] Haskell

[edit] unoptimized

data Door = Open | Closed deriving Show

toggle f []          = []
toggle f (Open:xs)   = Closed : f xs
toggle f (Closed:xs) = Open   : f xs

pass k [] = []
pass k xs = ys ++ toggle (pass k) zs where (ys,zs) = splitAt k xs

run n = snd $ (!! n) $ 
  iterate (\(k,xs) -> (k+1, pass k xs)) $ (0, replicate n Closed)

[edit] optimized

(without using square roots)

gate :: Eq a => [a] -> [a] -> [Door]
gate (x:xs) (y:ys) | x == y  =  Open   : gate xs ys
gate (x:xs) ys               =  Closed : gate xs ys
gate []     _                =  []

run n = gate [1..n] [k*k | k <- [1..]]

alternatively, returning a list of all open gates, it's a one-liner:

run n = takeWhile (< n) [k*k | k <- [1..]]

[edit] J

[edit] unoptimized

   ~:/ (100 $ - {. 1:)"0 >:i.100
1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ...

[edit] optimized

   (>:i.100) e. *: i.11
1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ...
   1 (<:*:i.10)} 100$0  NB. alternative
1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 ...

[edit] Java

[edit] unoptimized

public class Doors {
	public static void main(String[] args) {
		boolean[] doors = new boolean[100];
		for(int pass = 0; pass < 100; pass++){
			for(int door = pass; door < 100; door += pass + 1){
				doors[door] = !doors[door];
			}
		}
		for(int i = 0; i < 100; i++){
		 	System.out.println("Door #" + (i + 1) + " is " + (doors[i] ? 
		 				"open." : "closed."));
		}
	}
}

[edit] optimized

public class Doors {
	public static void main(String[] args) {
		boolean[] doors = new boolean[100];
		for(int pass = 0; pass < 10; pass++){
			doors[(pass + 1) * (pass + 1) - 1] = true;
		}
		for(int i = 0; i < 100; i++){
			System.out.println("Door #" + (i + 1) + " is " + (doors[i] ? 
						"open." : "closed."));
		}
	}
}

[edit] MAXScript

[edit] unoptimized

doorsOpen = for i in 1 to 100 collect false

for pass in 1 to 100 do
(
    for door in pass to 100 by pass do
    (
        doorsOpen[door] = not doorsOpen[door]
    )
)

for i in 1 to doorsOpen.count do
(
    format ("Door % is open?: %\n") i doorsOpen[i]
)

[edit] optimized

for i in 1 to 100 do
(
    root = pow i 0.5
    format ("Door % is open?: %\n") i (root == (root as integer))
)

[edit] OCaml

[edit] unoptimized

let max_doors = 100

let show_doors =
  Array.iteri (fun i x -> Printf.printf "Door %d is %s\n" (i+1)
                                        (if x then "open" else "closed"))

let flip_doors doors =
  for i = 1 to max_doors do
    let rec flip idx =
      if idx < max_doors then begin
        doors.(idx) <- not doors.(idx);
        flip (idx + i)
      end
    in flip (i - 1)
  done;
  doors

let () =
  show_doors (flip_doors (Array.make max_doors false))

[edit] optimized

let optimised_flip_doors doors =
  for i = 1 to int_of_float (sqrt (float_of_int max_doors)) do
    doors.(i*i - 1) <- true
  done;
  doors

let () =
  show_doors (optimised_flip_doors (Array.make max_doors false))

[edit] Perl

[edit] unoptimized

Works with: Perl version 5.x

my @doors;
foreach my $pass (1 .. 100) {
    foreach (1 .. 100) {
        if (0 == $_ % $pass) {
            if (1 == $doors[$_]) {
                $doors[$_] = 0;
            } else {
                $doors[$_] = 1;
            };
        };
    };
};

print "$_\t$doors[$_]\n" foreach 1 .. 100;

[edit] optimized

Works with: Perl version 5.x

while( ++$i <= 100 )
{
        $root = sqrt($i);
        if ( int( $root ) == $root )
        {
                print "Door $i is open\n";
        }
        else
        {
                print "Door $i is closed\n";
        }
}

[edit] Pop11

[edit] unoptimized

lvars i;
lvars doors = {% for i from 1 to 100 do false endfor %};
for i from 1 to 100 do
   for j from i by i to 100 do
      not(doors(j)) -> doors(j);
   endfor;
endfor;
;;; Print state
for i from 1 to 100 do
   printf('Door ' >< i >< ' is ' ><
            if doors(i) then 'open' else 'closed' endif, '%s\n');
endfor;

[edit] optimized

lvars i, ri, rri, s;
for i from 1 to 100 do
    sqrt(i) -> ri;
    round(ri) -> rri;
    if rri = ri then 'open' else 'closed' endif -> s;
    printf('Door ' >< i >< ' is ' >< s, '%s\n');
endfor;

[edit] Python

Note: both versions require Python 2.5 for the ternary syntax.

[edit] unoptimized

close = 0
open = 1
doors = [close] * 100
  
for i in range(100):
    for j in range(i, 100, i+1):
        doors[j] = open if doors[j] is close else close
    print "Door %d:" % (i+1), 'open' if doors[i] else 'close'
  
for k, door in enumerate(doors):
    print "Door %d:" % (k+1), 'open' if door else 'close'

[edit] optimized

A version that only visits each door once:

for i in xrange(1, 101):
    root = i ** 0.5
    print "Door %d:" % i, 'open' if root == int(root) else 'close'

[edit] R

[edit] unoptimized

doors_puzzle <- function(ndoors=100,passes=100) {
    doors <- rep(FALSE,ndoors)
    for (ii in seq(1,passes)) {
        mask <- seq(0,ndoors,ii)
        doors[mask] <- !doors[mask]	
    }
    return (which(doors == TRUE))
}

doors_puzzle()

[edit] optimized

## optimized version... we only have to to up to the square root of 100
seq(1,sqrt(100))**2

[edit] Ruby

[edit] unoptimized

n = 100
Open = "open"
Closed = "closed"
def Open.f
    Closed
end
def Closed.f
    Open
end
doors = [Closed] * (n+1)
for mul in 1..n
    for x in 1..n
        doors[mul*x] = (doors[mul*x] || break).f
    end
end
doors.each_with_index {
    |b, i|
    puts "Door #{i} is #{b}" if i>0
}

[edit] optimized

n = 100
doors = ["closed"] * (n+1)
for x in 1..n
    doors[x**2] = (doors[x**2] || break) && "open"
end
doors.each_with_index {
    |b, i|
    puts "Door #{i} is #{b}" if i>0
}

[edit] Scheme

[edit] unoptimized

(define *max-doors* 100)

(define (show-doors doors)
  (let door ((i 0)
             (l (vector-length doors)))
    (cond ((= i l) 
           (newline))
          (else 
           (printf "~nDoor ~a is ~a" 
                   (+ i 1) 
                   (if (vector-ref doors i) "open" "closed"))
           (door (+ i 1) l)))))

(define (flip-doors doors)
  (define (flip-all i)
    (cond ((> i *max-doors*) doors)
          (else 
           (let flip ((idx (- i 1)))
             (cond ((>= idx *max-doors*) 
                    (flip-all (+ i 1))) 
                   (else 
                    (vector-set! doors idx (not (vector-ref doors idx)))
                    (flip (+ idx i))))))))
  (flip-all 1))

(show-doors (flip-doors (make-vector *max-doors* #f)))

[edit] optimized

(define (optimised-flip-doors doors)
  (define (flip-all i)
    (cond ((> i (floor (sqrt *max-doors*))) doors)
          (else 
           (vector-set! doors (- (* i i) 1) #t)
           (flip-all (+ i 1)))))
  (flip-all 1))

(show-doors (optimised-flip-doors (make-vector *max-doors* #f)))

[edit] Visual Basic .NET

Platform: .NET

Language Version: 9.0+

[edit] unoptimized

Module Module1

   Sub Main()
       Dim doors(100) As Boolean 'Door 1 is at index 0

       For pass = 1 To 100
           For door = pass - 1 To 99 Step pass
               doors(door) = Not doors(door)
           Next
       Next

       For door = 0 To 99
           Console.WriteLine("Door # " & (door + 1) & " is " & If(doors(door), "Open", "Closed"))
       Next

       Console.ReadLine()
   End Sub

End Module

[edit] optimized

Module Module1

   Sub Main()
       Dim doors(100) As Boolean 'Door 1 is at index 0

       For i = 1 To 10
           doors(i ^ 2 - 1) = True
       Next

       For door = 0 To 99
           Console.WriteLine("Door # " & (door + 1) & " is " & If(doors(door), "Open", "Closed"))
       Next

       Console.ReadLine()
   End Sub

End Module