no one important no one important - 3 months ago 38
Python Question

Google Foobar challenge failing 2 out of 5 test cases

I am doing the Google Foobar challenge power_hungry (see below).

I cannot figure out why the following code fails test cases #3 and #5. Can anyone see what I'm missing? Have I failed to consider an edge case?

Here is my Python code:

from functools import reduce
import operator

def get_pair_prod(xs):
if len(xs) < 2:
return 1
xs.sort()
return xs[0] * xs[1]

def answer(xs):
if len(xs) == 0:
return "0"
positive = [x for x in xs if x > 0]
negative = [x for x in xs if x < 0]
if len(negative) == 1 and len(positive) == 0:
return str(negative[0])
elif len(negative) == 0 and len(positive) == 0:
return str("0")
positive.append(get_pair_prod(negative))
return str(reduce(operator.mul, positive, 1))


Here is the challenge:

Power Hungry

Commander Lambda's space station is HUGE. And huge space stations take a LOT of power. Huge space stations with doomsday devices take even more power. To help meet the station's power needs, Commander Lambda has installed solar panels on the station's outer surface. But the station sits in the middle of a quasar quantum flux field, which wreaks havoc on the solar panels. You and your team of henchmen has been assigned to repair the solar panels, but you can't take them all down at once without shutting down the space station (and all those pesky life support systems!).

You need to figure out which sets of panels in any given array you can take offline to repair while still maintaining the maximum amount of power output per array, and to do THAT, you'll first need to figure out what the maximum output of each array actually is. Write a function answer(xs) that takes a list of integers representing the power output levels of each panel in an array, and returns the maximum product of some non-empty subset of those numbers. So for example, if an array contained panels with power output levels of [2, -3, 1, 0, -5], then the maximum product would be found by taking the subset: xs[0] = 2, xs[1] = -3, xs[4] = -5, giving the product 2*(-3)*(-5) = 30. So answer([2,-3,1,0,-5]) will be "30".

Each array of solar panels contains at least 1 and no more than 50 panels, and each panel will have a power output level whose absolute value is no greater than 1000 (some panels are malfunctioning so badly that they're draining energy, but you know a trick with the panels' wave stabilizer that lets you combine two negative-output panels to produce the positive output of the multiple of their power values). The final products may be very large, so give the answer as a string representation of the number.

Languages

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

Test cases

Inputs: (int list) xs = [2, 0, 2, 2, 0] Output: (string) "8"

Inputs: (int list) xs = [-2, -3, 4, -5] Output: (string) "60"

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.

2ps 2ps
Answer Source

In short, there’s quite a bit wrong with your code in that you haven’t properly evaluated two cases which relate to negative numbers: where the negative list length is odd and greater than 1 and where the negative list length is even but greater than length 2. Once you solve that you are set.

def answer(rg):
    positives = [ x for x in rg if x > 0 ]
    negatives = [ x for x in rg if x < 0 ]
    if len(rg) == 1 or not positives and not negatives:
        return rg[0]
    negatives.sort()
    if len(negatives) % 2 == 1:
        negatives = negatives[:-1]
    product = Decimal(1)
    for x in chain(positives, negatives)
        product *= Decimal(x)
    return product