Ruby 100 doors returning 100 nil

Question

I'm solving the '100 doors' problem from Rosetta Code in Ruby. Briefly,

there are 100 doors, all closed, designated 1 to 100
100 passes are made, designated 1 to 100
on the ith pass, every ith door is "toggled": opened if it's closed, closed if it's open
determine the state of each door after 100 passes have been completed.

Therefore, on the first pass all doors are opened. On the second pass even numbered doors are closed. On the third pass doors i for which i%3 == 0 are toggled, and so on.

Here is my attempt at solving the problem.

visit_number = 0
door_array = []
door_array = 100.times.map {"closed"}

until visit_number == 100 do
  door_array = door_array.map.with_index { |door_status, door_index|
    if (door_index + 1) % (visit_number + 1) == 0
      if door_status == "closed"
        door_status = "open"
      elsif door_status == "open"
        door_status = "closed"
      end
    end
  }
  visit_number += 1
end

print door_array

But it keeps printing me an array of 100 nil when I run it: Look at all this nil !

What am I doing wrong?

As a note it's usually better to represent things internally as `true`/`false` when dealing with open state. That's less messy than string representations of the same thing. You can render these out with the right labels when you want to. Plus, `open = !open` is a lot easier to understand than this big `if` that tests strings. Additionally, `Array.new(100, 'closed')` makes a 100 element array with 'closed' in every slot. — tadman, Oct 11 '16 at 05:44
Piggybacking on tadman's comment, if I were approaching this problem, I would create a Door class that kept track of whether it was open or closed, and had a `#toggle!` method to switch state internally. You're writing this in Ruby -- I recommend taking advantage of what the language has to offer. — Matt, Oct 11 '16 at 14:40
Dex, I trust you don't mind the edit I did (but roll back or edit if you don't like it). I mainly added a brief summary of the problem, in case the link is broken in future. In general, questions should be self-contained, though links to other SO questions are of course not a problem. — Cary Swoveland, Oct 11 '16 at 22:53

score 0 · Answer 1 · answered Oct 11 '16 at 05:01

That's what your if clauses return. Just add a return value explicitly.

until visit_number == 100 do
  door_array = door_array.map.with_index { |door_status, door_index|
    if (door_index + 1) % (visit_number + 1) == 0
      if door_status == "closed"
        door_status = "open"
      elsif door_status == "open"
        door_status = "closed"
      end
    end
    door_status
  }
  visit_number += 1
end

OR:

1.upto(10) {|i| door_array[i*i-1] = 'open'}

score 0 · Answer 2 · answered Oct 11 '16 at 05:03

The problem is the outer if block doesn't explicitly return anything (thus returns nil implicitly) when the condition does not meet.

A quick fix:

visit_number = 0
door_array = []
door_array = 100.times.map {"closed"}

until visit_number == 100 do
  door_array = door_array.map.with_index { |door_status, door_index|
    if (door_index + 1) % (visit_number + 1) == 0
      if door_status == "closed"
        door_status = "open"
      elsif door_status == "open"
        door_status = "closed"
      end
    else  #<------------- Here
      door_status  #<------------- And here
    end
  }
  visit_number += 1
end

print door_array

Sagar Pandya · Answer 3 · 2016-10-11T11:01:34.220

0

Consider these approaches:

door_array.map { |door|
  case door
  when "open"
    "closed"
  when "closed"
    "open"
  end
}

or

rule = { "open" => "closed", "closed" => "open" }
door_array.map { |door| rule[door] }

or

door_array.map { |door| door == 'open' ? 'closed' : 'open' }

edited Oct 11 '16 at 11:01

answered Oct 11 '16 at 05:08

Sagar Pandya

9,323
2
24
35

The `door =` assignment inside the case is totally pointless. That variable is thrown away. The value alone is sufficient. – tadman Oct 11 '16 at 05:53
The `door =` assignment inside the block is totally pointless. That variable is thrown away. The value alone is sufficient. – Jörg W Mittag Oct 11 '16 at 08:31
`door_array.map &rule.method(:[])` to avoid a chance to introduce redundant variable :) – Aleksei Matiushkin Oct 11 '16 at 08:46

score 0 · Answer 4 · answered Oct 11 '16 at 22:34

Code

require 'prime'

def even_nbr_divisors?(n)
  return false if n==1
  arr = Prime.prime_division(n).map { |v,exp| (0..exp).map { |i| v**i } }
  arr.shift.product(*arr).map { |a| a.reduce(:*) }.size.even?
end

closed, open = (1..100).partition { |n| even_nbr_divisors?(n) }
closed #=> [ 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 
       #    23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 40,
       #    41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57,
       #    58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74,
       #    75, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91,
       #    92, 93, 94, 95, 96, 97, 98, 99],
open   #= [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Explanation

All doors are initially closed. Consider the 24th door. It is toggled during the following passes:

pass  1: opened
pass  2: closed
pass  3: opened
pass  4: closed
pass  6: opened
pass  8: closed
pass 12: opened
pass 24: closed

Notice that the door is toggled once for each of 24's divisors. Therefore, if we had a method divisors(n) that returned an array of n's divisors, we could determine the number of toggles as follows:

nbr_toggles = divisors(24).size
  #=> [1,2,3,4,6,8,12,24].size
  #=> 8

Since the door is toggled an even number of times, we conclude that it will be in its original state (closed) after all the dust has settled. Similarly, for n = 9,

divisors(9).size
  #=> [1,3,9].size
  #=> 3

We therefore conclude door #9 will be open at the end, since 3 is odd.

divisors can be defined as follows.

def divisors(n)
  arr = Prime.prime_division(n).map { |v,exp| (0..exp).map { |i| v**i } }
  arr.first.product(*arr[1..-1]).map { |a| a.reduce(:*) }
end

For example,

divisors 24
  #=> [1, 3, 2, 6, 4, 12, 8, 24] 
divisors 9
  #=> [1, 3, 9] 
divisors 1800
  #=> [1, 5, 25, 3, 15, 75, 9, 45, 225, 2, 10, 50, 6, 30, 150, 18, 90, 450,
  #    4, 20, 100, 12, 60, 300, 36, 180, 900, 8, 40, 200, 24, 120, 600, 72,
  #    360, 1800]

Since we only care if there are an odd or even number of divisors, we can instead write

def even_nbr_divisors?(n)
  return false if n==1
  arr = Prime.prime_division(n).map { |v,exp| (0..exp).map { |i| v**i } }
  arr.shift.product(*arr).map { |a| a.reduce(:*) }.size.even?
end

For n = 24, the steps are as follows:

n   = 24
a   = Prime.prime_division(n)
  #=> [[2, 3], [3, 1]] 
arr = a.map { |v,exp| (0..exp).map { |i| v**i } }
  #=> [[1, 2, 4, 8], [1, 3]] 
b   = arr.shift
  #=> [1, 2, 4, 8] 
arr
  #=> [[1, 3]] 
c   = b.product(*arr)
  #=> [[1, 1], [1, 3], [2, 1], [2, 3], [4, 1], [4, 3], [8, 1], [8, 3]] 
d   = c.map { |a| a.reduce(:*) }
  #=> [1, 3, 2, 6, 4, 12, 8, 24] 
e   = d.size
  #=> 8 
e.even?
  #=> true

Lastly,

(1..100).partition { |n| even_nbr_divisors?(n) }

returns the result shown above.

Ruby 100 doors returning 100 nil

4 Answers4