DEV Community

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

Collapse
 
jbristow profile image
Jon Bristow • Edited

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
}

Collapse
 
jbristow profile image
Jon Bristow

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)