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

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));

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];
    }
  }
}

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(' '));

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

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())

#!/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

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)

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
}