Doubts with 100 doors algorithm

JavaScript
1

Tell us what’s happening:
What it’s supposed that is the expected output?. Can you give me some examples?

Your code so far


let doors;
//initDoors represents the first time that the doors are checked
let size = 100;
function initDoors(value){
  doors = Array(value).fill(true);
}

function passTheDoors(value){
  doors.forEach((n, index) => {
    //evaluating doors. Ex: 2th pass: only 2, 4, 6, ...10.
    if(index % value === 0 && index !== 0){
      doors[index] = !doors[index];
    }
  });
}

function getFinalOpenedDoors (numDoors) {
  initDoors(size);
  for(let i = 0; i < size; i ++){
    //checking the doors
    passTheDoors(i);
  }
  return new Array(doors[numDoors - 1]);
}

Any clues?. Thanks

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_14_2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/69.0.3497.100 Safari/537.36 OPR/56.0.3051.99.

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/rosetta-code/100-doors/

2

@gersonm

// where does n get it's value from?
function passTheDoors(value){
  doors.forEach((n, index) => { //<-------- ???
    //evaluating doors. Ex: 2th pass: only 2, 4, 6, ...10.
    if(index % value === 0 && index !== 0){
      doors[index] = !doors[index];
    }
  });
}

Also, why not toggle the door at index zero? The array will have a door at index zero.

3

I only toggled the door at index 0 (door 1) one time, in the init, because that door is only checked once, or at least that’s what I understood :frowning:

4

If you want to see what your 100 doors are up to each pass something like this might help.
You’ll need some screen space at least 100 char wide to see each row on one line though

function passTheDoors(value){
  doors.forEach((n, index) => {
    //evaluating doors. Ex: 2th pass: only 2, 4, 6, ...10.
    if(index % value === 0 && index !== 0){
      doors[index] = !doors[index];
    }
  });
  console.log(doors.map(el =>  el ? 'X' : '.').join(""));  // this line
}

EDIT:

The first time through, visit every door and ‘toggle’ the door

if every door starts closed then after first pass every door should then be open. Yours are not. That is what @TomerPacific is telling you.

Return the final result in an array, with only the door number included in the array if it is open.

If you end up with doors #5, 10, 15 …etc open then your returned array should be [5,10,15,…, etc]

You are on the right track. I logged out your code to watch the doors open and close each pass and a pattern forms as expected. You’ll need to fix that thing TomerPacific is talking about first though.

Once you figure out the pattern you technically would not need to loop 100 times to get the answer - there is a mathematical pattern. Recognize the pattern and you get a formula that yields the answer with far fewer calculations that should work for 100 doors, 110 doors or 100,000,000 doors.

5

The algorithm’s logic is stated as such:

There are 100 doors in a row that are all initially closed. You make 100 passes by the doors. The first time through, visit every door and ‘toggle’ the door (if the door is closed, open it; if it is open, close it). The second time, only visit every 2nd door (i.e., door #2, #4, #6, …) and toggle it. The third time, visit every 3rd door (i.e., door #3, #6, #9, …), etc., until you only visit the 100th door.

What you have done in your code is this:

if(index % value === 0 && index !== 0){

Meaning, if the current index divided by the value is zero (meaning, there is no remainder and it is divisible) then toggle the door.

6

Ok guys, after read all your comments, I changed some things, but now there is an issue and I didn’t know if is a restriction:

let doors = [];
let arraySize = 100;
function initDoors(value){
  doors = Array(value).fill(false);
}

function passTheDoors(value){
  let base = value;
  while(value <= size){
    doors[value] = !doors[value];
    value += base;
  }
  PrintDoors();
}

function PrintDoors(){
  console.log(doors.map(el =>  el ? 'X' : '.').join(""));  // this line
}

function getFinalOpenedDoors (numDoors) {
  initDoors(arraySize);
  PrintDoors();
  for(let i = 1; i <= arraySize; i ++){
    console.log(i, arraySize);//sometimes goes until 28, sometimes until 34. Why?
  }
  return new Array(doors[numDoors - 1]);
}

In the “for” statement, the iterations have a behavior that I didn’t expect: ends early so, Does every loop have an iteration limit in milliseconds?

7

Ok, I decided study and read a little more about this algorithm, because I’m struggling a lot with it, and after understand what the output must be, and use another way in order to achieve the goal, I finished:

function getFinalOpenedDoors (numDoors) {
  let doors = [];
  for(let d = 1; d <= numDoors; d ++){
    let factors = CalculateFactors(d);
    if(factors.length % 2 !== 0){//Even factors, door close. Odd factor, door open.
      doors.push(d);//the final result is only an array with the doors open after 100 times making the exercise
    }
  }
  return doors;
}

function CalculateFactors(value){
    let factors = [];
    for(let i = value; i >= 1; i --){
        if(value % i === 0){
            factors.push(i);
        }
    }
    return factors;
}

Thanks for the clues :slight_smile:

1 Like