Skip to content
loading...

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

Jon Bristow on December 12, 2019

We've got to mind our moons! So let's tighten our belts and drop into the orbit of Day 12. Day 12 - The Problem Fresh from our run-in w... [Read Full]
markdown guide
 

Finally got the second part! 🥳

I actually had the right idea right off the bat, but I tried to cut the corners thinking if would have been too cumbersome... It turned out it was the opposite! 😄

But... Let's start with

Part One

This was fairly simple. All we had to do is to write a function that takes a step and evolves it into the next one. I used a JavaScript generator again, because why the heck not:

const coordRE = /<x=(-?\d+), y=(-?\d+), z=(-?\d+)>/;
function* getStates() {
  // Every satellite state is a vector of six numbers
  let satellites = input.trim().split('\n').map(line => ([
    ...line.match(coordRE).slice(1).map(Number),
    0, 0, 0
  ]));
  while (true) {
    satellites = satellites.map(satellite => {
      const velocity = satellite.slice(3);
      const nextVelocity = velocity.map((value, index) => {
        return satellites.reduce((diff, sat) => {
          return diff + Math.sign(sat[index] - satellite[index])
        }, value);
      });
      const nextPosition = satellite.slice(0, 3).map((value, index) => value + nextVelocity[index]);
      return [
        ...nextPosition,
        ...nextVelocity
      ];
    });
    yield satellites;
  }
}

function getTaxiDriverLength(vector) {
  return vector.reduce((sum, length) => sum + Math.abs(length), 0);
}

function getTotalEnergy(satellites) {
  return satellites.reduce((total, satellite) => {
    return total +
      getTaxiDriverLength(satellite.slice(0, 3)) *
      getTaxiDriverLength(satellite.slice(3));
  }, 0)
}

const states = getStates();
let satellites;
for (let i = 0; i < 1000; i++) {
  ({ value: satellites } = states.next());
}
console.log(getTotalEnergy(satellites));

I don't think there's much to say here...

Part Two

Now it comes the tricky part... My solution is 332477126821644 (~3.3e14), yours will be similar in size, so brute force is out of question.

I thought that this system is quite chaotic, but not that much chaotic, so satelite configurations could have a shorter period. When all 4 periods are found, all I had to do was to compute the least common multiple and I would have been golden! Right?

Well, in theory. In practice, I couldn't find the period of any of my satellites after one billion cycles, so that was no good. The next attempt consisted in splitting a satellite's state into position and velocity vectors, hoping that would have reduced their periods enough. And it did, but... that led me to a very high result.

Note that a "period" at that time consisted in the step number of the first time a vector was equal to the respective initial value. That's wrong too. For instance, in the first given example (with a period of 2772), the position of Europa (the second satellite) was the same of the initial position after 616, 1232, 1539, 2155, 2771 and 2772 steps. No clear period was evident.

But computing the differences between step marks gives the following sequence: 616, 616, 307, 616, 616, 1, 616, 616, 307, 616, 616, 1, 616, 616, 307, 616, 616, 1, 616... and so on. Grouping these numbers every 6 gives us a period of exactly 2772 steps. So I made this function to compute the period of a given array of (distances between) marks:

function getPeriod(distances) {
  for (let length = 1; length <= distances.length; length++) {
    const sums = [];
    const limit = distances.length - distances.length % length;
    for (let i = 0; i < limit; i += length) {
      let sum = 0;
      for (let j = 0; j < length; j++) {
        sum += distances[i + j];
      }
      sums.push(sum);
    }
    // If every sum is the same, then that sum is *probably* the period
    if (sums.length > 0 && sums.every(sum => sum === sums[0])) {
      return sums[0];
    }
  }
}

The following correction was to split everything down to every single vector component, and started marking all the occurences of a value equalling the initial value. And lo and behold, periods started to come out after "just" one million iterations! This is the last part of my script:

const states = getStates();
let { value: satellites } = states.next();
const initialStates = satellites.flatMap(satellite => [ ...satellite ]);
const marks = initialStates.map(() => new Set());

for (let i = 1; i < 1e6; i++) {
  ({ value: satellites } = states.next());
  satellites.forEach((satellite, index) => {
    for (let j = 0; j < 6; j++) {
      if (satellite[j] === initialStates[index * 6 + j]) {
        marks[index * 6 + j].add(i);
      }
    }
  });
}

const markDistances = marks.map(
  set => Array.from(set).map((mark, i) => mark - (i ? marks[i - 1] : 0))
);
console.log([ ...new Set(markDistances.map(getPeriod)) ].join(' '));

I admit that I actually did not compute the least common multiple. That problem wasn't interesting and I just used an online calculator to get the final result 😂

As usual, text, complete solutions and input are on my repo.

Tomorrow... IntCodes?

 

Part 1 was...not easy, exactly, but straightforward. Apply some logic, iterate 1000 times, cool.

Part 2 took me the rest of the day to work out, and the key insight turned out to be 2-pronged:

  1. looking for a single satellite to repeat itself is probably faster than looking for all four to repeat at the same time. this turned out to be the wrong approach, but the idea of breaking it down into parts and then looking for a multiple turned out to be the right path...
  2. satellite motion in a given direction is totally independent of the other directions, meaning that we can look for the four satellites to repeat themselves in just one axis, and they will have a consistent period of oscillation on that single axis. We can repeat on the other 2 axes to find 3 time periods and then the moment the satellites all find themselves at the starting location is the least common multiple of the 3 periods. I confess that this had me stumped for a looong time, and I went looking for hints on reddit before something jogged my brain.

Anyways, ruby code for part 2:

#!/usr/bin/env ruby

class Moon
    attr_accessor :pos
    attr_accessor :v
    def initialize(pos)
        @pos = Vector3D.new(pos)
        @v = Vector3D.new([0,0,0])
    end

    def apply_gravity(other_moon)
        dx = sign(@pos.x - other_moon.pos.x)
        dy = sign(@pos.y - other_moon.pos.y)
        dz = sign(@pos.z - other_moon.pos.z)

        @v.x -= dx
        @v.y -= dy
        @v.z -= dz

        other_moon.v.x += dx
        other_moon.v.y += dy
        other_moon.v.z += dz
    end

    def move()
        @pos.x += @v.x
        @pos.y += @v.y
        @pos.z += @v.z
    end

    def potential_energy()
        return @pos.x.abs + @pos.y.abs + @pos.z.abs
    end

    def kinetic_energy()
        return @v.x.abs + @v.y.abs + @v.z.abs
    end

    def energy()
        return potential_energy() * kinetic_energy()
    end

    def to_s()
        return "#{@pos}|#{@v}"
    end

    def clone()
        return Moon.new([@pos.x,@pos.y,@pos.z])
    end
end

class Vector3D
    attr_accessor :x
    attr_accessor :y
    attr_accessor :z
    def initialize(coords)
        @x = coords[0]
        @y = coords[1]
        @z = coords[2]
    end
    def to_s()
        return "#{@x},#{@y},#{@z}"
    end
end

def sign(n)
    return n <=> 0
end

def parse_position(line)
    stripped = line[1..-2] # get rid of <>
    chunks = stripped.split(",")
    nums = []
    chunks.each do |c|
        bits = c.split("=")
        num = bits[1]
        nums.push(num.to_i)
    end
    return nums
end

def step(moons)
    for i in 0..moons.length-1
        m = moons[i]
        for j in i+1..moons.length-1
            other = moons[j]
            m.apply_gravity(other)
        end
    end
    moons.each do |m|
        m.move()
    end
end

def pp(moons)
    moons.each do |m|
        puts "#{m.pos.x},#{m.pos.y},#{m.pos.z} || #{m.v.x},#{m.v.y},#{m.v.z}"
    end
end

def state(moons)
    s = ""
    moons.each do |m|
        s += m.to_s + "."
    end
    return s
end

def find_repeat_state(moons)
    initial_moons = moons.map { |m| m.clone() }
    periods = [nil,nil,nil]
    num_steps = 0
    while true
        num_steps += 1
        step(moons)

        # x
        if periods[0] == nil
            xmatch = true
            4.times do |idx|
                current_moon = moons[idx]
                initial_state = initial_moons[idx]
                if !(current_moon.pos.x == initial_state.pos.x && current_moon.v.x == initial_state.v.x)
                    xmatch = false
                end
            end
            if xmatch
                periods[0] = num_steps
            end
        end

        # y
        if periods[1] == nil
            ymatch = true
            4.times do |idx|
                current_moon = moons[idx]
                initial_state = initial_moons[idx]
                if !(current_moon.pos.y == initial_state.pos.y && current_moon.v.y == initial_state.v.y)
                    ymatch = false
                end
            end

            if ymatch
                periods[1] = num_steps
            end
        end

        # z
        if periods[2] == nil
            zmatch = true
            4.times do |idx|
                current_moon = moons[idx]
                initial_state = initial_moons[idx]
                if !(current_moon.pos.z == initial_state.pos.z && current_moon.v.z == initial_state.v.z)
                    zmatch = false
                end
            end
            if zmatch
                periods[2] = num_steps
            end
        end

        if !periods.include?(nil)
            break
        end
    end
    return periods.reduce(1, :lcm)
end

if __FILE__ == $0
    moons = []
    File.open(ARGV[0], "r") do |file_handle|
        file_handle.each_line do |line|
            pos = parse_position(line.chomp)
            moons.push(Moon.new(pos))
        end
    end
    puts find_repeat_state(moons)
end
 

Part 1 in "modern" Python complete with tests. I need to think a bit about part 2. Can it be done with some form of integration?

from dataclasses import dataclass, field
from typing import List, Generator, TypeVar
import pytest

@dataclass(frozen=True)
class Vector:
  x: int = 0
  y: int = 0
  z: int = 0

  def magnitude(self):
    return abs(self.x) + abs(self.y) + abs(self.z)

  def __add__(self, other):
    return Vector(self.x+other.x, self.y+other.y, self.z+other.z)


@dataclass(frozen=True)
class Moon:
  pos: Vector
  velocity: Vector = field(default_factory=Vector)


  def energy(self):
    return self.pos.magnitude() * self.velocity.magnitude()


def load(text):
  """
  Load multi-line `text` into a collection of Moons
  """
  def vector(line):
    parts = line.strip("<>").split(",")
    return Vector(*[int(p.strip()[2:]) for p in parts])

  return [Moon(pos=vector(line)) for line in text.strip().splitlines()]


def simulate(moons: List[Moon]) -> List[Moon]:
  """
  Simulate the motion of `moons`, returning a new collection of Moons
  """
  def compare_axis(x, y):
    if x < y: return 1
    elif x == y: return 0
    else: return -1

  def gravity_vector(a: Vector, b: Vector) -> Vector:
    return Vector(
      x = compare_axis(a.x, b.x),
      y = compare_axis(a.y, b.y),
      z = compare_axis(a.z, b.z)
    )

  def simulate_moon(m: Moon) -> Moon:
    gravity = Vector()
    for n in moons:
      gravity += gravity_vector(m.pos, n.pos)
    velocity = m.velocity + gravity
    return Moon(pos=m.pos + velocity, velocity=velocity)

  return [simulate_moon(m) for m in moons]


def simulate_seq(moons: List[Moon]) -> Generator[List[Moon], None, None]:
  """
  Generate a sequence of simulated states for `moons`
  """
  m = moons
  while True:
    m = simulate(m)
    yield m


T = TypeVar("T")
def after(n: int, seq: Generator[T, None, None]) -> T:
  """
  Get the `n`th value from `seq`
  """
  for x in range(n):
    r = next(seq)
  return r


def total_energy(moons: List[Moon]) -> int:
  return sum(m.energy() for m in moons)


def test_load():
  """
  Verify parsing text into Moons
  """
  r = load("""<x=-1, y=0, z=2>
<x=2, y=-10, z=-7>
<x=4, y=-8, z=8>
<x=3, y=5, z=-1>""")
  assert len(r) == 4
  assert r[0] == Moon(pos=Vector(-1, 0, 2))
  assert r[1] == Moon(pos=Vector(2,-10,-7))
  assert r[2] == Moon(pos=Vector(4,-8,8))
  assert r[3] == Moon(pos=Vector(3,5,-1))


EXAMPLE_MOONS_1 = [
  Moon(pos=Vector(-1,  0, 2)),
  Moon(pos=Vector( 2,-10,-7)),
  Moon(pos=Vector( 4, -8, 8)),
  Moon(pos=Vector( 3,  5,-1))
]

EXAMPLE_MOONS_2 = [
  Moon(pos=Vector(-8,-10,  0)),
  Moon(pos=Vector( 5,  5, 10)),
  Moon(pos=Vector( 2, -7,  3)),
  Moon(pos=Vector( 9, -8, -3))
]

@pytest.mark.parametrize("moons,steps,expect", [
  (EXAMPLE_MOONS_1, 1, [
    Moon(pos=Vector(2,-1, 1), velocity=Vector( 3,-1,-1)),
    Moon(pos=Vector(3,-7,-4), velocity=Vector( 1, 3, 3)),
    Moon(pos=Vector(1,-7, 5), velocity=Vector(-3, 1,-3)),
    Moon(pos=Vector(2, 2, 0), velocity=Vector(-1,-3, 1))
  ]),
  (EXAMPLE_MOONS_1, 2, [
    Moon(pos=Vector(5,-3,-1), velocity=Vector( 3,-2,-2)),
    Moon(pos=Vector(1,-2, 2), velocity=Vector(-2, 5, 6)),
    Moon(pos=Vector(1,-4,-1), velocity=Vector( 0, 3,-6)),
    Moon(pos=Vector(1,-4, 2), velocity=Vector(-1,-6, 2))
  ]),
  (EXAMPLE_MOONS_1, 10, [
    Moon(pos=Vector(2, 1,-3), velocity=Vector(-3,-2, 1)),
    Moon(pos=Vector(1,-8, 0), velocity=Vector(-1, 1, 3)),
    Moon(pos=Vector(3,-6, 1), velocity=Vector( 3, 2,-3)),
    Moon(pos=Vector(2, 0, 4), velocity=Vector( 1,-1,-1))
  ])
])
def test_simulate_one_step(moons, steps, expect):
  """
  Verify moon simulation
  """
  assert after(steps, simulate_seq(moons)) == expect



@pytest.mark.parametrize("moons,steps,energy", [
  (EXAMPLE_MOONS_1, 10, 179),
  (EXAMPLE_MOONS_2, 100, 1940)
])
def test_energy(moons, steps, energy):
  final = after(steps, simulate_seq(moons))
  assert total_energy(final) == energy


def part1(moons):
  final = after(1000, simulate_seq(moons))
  print(f"Part 1 : {total_energy(final)}")


if __name__ == "__main__":
  with open("input.txt", "rt") as f:
    moons = load(f.read())

  part1(moons)
 

Quick and dirty part one in swift. Need more time for part 2.

import Cocoa

let input = """
<x=17, y=5, z=1>
<x=-2, y=-8, z=8>
<x=7, y=-6, z=14>
<x=1, y=-10, z=4>
""".components(separatedBy: "\n")

let pattern = "<x=(.+), y=(.+), z=(.+)>"
let regex = try? NSRegularExpression(pattern: pattern, options: [])

var vectors = input.map { line -> [Int] in
    if let match = regex?.firstMatch(in: line, options: [], range: NSRange.init(location: 0, length: line.utf8.count)) {
        if let x = Range(match.range(at: 1), in: line),
            let y = Range(match.range(at: 2), in: line),
            let z = Range(match.range(at: 3), in: line) {
            return [Int(line[x])!, Int(line[y])!, Int(line[z])!]
        }
    }
    return []
}

print(vectors)


func partOne() -> Int {
    var vel: [[Int]] = [[0,0,0],[0,0,0],[0,0,0],[0,0,0]]
    for _ in 0 ... 999 {
        for i in 0 ... vectors.count - 1 {
            for j in 0 ... vectors.count - 1  {
                for k in 0 ... vectors[i].count - 1 {
                    //print("\(i) \(j) \(k)")
                    if vectors[i][k] < vectors[j][k] {
                        vel[i][k] += 1
                    }
                    else if vectors[i][k] > vectors[j][k] {
                        vel[i][k] -= 1
                    }
                }
            }
        }
        for i in 0 ... vectors.count - 1 {
            for k in 0 ... vectors[i].count - 1 {
                vectors[i][k] += vel[i][k]
            }
        }
    }

    var p1 = 0
    for i in 0 ... vectors.count - 1  {
        var pot = 0
        var kin = 0
        for k in 0 ... vectors[i].count - 1 {
            pot += abs(vectors[i][k])
            kin += abs(vel[i][k])
        }
        p1 += pot*kin
    }

    print(vectors)
    print(vel)
    print(p1)
    return p1
}

print(partOne())

 

Forgot to post day 12 part two solution - It Took long time and don't know any leads so I checked the hit from r site and it was easy ride from that.

Swift code can be found here github.com/rizwankce/AdventOfCode/...

 

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
      states.add(s)

  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
 

Part 1. Straightforward.

Part 2 is... in progress. I'm trying to save every spare bit of heap space I can. :( I keep stalling out around 10 million.

import arrow.optics.optics
import java.nio.file.Files
import java.nio.file.Paths
import java.security.MessageDigest
import java.util.*
import kotlin.math.abs

val ZERO_3D = Point3d(0, 0, 0)

@optics
data class Point3d(var x: Int, var y: Int, var z: Int) {
    override fun toString() = "$x,$y,$z"

    companion object
}
typealias Velocity3d = Point3d

fun Point3d.sum() = abs(x) + abs(y) + abs(z)

@optics
data class Moon(
    val name: String = UUID.randomUUID().toString(),
    var location: Point3d,
    val velocity: Velocity3d = ZERO_3D.copy()
) {
    override fun toString() = "$location|$velocity"

    companion object
}


val Moon.potential: Int get() = location.sum()
val Moon.kinetic: Int get() = velocity.sum()
val Moon.total: Int get() = potential * kinetic

object Day12 {
    private const val FILENAME = "src/main/resources/day12.txt"
    val fileData = Files.readAllLines(Paths.get(FILENAME))
}

fun Int.gravity1d(other: Int): Int {
//    println("gravity: $this, $other")
    return when {
        this > other -> -1
        this < other -> 1
        else -> 0
    }
}


@ExperimentalStdlibApi
fun main() {
    val moons = arrayOf(
        Moon(location = Point3d(-16, -1, -12)),
        Moon(location = Point3d(0, -4, -17)),
        Moon(location = Point3d(-11, 11, 0)),
        Moon(location = Point3d(2, 2, -6))
    )
    val testMoons = arrayOf(
        Moon(location = Point3d(x = -1, y = 0, z = 2)),
        Moon(location = Point3d(x = 2, y = -10, z = -7)),
        Moon(location = Point3d(x = 4, y = -8, z = 8)),
        Moon(location = Point3d(x = 3, y = 5, z = -1))
    )
    val testMoons2 = arrayOf(
        Moon(location = Point3d(-8, -10, 0)),
        Moon(location = Point3d(5, 5, 10)),
        Moon(location = Point3d(2, -7, 3)),
        Moon(location = Point3d(9, -8, -3))
    )

    val newMoons = moons.stepForever()
    println(newMoons.first)
    println(newMoons.second.first)
    println(newMoons.second.second.joinToString("\n"))
}

private tailrec fun Array<Moon>.step(times: Int = 1): Array<Moon> {
    return when (times) {
        0 -> this
        else -> {
            indices.forEach { a ->
                indices.filterNot { b -> a == b }
                    .forEach {
                        this[a].velocity.x += this[a].location.x.gravity1d(this[it].location.x)
                        this[a].velocity.y += this[a].location.y.gravity1d(this[it].location.y)
                        this[a].velocity.z += this[a].location.z.gravity1d(this[it].location.z)
                    }
            }
            indices.forEach {
                this[it].location += this[it].velocity
            }
            println("$times)\n\t${this.joinToString("\n\t")}")
            println("\t${this.sumBy { it.total }}")
            step(times - 1)
        }
    }
}

fun String.toMD5(): ByteArray {
    return MessageDigest.getInstance("MD5").digest(toByteArray())
}

val base64 = Base64.getEncoder()

@ExperimentalStdlibApi
private tailrec fun Array<Moon>.stepForever(
    step: Int = 0,
    seen: MutableSet<String> = mutableSetOf()
): Pair<Int, Pair<Int, Array<Moon>>> {


    val blob = base64.encodeToString(this.contentToString().toByteArray())
    return when (blob) {
        in seen -> step to (seen.indexOf(blob) to this)
        else -> {
            seen.add(blob)
            indices.forEach { a ->
                indices.filterNot { b -> a == b }
                    .forEach {
                        this[a].velocity.x += this[a].location.x.gravity1d(this[it].location.x)
                        this[a].velocity.y += this[a].location.y.gravity1d(this[it].location.y)
                        this[a].velocity.z += this[a].location.z.gravity1d(this[it].location.z)
                    }
            }
            indices.forEach {
                this[it].location += this[it].velocity
            }
            if (step % 1000000 == 0) {
                println("$step - ${this.contentToString()}")
            }
            stepForever(step + 1, seen)
        }
    }
}

private operator fun Point3d.plus(other: Point3d) = this.apply {
    x += other.x
    y += other.y
    z += other.z
}

 

Ugh! Part 2 was also straightforward. But only once you intuited (were hinted) that each dimension was independent. Definitely finding a way to cheat was the way to go!

import arrow.optics.optics
import java.math.BigInteger
import java.nio.file.Files
import java.nio.file.Paths
import java.util.*
import kotlin.math.abs

val ZERO_3D = Point3d(0, 0, 0)

@optics
data class Point3d(val x: Int, val y: Int, val z: Int) {
    override fun toString() = "<x=$x,y=$y,z=$z>"

    companion object
}
typealias Velocity3d = Point3d

private fun Point3d.asMoonLocation() = Moon(location = this)

typealias PointVel = Array<Int>

fun pv(p: Int): PointVel = arrayOf(p, 0)
var PointVel.point
    get() = this[0]
    set(value) {
        this[0] = value
    }
var PointVel.velocity
    get() = this[1]
    set(value) {
        this[1] = value
    }


fun Point3d.sum() = abs(x) + abs(y) + abs(z)

@optics
data class Moon(
    val location: Point3d,
    val velocity: Velocity3d = ZERO_3D.copy()
) {
    override fun toString() = "$location, $velocity"

    companion object
}


val Moon.potential: Int get() = location.sum()
val Moon.kinetic: Int get() = velocity.sum()
val Moon.total: Int get() = potential * kinetic

object Day12 {
    private const val FILENAME = "src/main/resources/day12.txt"
    private val fileData = Files.readAllLines(Paths.get(FILENAME))

    fun part1(): Int {
        return moons.step(1000).sumBy(Moon::total)
    }

    fun part2(): BigInteger {
        return lcm(
            moons.map { pv(it.location.x) }.findLoop(),
            lcm(
                moons.map { pv(it.location.y) }.findLoop(),
                moons.map { pv(it.location.z) }.findLoop()
            )
        )
    }

    private val moons = fileData.asSequence()
        .map("""<x=(-?\d+), y=(-?\d+), z=(-?\d+)>""".toRegex()::matchEntire)
        .map { o ->
            Point3d(o!!.groupValues[1].toInt(), o.groupValues[2].toInt(), o.groupValues[3].toInt())
        }.map(Point3d::asMoonLocation).toList()

}


fun Int.gravity1d(other: Int): Int {
    return when {
        this > other -> -1
        this < other -> 1
        else -> 0
    }
}


tailrec fun Array<PointVel>.stepForeverX(
    step: Int = 0,
    seen: MutableMap<String, MutableList<Int>> = TreeMap(),
    max: Int = 1000000
): MutableMap<String, MutableList<Int>> {
    val blob = this.contentDeepToString()
    if (blob in seen) {
        seen[blob]!!.add(step)
    } else {
        seen[blob] = mutableListOf(step)
    }
    when {
        (step < max) -> {
            indices.forEach { a ->
                indices.filterNot { b -> a == b }
                    .forEach {
                        this[a].velocity += this[a].point.gravity1d(this[it].point)
                    }
            }
            indices.forEach {
                this[it].point += this[it].velocity
            }
            return this.stepForeverX(step + 1, seen)
        }
        else -> return seen
    }
}


private tailrec fun List<Moon>.step(times: Int = 1): List<Moon> {
    return when (times) {
        0 -> this
        else -> {
            indices.map { a ->
                this[a].copy(velocity =
                this[a].velocity +
                        indices.filterNot { b -> a == b }.fold(ZERO_3D) { acc, it ->
                            acc + Velocity3d(
                                x = this[a].location.x.gravity1d(this[it].location.x),
                                y = this[a].location.y.gravity1d(this[it].location.y),
                                z = this[a].location.z.gravity1d(this[it].location.z)
                            )

                        })
            }.map {
                it.copy(location = it.location + it.velocity)
            }.step(times - 1)
        }
    }
}

private operator fun Point3d.plus(other: Point3d) = this.copy(x = x + other.x, y = y + other.y, z = z + other.z)

fun main() {
    println(Day12.part1())
    println(Day12.part2())
}

private fun List<PointVel>.findLoop() =
    toTypedArray().stepForeverX().asSequence().filter { it.value.size > 1 }
        .flatMap { result ->
            result.value.asSequence().windowed(2).map { (a, b) -> b - a }.toSet().asSequence()
                .map { it to result.value.first() }
        }.groupBy { it.first }.mapValues { it.value.map { v -> v.second }.toSortedSet() }.asSequence()
        .sortedBy { it.key }.first().key

tailrec fun gcd(n1: BigInteger, n2: BigInteger): BigInteger {
    require(n1 > BigInteger.ZERO || n2 > BigInteger.ZERO) { "a or b is less than 1 ($n1,$n2)" }
    return when (val remainder: BigInteger = n1 % n2) {
        BigInteger.ZERO -> n2
        else -> gcd(n2, remainder)
    }
}

fun lcm(n1: BigInteger, n2: BigInteger) = (n1 * n2) / gcd(n1, n2)

fun lcm(n1: Int, n2: Int): BigInteger = lcm(n1.toBigInteger(), n2.toBigInteger())

fun lcm(n1: Int, n2: BigInteger): BigInteger = lcm(n1.toBigInteger(), n2)

code of conduct - report abuse