Archive for August, 2009

Solution for Daily WTF Praxis on 8-5-2009

Posted by Scott Seely in Uncategorized on August 5, 2009

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

Leave a comment