Google Kickstart布料排序问题：样例通过但测试用例1报错求优化

问题背景 #

在2022年Google Kickstart竞赛的F轮中，有一项任务要求实现算法对布料列表进行两种方式排序：

• 按颜色（字典序）排序（Ada的排序方式）
• 按耐用性排序（Charles的排序方式）

输入包含T组测试用例，每组有N块布料，每块布料包含颜色、耐用性及唯一ID。程序需要输出两种排序后位置完全相同的布料数量。

用户编写的Python代码能通过样例输入，但提交后仅通过样例，测试用例1失败，需要优化代码以通过所有测试用例。

用户原始代码 #

import operator
        
def sort():
    N = int(input())
    my_fabric = []
    fabric_list = []
    i = 0
    while i < N:
        input_fabric = str(input())
        split_list = input_fabric.split(' ')
        color = split_list[0]
        dura = split_list[1]
        ident = split_list[2]
        my_fabric.append(color)
        my_fabric.append(dura)
        my_fabric.append(ident)
        fabric_list.append(my_fabric)
        my_fabric = []
        i += 1
    return fabric_list

def ada(fabric_list):
    ada_list = sorted(fabric_list, key = operator.itemgetter(0))
    return ada_list

def charles(fabric_list):
    charles_list = sorted(fabric_list, key = operator.itemgetter(1))
    return charles_list

def comparison(ada_list, charles_list):
    list_len = len(ada_list)
    i = 0
    same_counter = 0
    while i < list_len: 
        if ada_list[i] == charles_list[i]:
            ada_list = sorted(ada_list, key = operator.itemgetter(2))
            charles_list = sorted(charles_list, key = operator.itemgetter(2))
            if ada_list[i][2] == charles_list[i][2]:
                same_counter += 1
                i += 1
            else:
                i += 1
        else:
            i += 1
    return same_counter

def main():
    t = int(input())
    i = 0
    while i < t:
        fabric_list = sort()
        ada_list = ada(fabric_list)
        charles_list = charles(fabric_list)
        same_counter = comparison(ada_list, charles_list)
        print("Case #{}: {}".format(i+1, same_counter))
        i += 1

main()

代码问题分析 #

1. 排序键的正确性问题
   • 耐用性是数值类型，但代码中直接作为字符串处理，字符串排序逻辑与数值不同（比如"10"会比"2"小），导致Charles的排序结果完全错误。
   • Ada的排序仅按颜色，未处理颜色相同的情况；Charles的排序仅按耐用性，未处理耐用性相同的情况。由于ID唯一，相同主排序键时必须以ID作为次要排序键，才能保证排序结果唯一、可预测。
2. 比较函数逻辑错误
   • 每次发现位置元素"相同"时，重新对整个列表按ID排序，直接破坏了原有的排序结果，导致后续位置对比完全失效。
3. 输入处理与命名问题
   • 使用split(' ')分割输入，无法处理多空格或制表符的情况；sort函数名与Python内置函数重名，易引发冲突。

优化后的代码 #

def read_test_case():
    N = int(input())
    fabrics = []
    for _ in range(N):
        color, dura_str, ident = input().split()
        dura = int(dura_str)
        fabrics.append((color, dura, ident))
    return fabrics

def get_ada_sorted(fabrics):
    # Ada排序规则：先颜色字典序，颜色相同按ID排序（保证唯一）
    return sorted(fabrics, key=lambda x: (x[0], x[2]))

def get_charles_sorted(fabrics):
    # Charles排序规则：先耐用性升序，耐用性相同按ID排序（保证唯一）
    return sorted(fabrics, key=lambda x: (x[1], x[2]))

def count_matching_positions(ada_list, charles_list):
    count = 0
    # 直接对比唯一ID判断是否为同一块布料
    for ada_fab, charles_fab in zip(ada_list, charles_list):
        if ada_fab[2] == charles_fab[2]:
            count += 1
    return count

def main():
    t = int(input())
    for case in range(1, t+1):
        fabrics = read_test_case()
        ada_sorted = get_ada_sorted(fabrics)
        charles_sorted = get_charles_sorted(fabrics)
        match_count = count_matching_positions(ada_sorted, charles_sorted)
        print(f"Case #{case}: {match_count}")

if __name__ == "__main__":
    main()

优化说明 #

1. 修正排序逻辑
   • 将耐用性转换为整数，确保数值排序的正确性；两种排序都添加ID作为次要排序键，保证排序结果唯一稳定。
2. 修复比较逻辑
   • 直接遍历两个排序后的列表，通过唯一ID对比判断是否为同一块布料，无需在比较过程中重新排序。
3. 输入与命名优化
   • 重命名冲突函数为read_test_case；使用split()处理任意空白字符分割输入；用元组存储布料信息，更轻量且不可变。
4. 可读性提升
   • 使用清晰的函数名和变量名；用for循环替代while循环；用f-string简化输出格式化。

内容的提问来源于stack exchange，提问作者Xman343