twolips twolips - 3 months ago 15x
Ruby Question

Ruby - Hackerrank Puzzle - Save the Prisoner

I'm having a hard time understanding how to solve this problem without causing memory allocation problems. I'm pretty sure my logic is sound but unfortunately that doesn't seem to be good enough. Does anyone have any recommendations for this so I can understand how to write the code more efficiently?

Here's the problem:
Sample Input:
5 2 1
Sample Output
There are N = 5 prisoners and M = 2 sweets. Distribution starts at ID number S = 1, so prisoner 1 gets the first sweet and prisoner 2 gets the second (last) sweet. Thus, we must warn prisoner about the poison, so we print 2 on a new line.

# Enter your code here. Read input from STDIN. Print output to STDOUT
n = gets.strip.to_i
n.times do

arr = gets.strip.split(" ").map { |s| s.to_i}
prisoners = arr[0].to_i
sweets = arr[1].to_i
position = arr[2].to_i
prisoners_array = (1..prisoners).map { |p| p.to_i}
starting_position = prisoners_array[position - 1]
end_position = prisoners_array.size

awesome_array = (starting_position..end_position).map { |p| p.to_i}
awesomer_array = (prisoners_array[0]...starting_position).map { |p| p.to_i}
awesomest_array = awesome_array + awesomer_array

warning = 0

if sweets > prisoners
sweets = sweets % prisoners
for i in awesomest_array

warning += 1
if warning === sweets
puts prisoners_array[i - 1]

Cam Cam

This appears to be the exercise in question. The key here is managing your use of modulo (which calculates a 0-indexed position) with the problem (which uses 1-indexed positions).

In the example case, we have 5 people (n) and want to iterate 2 positions (m) over them starting from person #1 (s). Person #1 is index position 0 which we calculate by subtracting one from s. We must also subtract one from the distance travelled t because getting to the starting position is considered the first move. So we have s+m-2.

By taking this resultant number, modulo % the total number of people, we will have calculated the 0-indexed position that we end up at. We'll need to add one back to this number to convert back to a 1-indexed system.

While it's okay to take a long-form approach to working exercise problems out (such as by populating arrays and actually iterating over them), this problem can also be solved as follows:

# Enter your code here. Read input from STDIN. Print output to STDOUT
gets.strip.to_i.times do
    # n - number of prisoners
    # m - number of sweets
    # s - starting id
    n, m, s = &:to_i
    puts ((m+s-2) % n) + 1