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