9
\$\begingroup\$

A jail has prisoners, and each prisoner has a unique id number, S, ranging from 1 to N. There are M sweets that must be distributed to the prisoners.

The jailer decides the fairest way to do this is by sitting the prisoners down in a circle (ordered by ascending S), and then, starting with some random S, distribute one candy at a time to each sequentially numbered prisoner until all M candies are distributed. For example, if the jailer picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5, ..., n-1, n, 1, 2, 3, 4, ...) until all sweets are distributed.

But wait—there's a catch—the very last sweet is poisoned! Find and print the ID number of the last prisoner to receive a sweet so he can be warned.

Input Format

The first line contains an integer, T, denoting the number of test cases. The T subsequent lines each contain 3 space-separated integers: N (the number of prisoners), M (the number of sweets), and S (the prisoner ID), respectively.

Output Format

For each test case, print the ID number of the prisoner who receives the poisoned sweet on a new line.

Sample Input

1
5 2 1

Sample Output

2

My solution:

test_cases = int(input())

for _ in range(test_cases):
    n, m, s = map(int, input().split())

    while m > 0:
        m -= 1
        s = n if s > n else s + 1

    s = n if s < 1 else s - 1
    print(s)

I think big-O can be very large since M could be up to 10^9. When I test with M = 10^9, my terminal "killed" so please help!

\$\endgroup\$
  • 1
    \$\begingroup\$ You should therefore try to think of an alternative algorithm do you have some ideas yourself? \$\endgroup\$ – N3buchadnezzar Jul 23 '16 at 10:53
  • \$\begingroup\$ SInce it sounds like you want to give this bounty to N3buchadnezzar regardless I'll leave my answer alone. \$\endgroup\$ – chicks Jan 17 '17 at 22:23
7
\$\begingroup\$

use variable names that mean something

I can't keep track of whether n is the number of sweets or the number of prisoners because it is a single letter that doesn't mean much. Maybe s is for sweets? No it probably means "start". Bah! So confusing. Using words that mean something makes for better variable names for humans.

So

prisoners = n
sweets = m
first_prisoner = s

Now I can follow what's happening.

use modulus!

As Billyoyo put it:

You have a clock with N hours on it, the hand is currently pointed at x. Where will the hand be pointing in M hours?

which is an excellent hint. If you're thinking about things that are periodic modulus will very likely come in handy.

Let's start by figuring out how many sweets are left after all of the prisoners get an even numbers

odd_sweets = sweets % prisoners

So if we have 250 sweets and 200 prisoners there are 50 odd_sweets. If we have 400 sweets and 200 prisoners there are 0 odd_sweets since the candies were evenly distributed. Even if there aren't enough sweets to go around once modulus will still give you the right number. So if we have 1000 prisoners and 400 sweets (mean bums) there would be 400 odd_sweets since you wouldn't have been able to around one entire time so they're all "odd".

Then we want to know which prisoner got the last treat

sick_prisoner = (first_prisoner + odd_sweets) % prisoners

We start by adding the number of odd_sweets to the ID of the first prisoner. If those add up to less than the number of prisoners life is good and we didn't loop around. But if we get a number that is bigger than the number of prisoners we need to bring it back into range which the modulus will conveniently do for us.

So if we have 50 odd_sweets and 200 prisoners and the first_prisoners

  • = 20 then 50+20 = 70 and we're good
  • = 180 then 50+180 = 230 which is too big, but then after doing 230%200 we end up with 30 which makes sense

With that the entire calculation can be handled without internal loops.

\$\endgroup\$
  • \$\begingroup\$ I'm always trying to avoid single letter variables but when I hurry or code to fast I'm just forgetting. Thank you for the explanation, it really helps me a lot! \$\endgroup\$ – user102577 Jul 23 '16 at 15:34
  • \$\begingroup\$ Just a minor nitpick: I don't think anyone should use xrange with python-3.x except they want to get a NameError. \$\endgroup\$ – MSeifert Jul 23 '16 at 16:05
  • \$\begingroup\$ I see the python-3 tag now, I'll edit that out. \$\endgroup\$ – chicks Jul 23 '16 at 19:26
6
+500
\$\begingroup\$

General feedback

Does your code work properly for the small number of test cases? For an example n, m, s = 19, 23, 1 should intuitively give s = 4 as an answer. Your code seem to return 19 for some reason.

Low hanging improvement

  • Writing code is much more about getting the right answers. The purpose of writing in Python is to produce, clear understandable code. Will you understand what your code does in half a year, what about three years? For some inspiration of what python is trying to achieve, seezen of python. Python also have a more in depth guide on how to properly format code, see PEP 8.

  • Never use single letter variables for things other than counters.

  • Try to make it clear what your function does, through your variable and coding style. If this is not enough include a short explanation what the purpose of your code is
  • Use functions and the if __name__ == "__main__": module

Using all of these improvements your code can now be written as

def naive_prisoner(number_of_prisoners, candy, current_prisoner):
    '''
    Problem:
    Solves the prisoner problem:
    The jailer decides the fairest way to do this is by sitting the prisoners down in a circle 
    (ordered by ascending S), and then, starting with some random S, distribute one candy at a time 
    to each sequentially numbered prisoner until all M candies are distributed. For example, if the 
    jailer picks prisoner S = 2, then his distribution order would be (2, 3, 4, 5, ..., n-1, n, 1, 2, 3, 4, ...) 
    until all sweets are distributed.

    But wait-there's a catch-the very last sweet is poisoned! Find and print the ID number of the last prisoner 
    to receive a sweet so he can be warned.

    Algorithm:
    This code naively distributes one candy for every prisoner. If the current prisoner is the last
    set current prison number to 1 and continue distributing candy.
    '''

    for _ in range(candy-1):
        if current_prisoner == number_of_prisoners:
            current_prisoner = 1
        else:
            current_prisoner += 1
    return current_prisoner

if __name__ == '__main__':

    n, m, s = 5, 19, 2
    print naive_prisoner(n, m, s)

The docstring should be shortened, however I will leave that to you.


Improved algorithm

To find a quicker algorithm, let us first try to solve a simpler problem. Assume for just a moment that the guard always starts at the first prisoner

I will begin by looking at some special cases


Case: n => m

Assume that we have less candy than prisoners. This is the simplest possible case, and since we are always starting on the first prisoner we know that the m'th prisoner will be poisoned.


Case: n < m

Assume on the other hand that we have more candy than prisoners. Another way to distribute the candy would be to first give everyone a fair share, then start going around distributing the remaining candy.

Example: Let us look at how this would work. Say we have n = 5, m = 18, s = 1.

 3   3   3   3   3
[1] [2] [3] [4] [5]

A fair distribution would give each prisoner \$3\$ candies each. Now we have left \$18 - 3*5 = 3\$ candies to distribute. Doing that we see

 3   3   3   3   3
[1] [2] [3] [4] [5]

that prisoner number 3 would get poisoned. How would a coding implementation of this strategy look? Well we can remove multiples of \$n\$ from \$m\$ until we reach the point where n > m.

def share_evenly(number_of_prisoners, candy):
    while candy > number_of_prisoners:
        candy -= number_of_prisoners
    print candy

This algorithm is surprisingly simple and seem to produce the correct results. The while-loop can be performed even faster by writing

candy -= candy*(candy//number_of_prisoners)

How does this work? // is integer division. So we 18//5 = 3. We are then multiplying this again by 3 so 3*(18//3) = 15. This is our even share!

def share_evenly(number_of_prisoners, candy):
    return candy - number_of_prisoners*(candy//number_of_prisoners)

Generalized case for s > 1.

Now we that we have solved the s = 1 case we can generalize it a bit further. Assume as before that we have n = 5, m = 18 but now s = 3.

We can still distribute the candy evenly as done previously

 3   3   3   3   3
[1] [2] [3] [4] [5]
         x

Note that we are now standing at prisoner number 3 instead of 1. If we were to move 3 steps to the right we would too far. One solution would be to first go n-1 steps backwards if we end up too far to the right. How do we know if we are too far to the right? A simple check is if prisoner > number.

def share_evenly(number_of_prisoners, candy, prisoner):
    candy -= number_of_prisoners*(candy//number_of_prisoners)
    prisoner += candy - 1

    if prisoner == 0:
        return number_of_prisoners
    elif prisoner <= number_of_prisoners:
        return prisoner
    else:
        return prisoner - number_of_prisoners

Here we had to take extra care since candy - 1 might be zero.


Introducing the modulus operator [%]

Now as other answers have mentioned what

candy - number_of_prisoners*(candy//number_of_prisoners)

is doing is calculating the remainder after integer divison. There is a special operator in Python that does excactly this, %. For an example 5%18 = 3 as we have calculated many times before. To read more about this operator see How does % work in Python?.

Using % instead our code can now be written as

def prisoner(number_of_prisoners, candy, prisoner):
    candy %= number_of_prisoners
    prisoner += candy - 1
    prisoner %= number_of_prisoners 
    if prisoner == 0:
        return number_of_prisoners
    else:
        return prisoner

We can do one more trick and get rid of the if-else bit at the end. The reason it is there is that 5%5 = 0 while we want 5%5 = 5. We can do (x-1)%n + 1 instead of x%n. Why does this work?

def prisoner(number_of_prisoners, candy, prisoner):
    candy %= number_of_prisoners
    prisoner += candy - 2
    return 1 + (prisoner % number_of_prisoners)

That is the cleanest shortest code I can write.


Things left to do

  • You should still make sure that prisoner, number_of_prioners and candy are positive integers before using the algorithm above.
  • Inlcude a docstring as a short explanation how the algorithm works.
\$\endgroup\$
3
\$\begingroup\$

Try thinking about it this way instead:

You have a clock with N hours on it, the hand is currently pointed at x. Where will the hand be pointing in M hours?

Think about how you would do it with a normal clock with just 12 numbers first, then see if you can apply that to a clock with any amount of numbers.

So for example, if the hand is at 7, 8 hours later it will be at 3.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy