100 doors: confused about counting

iamcharliekim · January 4, 2019, 2:02am

Tell us what’s happening:
So I was able to hack this algorithm together to pass the challenge but I’m a bit confused about the initial for-loop. I originally had let i = 0 instead of let i = 1 and just ended up changing the value of i as a guess and it turned out to be the right answer.

I’m confused because when I initialize the array of doors like this:

 for (let i = 1 ; i < numDoors; i++){
    arr[i] = 'closed'
  }

I end up getting an array with a length of 100, but index 0 is ‘empty’ since i starts at 1. So I ended up with doors starting at index 1 and stopping at index 99 which means there are only 99 doors?

How did I end up passing the challenge with this ?

My original answer had the intial for loop like this (with the array indexed from 0-99 which would equal 100 doors):

for (let i = 0 ; i < numDoors; i++){
    arr[i] = 'closed'
  }

Your code so far


function getFinalOpenedDoors (numDoors) {
  let arr = []

  for (let i = 1 ; i < numDoors; i++){
    arr[i] = 'closed'
  }

  function toggle(x){
      if (x === 'closed'){
          x = 'open'
      } else {
          x = 'closed'
      }
    return x
  }

  let counter = 1

  while (counter !== 100){
    for (let i = 0 ; i <= 100; i+=counter){
        arr[i] = toggle(arr[i])
    }
	  counter++
  }

  let final = []

  for (let i = 0 ; i < arr.length; i++){
    if (arr[i] === 'open'){
        final.push(i)
    }
  }

  return final

}

Your browser information:

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

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

kevinSmith · January 4, 2019, 2:37am

There are some flaws in your logic. It just happened to work out.

These two lines:

  while (counter !== 100){
    for (let i = 0 ; i <= 100; i+=counter){

Don’t you want to test when the counter is 100? I think you want <= there. Remember that you are 1 indexed there, when talking about which iteration you are on, going “every x door”.

And the second line - do you want to start with 0? Normally when we say “every 3rd door” we mean starting on door three, not on door one (remembering that we are actually zero indexed in the array.)

  for (let i = 0 ; i < arr.length; i++){
    if (arr[i] === 'open'){
        final.push(i)
    }
  }

Is i what you want to push there? Remember that i is zero indexed. But should the answer be?

I would argue that things would be simplified if you used boolean toggles instead of strings, and that toggle method could be greatly simplified - but these aren’t necessary to fix the code. See if you can fix it as it is.

iamcharliekim · January 4, 2019, 10:23pm

Thanks for the feedback! I went thru my code again and made some adjustments using your feedback. Would appreciate further advice to optimize my code, if necessary:

function getFinalOpenedDoors (numDoors) {
  let doors = []
  for (let i = 1; i <= numDoors; i++){
    doors[i] = false
  }
  
  function toggle(door){
    return door = !door
  }

  let counter = 1

  while (counter <= 100){
    for (let i = 0; i <= doors.length-1; i+=counter){
      if (i === 0){
        continue;
      }
      doors[i] = toggle(doors[i])
    }
      counter++
  }

  let final = []
  for (let i = 1; i <= doors.length-1; i++){
    if (doors[i]){
      final.push(i)
    }
  }
  return final
}

kevinSmith · January 5, 2019, 12:47am

It’s working, but it’s still a little odd to me.

First of all, yes the use of booleans is an improvement. But to me, you are confusing 1-indexing and 0-indexing.

But first, since you’re using booleans, and undefined evaluates as falsy, you could initialize your array with

let doors = new Array(100);

That gives you an array of undefined which will serve the same purpose. If you really, really want you can fill it with false by

let doors = new Array(100).fill(false);

but it isn’t necessary.

This would eliminate the need for the next part:

  for (let i = 1; i <= numDoors; i++){
    doors[i] = false
  }

which is fundamentally flawed anyway because it is starting at index 1 and you should be 0 indexing at this point.

Your counter could be a for loop, but that doesn’t really matter much - it just might look a little cleaner.

OK, this:

    for (let i = 0; i <= doors.length-1; i+=counter){
      if (i === 0){
        continue;
      }

OK, that takes care of not doing anything on the first one. But why even set i to 0 in the first place? Why not just start i at a different number? And remember that your counter is 1 indexed but your doors are 0 indexed. Yes, this is confusing.

This line:

doors[i] = toggle(doors[i])

Your toggle function works now, but is it necessary? Why not just:

doors[i] = !doors[i]

(or, realizing the that index is 1 indexed and your array is 0 indexed, that should be i-1)That is simple enough to do it directly without an extra function. If it were more complicated, abstracting it into a function would make sense, but I don’t think it is needed here.

Then at the end, that for loop works, but prototype methods are “sexier”. Something like:

  let final = []
  doors.forEach((e, i) => { if (e) final.push(i + 1); })

works nicely too. It does basically the same thing, but in a little bit more simple format. There may be an easier way, but I can’t see it.

These are hard. Don’t get frustrated. There are often more than one way to skin the cat. Go out on the internet and look at other solutions. That’s often a great way to see other ways to solve things. Good algorithm solving often involves imagining several ways to solve and using a developed “spidey sense” to know which is best.

iamcharliekim · January 5, 2019, 10:42pm

I didn’t know about the new Array() method but glad I do now.
I decided to index the doors array starting from 1 because it just makes it easier for me to think about (index1 === door#1, as opposed to index0 === door#1). What is the disadvantage of indexing from 1 as opposed to 0 in this case?
I guess I made that toggle helper-function just for readability but it is a bit redundant and unnecessary.

Regarding this:

    for (let i = 0; i <= doors.length-1; i+=counter){
      if (i === 0){
        continue;
      }

I indexed it starting at 0 so that the loop would increment properly with counter = 1 (i+=counter).

Thanks for all the help so far. What would your solution be? Just curious to see how you would go about solving this problem. I’ve been practicing my algorithm skills by solving as many problems as I can everyday. It can get messy but I do enjoy get deeply immersed in the process and nothing feels better than when I finally crack the code.

kevinSmith · January 6, 2019, 2:00am

I didn’t know about the new Array() method but glad I do now.

Yeah, that’s what it’s all about - picking up new tricks one by one.

I decided to index the doors array starting from 1 because it just makes it easier for me to think about (index1 === door#1, as opposed to index0 === door#1). What is the disadvantage of indexing from 1 as opposed to 0 in this case?

I hear you. That would be one way to solve it. My issue (if I were interviewing someone) would be that that would be a waste of cell. Sure, it’s only one cell, but it would seem a bit odd to me to waste that cell just to make the coding a little easier.

Regarding this: … [code] … I indexed it starting at 0 so that the loop would increment properly with counter = 1 (i+=counter).

Yeah, I get that. But instead of let i = 0, why not just start i where you want, at the first things? Like let i = counter. It saves you one iteration and gets rid of three lines of code.

This is probably along the lines of what I would have done:

const getFinalOpenedDoors = numDoors => {
  const doors = new Array(numDoors);

  for (let counter = 1; counter <=100; counter += 1) {
    for (let i = counter - 1; i < numDoors; i += counter) {
      doors[i] = !doors[i];
    }
  }

  let final = [];
  doors.forEach((e, i) => { if (e) final.push(i + 1); });
  return final;
}

The last three lines could be replaced with something like:

  return doors.reduce((filtered, e, i) => {
    if (e) filtered.push(i + 1);
    return filtered;
  }, []);

But I don’t know if that’s better. It’s “cooler” but doesn’t really gain anything and makes it a little harder to read so it’s not ideal.

You could do that last part in one line:

return doors.map((e, i) => e ? i + 1 : 0).filter(e => e);

This is more compact, but slightly less efficient - it makes two passes. (But is still O(n) for that selection. I’m not sure what the whole thing would be - O(n^2 log n)?)Those are the kinds of things I’d be ready to talk about the different choices for if I were doing this in an interview.

Don’t feel bad if those seem weird or are not intuitive. But thinking like this is a good skill to develop. I’m sure someone out there has a solution that would blow me out of the water. But that’s what this process is about - learning to see multiple solutions and understanding the strengths and weaknesses of each. But this takes time. We’re both on the same path, I’m just a year further down than you are. I was having the same questions a year ago. Just keep at it - it will get easier and make more sense. It’s all about practice.

Topic		Replies	Views
Doubts with 100 doors algorithm JavaScript	7	1455	February 2, 2021
Rosetta Code: 100 doors: expected output? JavaScript	5	2533	January 25, 2021
Rosetta Code 100 doors	9	1534	January 16, 2021
100 doors advice request	1	404	January 17, 2021
100 doors solution - how to input into code checker? JavaScript	2	850	February 2, 2021

100 doors: confused about counting

Related topics