Google Foobar挑战耗电大亨-测试失败. 5个测试用例中有3个(隐藏)? [英] Google Foobar challenge Power Hungry - failing test no. 3 [hidden] out of 5 test cases?

问题描述

我正在做Google foobar饥饿的挑战.我在5个隐藏的测试用例中只有一个无法通过.这是我的代码-

I am doing google foobar challenge power hungry. I am failing in one test case out of 5 test cases which are hidden. Here is my code -

def answer(b):
from itertools import combinations
arr = []
for i in range(1,len(b)+1):
    comb = combinations(b,i)
    for j in list(comb):
        mul = 1
        for x in j:
            mul *= x
            if mul > 1000:
                break
            else:
                arr.append(mul)
return str(max(arr))

任务在下面提到-

耗电

拉姆达指挥官的空间站非常庞大.巨大的空间站需要大量动力.配备世界末日设备的巨大空间站将消耗更多功率.为了满足车站的电力需求，指挥官Lambda在车站的外表面安装了太阳能电池板.但是该站位于类星体量子通量场的中间，这对太阳能电池板造成了严重破坏.您和您的武装分子团队已被指派修理太阳能电池板，但是如果不关闭空间站(以及所有讨厌的生命维持系统！)，您将无法立即将它们全部拆除.

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!).

您需要确定在给定阵列中可以脱机维修的几组面板，同时仍保持每个阵列的最大功率输出，而要做到这一点，首先需要确定最大数量的面板.每个数组的输出实际上是.编写一个函数answer(xs)，该函数采用一个整数列表，这些整数表示一个数组中每个面板的功率输出电平，并返回这些数字的一些非空子集的最大积.因此，例如，如果一个数组包含功率输出级别为[2，-3，1，0，-5]的面板，则通过乘以子集xs [0] = 2，xs [1]可以找到最大乘积. ] = -3，xs [4] = -5，乘积2 *(-3)*(-5)=30.因此，答案([2，-3,1,0，-5])为30.

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".

每个太阳能电池板阵列至少包含1个且不超过50个面板，并且每个面板将具有绝对不大于1000的功率输出水平(某些面板的故障非常严重，以至于浪费了能量，但是您知道面板的稳波器有一个技巧，可让您组合两个负输出面板以产生其功率值倍数的正输出).最终产品可能很大，因此请以数字的字符串表示形式给出答案.

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.

语言

要提供Python解决方案，请编辑solution.py要提供Java解决方案，请编辑solution.java

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

测试用例

输入:(整数列表)xs = [2，0，2，2，0]输出:(字符串)"8"

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

输入:(整数列表)xs = [-2，-3、4，-5]输出:(字符串)"60"

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

使用verify [file]测试您的解决方案并查看其效果.完成代码编辑后，请使用Submit [file]提交答案.如果您的解决方案通过了测试案例，它将从您的主文件夹中删除.

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.

如果可能，请提出我在代码中的错误之处?谢谢.

If possible, please suggest where I am mistaking in my code? Thanks.

推荐答案

您当前的算法无法扩展为处理50个面板，因为您必须生成所有2 ** 50个子数组的子集.

Your current algorithm won't scale to handle 50 panels since you would have to generate all 2**50 subsets of subarrays.

初始算法

来自> https://www.geeksforgeeks.org/maximum-product-subset -array/

此方法具有 O(n)的复杂度(与发布方法的O(2 ^ n)相比).

This method has O(n) complexity (as compared to the O(2^n) of the posted method).

from random import randint

def maxProductSubset(a, n): 
    if n == 1: 
        return a[0]  

    # Find count of negative numbers, count  
    # of zeros, maximum valued negative  
    # number and product of non-zero numbers  
    max_neg = -999999999999
    count_neg = 0
    count_zero = 0
    prod = 1
    for i in range(n): 

        # If number is 0, we don't  
        # multiply it with product.  
        if a[i] == 0:  
            count_zero += 1
            continue

        # Count negatives and keep  
        # track of maximum valued negative.  
        if a[i] < 0:  
            count_neg += 1
            max_neg = max(max_neg, a[i]) 

        prod = prod * a[i] 

    # If there are all zeros  
    if count_zero == n:  
        return 0

    # If there are odd number of  
    # negative numbers  
    if count_neg & 1:  

        # Exceptional case: There is only  
        # negative and all other are zeros  
        if (count_neg == 1 and count_zero > 0 and 
            count_zero + count_neg == n): 
            return 0

        # Otherwise result is product of  
        # all non-zeros divided by maximum  
        # valued negative.  
        prod = int(prod / max_neg) 

    return str(prod)  # Problem asks for string to be returned

# Test Code
if __name__ == '__main__': 
    big_array = [randint(-1000, 1000) for _ in range(51)]
    tests = [[-1], [-1, 0], [2, 0, 2, 2, 0],  [-2, -3, 4, -5], [ -1, -1, -2, 4, 3 ], big_array ]
    for t in tests:
        print('array {} \n\t max: {}'.format(t, maxProductSubset(t, len(t))))

输出

array [-1] 
     max: -1
array [-1, 0] 
     max: 0
array [2, 0, 2, 2, 0] 
     max: 8
array [-2, -3, 4, -5] 
     max: 60
array [-1, -1, -2, 4, 3] 
     max: 24
array [696, 254, 707, 730, 252, 144, 18, -678, 921, 681, -665, 421, -501, 204, 742, -609, 672, -72, 339, -555, -736, 230, -450, 375, 941, 50, 897, -192, -912, -915, 609, 100, -933, 458, -893, 932, -590, -209, 107, 473, -311, 73, 68, -229, 480, 41, -235, 558, -615, -289, -643] 
     max: 112783193423281396421025291063982496313759557506029207349556366834514274891010648892576460433185005069070271452630069726538629120

策略

基于以下事实的算法代码:

1. 如果负数为偶数且不为零，则结果为 只是全部的产品
2. 如果负数个数为奇数且不为零，则结果为 除最大负数外的所有乘积.
3. 如果有零，则结果是除这些零以外的所有结果的乘积 一种例外的情况.例外情况是当有一个 负数，其他所有元素均为0.在这种情况下，结果 是0.

1. If there are even number of negative numbers and no zeros, result is simply product of all
2. If there are odd number of negative numbers and no zeros, result is product of all except the largest valued negative number.
3. If there are zeros, result is product of all except these zeros with one exceptional case. The exceptional case is when there is one negative number and all other elements are 0. In this case, result is 0.

备用算法

from functools import reduce
from itertools import combinations
from random import randint

def answer(a, n):
    def prod(arr):
        " Multiply elements of array "
        return reduce((lambda x, y: x * y), arr, 1)

    def max_single_sign_prod(arr):
        " Find max product of array assuming all element are same sign "
        if arr[0] == 0:
            return 0  # all zero
        if arr[0] > 0:
            return proc(arr) # all positive

        # all negative
        p = prod(arr)
        if len(arr) > 1 and len(arr) % 2:
            return p // max(arr)
        else:
            return p

    # Generate all positive, all negative and all zero sublists of arr
    pos = [i for i in a if i > 0]
    neg = [i for i in a if i < 0]
    zeros = [i for i in a if i == 0]

    # Find non-empty sublists
    b = [x for x in [pos, neg, zero] if len(x) > 0]

    products = list(map(max_single_sign_prod, b))

    # Find optimal combinations of these product to product max
    # There's only 3**2 or 9 combinations to try
    max_product = max(prod(c) for c in list(comb) for comb in combinations(products, i) for i in range(len(b)+1))

    return str(max_product)

if __name__ == '__main__': 
    big_array = [randint(-1000, 1000) for _ in range(51)]
    tests = [[-1], [1], [-1, 0], [2, 0, 2, 2, 0],  [-2, -3, 4, -5], [ -1, -1, -2, 4, 3 ], big_array ]
    for t in tests:
        print('array {} \n\t max: {}'.format(t, maxProductSubset(t, len(t))))

策略

我们从数组生成三个子序列:

We generate three subsequences from the array:

1. 所有正数
2. 所有零元素
3. 所有负面因素

每个序列的最大乘积如下:

The maximum product for each of these sequences is as follows:

• 所有正数-所有数字的乘积
• 全零-零
• 所有负数-所有数字的乘积(对于偶数长度)，否则除 乘以最大值(如果是奇数长度)的乘积

• all positive -- the product of all the numbers
• all zeros -- zero
• all negative -- product of all numbers (for even length) else divide the product by the max (if odd length)

我们为每个非空序列(即所有正数，零数和负数)计算最大乘积.

We compute the maximum product for each of the non-empty sequences (i.e. all positive, zeros, and negative).

这将产生1到3个与非空子序列相对应的乘积.

This results in from 1 to 3 products corresponding to the non-empty subsequences.

我们的答案是找到提供最大值的1至3种产品的组合.

Our answer is to find the combination of the 1 to 3 products that provides the maximum value.

最多有3 ** 2个组合，因此很容易计算.

There are at most 3**2 combinations so this is easily computed.

这篇关于Google Foobar挑战耗电大亨-测试失败. 5个测试用例中有3个(隐藏)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！