Over at The Daily WTF, they’ve started posting programming puzzles. The latest one is a puzzle where a set of locker doors are toggled, starting from the closed state, to the open state. Starting at a step size of 1 and stopping at a step size equal to the number of lockers, one toggles each door. At a step size of 1, all doors are opened, step size of 2, all the even doors are closed. At a step size of 3, door 3 is closed, door 6 opened, and so on.
Many of the solutions observe that only perfect squares remain opened when the algorithm is complete. That option is easy, but I wanted to do one that mimics the jocks effort of brute force solving the problem.
// Init the lockers to the initial state
// and mark all doors as closed (false)
let sw = System.Diagnostics.Stopwatch.StartNew()
let totalLockers = 100
let lockers =
[1..totalLockers]
|> Seq.map( fun e -> (e, false))
// Recursive function to set each door.
let rec openLockers l skip =
let listLength = Seq.length(l)
if (totalLockers < skip) then
// We’ve done our last toggle on the previous iteration.
l
else
// Do the toggling and try again.
let newList =
l |> Seq.map(
fun (e, f : System.Boolean) ->
let modValue = (e % skip)
match modValue with
| 0 -> (e, not(f))
| _ -> (e, f))
openLockers newList (skip + 1)
let remainingOpen =
(openLockers lockers 1) |>
Seq.filter(fun (e, f:System.Boolean) -> f) |>
Seq.map(fun (e, f:System.Boolean) -> e)
sw.Stop()
Seq.iter (printf "%dn") remainingOpen
printf ("%sn") (sw.Elapsed.ToString())
Karmic Code Monkey 