100 doors

From Rosetta Code

Jump to: navigation, search

Puzzle
This is a programming puzzle. It lays out a problem which Rosetta Code users are encouraged to solve, using languages and techniques they know. Multiple approaches are not discouraged, so long as the puzzle guidelines are followed.

Code examples should be formatted along the lines of one of the existing prototypes.

For other Puzzles, see Category:Puzzles


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

[edit] Ada

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;

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

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;

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] AmigaE

PROC main()
  DEF t[100]: ARRAY,
      pass, door
  FOR door := 0 TO 99 DO t[door] := FALSE
  FOR pass := 0 TO 99
    door := pass
    WHILE door <= 99
      t[door] := Not(t[door])
      door := door + pass + 1
    ENDWHILE
  ENDFOR
  FOR door := 0 TO 99 DO WriteF('\d is \s\n', door+1,
                                IF t[door] THEN 'open' ELSE 'closed')
ENDPROC

[edit] AutoHotkey

 
Loop, 100
  Door%A_Index% := "closed"
 
Loop, 100 {
  x := A_Index, y := A_Index
  While (x <= 100)
  {
    CurrentDoor := Door%x%
    If CurrentDoor contains closed
    {
      Door%x% := "open"
      x += y
    }
    else if CurrentDoor contains open
    {
      Door%x% := "closed"
      x += y
    }
  }
}
 
Loop, 100 {
   CurrentDoor := Door%A_Index%
   If CurrentDoor contains open
      Res .= "Door " A_Index " is open`n"
}
MsgBox % Res
 

[edit] AWK

unoptimized 

BEGIN {
  for(i=1; i <= 100; i++)
  {
    doors[i] = 0 # close the doors
  }
  for(i=1; i <= 100; i++)
  {
    for(j=i; j <= 100; j += i)
    {
      doors[j] = (doors[j]+1) % 2
    }
  }
  for(i=1; i <= 100; i++)
  {
    print i, doors[i] ? "open" : "close"
  }
}

optimized 

BEGIN {
  for(i=1; i <= 100; i++) {
    doors[i] = 0 # close the doors
  }
  for(i=1; i <= 100; i++) {
    if ( int(sqrt(i)) == sqrt(i) ) {
      doors[i] = 1
    }
  }
  for(i=1; i <= 100; i++)
  {
    print i, doors[i] ? "open" : "close"
  }
}

[edit] BASIC

Works with: QuickBasic version 4.5 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

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

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;
 }

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 n^2 = 1 + 3 + 5 + \ldots + (2n+1). 

 #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)

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;
 }

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 n^2 = 1 + 3 + 5 + \ldots + (2n+1). 

 #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] C#

Unoptimized 

 
using System;
class Program
{
    static void Main()
    {
        //To simplify door numbers, uses indexes 1 to 100 (rather than 0 to 99)
        bool[] doors = new bool[101];
        for (int pass = 1; pass <= 100; pass++)
            for (int current = pass; current <= 100; current += pass)
                doors[current] = !doors[current];
        for (int i = 1; i <= 100; i++)
            Console.WriteLine("Door #{0} " + (doors[i] ? "Open" : "Closed"), i);
    }
}
 

Optimized 

 
using System;
class Program
{
    static void Main()
    {
        int door = 1, inrementer = 0;
        for (int current = 1; current <= 100; current++)
        {
            Console.Write("Door #{0} ", current);
            if (current == door)
            {
                Console.WriteLine("Open");
                inrementer++;
                door += 2 * inrementer + 1;
            }
            else
                Console.WriteLine("Closed");
        }
    }
}
 

[edit] Common Lisp

Unoptimized / functional

This is a very unoptimized version of the problem, using recursion and quite considerable list-copying. It emphatises the functional way of solving this problem 

(defun visit-door (doors doornum value1 value2)
    "visits a door, swapping the value1 to value2 or vice-versa"
    (let ((d (copy-list doors))
          (n (- doornum 1)))
             (if (eq   (nth n d) value1)
                 (setf (nth n d) value2)
                 (setf (nth n d) value1))
             d))
 
(defun visit-every (doors num iter value1 value2)
    "visits every 'num' door in the list"
    (if (> (* iter num) (length doors))
        doors
        (visit-every (visit-door doors (* num iter) value1 value2)
                     num
                     (+ 1 iter)
                     value1
                     value2)))
 
(defun do-all-visits (doors cnt value1 value2)
    "Visits all doors changing the values accordingly"
    (if (< cnt 1)
        doors
        (do-all-visits (visit-every doors cnt 1 value1 value2)
                       (- cnt 1)
                       value1
                       value2)))
 
(defun print-doors (doors)
    "Pretty prints the doors list"
    (format T "~{~A ~A ~A ~A ~A ~A ~A ~A ~A ~A~%~}~%" doors))
 
(defun start (&optional (size 100))
    "Start the program"
    (let* ((open "_")
           (shut "#")
           (doors (make-list size :initial-element shut)))
               (print-doors (do-all-visits doors size open shut))))
 

Optimized

This is an optimized version of the above, using the perfect square algorithm (Note: This is non-functional as the state of the doors variable gets modified by a function call) 

(defun perfect-square-list (n)                       
    "Generates a list of perfect squares from 0 up to n"
    (loop for i from 1 to (sqrt n) collect (expt i 2))) 
 
(defun open-door (doors num open)
    "Sets door at num to open"
    (setf (nth (- num 1) doors) open)
    doors) 
 
(defun visit-all (doors vlist open)
    "Visits and opens all the doors indicated in vlist"
    (if (null vlist) 
        doors                     
        (visit-all (open-door doors (car vlist) open) 
                   (cdr vlist) 
                   open))) 
 
(defun start2 (&optional (size 100))                        
    "Start the program"
    (print-doors (visit-all (make-list size :initial-element "#")
                            (perfect-square-list size) "_")))
 

Optimized (2)

This version displays a much more functional solution through the use of (mapcar ...) 

(let  ((i 0))
    (mapcar (lambda (x)
                (if (zerop (mod (sqrt (incf i)) 1))
                    "_"
                    x))
            (make-list 100 :initial-element "#")))

[edit] Clojure

Unoptimized / mutable array 

(defn doors []
  (let [doors (into-array (repeat 100 false))]
    (doseq [pass   (range 1 101) 
            i      (range (dec pass) 100 pass) 
            :while (< i 100)]
      (aset doors i (not (aget doors i))))
    doors))   

(defn open-doors [] (for [[d n] (map vector (doors) (iterate inc 1)) :when d] n))

(defn print-open-doors []
  (println 
    "Open doors after 100 passes:"
    (apply str (interpose ", " (open-doors)))))

Unoptimized / functional 

(defn doors []
  (reduce (fn [doors toggle-idx] (update-in doors [toggle-idx] not))
          (into [] (repeat 100 false))
          (for [pass   (range 1 101)
                i      (range (dec pass) 100 pass)
                :while (< i 100)]
            i)))

(defn open-doors [] (for [[d n] (map vector (doors) (iterate inc 1)) :when d] n))

(defn print-open-doors []
  (println 
    "Open doors after 100 passes:"
    (apply str (interpose ", " (open-doors)))))

Optimized / functional 

(defn doors []
	(reduce (fn [doors idx] (assoc doors idx true)) 
	        (into [] (repeat 100 false))
	        (map #(dec (* % %)) (range 1 11))))

(defn open-doors [] (for [[d n] (map vector (doors) (iterate inc 1)) :when d] n))

(defn print-open-doors []
  (println 
    "Open doors after 100 passes:"
    (apply str (interpose ", " (open-doors)))))

[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

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 ;  
}

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] E

Graphical

Works with: E-on-Java

This version animates the changes of the doors (as checkboxes). 

#!/usr/bin/env rune

var toggles := []
var gets := []

# Set up GUI (and data model)
def frame := <swing:makeJFrame>("100 doors")
frame.getContentPane().setLayout(<awt:makeGridLayout>(10, 10))
for i in 1..100 {
  def component := <import:javax.swing.makeJCheckBox>(E.toString(i))
  toggles with= fn { component.setSelected(!component.isSelected()) }
  gets with= fn { component.isSelected() }
  frame.getContentPane().add(component)
}

# Set up termination condition
def done
frame.addWindowListener(def _ {
  to windowClosing(event) {
    bind done := true
  }
  match _ {}
})

# Open and close doors
def loop(step, i) {
  toggles[i] <- ()
  def next := i + step
  timer.whenPast(timer.now() + 10, fn {
    if (next >= 100) {
      if (step >= 100) {
        # Done.
      } else {
        loop <- (step + 1, step)
      }
    } else {
      loop <- (step, i + step)
    }    
  })
}
loop(1, 0)

frame.pack()
frame.show()
interp.waitAtTop(done)

[edit] Forth

The problem with unfactored code is it's difficult to follow. The included example works, but to comprehend the code, you're mentally juggling items on the return stack (e.g., i, j) as well as items on the data stack, plus whatever is in dictionary space. Since people can only keep seven things in his or her mind, plus or minus two, this quickly becomes an intellectual burden. This style of coding typifies Forth software development in the mid-70s and -80s, which resulted in Forth's undeserved "write-only language" reputation.

The well-factored code works much better from a readability point of view (assuming familiarity with Forth's coding conventions), but without the aid of an optimizing compiler, can suffer from slower execution performance and somewhat larger memory consumption.

Of course, this size/speed tradeoff appears in many languages, not just Forth.

Factored 

100 constant /doors
create 'doors
    /doors allot
'doors /doors + constant <doors

: toggle    1 over c@ xor swap c! ;
: pass      dup 1- 'doors + begin dup <doors < while dup toggle over + repeat 2drop ;
: passes    /doors 1 begin 2dup >= while dup pass 1+ repeat 2drop ;
: .closed   over c@ if over 'doors - 1+ . then ;
: report    'doors /doors begin dup while .closed 1 /string repeat cr 2drop ;
: open      'doors /doors erase ;

: doors     open passes report ;

Unfactored 

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

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] Groovy

unoptimized 

 
 doors = [false] * 100
 (0..99).each {
    it.step(100, it + 1) {
       doors[it] ^= true
    }
 }
 (0..99).each {
    println("Door #${it + 1} is ${doors[it] ? 'open' : 'closed'}.")
 }
 

optimized a

Using square roots 

 
 (1..100).each {
    println("Door #${it} is ${Math.sqrt(it).with{it==(int)it} ? 'open' : 'closed'}.")
 }
 

optimized b

Without using square roots 

 
 doors = ['closed'] * 100
 (1..10).each { doors[it**2 - 1] = 'open' }
 (0..99).each {
    println("Door #${it + 1} is ${doors[it]}.")
 }
 

[edit] Haskell

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)

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

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

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

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."));
 		}
 	}
 }

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] Mathematica

unoptimized 

n=100;
tmp=ConstantArray[-1,n];
Do[tmp[[i;;;;i]]*=-1;,{i,n}];
Do[Print["door ",i," is ",If[tmp[[i]]==-1,"closed","open"]],{i,1,Length[tmp]}]

optimized 1 

Do[Print["door ",i," is ",If[IntegerQ[Sqrt[i]],"open","closed"]],{i,100}]

optimized 2 

n=100;
a=Range[1,Sqrt[n]]^2
Do[Print["door ",i," is ",If[MemberQ[a,i],"open","closed"]],{i,100}]

optimized 3 

n=100
nn=1
a=0
For[i=1,i<=n,i++,
 If[i==nn,
  Print["door ",i," is open"];
  a++;
  nn+=2a+1;
 ,
  Print["door ",i," is closed"];
 ];
]

[edit] MAXScript

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]
)

optimized 

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

[edit] Metafont

boolean doors[];
for i = 1 upto 100: doors[i] := false; endfor
for i = 1 upto 100:
  for j = 1 step i until 100:
    doors[j] := not doors[j];
  endfor
endfor
for i = 1 upto 100:
  message decimal(i) & " " & if doors[i]: "open" else: "close" fi;
endfor
end

[edit] Modula-3

unoptimized 

MODULE Doors EXPORTS Main;
 
IMPORT IO, Fmt;
 
TYPE State = {Closed, Open};
TYPE List = ARRAY [1..100] OF State;
 
VAR doors := List{State.Closed, ..};
 
BEGIN
  FOR i := 1 TO 100 DO
    FOR j := FIRST(doors) TO LAST(doors) DO
      IF j MOD i = 0 THEN
        IF doors[j] = State.Closed THEN
          doors[j] := State.Open;
        ELSE
          doors[j] := State.Closed;
        END;
      END;
    END;
  END;
 
  FOR i := FIRST(doors) TO LAST(doors) DO
    IO.Put(Fmt.Int(i) & " is ");
    IF doors[i] = State.Closed THEN
      IO.Put("Closed.\n");
    ELSE
      IO.Put("Open.\n");
    END;
  END;
END Doors.

optimized 

MODULE DoorsOpt EXPORTS Main;
 
IMPORT IO, Fmt;
 
TYPE State = {Closed, Open};
TYPE List = ARRAY [1..100] OF State;
 
VAR doors := List{State.Closed, ..};
 
BEGIN
  FOR i := 1 TO 10 DO
    doors[i * i] := State.Open;
  END;
 
  FOR i := FIRST(doors) TO LAST(doors) DO
    IO.Put(Fmt.Int(i) & " is ");
    IF doors[i] = State.Closed THEN
      IO.Put("Closed.\n");
    ELSE
      IO.Put("Open.\n");
    END;
  END;
END DoorsOpt.

[edit] OCaml

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))
 

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] Octave

doors = false(100,1);
for i = 1:100
  for j = i:i:100
    doors(j) = !doors(j);
  endfor
endfor
for i = 1:100
  if ( doors(i) )
    s = "open";
  else
    s = "closed";
  endif
  printf("%d %s\n", i, s);
endfor

[edit] Pascal

Program OneHundredDoors;
 
var
   doors : Array[1..100] of Boolean;
   i, j	 : Integer;
 
begin
   for i := 1 to 100 do
      doors[i] := False;
   for i := 1 to 100 do begin
      j := i;
      while j <= 100 do begin
	 doors[j] := not doors[j];
	 j := j + i
      end
   end;
   for i := 1 to 100 do begin
      Write(i, ' ');
      if doors[i] then
	 WriteLn('open')
      else
	 WriteLn('closed');
   end
end.

[edit] PHP

optimized 

 
<?php
for ($i = 1; $i <= 100; $i++) {
	$root = sqrt($i);
	$state = ($root == ceil($root)) ? "open" : "closed";
	echo "Door $i: $state";
}
?>
 

[edit] Perl

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;

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

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;

optimized 

for i to 100 do
    lvars root = sqrt(i);
    i; if root = round(root) then ' open' ><; else ' closed' ><; endif; =>
endfor;

[edit] Python

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

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'
 

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

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()

optimized 

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

[edit] Ruby

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
}
 

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

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)))
 

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] Slate

Unoptimized 

define: #a -> (Array newSize: 100).
a infect: [| :_ | False].

a keysDo: [| :pass |
  pass to: a indexLast by: pass do: [| :door |
    a at: door infect: #not `er]].

a keysAndValuesDo: [| :door :isOpen |
  inform: 'door #' ; door ; ' is ' ; (isOpen ifTrue: ['open'] ifFalse: ['closed'])].

Optimized 

define: #a -> (Array newSize: 100).
a infect: [| :_ | False].

0 below: 10 do: [| :door | a at: door squared put: True].
a keysAndValuesDo: [| :door :isOpen |
  inform: 'door #' ; door ; ' is ' ; (isOpen ifTrue: ['open'] ifFalse: ['closed'])].

[edit] Smalltalk

Works with: GNU Smalltalk Unoptimized 

|a|
a := Array new: 100 .
1 to: 100 do: [ :i | a at: i put: false ].
 
1 to: 100 do: [ :pass |
  pass to: 100 by: pass do: [ :door |
    a at: door put: (a at: door) not .
  ]
].
 
"output"
1 to: 100 do: [ :door |
   ( 'door #%1 is %2' %
     { door . (a at: door) ifTrue: [ 'open' ] ifFalse: [ 'closed' ] } ) displayNl
]

Optimized 

|a|
a := (1 to: 100) collect: [ :x | false ].
1 to: 10 do: [ :i | a at: (i squared) put: true ].
1 to: 100 do: [ :i |
   ( 'door #%1 is %2' % { i . 
           (a at: i) ifTrue: [ 'open' ] 
                     ifFalse: [ 'closed' ] }
   ) displayNl
]

[edit] SETL

Unoptimized 

program hundred_doors;

const toggle := {['open', 'closed'], ['closed', 'open']};

doorStates := ['closed'] * 100;

(for interval in [1..100])
  doorStates := [if i mod interval = 0 then
                    toggle(prevState) else
                    prevState end:
                 prevState = doorStates(i)];
end;

(for finalState = doorStates(i))
  print('door', i, 'is', finalState);
end;

end program;

If 'open' weren't a reserved word, we could omit the single quotes around it.

Optimized

Exploits the fact that squares are separated by successive odd numbers. Use array replication to insert the correct number of closed doors in between the open ones. 

program hundred_doors;

doorStates := (+/ [['closed'] * oddNum with 'open': oddNum in [1,3..17]]);

(for finalState = doorStates(i))
  print('door', i, 'is', finalState);
end;

end program;

[edit] Tcl

unoptimized 

package require Tcl 8.5
set n 100
set doors [concat - [lrepeat $n 0]]
for {set step 1} {$step <= $n} {incr step} {
    for {set i $step} {$i <= $n} {incr i $step} {
        lset doors $i [expr { ! [lindex $doors $i]}]
    }
}
for {set i 1} {$i <= $n} {incr i} {
    puts [format "door %d is %s" $i [expr {[lindex $doors $i] ? "open" : "closed"}]]
}

optimized 

package require Tcl 8.5
set doors [lrepeat [expr {$n + 1}] closed]
for {set i 1} {$i <= sqrt($n)} {incr i} {
    lset doors [expr {$i ** 2}] open
}
for {set i 1} {$i <= $n} {incr i} {
    puts [format "door %d is %s" $i [lindex $doors $i]]
}

graphical

Library: Tk

Inspired by the E solution, here's a visual representation 

package require Tcl 8.5
package require Tk
 
array set door_status {}
 
# create the gui
set doors [list x]
for {set i 0} {$i < 10} {incr i} {
    for {set j 0} {$j < 10} {incr j} {
        set k [expr {1 + $j + 10*$i}]
        lappend doors [radiobutton .d_$k -text $k -variable door_status($k) \
                         -indicatoron no -offrelief flat -width 3 -value open]
        grid [lindex $doors $k] -column $j -row $i
    }
}
 
# create the controls
button .start -command go -text Start
label .i_label -text " door:"
entry .i -textvariable i -width 4
label .step_label -text " step:"
entry .step -textvariable step -width 4
grid .start - .i_label - .i - .step_label - .step - -row $i
grid configure .start -sticky ew
grid configure .i_label .step_label -sticky e
grid configure .i .step -sticky w
 
proc go {} {
    global doors door_status i step
 
    # initialize the door_status (all closed)
    for {set d 1} {$d <= 100} {incr d} {
        set door_status($d) closed
    }
 
    # now, begin opening and closing
    for {set step 1} {$step <= 100} {incr step} {
        for {set i 1} {$i <= 100} {incr i} {
            if {$i % $step == 0} {
                [lindex $doors $i] [expr {$door_status($i) eq "open" ? "deselect" : "select"}]
                update
                after 50
            }
        }
    }
}

[edit] UNIX Shell

Works with: Bourne Again SHell 

#! /bin/bash
 
declare -a doors
for((i=1; i <= 100; i++)); do
    doors[$i]=0
done
 
for((i=1; i <= 100; i++)); do
    for((j=i; j <= 100; j += i)); do
	echo $i $j
	doors[$j]=$(( doors[j] ^ 1 ))
    done
done
 
for((i=1; i <= 100; i++)); do
    if [[ ${doors[$i]} -eq 0 ]]; then
	op="closed"
    else
	op="open"
    fi
    echo $i $op
done

[edit] Vedit macro language

Unoptimized

This implementation uses a free edit buffer as data array and for displaying the results.
A closed door is represented by a character '-' and an open door by character 'O'. 

Buf_Switch(Buf_Free)
Ins_Char('-', COUNT, 100)                      // All doors closed
for (#1 = 1; #1 <= 100; #1++) {
    for (#2 = #1; #2 <= 100; #2 += #1) {
        Goto_Col(#2)
        Ins_Char((Cur_Char^0x62), OVERWRITE)   // Toggle between '-' and 'O'
    }
}

Optimized 

Buf_Switch(Buf_Free)
Ins_Char('-', COUNT, 100)
for (#1=1; #1 <= 10; #1++) {
    Goto_Col(#1*#1)
    Ins_Char('O', OVERWRITE)
}

Output: 

O--O----O------O--------O----------O------------O--------------O----------------O------------------O

[edit] Visual Basic .NET

Platform: .NET

Language Version: 9.0+

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

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
Retrieved from "http://rosettacode.org/wiki/100_doors"
Personal tools