require_relative 'util'
# --- Day 20: Particle Swarm ---
# Suddenly, the GPU contacts you, asking for help. Someone has asked
# it to simulate too many particles, and it won't be able to finish
# them all in time to render the next frame at this rate.
# It transmits to you a buffer (your puzzle input) listing each
# particle in order (starting with particle 0, then particle 1,
# particle 2, and so on). For each particle, it provides the X, Y, and
# Z coordinates for the particle's position (p), velocity (v), and
# acceleration (a), each in the format .
# Each tick, all particles are updated simultaneously. A particle's
# properties are updated in the following order:
# - Increase the X velocity by the X acceleration.
# - Increase the Y velocity by the Y acceleration.
# - Increase the Z velocity by the Z acceleration.
# - Increase the X position by the X velocity.
# - Increase the Y position by the Y velocity.
# - Increase the Z position by the Z velocity.
# Because of seemingly tenuous rationale involving z-buffering, the
# GPU would like to know which particle will stay closest to position
# <0,0,0> in the long term. Measure this using the Manhattan distance,
# which in this situation is simply the sum of the absolute values of
# a particle's X, Y, and Z position.
# For example, suppose you are only given two particles, both of which
# stay entirely on the X-axis (for simplicity). Drawing the current
# states of particles 0 and 1 (in that order) with an adjacent a
# number line and diagram of current X positions (marked in
# parenthesis), the following would take place:
# p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4
# p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0> (0)(1)
# p=< 4,0,0>, v=< 1,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4
# p=< 2,0,0>, v=<-2,0,0>, a=<-2,0,0> (1) (0)
# p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4
# p=<-2,0,0>, v=<-4,0,0>, a=<-2,0,0> (1) (0)
# p=< 3,0,0>, v=<-1,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4
# p=<-8,0,0>, v=<-6,0,0>, a=<-2,0,0> (0)
# At this point, particle 1 will never be closer to <0,0,0> than
# particle 0, and so, in the long run, particle 0 will stay closest.
# Which particle will stay closest to position <0,0,0> in the long
# term?
class Coordinate
attr_accessor :x, :y, :z
def initialize(x, y, z)
@x = x
@y = y
@z = z
end
def to_a
[@x, @y, @z]
end
end
class Particle
attr_accessor :p, :v, :a
def initialize(p, v, a)
@p = p
@v = v
@a = a
end
def self.from(input)
re = /[pva]=<(-?\d+),(-?\d+),(-?\d+)>/
parts = input.split(', ').map { |p| p[re] && [$1.to_i, $2.to_i, $3.to_i] }
coordinates = parts.map { |part| Coordinate.new(*part) }
Particle.new(*coordinates)
end
def distance
@p.x.abs + @p.y.abs + @p.z.abs
end
def ==(other)
p.to_a == other.p.to_a
end
alias eql? ==
def hash
@p.to_a.hash
end
end
class ParticleSystem
attr_reader :particles
def initialize(input)
@particles = input.split("\n").map { |line| Particle.from(line) }
end
def cycle
@particles.each do |particle|
particle.v.x += particle.a.x
particle.v.y += particle.a.y
particle.v.z += particle.a.z
particle.p.x += particle.v.x
particle.p.y += particle.v.y
particle.p.z += particle.v.z
end
end
def closest
particle = @particles.min_by(&:distance)
@particles.find_index(particle)
end
end
test_input = 'p=<3,0,0>, v=<2,0,0>, a=<-1,0,0>
p=<4,0,0>, v=<0,0,0>, a=<-2,0,0>'
input = File.open('20.txt') { |f| f.read.chomp }
def easy(input)
system = ParticleSystem.new(input)
1000.times { system.cycle }
system.closest
end
assert(easy(test_input) == 0)
puts "easy(input): #{easy(input)}"
# --- Part Two ---
# To simplify the problem further, the GPU would like to remove any
# particles that collide. Particles collide if their positions ever
# exactly match. Because particles are updated simultaneously, more
# than two particles can collide at the same time and place. Once
# particles collide, they are removed and cannot collide with anything
# else after that tick.
# For example:
# p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0>
# p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3
# p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0> (0) (1) (2) (3)
# p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0>
# p=<-3,0,0>, v=< 3,0,0>, a=< 0,0,0>
# p=<-2,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3
# p=<-1,0,0>, v=< 1,0,0>, a=< 0,0,0> (0)(1)(2) (3)
# p=< 2,0,0>, v=<-1,0,0>, a=< 0,0,0>
# p=< 0,0,0>, v=< 3,0,0>, a=< 0,0,0>
# p=< 0,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3
# p=< 0,0,0>, v=< 1,0,0>, a=< 0,0,0> X (3)
# p=< 1,0,0>, v=<-1,0,0>, a=< 0,0,0>
# ------destroyed by collision------
# ------destroyed by collision------ -6 -5 -4 -3 -2 -1 0 1 2 3
# ------destroyed by collision------ (3)
# p=< 0,0,0>, v=<-1,0,0>, a=< 0,0,0>
# In this example, particles 0, 1, and 2 are simultaneously destroyed
# at the time and place marked X. On the next tick, particle 3 passes
# through unharmed.
# How many particles are left after all collisions are resolved?
class OptimizedParticleSystem < ParticleSystem
def collisions
seen = Hash.new { |h, k| h[k] = 0 }
dups = []
@particles.each { |particle| seen[particle] += 1 }
seen.each { |k, v| dups << k if v > 1 }
dups
end
def cycle
super
collisions.each { |p| @particles.delete(p) }
end
end
test_input2 = 'p=<-6,0,0>, v=<3,0,0>, a=<0,0,0>
p=<-4,0,0>, v=<2,0,0>, a=<0,0,0>
p=<-2,0,0>, v=<1,0,0>, a=<0,0,0>
p=<3,0,0>, v=<-1,0,0>, a=<0,0,0>'
def hard(input)
system = OptimizedParticleSystem.new(input)
1000.times { system.cycle }
system.particles.length
end
assert(hard(test_input2) == 1)
puts "hard(input): #{hard(input)}"