Code 2021 的到来：第 6 天 - 双端队列的问题
Advent of Code 2021: Day 6 - problems with deque
我今天要解决的问题是Advent of Code 2021 - Day 6: Lanternfish。
问题的主要摘录已包含在下面，以确保这个问题是独立的。
suppose you have a lanternfish with an internal timer value of 3:
- After one day, its internal timer would become
2.
- After another day, its internal timer would become
1.
- After another day, its internal timer would become
0.
- After another day, its internal timer would reset to
6, and it would create a new lanternfish with an internal timer of 8.
- After another day, the first lanternfish would have an internal timer of
5, and the second lanternfish would have an internal timer
of 7. A lanternfish that creates a new fish resets its timer to 6,
not 7 (because 0 is included as a valid timer value). The new lanternfish starts with an internal timer of 8` and does not start
counting down until the next day.
Realizing what you're trying to do, the submarine automatically
produces a list of the ages of several hundred nearby lanternfish
(your puzzle input). For example, suppose you were given the following
list:
3,4,3,1,2
This list means that the first fish has an internal timer of 3, the
second fish has an internal timer of 4, and so on until the fifth
fish, which has an internal timer of 2. Simulating these fish over
several days would proceed as follows:
Initial state: 3,4,3,1,2
After 1 day: 2,3,2,0,1
After 2 days: 1,2,1,6,0,8
After 3 days: 0,1,0,5,6,7,8
After 4 days: 6,0,6,4,5,6,7,8,8
After 5 days: 5,6,5,3,4,5,6,7,7,8
After 6 days: 4,5,4,2,3,4,5,6,6,7
After 7 days: 3,4,3,1,2,3,4,5,5,6
After 8 days: 2,3,2,0,1,2,3,4,4,5
After 9 days: 1,2,1,6,0,1,2,3,3,4,8
After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8
After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8
Each day, a 0 becomes a 6 and adds a new 8 to the end of the list,
while each other number decreases by 1 if it was present at the start
of the day.
In this example, after 18 days, there are a total of 26 fish.
After 80 days, there would be a total of 5934.
我能够解决上面的问题如下
def update(lanternfish):
new_lanternfish = list(lanternfish)
new_fish = 0
for i, fish in enumerate(lanternfish):
new_lanternfish[i] = fish - 1
if new_lanternfish[i] < 0:
new_lanternfish[i] = LANTERNFISH_SPAWN_RATE
new_fish += 1
if new_fish:
new_lanternfish.extend([LANTERNFISH_SPAWN_RATE + LANTERNFISH_DELAY] * new_fish)
return new_lanternfish
lanterfish = [3,4,3,1,2]
for _ in range(18):
lanterfish = update(lanterfish)
print(len(lanterfish))
但是，当我需要增加天数时，这段代码太慢无法完成
我选择了一种更面向对象的方法，如下所示
from dataclasses import dataclass
from typing import Union
import collections
LANTERNFISH_DELAY = 2
LANTERNFISH_SPAWN_RATE = 6
LANTERNFISH = LANTERNFISH_DELAY + LANTERNFISH_SPAWN_RATE
@dataclass
class LanternFish:
pools: list[int]
incubation = collections.deque([0] * LANTERNFISH_DELAY, maxlen=LANTERNFISH_DELAY)
day = 1
def __post_init__(self):
self.fish = sum(self.pools) + sum(self.incubation)
def update(self, days: int = 1):
for i in range(days):
pool_2_update = (self.day + i - 1) % LANTERNFISH_SPAWN_RATE
fish_in = self.pools[pool_2_update]
fish_out = self.incubation[0]
self.incubation.append(fish_in)
self.pools[pool_2_update] += fish_out
self.day += days
self.fish = sum(self.pools) + sum(self.incubation)
def fish_pools(lanternfish) -> list[int]:
total_fish = [0] * LANTERNFISH_SPAWN_RATE
for fish in lanternfish:
total_fish[fish] += 1
return total_fish
def mark_pool(pools: list[int], index: int) -> list[Union[int, str]]:
marked = f"({pools[index]})"
new_pools: list[Union[int, str]] = list(pools)
new_pools[index] = marked
return new_pools
if __name__ == "__main__":
lanternfish_data = [3, 4, 3, 1, 2]
pools = fish_pools(lanternfish_data)
lanternfish = LanternFish(pools)
days = 18
for _ in range(18):
print(
f"day={lanternfish.day:02d}, {mark_pool(lanternfish.pools, (lanternfish.day-1) % LANTERNFISH_SPAWN_RATE)}, incubation={lanternfish.incubation}, fish={lanternfish.fish:4d}"
)
lanternfish.update()
print(lanternfish.fish)
我目前只是想模仿测试数据
这应该会导致 18 天后 26 鱼和 80 天后 5934 鱼。相反，我在 18 天后获得 29，在 80 天后获得 15820。
关于如何调试我的程序有什么建议吗？
我试图通过每天打印出来来调试它。我把鱼分成一个孵化期，X 天后它们就长大了，然后和其他鱼一起放入池中。我没有保留每条鱼的清单，而是保留了每天繁殖的鱼数的清单。
day=01, ['(0)', 1, 1, 2, 1, 0], incubation=deque([0, 0], maxlen=2), fish= 5
day=02, [0, '(1)', 1, 2, 1, 0], incubation=deque([0, 0], maxlen=2), fish= 5
day=03, [0, 1, '(1)', 2, 1, 0], incubation=deque([0, 1], maxlen=2), fish= 6
day=04, [0, 1, 1, '(2)', 1, 0], incubation=deque([1, 1], maxlen=2), fish= 7
day=05, [0, 1, 1, 3, '(1)', 0], incubation=deque([1, 2], maxlen=2), fish= 9
day=06, [0, 1, 1, 3, 2, '(0)'], incubation=deque([2, 1], maxlen=2), fish= 10
day=07, ['(0)', 1, 1, 3, 2, 2], incubation=deque([1, 0], maxlen=2), fish= 10
day=08, [1, '(1)', 1, 3, 2, 2], incubation=deque([0, 0], maxlen=2), fish= 10
day=09, [1, 1, '(1)', 3, 2, 2], incubation=deque([0, 1], maxlen=2), fish= 11
day=10, [1, 1, 1, '(3)', 2, 2], incubation=deque([1, 1], maxlen=2), fish= 12
day=11, [1, 1, 1, 4, '(2)', 2], incubation=deque([1, 3], maxlen=2), fish= 15
day=12, [1, 1, 1, 4, 3, '(2)'], incubation=deque([3, 2], maxlen=2), fish= 17
day=13, ['(1)', 1, 1, 4, 3, 5], incubation=deque([2, 2], maxlen=2), fish= 19
day=14, [3, '(1)', 1, 4, 3, 5], incubation=deque([2, 1], maxlen=2), fish= 20
day=15, [3, 3, '(1)', 4, 3, 5], incubation=deque([1, 1], maxlen=2), fish= 21
day=16, [3, 3, 2, '(4)', 3, 5], incubation=deque([1, 1], maxlen=2), fish= 22
day=17, [3, 3, 2, 5, '(3)', 5], incubation=deque([1, 4], maxlen=2), fish= 26
day=18, [3, 3, 2, 5, 4, '(5)'], incubation=deque([4, 3], maxlen=2), fish= 29
我可以看到我的解决方案在第 9 天出现了分歧，但不确定原因。可能我也可以为池使用 deque，这样我就不必做模魔术，但我看不出这如何解决代码的继承问题。
也许你想得太复杂了。如果你想使用双端队列，用它来跟踪你有多少个年龄。然后你只需要每天向左旋转并将新鱼从 bin 0 添加到 bin 6（在旋转之前是 bin 7）：
def count_fish(days, fish):
# init counts
bins = deque([0] * 9)
for f in fish:
bins[f] += 1
# run through days
for day in range(days):
bins[7] += bins[0]
bins.rotate(-1)
return sum(bins)
print(f"solution1: {count_fish(80, [3,4,3,1,2])}")
# solution1: 5934
我今天要解决的问题是Advent of Code 2021 - Day 6: Lanternfish。 问题的主要摘录已包含在下面，以确保这个问题是独立的。
suppose you have a lanternfish with an internal timer value of
3:
- After one day, its internal timer would become
2.- After another day, its internal timer would become
1.- After another day, its internal timer would become
0.- After another day, its internal timer would reset to
6, and it would create a new lanternfish with an internal timer of8.- After another day, the first lanternfish would have an internal timer of
5, and the second lanternfish would have an internal timer of7. A lanternfish that creates a new fish resets its timer to6, not7(because0 is included as a valid timer value). The new lanternfish starts with an internal timer of8` and does not start counting down until the next day.Realizing what you're trying to do, the submarine automatically produces a list of the ages of several hundred nearby lanternfish (your puzzle input). For example, suppose you were given the following list:
3,4,3,1,2This list means that the first fish has an internal timer of
3, the second fish has an internal timer of4, and so on until the fifth fish, which has an internal timer of2. Simulating these fish over several days would proceed as follows:Initial state: 3,4,3,1,2 After 1 day: 2,3,2,0,1 After 2 days: 1,2,1,6,0,8 After 3 days: 0,1,0,5,6,7,8 After 4 days: 6,0,6,4,5,6,7,8,8 After 5 days: 5,6,5,3,4,5,6,7,7,8 After 6 days: 4,5,4,2,3,4,5,6,6,7 After 7 days: 3,4,3,1,2,3,4,5,5,6 After 8 days: 2,3,2,0,1,2,3,4,4,5 After 9 days: 1,2,1,6,0,1,2,3,3,4,8 After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8 After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8 After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8 After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8 After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8 After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7 After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8 After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8 After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8Each day, a
0becomes a 6 and adds a new8to the end of the list, while each other number decreases by 1 if it was present at the start of the day.In this example, after
18days, there are a total of26fish. After 80 days, there would be a total of5934.
我能够解决上面的问题如下
def update(lanternfish):
new_lanternfish = list(lanternfish)
new_fish = 0
for i, fish in enumerate(lanternfish):
new_lanternfish[i] = fish - 1
if new_lanternfish[i] < 0:
new_lanternfish[i] = LANTERNFISH_SPAWN_RATE
new_fish += 1
if new_fish:
new_lanternfish.extend([LANTERNFISH_SPAWN_RATE + LANTERNFISH_DELAY] * new_fish)
return new_lanternfish
lanterfish = [3,4,3,1,2]
for _ in range(18):
lanterfish = update(lanterfish)
print(len(lanterfish))
但是，当我需要增加天数时，这段代码太慢无法完成
我选择了一种更面向对象的方法，如下所示
from dataclasses import dataclass
from typing import Union
import collections
LANTERNFISH_DELAY = 2
LANTERNFISH_SPAWN_RATE = 6
LANTERNFISH = LANTERNFISH_DELAY + LANTERNFISH_SPAWN_RATE
@dataclass
class LanternFish:
pools: list[int]
incubation = collections.deque([0] * LANTERNFISH_DELAY, maxlen=LANTERNFISH_DELAY)
day = 1
def __post_init__(self):
self.fish = sum(self.pools) + sum(self.incubation)
def update(self, days: int = 1):
for i in range(days):
pool_2_update = (self.day + i - 1) % LANTERNFISH_SPAWN_RATE
fish_in = self.pools[pool_2_update]
fish_out = self.incubation[0]
self.incubation.append(fish_in)
self.pools[pool_2_update] += fish_out
self.day += days
self.fish = sum(self.pools) + sum(self.incubation)
def fish_pools(lanternfish) -> list[int]:
total_fish = [0] * LANTERNFISH_SPAWN_RATE
for fish in lanternfish:
total_fish[fish] += 1
return total_fish
def mark_pool(pools: list[int], index: int) -> list[Union[int, str]]:
marked = f"({pools[index]})"
new_pools: list[Union[int, str]] = list(pools)
new_pools[index] = marked
return new_pools
if __name__ == "__main__":
lanternfish_data = [3, 4, 3, 1, 2]
pools = fish_pools(lanternfish_data)
lanternfish = LanternFish(pools)
days = 18
for _ in range(18):
print(
f"day={lanternfish.day:02d}, {mark_pool(lanternfish.pools, (lanternfish.day-1) % LANTERNFISH_SPAWN_RATE)}, incubation={lanternfish.incubation}, fish={lanternfish.fish:4d}"
)
lanternfish.update()
print(lanternfish.fish)
我目前只是想模仿测试数据
这应该会导致 18 天后 26 鱼和 80 天后 5934 鱼。相反，我在 18 天后获得 29，在 80 天后获得 15820。
关于如何调试我的程序有什么建议吗？
我试图通过每天打印出来来调试它。我把鱼分成一个孵化期，X 天后它们就长大了，然后和其他鱼一起放入池中。我没有保留每条鱼的清单，而是保留了每天繁殖的鱼数的清单。
day=01, ['(0)', 1, 1, 2, 1, 0], incubation=deque([0, 0], maxlen=2), fish= 5
day=02, [0, '(1)', 1, 2, 1, 0], incubation=deque([0, 0], maxlen=2), fish= 5
day=03, [0, 1, '(1)', 2, 1, 0], incubation=deque([0, 1], maxlen=2), fish= 6
day=04, [0, 1, 1, '(2)', 1, 0], incubation=deque([1, 1], maxlen=2), fish= 7
day=05, [0, 1, 1, 3, '(1)', 0], incubation=deque([1, 2], maxlen=2), fish= 9
day=06, [0, 1, 1, 3, 2, '(0)'], incubation=deque([2, 1], maxlen=2), fish= 10
day=07, ['(0)', 1, 1, 3, 2, 2], incubation=deque([1, 0], maxlen=2), fish= 10
day=08, [1, '(1)', 1, 3, 2, 2], incubation=deque([0, 0], maxlen=2), fish= 10
day=09, [1, 1, '(1)', 3, 2, 2], incubation=deque([0, 1], maxlen=2), fish= 11
day=10, [1, 1, 1, '(3)', 2, 2], incubation=deque([1, 1], maxlen=2), fish= 12
day=11, [1, 1, 1, 4, '(2)', 2], incubation=deque([1, 3], maxlen=2), fish= 15
day=12, [1, 1, 1, 4, 3, '(2)'], incubation=deque([3, 2], maxlen=2), fish= 17
day=13, ['(1)', 1, 1, 4, 3, 5], incubation=deque([2, 2], maxlen=2), fish= 19
day=14, [3, '(1)', 1, 4, 3, 5], incubation=deque([2, 1], maxlen=2), fish= 20
day=15, [3, 3, '(1)', 4, 3, 5], incubation=deque([1, 1], maxlen=2), fish= 21
day=16, [3, 3, 2, '(4)', 3, 5], incubation=deque([1, 1], maxlen=2), fish= 22
day=17, [3, 3, 2, 5, '(3)', 5], incubation=deque([1, 4], maxlen=2), fish= 26
day=18, [3, 3, 2, 5, 4, '(5)'], incubation=deque([4, 3], maxlen=2), fish= 29
我可以看到我的解决方案在第 9 天出现了分歧，但不确定原因。可能我也可以为池使用 deque，这样我就不必做模魔术，但我看不出这如何解决代码的继承问题。
也许你想得太复杂了。如果你想使用双端队列，用它来跟踪你有多少个年龄。然后你只需要每天向左旋转并将新鱼从 bin 0 添加到 bin 6（在旋转之前是 bin 7）：
def count_fish(days, fish):
# init counts
bins = deque([0] * 9)
for f in fish:
bins[f] += 1
# run through days
for day in range(days):
bins[7] += bins[0]
bins.rotate(-1)
return sum(bins)
print(f"solution1: {count_fish(80, [3,4,3,1,2])}")
# solution1: 5934