Removing/deleting the alternate numbers from a list in Ruby

Question

I have a problem statement i.e In the case of 10 persons with chairs arranged in a circle. There is a pattern of skipping one person and asking the next to leave(starting from the first person in the list). Say, 10 persons in in circle numbered 1 to 10. Persons were asked to leave in this order 1,3,5,7,9,2,6,10 and 8. So, person 4 is the winner.

What would be the approach to get the expected result. I tried it using array of 10 elements and programming like this,

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

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

and again doing the same to the returned result till I get one element, but I am not getting the expected result. eg;

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]

In this case the output is but I am expecting 4. Is there some simpler way to do this and get the desired output?

Answer 1

Your solution would only work if arr.size is a power of 2. For example, in your second step, you get:

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

This is where the nil comes from: Because [10].second == nil.

Moreover, the logic is flawed: On the next iteration of the loop, it's the second person who needs to leave, not the first.

What you need to do is keep track of "should the next person leave?" as a separate concern to the array index.

Here's a possible solution:

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 creates an infinite enumerator, of [true, false, true, false, true, .....]. So as we loop over and over the array, we keep track of whether the next person must leave by this variable.

---

Side note: This is a famous puzzle, known as the Josephus problem. I recommend this video for a good explanation. You can actually determine the "winner" via a simple formula, rather than looping over the array like that!