List Index out of Bounds (Arcade game)

user_14200074 0
Viewed 550

I have recently attended an interview and I was asked below question :

Adam is so good at playing arcade games that he will win at every game he plays. One fine day as he was walking on the street, he discovers an arcade store that pays real cash for every game that the player wins - however, the store will only pay out once per game. The store has some games for which they will pay winners, and each game has its own completion time and payout rate. Thrilled at the prospect of earning money for his talent, Adam walked into the store only to realize that the store closes in 2 hours (exactly 120 minutes). Knowing that he cannot play all the games in that time, he decides to pick the games that maximize his earnings

Sample game board at the arcade GAME COMPLETION_TIME (in minutes) PAYOUT_RATE

Pac-man 90  400
Mortal Kombat   10  30
Super Tetris    25  100
Pump it Up  10  40
Street Fighter II   90  450
Speed Racer 10  40

An acceptable solution is the one where it still picks the best earnings even when the list of games or completion times or payout rates change.

Question: Write code in Java/Scala/Python to help Adam pick the sequence(s) of games that earn him the most money.

Then, assume you have a variable list of games and their payout rates. What is the best way to pick the games that earn you the most?

Input Explanation: The first line of input is always an integer denoting many lines to read after the first line. In our sample test case, we have 6 in the first line and 6 lines after the first line, each having a game, completion_time and payout_rate. In each data line, the game, completion_time and payout_rate are separated by a ','(comma). The games board may change but the store still closes in 120 minutes.

Input: 6

Pac-man,80,400
Mortal Kombat,10,30
Super Tetris,25,100
Pump it Up,10,40
Street Fighter II,90,450
Speed Racer,10,40

Output Explanation : Print the game names that earn him the most into the standard output in alphabetical order

Output

Mortal Kombat
Pump it Up
Speed Racer
Street Fighter II

Tried So far:

import sys
import itertools

line = sys.stdin.readline()
def biggest_payout(line):
   
    a = line.split(sep=' ')
    b = []
    for i in range(1, len(a)):
        b.append(a[i].split(sep=','))
    c = []
    for i in range(len(b)):
        c.append(int(b[i][1]))
    min_sums = []
    for L in range(0, len(c)+1):
        for subset in itertools.permutations(c, L):
            min_sums.append(sum(subset))
    e = []
    for i in range(len(b)):
        e.append(int(b[i][2]))
    money_sums = []
    for L in range(0, len(e)+1):
        for subset in itertools.permutations(e, L):
            money_sums.append(sum(subset))
    k = []
    for i in range(len(b)):
        k.append(b[i][0])
    movie_combos = []
    for L in range(0, len(k)+1):
        for subset in itertools.permutations(k, L):
            movie_combos.append(subset)   
    while True:
        if min_sums[money_sums.index(max(money_sums))] > 120:
            money_sums[money_sums.index(max(money_sums))] = 0
        else:
            index = money_sums.index(max(money_sums))
            break
    return movie_combos[index]

for line in sys.stdin:       
       print(biggest_payout(line))

Error :

  File "/temp/file.py", line 13, in biggest_payout
    c.append(int(b[i][1]))
IndexError: list index out of range

I am getting array index outbounds, can some please guide me how to solve this?

knapsack-problem python-3.x list algorithm python
1 Answers

You should not split line by ' 'and there are more issues with your code.

Also permutations will contain (Pac-man, Mortal Kombat) and (Mortal Kombat, Pac-man) etc. I'd rather use combinations (there are 10 time less combinations then permutations in this case) and write something like this.

import sys
import itertools

n = int(sys.stdin.readline())

games = {}
for i in range(n):
    s = sys.stdin.readline().rstrip().split(',')
    games[s[0]] =  (int(s[1]), int(s[2]))

res = ()
maxpay = 0

for k in range(1, n):
    for z in itertools.combinations(games, k):
        time = 0
        pay = 0
        for x in z:
            time += games[x][0]
            if time > 120:
                break
            pay +=  games[x][1]
        if time <= 120 and pay > maxpay:
            res = z
            maxpay = pay

print('\n'.join(sorted(list(res))))

Testing.

$cat data 
6
Pac-man,80,400
Mortal Kombat,10,30
Super Tetris,25,100
Pump it Up,10,40
Street Fighter II,90,450
Speed Racer,10,40

$python3 solution.py < data
Mortal Kombat
Pump it Up
Speed Racer
Street Fighter II
user_23976840
Related