Python切片优化及AoC第5天Crate移动问题修正

问题背景 #

正在解决AoC第5天问题，需模拟CrateMover 9001规则：移动多个货箱时保持原有顺序。初始货箱栈结构：

[D]    
[N] [C]    
[Z] [M] [P]
 1   2   3 

按给定指令执行后，预期最终栈顶序列为MCD，但代码运行输出异常，相关信息如下：

错误输出 #

['Z', 'N', ['M', 'C', 'D'], ['M', 'C', 'D'], ['C', 'D']] ['M', 'C', 'D', ['Z', 'N', ['M', 'C', 'D'], ['M', 'C', 'D'], ['C', 'D']]] ['P', ['Z', 'N', ['M', 'C', 'D']], ['N', ['M', 'C', 'D']], [['M', 'C', 'D']]]
['C', 'D', 'Z', 'N', ['M', 'C', 'D'], ['M', 'C', 'D'], ['C', 'D'], ['M', 'C', 'D']]

原代码 #

import re

data ="""move 1 from 2 to 1
    move 3 from 1 to 3
    move 2 from 2 to 1
    move 1 from 1 to 2"""

first = ['Z', 'N']
second = ['M', 'C', 'D']
third = ['P']
stack_numbers = {1: first, 2: second, 3: third}
for i in data.splitlines():
    i = i.strip()
    temp = re.findall(r'\d+', i)
    res = list(map(int, temp))
    n = res[0]
    move_from = stack_numbers[res[1]]
    move_to = stack_numbers[res[2]]
    for i in range(n):
        a = move_from[i:]
        move_to.append(a)
        res[1] = move_from[:i]
        res[2] = move_to
print(first, second, third)
seq = first.pop() + second.pop() + third.pop()
print(seq)

错误原因解析 #

1. 循环逻辑错误：CrateMover 9001是一次性移动n个货箱，不需要循环n次逐个处理，你的循环反而重复执行了错误的移动操作。
2. 切片与列表操作错误：
   • move_from[i:]取的是从第i个元素开始的子列表，而非末尾n个货箱，正确应该用move_from[-n:]获取最后n个元素。
   • move_to.append(a)是把整个子列表作为单个元素添加到目标栈，导致栈内嵌套列表，正确做法是用extend或+=扩展目标栈。
3. 无效赋值操作：res[1] = move_from[:i]完全没用，res是指令解析出的数字列表，修改它不会改变原栈内容，应该直接修改move_from本身，截断为去掉最后n个元素的结果。

修复后的代码 #

import re

data ="""move 1 from 2 to 1
    move 3 from 1 to 3
    move 2 from 2 to 1
    move 1 from 1 to 2"""

first = ['Z', 'N']
second = ['M', 'C', 'D']
third = ['P']
stack_numbers = {1: first, 2: second, 3: third}

for line in data.splitlines():
    line = line.strip()
    if not line:
        continue
    counts, from_stack, to_stack = map(int, re.findall(r'\d+', line))
    src = stack_numbers[from_stack]
    dest = stack_numbers[to_stack]
    # 取出最后counts个元素，保持原有顺序
    moved_crates = src[-counts:]
    # 扩展目标栈，添加移动的货箱
    dest.extend(moved_crates)
    # 截断原栈，移除已移动的元素
    src[:] = src[:-counts]

print(first, second, third)
seq = first[-1] + second[-1] + third[-1]  # 直接取栈顶，避免pop修改原栈
print(seq)  # 输出MCD

更高效的实现方式 #

1. 用collections.deque优化栈操作：列表从末尾操作虽高效，但deque的append和pop都是严格O(1)，性能更稳定：

from collections import deque
import re

data ="""move 1 from 2 to 1
    move 3 from 1 to 3
    move 2 from 2 to 1
    move 1 from 1 to 2"""

stacks = {
    1: deque(['Z', 'N']),
    2: deque(['M', 'C', 'D']),
    3: deque(['P'])
}

for line in data.splitlines():
    line = line.strip()
    if not line:
        continue
    counts, from_stack, to_stack = map(int, re.findall(r'\d+', line))
    src = stacks[from_stack]
    dest = stacks[to_stack]
    # 取出最后counts个元素，转为列表保持顺序
    moved = list(src)[-counts:]
    dest.extend(moved)
    # 移除原栈的counts个元素
    for _ in range(counts):
        src.pop()

seq = ''.join(stack[-1] for stack in stacks.values())
print(seq)  # 输出MCD

2. 通用栈初始化：如果处理原题完整输入，可直接从输入文本解析栈结构，无需硬编码——按行读取栈的部分，反向遍历构建每个栈，适配任意数量的货箱栈。

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