foobar please-pass-the-coded-messages 隐藏测试用例未通过
foobar please-pass-the-coded-messages hidden test case not passing
我一直在尝试 google foobar，在第二关我得到了名为 please-pass-the-coded-messages 的任务。下面是任务
==============================
You need to pass a message to the bunny workers, but to avoid detection, the code you agreed to use is... obscure, to say the least. The bunnies are given food on standard-issue plates that are stamped with the numbers 0-9 for easier sorting, and you need to combine sets of plates to create the numbers in the code. The signal that a number is part of the code is that it is divisible by 3. You can do smaller numbers like 15 and 45 easily, but bigger numbers like 144 and 414 are a little trickier. Write a program to help yourself quickly create large numbers for use in the code, given a limited number of plates to work with.
You have L, a list containing some digits (0 to 9). Write a function solution(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the solution. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution({3, 1, 4, 1})
Output:
4311
Input:
Solution.solution({3, 1, 4, 1, 5, 9})
Output:
94311
-- Python cases --
Input:
solution.solution([3, 1, 4, 1])
Output:
4311
Input:
solution.solution([3, 1, 4, 1, 5, 9])
Output:
94311
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.
我已经尝试了一个解决方案，它在我的 ide 中非常有效（注意我想要一个没有任何库的解决方案）
def solution(l):
# Your code here
if (len(l) == 1 and l[0] % 3 != 0) or (len(l) == 0):
return 0
number = formGreatestNumber(l)
remainder = number % 3
if remainder == 0:
result = formGreatestNumber(l)
return result
result = removeUnwanted(l, remainder)
return result
def formGreatestNumber(li):
li.sort(reverse=True) # descending order
li = [str(d) for d in li] # each digit in string
number = 0
if len(li) > 0:
number = int("".join(li)) # result
return number
def removeUnwanted(l, remainder):
possibleRemovals = [i for i in l if i % 3 == remainder]
if len(possibleRemovals) > 0:
l.remove(min(possibleRemovals))
result = formGreatestNumber(l)
return result
pairs = checkForTwo(l, remainder)
if len(pairs) > 0:
for ind in pairs:
l.remove(ind)
result = formGreatestNumber(l)
return result
else:
divisibleDigits = [d for d in l if d % 3 == 0]
if len(divisibleDigits) > 0:
result = formGreatestNumber(divisibleDigits)
return result
else:
return 0
def checkForTwo(l, remainder): # check of (sum of any two pairs - remainder) is divisible by 3
result = []
for i in range(len(l)):
for j in range(i+1, len(l)):
if ((l[i]+l[j])-remainder) % 3 == 0:
result.append(l[i])
result.append(l[j])
return result
return []
print(solution([]))
print(solution([1]))
print(solution([9]))
print(solution([3, 1, 4, 1, 9, 2, 5, 7]))
不过正在验证显示-
Verifying solution...
Test 1 passed!
Test 2 passed!
Test 3 failed [Hidden]
Test 4 passed! [Hidden]
Test 5 passed! [Hidden]
那么我没有注意到的错误在哪里，有没有其他方法没有像 itertools 这样的库？
我不会泄露代码并破坏您的乐趣，我可能会尝试解释直觉。
关于您的代码，我认为函数 removeUnwanted() 的（第二部分）在这里有问题。
让我们看看。
所以首先，您要将输入的数字排列成一个数字，按照从大到小的顺序，您已经完成了。
然后，如果形成的数字不能被 3 整除，请尝试删除最小的数字。
如果这不起作用，请重新插入最小的数字并删除第二个最小的数字，依此类推。
一次删除所有可能的数字后，尝试一次删除两个数字，从两个最小的数字开始。
如果其中任何一个结果是一个可以被 3 整除的数字，你就完成了。
请注意，对于此问题，您永远不需要删除超过 2 位数字。不可能形成所需数字的唯一方法是，如果有 2 个或更少的数字，并且它们都在集合 {1,4,7} 或 {2,5,8} 中。
编辑：关于您的代码的更多信息 -
您的 removeUnwanted() 的初始部分看起来不错，您检查数字中是否有可以删除的单个数字，从单个数字的选择中删除最小值并获得答案。
我认为问题出在您的函数 checkForTwo() 上，您随后在 removeUnwanted 中调用了该函数。
当您将列表传递给 checkForTwo() 时，请注意列表实际上是按降序排列的。这是因为 li.sort(reverse=True) 在您的函数 formGreatestNumber() 中对列表进行了适当的排序，这意味着列表 l 的内容也按降序排序。
然后在 checkForTwo() 中，您尝试找到满足要求条件的一对，但您正在从可能被删除的最大 2 对中循环。 i 从 0 开始，j 从 i+1 which is 1 开始，并且由于您的列表是按降序排列的，因此您正在尝试删除可能的最大 2 个元素。
快速解决方法是 按升序对列表进行排序，然后进一步以相反的顺序遍历列表，因为列表已经按降序排序，反向迭代为您提供升序排列的列表，并使我们免于重新排序，这通常会花费额外的 O(NlogN) 时间。
我一直在尝试 google foobar，在第二关我得到了名为 please-pass-the-coded-messages 的任务。下面是任务
==============================
You need to pass a message to the bunny workers, but to avoid detection, the code you agreed to use is... obscure, to say the least. The bunnies are given food on standard-issue plates that are stamped with the numbers 0-9 for easier sorting, and you need to combine sets of plates to create the numbers in the code. The signal that a number is part of the code is that it is divisible by 3. You can do smaller numbers like 15 and 45 easily, but bigger numbers like 144 and 414 are a little trickier. Write a program to help yourself quickly create large numbers for use in the code, given a limited number of plates to work with.
You have L, a list containing some digits (0 to 9). Write a function solution(L) which finds the largest number that can be made from some or all of these digits and is divisible by 3. If it is not possible to make such a number, return 0 as the solution. L will contain anywhere from 1 to 9 digits. The same digit may appear multiple times in the list, but each element in the list may only be used once.
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution({3, 1, 4, 1})
Output:
4311
Input:
Solution.solution({3, 1, 4, 1, 5, 9})
Output:
94311
-- Python cases --
Input:
solution.solution([3, 1, 4, 1])
Output:
4311
Input:
solution.solution([3, 1, 4, 1, 5, 9])
Output:
94311
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.
我已经尝试了一个解决方案，它在我的 ide 中非常有效（注意我想要一个没有任何库的解决方案）
def solution(l):
# Your code here
if (len(l) == 1 and l[0] % 3 != 0) or (len(l) == 0):
return 0
number = formGreatestNumber(l)
remainder = number % 3
if remainder == 0:
result = formGreatestNumber(l)
return result
result = removeUnwanted(l, remainder)
return result
def formGreatestNumber(li):
li.sort(reverse=True) # descending order
li = [str(d) for d in li] # each digit in string
number = 0
if len(li) > 0:
number = int("".join(li)) # result
return number
def removeUnwanted(l, remainder):
possibleRemovals = [i for i in l if i % 3 == remainder]
if len(possibleRemovals) > 0:
l.remove(min(possibleRemovals))
result = formGreatestNumber(l)
return result
pairs = checkForTwo(l, remainder)
if len(pairs) > 0:
for ind in pairs:
l.remove(ind)
result = formGreatestNumber(l)
return result
else:
divisibleDigits = [d for d in l if d % 3 == 0]
if len(divisibleDigits) > 0:
result = formGreatestNumber(divisibleDigits)
return result
else:
return 0
def checkForTwo(l, remainder): # check of (sum of any two pairs - remainder) is divisible by 3
result = []
for i in range(len(l)):
for j in range(i+1, len(l)):
if ((l[i]+l[j])-remainder) % 3 == 0:
result.append(l[i])
result.append(l[j])
return result
return []
print(solution([]))
print(solution([1]))
print(solution([9]))
print(solution([3, 1, 4, 1, 9, 2, 5, 7]))
不过正在验证显示-
Verifying solution...
Test 1 passed!
Test 2 passed!
Test 3 failed [Hidden]
Test 4 passed! [Hidden]
Test 5 passed! [Hidden]
那么我没有注意到的错误在哪里，有没有其他方法没有像 itertools 这样的库？
我不会泄露代码并破坏您的乐趣，我可能会尝试解释直觉。
关于您的代码，我认为函数 removeUnwanted() 的（第二部分）在这里有问题。
让我们看看。
所以首先，您要将输入的数字排列成一个数字，按照从大到小的顺序，您已经完成了。
然后，如果形成的数字不能被 3 整除，请尝试删除最小的数字。
如果这不起作用，请重新插入最小的数字并删除第二个最小的数字，依此类推。
一次删除所有可能的数字后，尝试一次删除两个数字，从两个最小的数字开始。
如果其中任何一个结果是一个可以被 3 整除的数字，你就完成了。
请注意，对于此问题，您永远不需要删除超过 2 位数字。不可能形成所需数字的唯一方法是，如果有 2 个或更少的数字，并且它们都在集合 {1,4,7} 或 {2,5,8} 中。
编辑：关于您的代码的更多信息 -
您的 removeUnwanted() 的初始部分看起来不错，您检查数字中是否有可以删除的单个数字，从单个数字的选择中删除最小值并获得答案。
我认为问题出在您的函数 checkForTwo() 上，您随后在 removeUnwanted 中调用了该函数。
当您将列表传递给 checkForTwo() 时，请注意列表实际上是按降序排列的。这是因为 li.sort(reverse=True) 在您的函数 formGreatestNumber() 中对列表进行了适当的排序，这意味着列表 l 的内容也按降序排序。
然后在 checkForTwo() 中，您尝试找到满足要求条件的一对，但您正在从可能被删除的最大 2 对中循环。 i 从 0 开始，j 从 i+1 which is 1 开始，并且由于您的列表是按降序排列的，因此您正在尝试删除可能的最大 2 个元素。
快速解决方法是 按升序对列表进行排序，然后进一步以相反的顺序遍历列表，因为列表已经按降序排序，反向迭代为您提供升序排列的列表，并使我们免于重新排序，这通常会花费额外的 O(NlogN) 时间。