Re: Un bug que j'ai résolu sans jamais le trouver.

Joli, du coup j'ai honte de montrer ma solution avec liste chaînée maison. Mais je la montre quand même, allez :

from __future__ import annotations
import io
from typing import Iterable, Iterator, Optional
class Chain:
 def __init__(self, *elts: Element) -> None:
 self._len = len(elts)
 self.first = elts[0]
 last = elts[-1]
 prev: Optional[Element] = None
 for elt in elts:
 if prev is not None:
 prev.attach(elt)
 prev = elt
 last.attach(self.first)
 def __len__(self):
 return self._len
 def __getitem__(self, index: int) -> Element:
 index = index % len(self)
 current = self.first
 for _ in range(index):
 current = current.next
 return current
 def get_elt(self, base_elt: Element, index: int) -> Element:
 index = index % len(self)
 current = base_elt
 for _ in range(index):
 current = current.next
 return current
 def __iter__(self) -> Iterator[Element]:
 current = self.first
 for _ in range(self._len):
 yield current
 current = current.next
 def extract(self, index: int) -> Element:
 elt = self[index]
 elt.detach()
 self._len -= 1
 return elt
 def extract_elt(self, elt: Element) -> None:
 # WARNING: not checking that elt is part of self
 elt.detach()
 self._len -= 1
 def insert(self, index: int, elt: Element) -> None:
 prev = self[index]
 next_ = prev.next
 # Attach (prev and elt) and (elt and next_)
 prev.attach(elt)
 elt.attach(next_)
 self._len += 1
 def insert_elt(self, base: Element,
 shift: int, elt: Element) -> None:
 # WARNING: not checking that elt is part of self
 shift %= self._len
 prev = base
 for _ in range(shift):
 prev = prev.next
 next_ = prev.next
 # Attach (prev and elt) and (elt and next_)
 prev.attach(elt)
 elt.attach(next_)
 self._len += 1
 def __str__(self):
 result = io.StringIO()
 result.write('(')
 for elt in self:
 result.write('{}, '.format(elt.value))
 result.write(')')
 return result.getvalue()
class Element:
 def __init__(self, value: int) -> None:
 self.value = value
 self.prev = self
 self.next = self
 def attach(self, other: Element) -> None:
 self.next = other
 other.prev = self
 def detach(self) -> None:
 prev = self.prev
 next_ = self.next
 # Detach self
 self.prev = self
 self.next_ = self
 # Attach prev and next_
 prev.attach(next_)
def solve1(lines: Iterable[str]) -> int:
 """Solve part 1 of today's puzzle"""
 elts = [Element(int(line)) for line in lines]
 seq = Chain(*elts)
 zero: Optional[elt] = None
 for elt in elts:
 if zero is None and elt.value == 0:
 zero = elt
 prev = elt.prev
 seq.extract_elt(elt)
 seq.insert_elt(prev, elt.value, elt)
 if zero is None:
 raise ValueError("invalid input without a zero value")
 return (seq.get_elt(zero, 1000).value
 + seq.get_elt(zero, 2000).value
 + seq.get_elt(zero, 3000).value)
def solve2(lines: Iterable[str]) -> int:
 """Solve part 2 of today's puzzle"""
 key = 811589153
 elts = [Element(key * int(line)) for line in lines]
 seq = Chain(*elts)
 zero: Optional[elt] = None
 for _ in range(10):
 for elt in elts:
 if zero is None and elt.value == 0:
 zero = elt
 prev = elt.prev
 seq.extract_elt(elt)
 seq.insert_elt(prev, elt.value, elt)
 if zero is None:
 raise ValueError("invalid input without a zero value")
 return (seq.get_elt(zero, 1000).value
 + seq.get_elt(zero, 2000).value
 + seq.get_elt(zero, 3000).value)

À noter que c'est pas mal plus lent qu'avec des listes Python en fait... :-(