100 doors: Difference between revisions

Line 6,544:

=== ES5 ===

==== Iterative ====

<lang javascript>var doors=[];

var ~~doors~~=[];

for (var i=0;i<100;i++)

doors[i]=false;

for(var i=0;i<100;i++)

for (var i=1;i<=100;i++)

doors[i]=false; //create doors

for(var i=1;i<=100;i++)

for (var i2=i-1,g;i2<100;i2+=i)

⚫

doors[i2]=!doors[i2];

for(var ~~i2=~~i-1,g;i2<100;~~i2+=~~i)

for (var i=1;i<=100;i++)

⚫

doors[i2]=!doors[i2]; ~~//toggle doors~~

⚫

console.log("Door %d is %s",i,doors[i-1]?"open":"closed")</lang>

for(var i=1;i<=100;i++) //read doors

⚫

console.log("Door %d is %s",i,doors[i-1]?"open":"closed")

</lang>

====Functional Composition====

Naive search

<lang JavaScript>(function (n) {

'use strict';

"use strict";

// finalDoors :: Int -> [(Int, Bool)]

function finalDoors(n) {

var lstRange = range(1, n);

return lstRange

.reduce(function (a, _, k) {

var m = k + 1;

return a.map(function (x, i) {

var j = i + 1;

return [j, j % m ? x[1] : !x[1]];

});

Line 6,580:

Line 6,570:

));

};

// GENERIC FUNCTIONS

// zip :: [a] -> [b] -> [(a,b)]

function zip(xs, ys) {

return xs.length === ys.length ? (

Line 6,593:

Line 6,577:

) : undefined;

}

// replicate :: Int -> a -> [a]

function replicate(n, a) {

var v = [a],

o = [];

if (n < 1) return o;

while (n > 1) {

Line 6,607:

Line 6,588:

return o.concat(v);

}

// range(intFrom, intTo, optional intStep)

// Int -> Int -> Maybe Int -> [Int]

function range(m, n, delta) {

var d = delta || 1,

Line 6,616:

Line 6,594:

a = Array(lng),

i = lng;

if (blnUp)

while (i--) a[i] = (d * i) + m;

else

while (i--) a[i] = m - (d * i);

return a;

}

return finalDoors(n)

.filter(function (tuple) {

Line 6,638:

Line 6,612:

})(100);</lang>

⚫

==== Optimized (iterative)====

⚫

==== Optimized ( iterative )====

<lang javascript>for (var door = 1; door <= 100; door++) {

var sqrt = Math.sqrt(door);

Line 6,649:

Line 6,619:

}

}</lang>

Simple for loop. Optimizing the optimized?

<lang javascript>for(var door=1;i<10/*Math.sqrt(100)*/;i++){

console.log("Door %d is open",i*i);

}</lang>

⚫

==== Optimized (functional) ====

⚫

==== Optimized ( functional ) ====

The question of which doors are flipped an odd number of times reduces to the question of which numbers have an odd number of integer factors.

We can simply search for these:

<lang JavaScript>(function (n) {

'use strict';

"use strict";

return range(1, 100)

.filter(function (x) {

Line 6,670:

Line 6,633:

.length % 2;

});

function integerFactors(n) {

var rRoot = Math.sqrt(n),

intRoot = Math.floor(rRoot),

lows = range(1, intRoot)

.filter(function (x) {

return (n % x) === 0;

});

// for perfect squares, we can drop the head of the 'highs' list

return lows.concat(lows.map(function (x) {

return n / x;

Line 6,687:

Line 6,646:

.slice((rRoot === intRoot) | 0));

}

// range(intFrom, intTo, optional intStep)

// Int -> Int -> Maybe Int -> [Int]

function range(m, n, delta) {

var d = delta || 1,

Line 6,696:

Line 6,652:

a = Array(lng),

i = lng;

if (blnUp)

while (i--) a[i] = (d * i) + m;

else

while (i--) a[i] = m - (d * i);

return a;

}

})(100);</lang>

Or we can note, on inspection and further reflection, that only perfect squares have odd numbers of integer factors - all other numbers have only matched pairs of factors - low factors below the non-integer square root, and the corresponding quotients above the square root. In the case of perfect squares, the additional integer square root (not paired with any other factor than itself) makes the total number of distinct factors odd.

<lang JavaScript>(function (n) {

'use strict';

"use strict";

return perfectSquaresUpTo(100);

function perfectSquaresUpTo(n) {

return range(1, Math.floor(Math.sqrt(n)))

Line 6,720:

Line 6,669:

});

}

// GENERIC

// range(intFrom, intTo, optional intStep)

// Int -> Int -> Maybe Int -> [Int]

function range(m, n, delta) {

var d = delta || 1,

Line 6,731:

Line 6,675:

a = Array(lng),

i = lng;

if (blnUp)

while (i--) a[i] = (d * i) + m;

Line 6,738:

Line 6,681:

return a;

}

})(100);</lang>

=== ES6 ===