100 doors: Difference between revisions
Content deleted Content added
Output not needed or useful as is not really ran to generate page. Fixed whitespace. |
|||
Line 6,544:
=== ES5 ===
==== Iterative ====
<lang javascript>var doors=[];
for (var
doors[i]=false;
for (var i=
for (var
▲ doors[i2]=!doors[i2]; //toggle doors
▲ console.log("Door %d is %s",i,doors[i-1]?"open":"closed")
====Functional Composition====
Naive search
<lang JavaScript>(function (n) {
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 ⟶ 6,570:
));
};
function zip(xs, ys) {
return xs.length === ys.length ? (
Line 6,593 ⟶ 6,577:
) : undefined;
}
function replicate(n, a) {
var v = [a],
o = [];
if (n < 1) return o;
while (n > 1) {
Line 6,607 ⟶ 6,588:
return o.concat(v);
}
function range(m, n, delta) {
var d = delta || 1,
Line 6,616 ⟶ 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 ⟶ 6,612:
})(100);</lang>
▲==== Optimized ( iterative )====
<lang javascript>for (var door = 1; door <= 100; door++) {
var sqrt = Math.sqrt(door);
Line 6,649 ⟶ 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 ) ====
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) {
return range(1, 100)
.filter(function (x) {
Line 6,670 ⟶ 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;
});
return lows.concat(lows.map(function (x) {
return n / x;
Line 6,687 ⟶ 6,646:
.slice((rRoot === intRoot) | 0));
}
function range(m, n, delta) {
var d = delta || 1,
Line 6,696 ⟶ 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) {
return perfectSquaresUpTo(100);
function perfectSquaresUpTo(n) {
return range(1, Math.floor(Math.sqrt(n)))
Line 6,720 ⟶ 6,669:
});
}
function range(m, n, delta) {
var d = delta || 1,
Line 6,731 ⟶ 6,675:
a = Array(lng),
i = lng;
if (blnUp)
while (i--) a[i] = (d * i) + m;
Line 6,738 ⟶ 6,681:
return a;
}
})(100);</lang>
=== ES6 ===
|