Sean McLemon | Advent of Code

2017-12-20 - Particle Swarm

(original .ipynb)

import math

puzzle_input_str = open("puzzle_input/day20.txt").read()
test_input_str="""p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>
p=< 4,0,0>, v=< 1,0,0>, a=<-1,0,0>
p=< 2,0,0>, v=<-2,0,0>, a=<-2,0,0>
p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0>
p=<-2,0,0>, v=<-4,0,0>, a=<-2,0,0>
p=< 3,0,0>, v=<-1,0,0>, a=<-1,0,0>
p=<-8,0,0>, v=<-6,0,0>, a=<-2,0,0>"""


def get_triple(triple_str):
    # triple_str is like `x=`
    x_str, y_str, z_str = triple_str[3:][:-1].split(",")
    return [int(x_str), int(y_str), int(z_str)]


def parse_line(line):
    p_str, v_str, a_str = line.split(", ")
    p = get_triple(p_str)
    v = get_triple(v_str)
    a = get_triple(a_str)
    return (p, v, a)


def advance_particle(i, positions, velocities, accelerations, particles_by_position=None):
    if positions[i] is None:
        return
    
    x, y, z = positions[i]
    vx, vy, vz = velocities[i]
    ax, ay, az = accelerations[i]

    vx += ax
    vy += ay
    vz += az

    velocities[i] = (vx, vy, vz)
    positions[i]  = (x+vx, y+vy, z+vz)
    
    if not (particles_by_position is None):
        particles_by_position[(x,y,z)].append(i)

    
def part_one(input_str, iterations=1024):
    raw_particles = [parse_line(line) for line in input_str.split("\n")]
    positions = [p for p, v, a in raw_particles]
    velocities = [v for p, v, a in raw_particles]
    accelerations = [a for p, v, a in raw_particles]
    
    while iterations > 0:
        for i in range(len(positions)):
            advance_particle(i, positions, velocities, accelerations)
        
        iterations -= 1
    
    closest_distance = math.inf
    closest = -1
    
    for i, (x, y, z) in enumerate(positions):
        distance = abs(x) + abs(y) + abs(z)
        if distance < closest_distance:
            closest = i
            closest_distance = distance
    
    return closest
    
    
assert 0 == part_one(test_input_str, 5)
print("part one:", part_one(puzzle_input_str))

part one: 308

from collections import defaultdict

test_input_str_2 = """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 part_two(input_str, iterations=1024):
    raw_particles = [parse_line(line) for line in input_str.split("\n")]
    positions = [p for p, v, a in raw_particles]
    velocities = [v for p, v, a in raw_particles]
    accelerations = [a for p, v, a in raw_particles]
    
    while iterations > 0:
        particles_by_position = defaultdict(list)
        for i in range(len(positions)):                
            advance_particle(i, positions, velocities, accelerations, particles_by_position)
        
        for position in particles_by_position:
            maybe_colliding_particles = particles_by_position[position]
            if len(maybe_colliding_particles) > 1:
                for p in maybe_colliding_particles:
                    positions[p] = None
        
        iterations -= 1
    
    return sum(1 for p in positions if p)
    
assert 1 == part_two(test_input_str_2, 5)
print("part two:", part_two(puzzle_input_str))

part two: 504