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 with the police, we are more safety minded than usual. It's bad enough to be driving while distracted by giant red dots, but Jupiter's moons are swirling about willy-nilly. We need to get tracking!
Part 1 has us simulating four moons as they pull on each other with gravity. Somehow, I don't think that this is how moons normally orbit Jupiter, but whatever!
Part 2 is all about optimization. We need to simulate until it loops! This is a really big number, so we're going to need to cheat to win.
Ongoing Meta
Dev.to List of Leaderboards
-
120635-5c140b9a
- provided by Linda Thompson
If you were part of Ryan Palo's leaderboard last year, you're still a member of that!
If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)
I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.
There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.
Neat Statistics
I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?
Languages Seen On Day 09
Under construction
Top comments (9)
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:
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:
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:
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?
Got part 2 in the end! The intuition that each axis is independent came to me while I was away from the keyboard!
Quick and dirty part one in swift. Need more time for part 2.
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/...
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:
Anyways, ruby code for part 2:
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?
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.
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!
In the progress of part 2. Do you notice some calculation?
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"
}
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"
}
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))
)
}
private tailrec fun Array.step(times: Int = 1): Array {
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.stepForever(
step: Int = 0,
seen: MutableSet = mutableSetOf()
): Pair>> {
}
private operator fun Point3d.plus(other: Point3d) = this.apply {
x += other.x
y += other.y
z += other.z
}
Code is fantastic. Usually, I use lcm-calculator.com for LCM Problems. You will love it!