Блог

Я решаю проблему «100 дверей» из кода Rosetta в Ruby. Кратко,

• есть 100 дверей, все закрыты, обозначены от 1 до 100
• выполнено 100 проходов, обозначенных от 1 до 100
• на i-м проходе каждая i-я дверь «переключается»: открыта, если она закрыта, закрыта, если она открыта
• определите состояние каждой двери после завершения 100 проходов.

Поэтому при первом проходе все двери открываются. На втором проходе четные двери закрываются. На третьем проходе двери i , для которых i%3 == 0 переключаются, и так далее.

Вот моя попытка решить проблему.

 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
  

Но он продолжает печатать мне массив из 100 нулей, когда я его запускаю: посмотрите на все это ноль!

Что я делаю не так?

Это то, что if возвращают ваши предложения. Просто добавьте возвращаемое значение явно.

 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
  

или:

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

Проблема в том, что внешний if блок явно ничего не возвращает (таким образом, возвращает nil неявно), когда условие не выполняется.

Быстрое исправление:

 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
  

Рассмотрим эти подходы:

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

или

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

или

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

Код

 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] 
  

Объяснение

Все двери изначально закрыты. Рассмотрим 24-ю дверь. Он переключается во время следующих проходов:

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

Обратите внимание, что дверь переключается один раз для каждого из 24 делителей. Поэтому, если бы у нас был метод divisors(n) , который возвращал массив n делителей ‘s, мы могли бы определить количество переключений следующим образом:

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

Поскольку дверь переключается четное количество раз, мы приходим к выводу, что она будет в исходном состоянии (закрыта) после того, как вся пыль осядет. Аналогично, для n = 9 ,

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

Поэтому мы заключаем, что дверь № 9 будет открыта в конце, поскольку 3 нечетно.

divisors может быть определено следующим образом.

 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
  

Например,

 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] 
  

Поскольку нас интересует только нечетное или четное число делителей, мы можем вместо этого написать

 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
  

Для n = 24 этого выполните следующие действия:

 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 
  

Наконец,

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

возвращает результат, показанный выше.