minion_interrogation.py

#!/usr/bin/env python

'''
Author: John D. Anderson (TigerJ)
Usage: minion_interrogation -case1 | -case2 | -case3 | -case4
Origin: Google "foo.bar" project - Problem 3.1
Problem Description:

    Minion interrogation
    ====================

    You think you have Professor Boolean's password to the control center.
    All you need is confirmation, so that you can use it without being
    detected. You have managed to capture some minions so you can interrogate
    them to confirm.

    You also have in your possession Professor Boolean's minion interrogation
    machine (yes, he interrogates his own minions). Its usage is simple: you
    ask the minion a question and put him in the machine. After some time
    (specific to the minion), you stop the machine and ask the minion for the
    answer. With certain probability (again, specific to the minion) you either
    get the truthful answer or the minion remains silent. Once you have
    subjected a minion to the machine, you cannot use it on the minion again
    for a long period.

    The machine also has a 'guarantee' setting, which will guarantee that the
    minion will answer the question truthfully. Unfortunately, that has the
    potential to cause the minion some irreversible brain damage, so you vow to
    only use it as a last resort: on the last minion you interrogate.

    Since Professor Boolean's password is periodically changed, you would like
    to know the answer as soon as possible. So you decide to interrogate the
    minions in an order which will take the least expected time (you can only
    use the machine on one minion at a time).

    For example, you have captured two minions: minion A taking 10 minutes, and
    giving the answer with probability 1/2, and minion B taking 5 minutes, but
    giving the answer with probability 1/5.

    If you interrogate A first, then you expect to take 12.5 minutes.
    If you interrogate B first, then you expect to take 13 minutes and thus
    must interrogate A first for the shortest expected time for getting the
    answer.

    Write a function answer(minions) which given a list of the characteristics
    of each minion, returns the lexicographically smallest ordering of minions,
    which gives you the smallest expected time of confirming the password.

    The minions are numbered starting from 0.

    The minions parameter will be a list of lists.

    minions[i] will be a list containing exactly three elements,
    corresponding to the i^th minion.

    The first element of minion[i] will be a positive integer representing the
    time the machine takes for that minion.

    The ratio of the second and third elements will be the probability of that
    minion giving you the answer: the second element, a positive integer will
    be the numerator of the ratio and the third element, also a positive
    integer will be the denominator of the ratio. The denominator will always
    be greater than the numerator. That is, [time, numerator, denominator].

    The return value must be a list of minion numbers (which are integers),
    depicting the optimal order in which to interrogate the minions. Since
    there could be multiple optimal orderings, return the lexicographically
    first optimal list.

    There will be at-least two and no more than 50 minions.
    All the integers in the input will be positive integers, no more than 1024.

    Languages
    =========

    To provide a Python solution, edit solution.py
    To provide a Java solution, edit solution.java

    Test cases
    ==========

    Inputs:
        (int) minions = [[5, 1, 5], [10, 1, 2]]
    Output:
        (int list) [1, 0]

    Inputs:
        (int) minions = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024],
                         [199, 148, 250]]
    Output:
        (int list) [2, 3, 0, 1]

    Use verify [file] to test your solution and see how it does. When you are
    finished editing your code, use submit [file] to submit your answer. If
    your solution passes the test cases, it will be removed from your home
    folder.
'''

# libs
import sys


# functions
def answer(minions):

    # minion risk list
    minion_risk = []

    # main loop
    for i, m in enumerate(minions):
        mr = [(float(m[0])*float(m[2]))/float(m[1]), i]
        minion_risk.append(mr)

    # sort
    minion_risk.sort()

    # get minion order
    minion_order = []
    for minion in minion_risk:
        minion_order.append(minion[1])

    # return
    return minion_order


# executable
if __name__ == '__main__':

    # usage message
    usage = '\nUsage: minion_interrogation -case1 | -case2 | -case3 | -case4\n'

    # CLA check
    if len(sys.argv) > 1:

        if sys.argv[1] == '-case1':
            minions = [[5, 1, 5], [10, 1, 2]]

        elif sys.argv[1] == '-case2':
            minions = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024],
                       [199, 148, 250]]

        elif sys.argv[1] == '-case3':
            minions = [[5, 1, 5], [10, 1, 2], [5, 1, 5], [10, 1, 2]]

        elif sys.argv[1] == '-case4':
            minions = [[10, 1, 2], [3, 1, 3], [4, 1, 8]]

        # wrong arguments passed
        else:
            sys.exit(usage)

        # correct arguments passed
        print answer(minions)
        sys.exit()

    # no arguments passed
    sys.exit(usage)