Skip to content

re: Advent of Code 2019 Solution Megathread - Day 12: The N-Body Problem VIEW POST


Got part 2 in the end! The intuition that each axis is independent came to me while I was away from the keyboard!

def simulate_until_repeat(moons: List[Moon]) -> int:
  Simulate `moons` until a repeated state is seen. Returns the
  number of simulation steps to get to that state
  def gcd(x: int, y: int) -> int:
    return y if x == 0 else gcd(y % x, x)

  def loop_size_for_axis(moons: List[Moon], axis) -> int:
    def state(m: List[Moon]) -> str:
      return str(list(axis(x) for x in m))

    states = set(state(moons))
    for n, m in enumerate(simulate_seq(moons)):
      s = state(m)
      if s in states:
        return n

  def axis_x(m): return (m.pos.x, m.velocity.x)
  def axis_y(m): return (m.pos.y, m.velocity.y)
  def axis_z(m): return (m.pos.z, m.velocity.z)

  overall_loop = 1
  for a in [axis_x, axis_y, axis_z]:
    loop = loop_size_for_axis(moons, a)
    overall_loop = overall_loop * loop // gcd(loop, overall_loop)

  return overall_loop
code of conduct - report abuse