Удаление / удаление альтернативных номеров из списка в Ruby

Question

У меня есть постановка задачи, т.е. в случае 10 человек со стульями, расположенными по кругу.Существует схема пропуска одного человека и просьбы следующего уйти (начиная с первого человека в списке).Скажем, 10 человек в кругу пронумерованы от 1 до 10. Людей попросили уйти в этом порядке 1,3,5,7,9,2,6,10 и 8.Итак, человек 4 является победителем.

Какой был бы подход для получения ожидаемого результата.Я попытался сделать это, используя массив из 10 элементов и запрограммировав это,

arr = [1,2,3,4,5,6,7,8,9,10]

arr = arr.each_slice(2).map(&:second)

и снова делая то же самое с возвращенным результатом, пока не получу один элемент, но я неполучить ожидаемый результат.например;

arr.each_slice(2).map(&:second)
=> [2, 4, 6, 8, 10]
[2, 4, 6, 8, 10].each_slice(2).map(&:second)
=> [4, 8, nil]
[4, 8, nil].each_slice(2).map(&:second)
=>[8, nil]

В этом случае вывод будет, но я ожидаю 4. Есть ли какой-нибудь более простой способ сделать это и получить желаемый результат?

Answer 1

Поскольку стулья расположены по кругу, вы можете просто сделать что-то вроде:

• Возьмите первый стул в списке и выбросьте его
• Поверните круг (переместитепервый стул до конца списка, пропускающий его)
• Повторяйте, пока не останется только одно место

В коде:

arr = [1,2,3,4,5,6,7,8,9,10]

until arr.size == 1
  arr.delete_at(0)
  arr.rotate!
end

Answer 2

def last_person_standing(arr)
  (arr.size-1).times.reduce(arr) { |a,_| a << a.shift(2).last }.first
end

Далее следуют несколько пунктов.

• Если массив содержит n элементов, то существует n-1 шагов, при этом один элемент массива удаляется на каждом шаге;
• с помощью Enumerable # уменьшать (он же inject) нет необходимости добавлять строку в конце, чтобы вернуть желаемое значение;
• , чтобы избежать мутации arr replace *Аргумент 1015 * (arr) с arr.dup;
• a << a.shift(2).last удаляет первые два элемента массива a и добавляет второй из них в конец a;
• Я прикрепил .first к концу рабочей строки, чтобы вернуть оставшийся элемент, а не массив, содержащий этот единственный элемент, поскольку это кажется более полезным;и
• код должен быть добавлен, чтобы справиться со случаями, когда arr.size < 2.

Давайте попробуем.

last_person_standing %w| Agnes Billy-Bob Trixy Bubba Wanda |
   #=> "Billy-Bob"

Далее следуют другие примеры.

(2..10).each do |n|
   a = [*1..n]
   puts "#{ a }: #{ last_person_standing(a) }"
end

печатает

[1, 2]: 2
[1, 2, 3]: 2
[1, 2, 3, 4]: 4
[1, 2, 3, 4, 5]: 2
[1, 2, 3, 4, 5, 6]: 4
[1, 2, 3, 4, 5, 6, 7]: 6
[1, 2, 3, 4, 5, 6, 7, 8]: 8
[1, 2, 3, 4, 5, 6, 7, 8, 9]: 2
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]: 4

Вот еще один способ.

def last_person_standing(arr)
  while arr.size > 1
    odd = arr.size.odd?
    arr.pop if odd
    arr.delete_if.with_index { |_,i| i.even? }
    arr.unshift(nil) if odd
  end
  arr.first
end

Если после каждого раунда удалений из arr, если arr.size нечетно, выскочитьпоследний элемент arr, удалить элементы из arr с четными индексами и затем unshift любой объект-заполнитель (я выбрал nil) в начале arr (будет удален в следующем цикле);если arr.size - это просто удалить элементы из arr с четными индексами.

Answer 3

Ваше решение будет работать только в том случае, если arr.size является степенью 2. Например, на втором шаге вы получите:

[2, 4, 6, 8, 10].each_slice(2).to_a #=> [[2, 4], [6, 8], [10]]

Вот откуда взято nil: Потому что [10].second == nil.

Более того, логика имеет недостатки: на следующей итерации цикла, *1001* второму человеку, который должен уйти, а не первому.

Чтовам нужно следить за "должен ли следующий человек уйти?"как отдельное отношение к индексу массива.

Вот возможное решение:

arr = [1,2,3,4,5,6,7,8,9,10]
should_delete = [true, false].cycle
while(arr.size > 1)
  arr.delete_if { should_delete.next }
end

p arr #=> [4]

[true, false].cycle создает бесконечный перечислитель, равный [true, false, true, false, true, .....].Поэтому, когда мы повторяем цикл по массиву, мы отслеживаем, должен ли следующий человек оставить эту переменную.

---

Примечание: это известная головоломка, известная как проблема Джозефуса.Я рекомендую это видео для хорошего объяснения.Вы действительно можете определить «победителя» с помощью простой формулы, а не циклически повторять массив таким образом!