extra/rosetta-code/100-doors/100-doors.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: bit-arrays formatting fry kernel math math.ranges
   4 sequences ;
   5 IN: rosetta-code.100-doors
   6
   7 ! http://rosettacode.org/wiki/100_doors
   8
   9 ! Problem: You have 100 doors in a row that are all initially
  10 ! closed. You make 100 passes by the doors. The first time
  11 ! through, you visit every door and toggle the door (if the door
  12 ! is closed, you open it; if it is open, you close it). The second
  13 ! time you only visit every 2nd door (door #2, #4, #6, ...). The
  14 ! third time, every 3rd door (door #3, #6, #9, ...), etc, until
  15 ! you only visit the 100th door.
  16
  17 ! Question: What state are the doors in after the last pass?
  18 ! Which are open, which are closed? [1]
  19
  20 ! Alternate: As noted in this page's discussion page, the only
  21 ! doors that remain open are whose numbers are perfect squares of
  22 ! integers. Opening only those doors is an optimization that may
  23 ! also be expressed.
  24
  25 CONSTANT: number-of-doors 100
  26
  27 : multiples ( n -- range )
  28     0 number-of-doors rot <range> ;
  29
  30 : toggle-multiples ( n doors -- )
  31     [ multiples ] dip '[ _ [ not ] change-nth ] each ;
  32
  33 : toggle-all-multiples ( doors -- )
  34     [ number-of-doors [1..b] ] dip '[ _ toggle-multiples ] each ;
  35
  36 : print-doors ( doors -- )
  37     [
  38         swap "open" "closed" ? "Door %d is %s\n" printf
  39     ] each-index ;
  40
  41 : doors-main ( -- )
  42     number-of-doors 1 + <bit-array>
  43     [ toggle-all-multiples ] [ print-doors ] bi ;