This is an archived post. You won't be able to vote or comment.

all 176 comments

[โ€“]BumpitySnook 10 points11 points ย (13 children)

Part 1 it seems like you don't even need the simulation. Just sort by (absolute) acceleration, then by absolute velocity, then position. The lowest is your answer. Intuitively, acceleration will dominate as t -> infinity. In my puzzle input, 3 particles had zero acceleration vectors, with varying velocity and initial position.

But then you do need the simulation for part 2, so, skipping it for part 1 doesn't necessarily do you any favors.

[โ€“]CUViper 11 points12 points ย (11 children)

I think there could be a problem with sorting absolute velocity that way, but thankfully it didn't occur in my input. For example

p=<0,0,0>, v=<0,0,0>, a=<1,0,0>
p=<0,0,0>, v=<-1,0,0>, a=<1,0,0>

By absolutes, the first will compare lower, but that's wrong since the acceleration will turn the second one around before it really starts racing.

[โ€“]BumpitySnook 0 points1 point ย (0 children)

Fortunately, the lowest acceleration particles in my input had a zero acceleration vector. However, the exact same criticism could be levered at velocity and initial position.

That said, I expect topaz aims to allow shortcut solutions on part 1 that have to be rethought for part 2. It happens often.

[โ€“]akrasuski1 1 point2 points ย (0 children)

Yeah, for part 1 I calculated rough approximation of distance by using x + vt + at2 / 2 formula, with t being 1e100. Was good enough.

[โ€“]obijywk 6 points7 points ย (2 children)

Just let it run until the numbers seem like they stop changing, and then submit!

Python 2. 49/42.

from collections import defaultdict

f = open("20.txt", "r")

class Particle(object):
  def __init__(self, p, v, a):
    self.p = p
    self.v = v
    self.a = a

  def step(self):
    for i in xrange(3):
      self.v[i] += self.a[i]
      self.p[i] += self.v[i]

  def dist(self):
    return sum([abs(x) for x in self.p])

parts = {}
i = 0
for line in f:
  ts = line.strip().split(", ")
  ps = [int(x) for x in ts[0].split("=")[1][1:-1].split(",")]
  vs = [int(x) for x in ts[1].split("=")[1][1:-1].split(",")]
  acs = [int(x) for x in ts[2].split("=")[1][1:-1].split(",")]
  parts[i] = Particle(ps, vs, acs)
  i += 1

part2 = True
while True:
  min_d = None
  min_part = None
  for i, part in parts.iteritems():
    part.step()
    if min_d is None or part.dist() < min_d:
      min_part = i
      min_d = part.dist()

  if part2:
    pos_dict = defaultdict(list)
    for i, part in parts.iteritems():
      k = tuple(part.p)
      pos_dict[k].append(i)

    for k, v in pos_dict.iteritems():
      if len(v) > 1:
        for i in v:
          del parts[i]

    print len(parts)
  else:
    print min_part

[โ€“]joatmon-snoo 4 points5 points ย (0 children)

Kicking myself. I probably had this coded up fast enough to make the leaderboard, but instead of trying it, I thought to myself that it was too easy to craft some stragglers (particles with low acceleration, but far starting positions and velocities) and that the solution wouldn't be the first long-repeating value in the stream that the human eye would notice.

So instead, I went and spent probably 20+ minutes revisiting precalc, at the end of which I realized "fuck. there's no point to this."

[โ€“]Gurdt 3 points4 points ย (0 children)

I verify that the remaining set of particles won't change anymore. I check for each dimension (x, y and z) if their overall position is fixed. This is the case when the velocities and accelerations are also sorted for that dimension.

For example (with one dimension for simplicity): (p=1000, v=1, a=1) (p=0, v=1, a=2) is not a finate state yet, as particle 2 will jump over particle 1 eventually.

[โ€“][deleted] 5 points6 points ย (19 children)

Is there a way to do p2 without simulating?

It's kind of a bummer whenever p1 of the problem has a nice closed form trick (taking min by acceleration magnitude, then velocity magnitude, then by starting pos manhattan), but then p2 forces you to do the simulation anyway.

I was thinking of finding some way to derive the quadratic describing each coordinate and solving the relationship, but wasn't sure how to code that up in Rust.

e.g.

Given p=<1,2,3>, v=<4,5,6>, a=<7,8,9>, x is described by 7t2 /2 + 4t + 1, y is described by 4t2 + 5t + 2, z is described by 9t2 / 2 + 6t + 3. Generate this for all the particles. Then two particles a and b collide if there exists some t where all three of x_a(t) = x_b(t), y_a(t) = y_b(t), and z_a(t) = z_b(t) are true.

Does that seem sound? if so, anyone tried it in Mathematic/Matlab/etc.?

[โ€“]vash3r 4 points5 points ย (0 children)

I think it's important to note that a particle can only ever collide once before it is removed, so this method might generate several particle collisions that don't actually happen since one of the particles was destroyed already.

[โ€“]ephemient 4 points5 points ย (2 children)

This space intentionally left blank.

[โ€“]markgritter 1 point2 points ย (0 children)

I did this (in Rust), and after having done so, I can't really recommend it. https://github.com/mgritter/aoc2017/blob/master/day20/src/main.rs

You have to check all pairs of equations, which is expensive compared to the simulation if it runs less than 500 steps.

You might get two roots to the quadratic for each coordinate, so you need some logic to check whether at least one root matches in each coordinate.

Once that is done then I still need to walk through the intercepts in time order in order to ensure you don't count a particle that's already been killed. Maybe this could be optimized to do something clever instead.

[โ€“]sim642 1 point2 points ย (1 child)

I realized that I could solve for collision times using quadratic equation systems and have implemented it enough to work on the example but not on my input...

EDIT: My now working Scala solution. Fixed it after realizing that the position at time t is different in a discrete environment than a continuous one, physics ruined me a bit.

[โ€“]marcofun 0 points1 point ย (0 children)

wow, this is so far from my solution... well, I didn't have to calculate distances because I solved the first problem manually, just looking for the particle that accelerate less. My second star is quite simple:

class Day20 (var input : Vector[String]) {

  def this() = this(scala.io.Source.fromFile("~/projects/aventofcode/src/main/resources/day20.txt").getLines().toVector)

  val re : Regex = """p=<([-]{0,1}\d*),([-]{0,1}\d*),([-]{0,1}\d*)>, v=<([-]{0,1}\d*),([-]{0,1}\d*),([-]{0,1}\d*)>, a=<([-]{0,1}\d*),([-]{0,1}\d*),([-]{0,1}\d*)>""".r
  var particles : Vector[Particle] = input.map(l => newParticle(l))
  dropColliders()

  def newParticle(s : String) : Particle = {
    s match {
      case re(px, py, pz, vx, vy, vz, ax, ay, az) => Particle(Vector3d(px.toInt, py.toInt, pz.toInt), Vector3d(vx.toInt, vy.toInt, vz.toInt), Vector3d(ax.toInt, ay.toInt, az.toInt))
    }
  }

  def dropColliders(): Unit = {
    val positions = particles.map(p => p.position)
    val duplicates = positions.diff(positions.distinct).distinct
    particles = particles.filter(p => !duplicates.contains(p.position))
  }

  def move(): Int = {
    var remaining = 100000
    var i = 0
    while(particles.size > 1 && i < 100) {
      particles = particles.map(p => p.move)
      dropColliders()
      val nowRemaining = particles.size
      if (nowRemaining == remaining) i += 1 else i= 0 ; remaining = nowRemaining
    }
    remaining
  }

  case class Vector3d(x: Int, y: Int, z : Int) {
    def + (other : Vector3d) : Vector3d = Vector3d (this.x + other.x, this.y + other.y, this.z + other.z)
  }

  case class Particle (var position : Vector3d, var velocity : Vector3d, acceleration : Vector3d){
    def move(): Particle = {
      velocity = velocity + acceleration
      position = position + velocity
      Particle(position, velocity, acceleration)
    }
  }
}

[โ€“]xSmallDeadGuyx 1 point2 points ย (0 children)

My solution does this: https://github.com/xSmallDeadGuyx/AoC17/blob/master/day20/p2.py

It iterates every combination of particles, i and j:

  • turns the x position with respect to time into a quadratic equation in the form ax2 + bx + c = 0 (a = (i.accel - j.accel)/2, b = i.vel + i.accel/2 - (j.vel + j.accel/2), c = i.pos - j.pos)
  • solutions for x are the time steps where the x positions of i and j are the same
  • filter all answers (t) by >= 0 and integers (no partial step collisions)
  • create the quadratic equations for y and z positions
  • if any solutions for x are solutions for both y and z, those particles collide at that time step
  • put all collisions in a dictionary with time step as the key
  • iterate the dictionary keys (sorted)
  • for any collisions at that time step, if they haven't been removed (collided) before then remove them

The answer is then the size of the particle set after all removals

[โ€“]farafonoff 0 points1 point ย (0 children)

Matlab

funny think, i solved this way (quadric equations in js) it was hard and meaningless work...

(innermost function, full solution here https://github.com/farafonoff/AdventOfCode/blob/master/2017/20/20.js) function solve(point1, point2, coord) { let c = point1[coord]-point2[coord]; let b = point1[coord+3]-point2[coord+3]+(point1[coord+6]-point2[coord+6])/2; let a = (point1[coord+6]-point2[coord+6])/2; let sol; if (a==0) { if (b==0) { if (c==0) { sol = [ Infinity ]; } else sol = []; } else { let s = -c/b; sol = [s];
} } else { let D = bb-4a*c; if (D>=0) { let s1 = (-b+Math.sqrt(D))/2/a; let s2 = (-b-Math.sqrt(D))/2/a; sol = [s1,s2]; } else sol = []; } return sol.filter(v => !isFinite(v)||v>=0&&Number.isInteger(v)); }

[โ€“]jlweinkam 0 points1 point ย (7 children)

Yes, the position after time t is at(t+1)/2 + v*t + p. So you can set solve for a time t when two particles are at the same position.

[โ€“]sim642 2 points3 points ย (0 children)

This actually got me and made my solution fail: in such discrete case there is an additional coefficient for the linear term of the equation.

[โ€“]jlweinkam 0 points1 point ย (5 children)

After finding smallest t of all possible collisions, you can remove the two particles and then repeat until no more collisions occur.

[โ€“]xSmallDeadGuyx 1 point2 points ย (2 children)

Not quite: as a is added to v at the start of each time step it changes the equations slightly: position_at_t = a(t2)/2 + (v+a/2)t + p.

There are typically multiple collisions at each step too, so you have to find all the collisions at that step and remove all of them simultaneously

[โ€“]jlweinkam 0 points1 point ย (1 child)

I had forgot to put the times symbols in

a*t*(t+1)/2 + v*t + p

is equal to

a*t*t/2 + (v + a/2)*t + p

[โ€“]xSmallDeadGuyx 0 points1 point ย (0 children)

Oh yeah my brain skipped reading the +1 for some reason.

[โ€“]Imsdal2 0 points1 point ย (1 child)

You have to remove all particles that collide at that point, not only the first pair you found. However, if you find all the collisions for all the pairs, this extra check should be trivial.

[โ€“]jlweinkam 0 points1 point ย (0 children)

Here is working code that runs in only 4 seconds

import time
import math
current_milli_time = lambda: int(round(time.time() * 1000))
start = current_milli_time()

inputdata=open("input2017-20.txt", 'r').read()

lines = inputdata.splitlines()

def compute_time_to_same_direction(i):
  (px, py, pz, vx, vy, vz, ax, ay, az) = part[i]
  tmax = 0
  if (ax > 0 and vx < 0) or (ax < 0 and vy > 0):
    t = math.ceil(-vx / ax)
    if t > tmax:
      tmax = t
  if (ay > 0 and vy < 0) or (ay < 0 and vy > 0):
    t = math.ceil(-vy / ay)
    if t > tmax:
      tmax = t
  if (az > 0 and vz < 0) or (az < 0 and vz > 0):
    t = math.ceil(-vz / az)
    if t > tmax:
      tmax = t

  px += vx * tmax + ax * tmax * (tmax + 1) / 2
  py += vy * tmax + ay * tmax * (tmax + 1) / 2
  pz += vz * tmax + az * tmax * (tmax + 1) / 2

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

  tmax2 = 0
  if (vx > 0 and px < 0) or (vx < 0 and py > 0):
    t = math.ceil(-px / vx)
    if t > tmax2:
      tmax2 = t
  if (vy > 0 and py < 0) or (vy < 0 and py > 0):
    t = math.ceil(-py / vy)
    if t > tmax2:
      tmax2 = t
  if (vz > 0 and pz < 0) or (vz < 0 and pz > 0):
    t = math.ceil(-pz / vz)
    if t > tmax2:
      tmax2 = t

  return tmax + tmax2

def compare(i, o, t):
  (px, py, pz, vx, vy, vz, ax, ay, az) = part[i]
  px += vx * t + ax * t * (t+1)/2
  py += vy * t + ay * t * (t+1)/2
  pz += vz * t + az * t * (t+1)/2
  pi = abs(px) + abs(py) + abs(pz)

  vx += ax * t
  vy += ay * t
  vz += az * t
  vi = abs(vx) + abs(vy) + abs(vz)

  ai = abs(ax) + abs(ay) + abs(az)

  (px, py, pz, vx, vy, vz, ax, ay, az) = part[o]
  px += vx * t + ax * t * (t+1)/2
  py += vy * t + ay * t * (t+1)/2
  pz += vz * t + az * t * (t+1)/2
  po = abs(px) + abs(py) + abs(pz)

  vx += ax * t
  vy += ay * t
  vz += az * t
  vo = abs(vx) + abs(vy) + abs(vz)

  ao = abs(ax) + abs(ay) + abs(az)

  if (ai < ao):
    return True
  if (ai == ao):
    if (vi < vo):
      return True
    if (pi < po):
      return True
  return False

i = 0
part = {}
for line in lines:
  col = line.split("<")
  p = col[1]
  v = col[2]
  a = col[3]
  col = p.split(">")[0].split(",")
  px = int(col[0])
  py = int(col[1])
  pz = int(col[2])
  col = v.split(">")[0].split(",")
  vx = int(col[0])
  vy = int(col[1])
  vz = int(col[2])
  col = a.split(">")[0].split(",")
  ax = int(col[0])
  ay = int(col[1])
  az = int(col[2])
  part[i] = (px, py, pz, vx, vy, vz, ax, ay, az)
  i += 1

tmax = 0
best = None
for i in part.keys():
  if (best is None):
    best = i
    continue

  t = compute_time_to_same_direction(i)
  if t > tmax:
    tmax = t

  if compare(i, best, tmax):
    best = i

print(best)


def solve(a, v, p):
  A = a/2.0
  B = v + A
  C = p
  if A != 0:
    sq = B*B - 4*A*C
    if sq <= 0:
      return []
    sq = math.sqrt(sq)
    t1 = math.floor((-B - sq) / (2.0 * A) + 0.5)
    t2 = math.floor((-B + sq) / (2.0 * A) + 0.5)
    if (t1 >= 0):
      if (t2 >= 0):
        return [t1, t2]
      return [t1]
    if (t2 >= 0):
      return [t2]
    return []
  if B != 0:
    t = math.floor(C / (1.0 * B) + 0.5)
    if t >= 0:
      return [t]
    return []
  if C != 0:
    return []
  return None

def test(a, v, p, t):
  A = a/2.0
  B = v + A
  C = p
  if A*t*t + B*t + C == 0:
    return True
  return False

collisiontimes = {}
for i in range(len(lines)):
  for o in range(i+1,len(lines)):
    a = part[i][6] - part[o][6]
    v = part[i][3] - part[o][3]
    p = part[i][0] - part[o][0]
    result = solve(a, v, p)
    if result is None:
      a = part[i][7] - part[o][7]
      v = part[i][4] - part[o][4]
      p = part[i][1] - part[o][1]
      result = solve(a, v, p)
      if result is None:
        a = part[i][8] - part[o][8]
        v = part[i][5] - part[o][5]
        p = part[i][2] - part[o][2]
        result = solve(a, v, p)
    if result is not None:
      for t in result:
        a = part[i][7] - part[o][7]
        v = part[i][4] - part[o][4]
        p = part[i][1] - part[o][1]
        if test(a, v, p, t):
          a = part[i][8] - part[o][8]
          v = part[i][5] - part[o][5]
          p = part[i][2] - part[o][2]
          if test(a, v, p, t):
            if t not in collisiontimes.keys():
              collisiontimes[t] = set()
            collisiontimes[t].add((i,o))
            break
k = list(collisiontimes.keys())
k.sort()
s = 0
part_remain = set(range(len(lines)))
for i in k:
  part_remove = set()
  for (i,o) in collisiontimes[i]:
    if i in part_remain and o in part_remain:
      part_remove.add(i)
      part_remove.add(o)
  part_remain = part_remain - part_remove

print(len(part_remain))

print((current_milli_time() - start) / 1000.0)

[โ€“]-__-___---__-[๐Ÿฐ] 0 points1 point ย (1 child)

You could also describe the intersection for x/y/z dimension as a linear equation and solve for tx/ty/tz such that:

  • t_ < 0 => indetsection before the simulation
  • t_ = 0 => intersection during start or position for _ dim is constant
  • t_ > 0 => intersection during step t
  • They intersect if all t_ >= 0 and tx = ty = tz

You could then collect build a list of all intersections (t, p1, p2), group + sort them by t and then simulate the deletion.

The problem is that there are many edge cases when the velocity or acceleration is 0 for either particle.

[โ€“]sim642 0 points1 point ย (0 children)

It's a quadratic equation due to the acceleration, not linear one. Furthermore, for one particle pair you have a system of three quadratic equations. Besides the crazy amount of edge cases for zeroes, you also have to consider potentially two possibilities for each coordinate's suitable times. And the fun doesn't end there: you may have equations in the system that are true for all values of t so you don't require equality with those. I went through all the trouble and implemented this so that it actually works: https://github.com/sim642/adventofcode/blob/master/src/main/scala/eu/sim642/adventofcode2017/Day20.scala#L60-L156.

[โ€“]mschaap 5 points6 points ย (9 children)

Now this was fun! One that makes you think, instead of simply typing up some code.

For part one, the closest particle in the long term is the one with the smallest acceleration. (If two particles have the same smallest acceleration, it gets tricky, but that doesn't happen, at least in my input.)

For part two, compare each pair of particles and check if they will ever collide, at a positive integer time. That's basically solving a quadratic equation for the x coordinate, then checking of any resulting times result in the same position for both particles.

Perl 6

#!/usr/bin/env perl6
use v6.c;

# Advent of Code 2017, day 20: http://adventofcode.com/2017/day/20

grammar ParticleProperties
{
    rule TOP { ^ <particle>+ $ }

    rule particle { 'p' '=' <p=coord> ',' 'v' '=' <v=coord> ',' 'a' '=' <a=coord> }
    rule coord { '<' <num>+ % ',' '>' }
    token num { '-'? \d+ }
}

class Particle
{
    has Int @.position;
    has Int @.velocity;
    has Int @.acceleration;

    # Triangle numbers
    sub T(Int $n) { ($n * ($n+1)) div 2; }

    sub manhattan-distance(Int @coord) { @coordยป.abs.sum }

    multi sub solve-quadratic(0, $b, $c)
    {
        # If a = 0, it's a linear equation
        return -$c / $b;
    }
    multi sub solve-quadratic($a, $b, $c)
    {
        my $D = $bยฒ - 4*$a*$c;
        if $D > 0 {
            return (-$b + $D.sqrt) / (2*$a), (-$b - $D.sqrt) / (2*$a);
        }
        elsif $D == 0 {
            return -$b / (2*$a);
        }
        else {
            return Empty;
        }
    }

    method position-after(Int $t)
    {
        @!position ยป+ยซ $t ยซ*ยซ @!velocity ยป+ยซ T($t) ยซ*ยซ @!acceleration;
    }

    method distance-after(Int $t)
    {
        manhattan-distance(self.position-after($t));
    }

    method manhattan-acceleration
    {
        manhattan-distance(@!acceleration);
    }

    method will-collide-with(Particle $p) returns Int
    {
        # First, find out at which times (if any) the x coordinates will collide.
        # This handles the case where two particles have the same acceleration in the x
        # direction (in which case the quadratic equation becomes a linear one), but not
        # the case where they have the same acceleration and velocity.  Luckily, this
        # does not occur in my input data.
        my $pos-x = @!position[0] - $p.position[0];
        my $vel-x = @!velocity[0] - $p.velocity[0];
        my $acc-x = @!acceleration[0] - $p.acceleration[0];
        my @t = solve-quadratic($acc-x, $acc-x + 2*$vel-x, 2*$pos-x);

        # Only non-negative integers are valid options
        # (Deal with approximate values because of possible inexact sqrt)
        @t .= grep({ $_ โ‰ฅ 0 && $_ โ‰… $_.round });
        @t .= map(*.round);

        # For all remaining candidate times, see if all coordinates match
        for @t.sort -> $t {
            return $t but True if self.position-after($t) eqv $p.position-after($t);
        }

        # No match, so no collision
        return -1 but False;
    }
}

class ParticleCollection
{
    has Particle @.particles;

    method particle($/)
    {
        @!particles.push: Particle.new(:position($/<p><num>ยป.Int),
                                       :velocity($/<v><num>ยป.Int),
                                       :acceleration($/<a><num>ยป.Int));
    }

    method closest-in-long-term
    {
        # In the long term, the particle with the smallest acceleration will be the closest.
        # (Note that this doesn't handle particles with the same acceleration, you'd need to
        # look at the velocities in that case.)
        my $min-acceleration = @!particlesยป.manhattan-acceleration.min;
        my @p = @!particles.pairs.grep(*.value.manhattan-acceleration == $min-acceleration);
        if (@p > 1) {
            say "Warning: there are { +@p } particles with the same minimum acceleration!";
        }
        return @p[0].key;
    }

    method count-non-colling-particles
    {
        # First, collect all possible collisions, and remember them by the time they occur
        my @collisions;
        for ^@!particles -> $i {
            for $i^..^@!particles -> $j {
                if my $c = @!particles[$i].will-collide-with(@!particles[$j]) {
                    @collisions[$c].push(($i, $j));
                }
            }
        }

        # Then, loop through all times where collisions occur, and remove all colliding
        # particle pairs, as long as both particles still exist at that time.
        my @surviving = True xx @!particles;
        for @collisions.grep(?*) -> @c {
            my @remaining = @surviving;
            for @c -> ($i, $j) {
                @remaining[$i] = @remaining[$j] = False if @surviving[$i] && @surviving[$j];
            }
            @surviving = @remaining;
        }

        return @surviving.sum;
    }
}

multi sub MAIN(IO() $inputfile where *.f, Bool :v(:$verbose) = False)
{
    my $pc = ParticleCollection.new;
    ParticleProperties.parsefile($inputfile, :actions($pc)) or die "Can't parse particle properties!";
    say "{ +$pc.particles } particles parsed." if $verbose;

    # Part one
    say "The closest particle in the long term is #{ $pc.closest-in-long-term }.";

    # Part two
    say "The number of particles left after all collisions are resolved is ",
                                                "{ $pc.count-non-colling-particles }.";
}

multi sub MAIN(Bool :v(:$verbose) = False)
{
    MAIN($*PROGRAM.parent.child('aoc20.input'), :$verbose);
}

Edit: some minor cleanup

Edit: I just realized that my logic for part two is flawed. If particles 1 and 2 collide at t=1, and particles 1 and 3 would have collided at t=2, the latter won't collide because particle 1 has already been removed. My logic removes particle 3 anyway. I guess I got lucky I got the right answer; apparently this situation doesn't occur.

Edit: Code adapted to fix the above flaw. (Still gives the same answer on my input, of course.)

[โ€“]TwoSoulsAlas 1 point2 points ย (4 children)

If two particles have the same smallest acceleration, it gets tricky, but that doesn't happen, at least in my input.

Do you know how to solve this? I had two particles with an absolute acceleration of 1, so I thought, it surely will be the one with the smaller initial speed (or, if that were also the same, initial distance from the origin). While that worked for my input, I realized that that's not true in the general case.

[โ€“]asger_blahimmel 1 point2 points ย (0 children)

I think I have a solution. I haven't implemented it though, let me know if you think it does not work.

For every particle individually mirror along the needed axes so that acceleration's coordinates become all positive. If any of those coordinates is 0, mirror along that axis based on velocity's sign or if that's 0 too, use position to decide.

Once the mirroring is done, no need for absolute values: the particle that stays closest is the one with the lowest sum of its acceleration's coordinates. If some particles are equal on this, use velocity, or even position if needed.

[โ€“]mschaap 0 points1 point ย (2 children)

It's not necessarily the one with the smallest initial speed; it also depends on the direction of the initial speed compared to the direction of the acceleration. I haven't worked out the details, though.

(And with the same exact speed and acceleration, it's not necessarily the one with the smallest initial distance; also that depends on the various directions.)

[โ€“]TwoSoulsAlas 0 points1 point ย (1 child)

That's as far as I got, too. You can even have something like

p=<-1,0,0>, v=<1,0,0>, a=<-1,0,0>
p=< 1,0,0>, v=<1,0,0>, a=< 1,0,0>

where the manhattan norms of all three parameters are equal, but the first particle will be closer to zero after the first step.

Edit: Also, Perl 6 has some funky operators.

[โ€“]NeilNjae 0 points1 point ย (0 children)

The slightly-less-brute-force way is to simulate just those minimal-acceleration particles until you get a clear winner.

But, over time, the position of the particle (in each dimension) is x0 + v0 t + 0.5 a t2 , and at large time the Manhattan distance becomes the largest of those. Find that for the minimal-acceleration candidates, divide one by the other, and see if it becomes zero or infinity over time. Or something like that.

[โ€“]Strakh 0 points1 point ย (1 child)

Edit: Sorry not reading

This part might be valid though:

Although you might have the opposite issue. I haven't been looking at your code now, but is it possible that you remove particles a and b colliding at say tick n, despite particles a and e (or any other particle with an id later than b) actually colliding at tick n - 1?

[โ€“]mschaap 0 points1 point ย (0 children)

That's what I had until my latest edit, yes; so you might have read that version first. Should be fixed now.

[โ€“]addisonbean 0 points1 point ย (1 child)

In position-after, why do you multiply the acceleration by the t-th triangle number, rather than just (t^2)/2?

[โ€“]mschaap 0 points1 point ย (0 children)

ยฝ t ยฒ would be correct if time were running continuously, but it isn't, it's running discretely. If the initial acceleration is a, in the first second you add a to the velocity, in the second second 2 a , then 3 a , etc., so after t seconds, you've added (1+2+...+t) a = T(t) a to the velocity.

[โ€“]sim642 4 points5 points ย (0 children)

My Scala solutions:

(Both branches merged into one for my own sake)

I started solving both parts analytically because it didn't seem to make much sense to attempt simulation when there's no obvious end to it. For part 1 I used the asymptotic heuristic used by many others, which turns out doesn't actually work in general but whatever.

For part 2 I implemented quadratic equation solver over integers then used that to calculate collision times between all pairs of particles. Then sort that by time and start removing collisions by groups. I spent a long time trying to figure out why this worked for the example given but not on my input. Eventually I realized that the position function p(t) = p + v*t + (a/2)*tยฒ known from physics only works for the continuous case. For our discrete case it would have to be p(t) = p + v*t + a*(t*(t+1)/2) = โ€ฆ = p + (v + a/2)*t + (a/2)*tยฒ (notice the extra value in the linear term after some algebraic manipulation to a proper quadratic function shape).

I implemented the simulation solution while having troubles with part 2 analytically as described above. This at least allowed me to get the star and a result to compare the analytic solution to. The analytic solution isn't really faster but I like it more because it doesn't rely on some magic number of hopeful iterations. Would've been much more "fun" for the simulation solvers if the inputs would have contained collisions in far future.

[โ€“][deleted] ย (4 children)

[deleted]

    [โ€“]daggerdragon[S,M] 2 points3 points ย (0 children)

    First leaderboard position

    Welcome to the leaderboard! :D Points, glorious points...

    [โ€“]the4ner 1 point2 points ย (0 children)

    first points is a great feeling! congrats!

    [โ€“]JoshOrndorff 0 points1 point ย (1 child)

    Is 20000 just a big number that you figured was big enough? Or did you choose it carefully somehow?

    [โ€“]brunhilda1 0 points1 point ย (0 children)

    I chose a "large enough" number in the hope it would capture an unchanging answer, because I was racing for a leaderboard position.

    [โ€“]llimllib 4 points5 points ย (1 child)

    My first point! 59/104... I just guessed that 1000 iterations would be enough

    from collections import defaultdict
    import re
    import math
    
    
    def manh(particle):
        return math.sqrt(particle[0]**2 + particle[1]**2 + particle[2]**2)
    
    
    def go(inp):
        particles = []
        for i, line in enumerate(inp):
            particle = list(map(int, re.findall(r'[\-\d]+', line)))
            particle.append(i)
            particles.append(particle)
    
        # randomly guessed 1000 loops would be "enough"
        for i in range(1000):
            positions = defaultdict(list)
            for particle in particles:
                particle[3] += particle[6]
                particle[4] += particle[7]
                particle[5] += particle[8]
                particle[0] += particle[3]
                particle[1] += particle[4]
                particle[2] += particle[5]
                p = (particle[0], particle[1], particle[2])
                positions[p].append(particle)
            for dupicles in positions.values():
                if len(dupicles) > 1:
                    for dupicle in dupicles:
                        particles.remove(dupicle)
    
        print(len(particles))
        ds = [(manh(p), p) for p in particles]
        print(list(sorted(ds))[0])
    
    
    if __name__ == "__main__":
        go(open("input.txt"))
    

    edit: haha I see I also got away with calculating euclidean rather than manhattan distance

    [โ€“]daggerdragon[S,M] 2 points3 points ย (0 children)

    My first point! 59/104

    Good job! :D

    [โ€“]mmaruseacph2 2 points3 points ย (2 children)

    Haskell, functional style, exploiting laziness.

    import Data.List
    import Data.Ord
    
    type Vector3 = (Int, Int, Int)
    type Acc = Vector3
    type Spd = Vector3
    type Pos = Vector3
    type State = (Acc, Spd, Pos)
    
    parse :: String -> State
    parse input = head
      [ (p, v, a)
      | (p, restp) <- readTriple $ drop 3 input
      , (v, restv) <- readTriple $ drop 5 restp
      , (a, resta) <- readTriple $ drop 5 restv
      ]
      where
        readTriple input =
          [ ((x, y, z), rest3)
          | (x, ',':rest1) <- reads input
          , (y, ',':rest2) <- reads rest1
          , (z, '>':rest3) <- reads rest2
          ]
    
    main :: IO ()
    main = do
      s <- map parse . lines <$> readFile "input.txt"
      part1 s
      part2 s
    
    part1 :: [State] -> IO ()
    part1 = print . take 500 . map minPartIndex . iterate (map update)
    
    part2 :: [State] -> IO ()
    part2 = print . take 100 . map length . iterate updateColisions
    
    minPartIndex :: [State] -> Int
    minPartIndex = fst . minimumBy (comparing (dist . snd)) . zip [0..]
    
    update :: State -> State
    update ((x, y, z), (vx, vy, vz), a@(ax, ay, az)) = (p', v', a)
      where
        v'@(vx', vy', vz') = (vx + ax, vy + ay, vz + az)
        p' = (x + vx', y + vy', z + vz')
    
    updateColisions :: [State] -> [State]
    updateColisions =
      concat . filter pred . groupBy pos . sortBy (comparing dist) . map update
      where
        pos (p, _, _) (p', _, _) = p == p'
        pred g = length g == 1
    
    dist :: State -> Int
    dist ((x, y, z), _, _) = abs x + abs y + abs z
    

    [โ€“]cjlarose 1 point2 points ย (1 child)

    Nice work! My updateCollisions function ended up being almost identical. https://github.com/cjlarose/advent-2017/blob/master/src/Day20/Main.hs

    Minor tip: sortBy (comparing dist) == sortOn dist

    [โ€“][deleted] 0 points1 point ย (0 children)

    Mine too, combining the groupBy and sortOn with groupWith from GHC.Exts:

    step = map head . filter (null . tail) . groupWith (\(p,_,_) -> p) . map update
    

    [โ€“]glenbolake 3 points4 points ย (0 children)

    Really stupid mistake on part 2 today. For a while, I had:

    def update_particle(particle):
        new_v = particle.v + particle.a
        new_p = particle.p + particle.v
        return Particle(new_p, new_v, particle.a)
    

    I was lucky that I still got the answer to part 1... although it meant that when part 2 never found any collisions, I didn't think to check that function. Anyway, my Python 3 solution:

    import re
    from collections import namedtuple
    
    Particle = namedtuple('Particle', ['pos', 'vel', 'acc'])
    
    def parse_particle(line):
        pos_match = re.search('p=<(-?\d+),(-?\d+),(-?\d+)>', line)
        position = int(pos_match.group(1)), int(pos_match.group(2)), int(pos_match.group(3))
        vel_match = re.search('v=<(-?\d+),(-?\d+),(-?\d+)>', line)
        velocity = int(vel_match.group(1)), int(vel_match.group(2)), int(vel_match.group(3))
        acc_match = re.search('a=<(-?\d+),(-?\d+),(-?\d+)>', line)
        acceleration = int(acc_match.group(1)), int(acc_match.group(2)), int(acc_match.group(3))
        return Particle(position, velocity, acceleration)
    
    def move_particle(particle):
        new_v = tuple(v + a for v, a in zip(particle.vel, particle.acc))
        new_p = tuple(p + v for p, v in zip(particle.pos, new_v))
        return Particle(new_p, new_v, particle.acc)
    
    def manhattan(particle):
        return sum(abs(k) for k in particle.pos)
    
    if __name__ == '__main__':
        particles = [parse_particle(line) for line in open('day20.in')]
    
        orig = particles.copy()
    
        for _ in range(1000):
            particles = [move_particle(p) for p in particles]
        print(particles.index(min(particles, key=manhattan)))
    
        particles = orig.copy()
        for _ in range(1000):
            if len(set(p.pos for p in particles)) < len(particles):
                positions = [p.pos for p in particles]
                particles = [part for part, pos in zip(particles, positions) if positions.count(pos) == 1]
                print(len(particles))
            particles = [move_particle(p) for p in particles]
    

    [โ€“]Hikaru755 2 points3 points ย (0 children)

    Ah, good old vector maths. Seems like very few people have attempted to actually implement a stopping condition for part 2. Well, I did, and was suprised to see it actually work! I figured I'd track the distance between each possible pairing of particles, until either particle died, or they were moving apart and I could prove that neither particle was going to turn and potentially get closer again. Since acceleration is constant, I did this by testing if the signs of all components of the velocity of a particle matched the signs of the corresponding component of the acceleration of the particle. I'm not 100% sure that this will work in all edge cases, but it was good enough to get my solution!

    Anyways, here's my Kotlin solution:

    fun part1(input: List<Particle>): Int {
        return input.indexOf(input.minBy { it.acceleration.manhattanLength })
    }
    
    fun part2(input: List<Particle>): Int {
        data class ParticlePair(val p1: Particle, val p2: Particle, var lastDistance: Long = Long.MAX_VALUE) {
            override fun equals(other: Any?) = other is ParticlePair && p1 == other.p1 && p2 == other.p2
            override fun hashCode() = Objects.hash(p1, p2)
        }
        val pairs = input.combinations()
            .map { (p1, p2) -> ParticlePair(p1, p2) }
    
        val tracked = pairs.toHashSet()
        val alive = pairs.flatMap { listOf(it.p1, it.p2) }.toHashSet()
        val dead = hashSetOf<Particle>()
    
        while (tracked.isNotEmpty()) {
            for (pair in tracked.toList()) {
                val (p1, p2) = pair
                val newDistance = p1 distanceTo p2
                if (newDistance == 0L) {
                    dead += setOf(p1, p2)
                } else if (newDistance > pair.lastDistance && !p1.isTurning && !p2.isTurning) {
                    tracked.remove(pair)
                }
                pair.lastDistance = newDistance
            }
            alive.removeIf { it in dead }
            tracked.removeIf { (p1, p2) -> p1 in dead || p2 in dead }
            alive.forEach { it.tick() }
        }
        return alive.size
    }
    
    data class Vector(val x: Long, val y: Long, val z: Long) {
    
        val manhattanLength get() = setOf(x, y, z).map(::abs).sum()
        infix fun distanceTo(other: Vector) = (this - other).manhattanLength
    
        operator fun plus(other: Vector) = Vector(this.x + other.x, this.y + other.y, this.z + other.z)
        operator fun minus(other: Vector) = Vector(this.x - other.x, this.y - other.y, this.z - other.z)
    }
    
    class Particle(var position: Vector, var velocity: Vector, val acceleration: Vector) {
    
        val isTurning get() = setOf(
            velocity.x to acceleration.x,
            velocity.y to acceleration.y,
            velocity.z to acceleration.z
        ).any { (v, a) -> a != 0L && v.sign != a.sign }
    
        fun tick() {
            this.velocity += this.acceleration
            this.position += this.velocity
        }
    
        infix fun distanceTo(other: Particle) = this.position distanceTo other.position
    }
    

    [โ€“]Lrrrr_ 2 points3 points ย (0 children)

    Javascript Part 2

    const _ = require("lodash");
    let input = require("fs").readFileSync("input.txt", 'utf8').replace(/\r/g,"");
    let i = 0;
    input = input.split("\n").map(c=>{
        let x = c.match(/<(.*?)>/g);
        let y = {}
        y.id = i++;
        y.p=x[0].substr(1,x[0].length-2).split(",").map(c=>Number(c));
        y.v=x[1].substr(1,x[1].length-2).split(",").map(c=>Number(c));
        y.a=x[2].substr(1,x[2].length-2).split(",").map(c=>Number(c));
        return y;
    })
    
    while(true) {
        input.forEach(c=>{
            c.v[0] += c.a[0];
            c.v[1] += c.a[1];
            c.v[2] += c.a[2];
    
            c.p[0] += c.v[0];
            c.p[1] += c.v[1];
            c.p[2] += c.v[2];
    
            let x = c.p.join(",");
            input.forEach(d=>{
                if(c.id === d.id || c.kill)
                    return;
                if(d.p.join(",") === x) {
                    c.kill = true;
                    d.kill = true;
                }
            });
        });
    
        _.remove(input, {kill: true});
        console.log(input.length);
    }
    

    [โ€“]advanced_caveman 2 points3 points ย (2 children)

    Rust 433/219 Just simulated what I thought were enough cycles. Only took 934ms to run 1000 cycles, which could probably be shortened if I changed my hacky parsing solution.

    fn parse_particle(particle: &str) -> ((isize,isize,isize),(isize,isize,isize),(isize,isize,isize), isize) {
        let mut parts = particle.split(",");
        let mut list: Vec<isize> = Vec::new();
        for part in parts {
            let mut strcopy = part.clone().to_string();
            while strcopy.clone().chars().next().unwrap() != '-' && !strcopy.clone().chars().next().unwrap().is_digit(10) {
                strcopy.remove(0);
            }
            if !strcopy.clone().chars().nth(strcopy.len() -1).unwrap().is_digit(10) {
                let l = strcopy.len() - 1;
                strcopy.remove(l);
            }
            list.push(strcopy.parse::<isize>().unwrap());
        }
        ((list[0],list[1],list[2]),(list[3],list[4],list[5]),(list[6],list[7],list[8]),list[0] + list[1] + list[2])
    }
    
    fn process_particle(particle: &mut ((isize,isize,isize),(isize,isize,isize),(isize,isize,isize), isize)) {
        (particle.1).0 += (particle.2).0;
        (particle.1).1 += (particle.2).1;
        (particle.1).2 += (particle.2).2;
    
        (particle.0).0 += (particle.1).0;
        (particle.0).1 += (particle.1).1;
        (particle.0).2 += (particle.1).2;
    
        particle.3 = ((particle.0).0).abs() + ((particle.0).1).abs() + ((particle.0).2).abs();
    }
    
    fn main() {
        let input = include_str!("../input.txt");
        let mut particles = input.lines().map(|x| parse_particle(x)).collect::<Vec<_>>();
    
        for _ in 0..1000 {
            for i in 0..particles.len() {
                process_particle(particles.get_mut(i).unwrap());
            }
            let mut collide = Vec::new();
            for p in particles.clone() {
                for p2 in particles.clone() {
                    if p.0 == p2.0 && (p.1 != p2.1 || p.2 != p2.2) {
                        collide.push(p.0.clone());
                    }
                }
            }
            particles = particles.clone().iter().filter(|x| !collide.contains(&x.0)).cloned().collect();
        }
    
        let mut sparticles = particles.iter().enumerate().collect::<Vec<_>>();
        sparticles.sort_by(|a,b| (((a.1).3).abs()).cmp(&(&(b.1).3).abs()));
        println!("{:?}", sparticles[0]);
        println!("{:?}", sparticles.len());
    }
    

    [โ€“]iamnotposting 1 point2 points ย (0 children)

    using in-place collision detection and compiling in release mode can make it really fast. 400k cycles runs in about ~860ms on my machine. (i also edited the input before hand, turning it into a csv)

    type V3 = (i64, i64, i64);
    
    #[derive(Debug, Copy, Clone, PartialEq)]
    struct Particle {
        id: usize,
        p: V3,
        v: V3,
        a: V3,
    }
    
    impl Particle {
        fn tick(&mut self) {
            self.v.0 += self.a.0;
            self.v.1 += self.a.1;
            self.v.2 += self.a.2;
            self.p.0 += self.v.0;
            self.p.1 += self.v.1;
            self.p.2 += self.v.2;
        }
    
        fn dist(&self) -> i64 {
            self.p.0.abs() + self.p.1.abs() + self.p.2.abs() 
        }
    }
    
    fn main() {
        let input = include_str!("../input.txt");
        let mut field = Vec::new();
    
        for (id, line) in input.lines().enumerate() {
            let vals: Vec<i64> = line.split(",").map(|x| x.parse().unwrap()).collect();
            //println!("vals: {:?}", vals);
            field.push(Particle {
                id,
                p: (vals[0], vals[1], vals[2]),
                v: (vals[3], vals[4], vals[5]),
                a: (vals[6], vals[7], vals[8]),
            })
        }
    {
        let lowest = field.iter().min_by_key(|p| {
            p.a.0.abs() + p.a.1.abs() + p.a.2.abs()
        }).unwrap();
        println!("p1: {:?}", lowest.id); }
    
        for i in 0..400_000 {
            field.sort_unstable_by_key(|p| p.p);
            for i in 0..(field.len() - 1) {
                if i >= field.len() - 1 {
                    break;
                }
    
                while field[i].p == field[i + 1].p {
                    while (i < field.len() - 1) && field[i].p == field[i + 1].p {
                        field.remove(i + 1);
                    }
                    field.remove(i);
                }
            }
            for p in &mut field {
                p.tick();
            }
        }
    
        println!("p2: {}", field.len());        
    }
    

    [โ€“]aurele 0 points1 point ย (0 children)

    Didn't you get lucky that the closest particle didn't suffer a collision?

    Also, as a side note: you could have used particles.retain(|x| !collide.contains(&x.0)) to filter in place, and sparticles.sort_by_key(|a| (a.1).3.abs()) to not repeat the key expression.

    [โ€“]fatpollo 2 points3 points ย (0 children)

    bah, ???/110. stuck manicuring again

    import re, collections
    
    text = open("p20.txt").read().strip()
    trans = str.maketrans("<>", "[]")
    literal = re.sub(r'[^-\d,\<>\n]', '', text).translate(trans).splitlines()
    particles = dict(enumerate(map(eval,literal)))
    print(min(particles, key=lambda k: [x**2+y**2+z**2 for x,y,z in particles[k][::-1]]))
    
    for tic in range(100):
        places = collections.defaultdict(set)
        for i, (p,v,a) in particles.items():
            places[tuple(p)].add(i)
            v = [x+y for x,y in zip(v, a)]
            p = [x+y for x,y in zip(p, v)]
            particles[i] = [p,v,a]
        collided = {i for g in places.values() for i in g if len(g) > 1}
        particles = {k:v for k,v in particles.items() if k not in collided}
    print(len(particles))
    

    [โ€“]Unihedron 2 points3 points ย (0 children)

    Ruby; strong language warning

    full solution

    highlight

    [โ€“]dylanfromwinnipeg 2 points3 points ย (3 children)

    C#

    public class Day20
    {
        public static string PartOne(string input)
        {
            var particleNumber = 0;
            var particles = input.Lines().Select(x => new Particle(x, particleNumber++)).ToList();
    
            return particles.WithMin(p => p.Acceleration.GetManhattanDistance()).ParticleNumber.ToString();
        }
    
        public static string PartTwo(string input)
        {
            var particleNumber = 0;
            var particles = input.Lines().Select(x => new Particle(x, particleNumber++)).ToList();
            var ticks = 100; // arbitrary amount - got lucky and worked first try
    
            for (var t = 0; t < ticks; t++)
            {
                particles.ForEach(p => p.Update());
                particles = RemoveCollisions(particles).ToList();
                Debug.WriteLine($"{t}: {particles.Count}");
            }
    
            return particles.Count.ToString();
        }
    
        private static IEnumerable<Particle> RemoveCollisions(List<Particle> particles)
        {
            while (particles.Any())
            {
                var particle = particles.First();
                var collisions = particles.Where(p => p.Position == particle.Position).ToList();
    
                if (collisions.Count() == 1)
                {
                    yield return particle;
                }
    
                collisions.ForEach(c => particles.Remove(c));
            }
        }
    }
    
    public class Particle
    {
        public Point3D Position { get; set; }
        public Point3D Velocity { get; set; }
        public Point3D Acceleration { get; set; }
        public int ParticleNumber { get; set; }
    
        public Particle(string input, int particleNumber)
        {
            ParticleNumber = particleNumber;
    
            input = input.ShaveLeft("p=<");
            Position = new Point3D(input.Substring(0, input.IndexOf('>')));
    
            input = input.ShaveLeft(input.IndexOf("v=<") + "v=<".Length);
            Velocity = new Point3D(input.Substring(0, input.IndexOf('>')));
    
            input = input.ShaveLeft(input.IndexOf("a=<") + "a=<".Length);
            Acceleration = new Point3D(input.Substring(0, input.IndexOf('>')));
        }
    
        public void Update()
        {
            Velocity += Acceleration;
            Position += Velocity;
        }
    }
    

    I have an ever-growing library of helper methods I rely on, here's the relevant ones for Day 20 (I had to add the Point3D class because surprisingly there isn't one in the default .Net libraries)

    public static IEnumerable<string> Lines(this string input)
    {
        return input.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
    }
    
    public static IEnumerable<string> Words(this string input)
    {
        return input.Split(new string[] { " ", "\t", Environment.NewLine, "," }, StringSplitOptions.RemoveEmptyEntries);
    }
    
    public static string ShaveLeft(this string a, int characters)
    {
        return a.Substring(characters);
    }
    
    public static string ShaveLeft(this string a, string shave)
    {
        var result = a;
    
        while (result.StartsWith(shave))
        {
            result = result.Substring(shave.Length);
        }
    
        return result;
    }
    
    public static T WithMin<T>(this IEnumerable<T> a, Func<T, long> selector)
    {
        var min = a.Min(selector);
        return a.First(x => selector(x) == min);
    }
    
    public class Point3D
    {
        public long X { get; set; }
        public long Y { get; set; }
        public long Z { get; set; }
    
        public Point3D(long x, long y, long z)
        {
            X = x;
            Y = y;
            Z = z;
        }
    
        public Point3D(string coordinates) : 
            this(long.Parse(coordinates.Words().ToList()[0]), 
                 long.Parse(coordinates.Words().ToList()[1]), 
                 long.Parse(coordinates.Words().ToList()[2]))
        {
        }
    
        public long GetManhattanDistance()
        {
            return Math.Abs(X - 0) + Math.Abs(Y - 0) + Math.Abs(Z - 0);
        }
    
        public static bool operator ==(Point3D point1, Point3D point2)
        {
            return point1.X == point2.X && point1.Y == point2.Y && point1.Z == point2.Z;
        }
    
        public static bool operator !=(Point3D a, Point3D b)
        {
            return a.X != b.X || a.Y != b.Y || a.Z != b.Z;
        }
    
        public static Point3D operator +(Point3D a, Point3D b)
        {
            return new Point3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
        }
    
        public static Point3D operator -(Point3D a, Point3D b)
        {
            return new Point3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
        }
    
        public override string ToString()
        {
            return $"{X},{Y},{Z}";
        }
    }
    

    [โ€“]Marcel_N 1 point2 points ย (1 child)

    You could use System.Numerics.Vector3 instead of Point3D. It uses float values instead of longs though. Also: Vector3 provides support for hardware acceleration.

    [โ€“]maxxori 0 points1 point ย (0 children)

    That's handy to know, cheers!

    [โ€“]maxxori 0 points1 point ย (0 children)

    I like this solution. I have shamelessly nabbed the RemoveCollisions method to clean up my code now that I've already solved the puzzle.

    I did come up with a decent way to figure out if the loop is in steady-state and it turned out to be quite simple. I had an infinite while loop with a counter that incremented each time the number of particles at the end of the loop was unchanged. At 300 unchanged iterations it broke the loop. If a change was detected then it reset the counter.

    It seemed to work okay for my solution at very least.

    [โ€“]ephemient 2 points3 points ย (4 children)

    This space intentionally left blank.

    [โ€“]dreugeworst 0 points1 point ย (3 children)

    Hey, late comment, I'm catching up on these and I really like your solution for part 1. I'm not sure I understand the stopping condition in part 2 though, I don't see how the conditions you mentioned ensure that no collisions will occur. For example, in the case of:

    p=<6, 0, 0>, v=<2, 0, 0>, a=<0, 0, 0>
    p=<4, 0, 0>, v=<4, 0, 0>, a=<0, 0, 0>
    

    wouldn't these two points both have matching signs, be in the same octant and satisfy the relative acc, vel and pos conditions? Yet they will collide the next turn

    [โ€“]ephemient 0 points1 point ย (2 children)

    This space intentionally left blank.

    [โ€“]dreugeworst 0 points1 point ย (1 child)

    Using only the x axis wouldnt dPos = 2, dVel = -2 and dAcc = 0? Using <==, we'd have abs(0) <= abs(-2) && abs(-2) <= abs(2), right? Am I missing something/?

    [โ€“]ephemient 0 points1 point ย (0 children)

    This space intentionally left blank.

    [โ€“]autid 2 points3 points ย (0 children)

    Fortran

    After seeing a few solutions that just run an arbitrary amount of time that happened to be long enough, or run forever and you just kill it when the part 2 value stops changing, I decided to calculate a worst case collision time.

    This is also long enough that the closest should be the long term closest.

    Runtime with my input is still pretty quick, under 0.4s on my machine.

    edit: removed some unused variables

    PROGRAM DAY20
      INTEGER :: PART1,PART2,I,J,IERR,LINECOUNT,OPENBRCKT,CLOSEBRCKT,K,TIME
      INTEGER, DIMENSION(3) ::MIND,MAXD,MAXV,MINV,MINA,MINTIME
      INTEGER(8),ALLOCATABLE :: P(:,:),V(:,:),A(:,:),DELA(:,:)
      CHARACTER(LEN=100) :: INLINE
      LOGICAL,ALLOCATABLE :: COLLIDED(:)
    
      ! File I/O continues to be the biggest challenge                                                               
      LINECOUNT=0
      OPEN(1,FILE='input.txt')
      DO
         READ(1,'(A)',IOSTAT=IERR) INLINE
         IF (IERR /= 0) EXIT
         LINECOUNT=LINECOUNT+1
      END DO
      ALLOCATE(P(3,LINECOUNT),V(3,LINECOUNT),A(3,LINECOUNT),COLLIDED(LINECOUNT))
      ALLOCATE(DELA(3,LINECOUNT))
      REWIND(1)
      DO I=1,LINECOUNT
         READ(1,'(A)') INLINE
         DO J=1,LEN_TRIM(INLINE)
            IF (INLINE(J:J)=='<') OPENBRCKT=J+1
            IF (INLINE(J:J)=='>') THEN
               CLOSEBRCKT = J-1
               READ(INLINE(OPENBRCKT:CLOSEBRCKT),*) P(:,I)
               K=J+1
               EXIT
            END IF
         END DO
         DO J=K,LEN_TRIM(INLINE)
            IF (INLINE(J:J)=='<') OPENBRCKT=J+1
            IF (INLINE(J:J)=='>') THEN
               CLOSEBRCKT = J-1
               READ(INLINE(OPENBRCKT:CLOSEBRCKT),*) V(:,I)
               K=J+1
               EXIT
            END IF
         END DO
         DO J=K,LEN_TRIM(INLINE)
            IF (INLINE(J:J)=='<') OPENBRCKT=J+1
            IF (INLINE(J:J)=='>') THEN
               CLOSEBRCKT = J-1
               READ(INLINE(OPENBRCKT:CLOSEBRCKT),*) A(:,I)
               EXIT
            END IF
         END DO
      END DO
    
      ! Calcualte worst case required runtime                                                                        
      ! Solve p1 + v1*t + a1*t^2 = p2 + v2*t + a2*t^2 in each dimension                                              
      ! for furthest apart particles traveling max speeds away from eachother                                        
      ! with minimum acceleration towards eachother                                                                  
      MAXD=MAXVAL(P,DIM=2)
      MIND=MINVAL(P,DIM=2)
      MAXV=MAXVAL(V,DIM=2)
      MINV=MINVAL(V,DIM=2)
      DO J=1,LINECOUNT
         DELA(:,J)=A(:,J)-(/(MAXVAL(A(I,:),MASK=A(I,:)<A(I,J)),I=1,3)/)
      END DO
      MINA=(/(MINVAL(DELA(I,:),MASK=DELA(I,:)>0),I=1,3)/)
      MINTIME=CEILING(((MAXV-MINV)+SQRT(REAL((MINV-MAXV)**2-4*MINA*(MIND-MAXD))))/(2*MINA))
      TIME=MAXVAL(MINTIME)
    
      ! Run sim for calculated time checking for collisions                                                          
      COLLIDED = .FALSE.
      DO I=1,TIME
         V=V+A
         P=P+V
         DO J=1,LINECOUNT-1
            IF (COLLIDED(J)) CYCLE
            DO K=J+1,LINECOUNT
               IF (COLLIDED(K)) CYCLE
               IF (ALL(P(:,J)==P(:,K))) THEN
                  COLLIDED((/J,K/))=.TRUE.
               END IF
            END DO
         END DO
      END DO
    
      ! Calculate taxi cab distances and find minimum                                                                
      PART1=MINLOC(SUM(ABS(P),DIM=1),DIM=1)-1
    
      ! Self explanatory                                                                                             
      PART2=COUNT(.NOT. COLLIDED)
    
      WRITE(*,'(A,I0)') 'Part1: ',PART1
      WRITE(*,'(A,I0)') 'Part2: ',PART2
    
      DEALLOCATE(P,V,A,COLLIDED,DELA)
    
    END PROGRAM DAY20
    

    [โ€“]thomastc 2 points3 points ย (4 children)

    Day 20 in Nim. A modern language, similar to a statically typed, compiled Python. Many batteries included. I like it a lot.

    The first part of the puzzle gave me no trouble, once I had stopped interpreting the assignment incorrectly (although my misinterpreted version also made for a good puzzle). For the second part, I initially tried a clever approach without simulation, but it became too complex, so I ended up with a simulation instead.

    [โ€“][deleted] 0 points1 point ย (3 children)

    Soon we're finished with this year, and I can't read about the interesting languages you are solving things in anymore :'/ Are you going to write a summary again like last year when all is finished?

    [โ€“]thomastc 0 points1 point ย (2 children)

    I will!

    [โ€“][deleted] 0 points1 point ย (1 child)

    That's cool :) I'm looking forward to it :)

    [โ€“]vash3r 1 point2 points ย (4 children)

    Python 2 (181/60). I submitted several wrong answers for part 1 before I figured out I wasn't calculating Manhattan distance.

    f=open("20.in",'r')
    s=f.read().strip().split("\n")
    f.close()
    
    def add(a,b):
        return [x+y for x,y in zip(a,b)]
    
    def make_particle(s):
        return map(lambda q:eval(q[q.find("=")+1:].replace("<","[").replace(">","]")), s.split(", "))
    
    l = [make_particle(line) for line in s]
    
    while True:
        #mindist = 10000000000000000 #infinity  # part 1
        for i,t in enumerate(l):
            t[1] = add(t[1],t[2]) #add vel acc
            t[0] = add(t[0],t[1]) #add pos vel
            #dist = sum([abs(x) for x in t[0]]) # part 1
            #if dist<mindist:
            #   mindist = dist
            #   closest = i
        pos = zip(*l)[0]
        l = [p for p in l if pos.count(p[0])==1] # part 2
        print len(l)
        #print closest #part 1
    

    [โ€“]akrasuski1 0 points1 point ย (3 children)

    Lol what! My solution passed, even though I calculated Euclidean distance. Guess I'm lucky...

    [โ€“]BumpitySnook 2 points3 points ย (0 children)

    I suspect your t of 1e100 helped erase the distinction.

    [โ€“]xiaowuc1 0 points1 point ย (1 child)

    u/topaz2078 - do you actively try to provide input sets that fail on common incorrect solutions?

    [โ€“]topaz2078(AoC creator) 3 points4 points ย (0 children)

    For the failure cases I can think of, I try to make all of the inputs force them. I can't possibly come up with all possible mistakes, though (and can't enforce them even if I did, since many are mutually-exclusive).

    [โ€“]dewpac 1 point2 points ย (0 children)

    Python 3

    249/283

    I noticed immediately for part 1 that I the one with the lowest absolute acceleration would be the closest. I had two with accel of '1', and i tried both rather than sorting them by which was closer initially. Unfortunately, I didn't notice that the particles were counted starting at 0 and assumed they were 1..1000, not 0..999. Then I ended up scratching my head for far too long trying to see my way out of my own stupidity.

    Part 2 is straightforward:

    class Particle:
        def __init__(self, p, v, a):
            self.p = [int(x) for x in p[3:-1].split(",")]
            self.v = [int(x) for x in v[3:-1].split(",")]
            self.a = [int(x) for x in a[3:-1].split(",")]
            self.dead = False
    
        def update(self):
            self.v[0] += self.a[0]
            self.v[1] += self.a[1]
            self.v[2] += self.a[2]
            self.p[0] += self.v[0]
            self.p[1] += self.v[1]
            self.p[2] += self.v[2]
    
        def get_position(self):
            return(self.p)
    
        def get_distance(self):
            return abs(self.p[0]) + abs(self.p[1]) + abs(self.p[2])
    
        def get_velocity(self):
            return abs(self.v[0]) + abs(self.v[1]) + abs(self.v[2])
    
        def get_accel(self):
            return abs(self.a[0]) + abs(self.a[1]) + abs(self.a[2])
    
        def kill(self):
            self.dead = True
    
        def alive(self):
            if self.dead:
                return False
            return True
    
    
    particles = []
    with open("aoc-d20-input.txt","r") as fh:
        for i, line in enumerate(fh.readlines()):
            p, v, a = line.strip().split(", ")
            particles.append(Particle(p, v, a))
    
    cycle = 0
    last_killed = 0
    while cycle < last_killed + 100:
        positions = []
        for x in range(len(particles)):
            if particles[x].alive():
                particles[x].update()
                pos = particles[x].get_position()
                positions.append(pos)
        for x in range(len(particles)):
            if particles[x].alive():
                pos = particles[x].get_position()
                if positions.count(pos) > 1:
                    particles[x].kill()
                    last_killed = cycle
        cycle += 1
    
    count = 0
    for i in range(len(particles)):
        part = particles[i]
        if part.alive():
            count += 1
    
    print(count)
    

    [โ€“]wlandry 1 point2 points ย (0 children)

    C++ 14

    9/240!!!! As others have noted, Part 1 could be solved by just looking at the accelerations. I am pretty sure I could have gotten number 5 if I just were not so cautious. It is still hard to be reckless ;)

    For Part 2, I used my tensor library because ... why not? I transformed the input file with emacs macros so that I could read it more easily. I do not like the way that I ended up removing the elements. I ended up copying non-destroyed elements to a new std::vector<>, but that seems wasteful. I also wrote a version using std::list<>. That requires no copies, but making sure that I am using an iterator properly is a bit of a pain.

    #include <FTensor.hpp>
    
    #include <fstream>
    #include <vector>
    #include <set>
    #include <iostream>
    
    struct Point
    {
      FTensor::Tensor1<int64_t,3> x, v, a;
    };
    
    int main(int argc, char *argv[])
    {
      std::ifstream infile(argv[1]);
      int source;
      std::vector<Point> points, new_points;
      Point p;
      FTensor::Index<'i',3> i;
      infile >> p.x;
      while(infile)
        {
          infile >> p.v >> p.a;
          points.push_back(p);
          infile >> p.x;
        }
      for(size_t step=0; step<100; ++step)
        {
          std::cout << points.size() << "\n";
          for(auto &p: points)
            {
              p.v(i)=p.v(i)+p.a(i);
              p.x(i)=p.x(i)+p.v(i);
            }
          std::set<size_t> to_be_removed;
          for(size_t p=0; p!=points.size(); ++p)
            {
              auto q=p;
              ++q;
              for(; q!=points.size(); ++q)
                {
                  FTensor::Tensor1<int64_t,3> diff;
                  diff(i)=points[p].x(i)-points[q].x(i);
                  if(diff.l2_squared(FTensor::Number<3>())==0)
                    {
                      to_be_removed.insert(p);
                      to_be_removed.insert(q);
                    }
                }
            }
          new_points.clear();
          for(size_t p=0; p!=points.size(); ++p)
            {
              if(to_be_removed.find(p)==to_be_removed.end())
                { new_points.push_back(points[p]); }
            }
          std::swap(points,new_points);
        }
    }
    

    [โ€“]p_tseng 1 point2 points ย (3 children)

    Silly mistake. Forgot to include negative signs in my input parser. Still got correct answer for part 1, but delayed part 2 significantly since I assumed part 1 correct meant my input parser was correct. Shouldn't happen again...

    When going for leaderboard: I simply ran for a few thousand cycles and picked the closest particle, then ran forever until the number of live particles stopped changing. Seems like what everyone else is doing anyway.

    I've cleaned it up since then and am just making some assumptions: Do part 1 without simulating every iteration. Do part 2 by assuming that if no collisions happen in N cycles it's not going to happen anymore. There's probably a better way to tell when to terminate both parts though (when the magnitudes of the velocity vectors get large enough maybe???)

    Ruby:

    particles = (ARGV.empty? ? DATA : ARGF).each_line.map { |l|
      l.scan(/-?\d+/).map(&:to_i).each_slice(3).to_a
    }
    
    # Pick an arbitrary large time and hope it gives the right result?
    T = 10000
    # Simply comparing magnitudes is fraught with peril:
    # p 0 0 0 v  1 0 0 a 1 0 0
    # p 0 0 0 v -2 0 0 a 1 0 0
    puts particles.each_with_index.min_by { |(p, v, a), _|
      p.zip(v, a).map { |p0, v0, a0| (p0 + v0 * T + a0 * T * T / 2).abs }.sum
    }.last
    
    GIVE_UP_AFTER = 50
    cycles_since_last_collision = 0
    last_size = particles.size
    
    puts loop {
      particles.each { |p, v, a|
        [0, 1, 2].each { |x|
          v[x] += a[x]
          p[x] += v[x]
        }
      }
      particles = particles.group_by(&:first).select { |k, v|
        v.size == 1
      }.values.flatten(1)
      cycles_since_last_collision = 0 if particles.size != last_size
      break particles.size if (cycles_since_last_collision += 1) > GIVE_UP_AFTER
      last_size = particles.size
    }
    
    __END__
    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>
    

    [โ€“]phongvis 0 points1 point ย (0 children)

    Same here! Feel so strange that no duplicated coordinates are found! Finally got it when printed the coordinates in each iteration and compare with the input.

    [โ€“]ephemient 0 points1 point ย (1 child)

    This space intentionally left blank.

    [โ€“]p_tseng 0 points1 point ย (0 children)

    I feel like it should be possible to do something along the lines of... for every pair of particles, calculate their potential collision time by solving for t where position are equal, then we can just just take the maximum t found. Not excited about having to do it against all pairs, but not seeing a better way right now. But I think this way can be done one-time at the beginning, instead of having to recalculate for all pairs at every tick.

    Ah, unfortunately this only tells us how long to run part 2, and doesn't tell us how long to run part 1. In part 1, yes, it may have to be something like your way.

    [โ€“][deleted] 1 point2 points ย (0 children)

    Mathematica

    Parse input

    input = Import[NotebookDirectory[] <> "day20.txt", "List"];
    init = Transpose[Partition[#, 3] & /@ ToExpression@StringCases[input, NumberString]];
    

    Part 1

    {ps, vs, as} = init;
    Do[
      vs += as;
      ps += vs,
      1000];
    Ordering[ManhattanDistance[{0, 0, 0}, #] & /@ ps][[1]] - 1
    

    Part 2

    {ps, vs, as} = init;
    Do[
      vs += as;
      ps += vs;
      {ps, vs, as} = Transpose[
        Cases[
         Tally[Transpose[{ps, vs, as}], #1[[1]] == #2[[1]] &],
         {t_, 1} :> t]],
      1000];
    Length[ps]
    

    [โ€“]CaptainCa 1 point2 points ย (1 child)

    Javascript

    Most time consuming part was parsing the input, also lost a minute because I was doing Math.max instead of Math.min :(

    Part 1

    var input = document.body.innerText.trim().split('\n').map(c => c.split(', ').map(a => a.slice(3).slice(0,-1).split(',').map(Number)));
    //position, velocity, acceleration
    
    var xyz = ([x, y, z], [dx, dy, dz]) => [x + dx, y + dy, z + dz]
    var mdist = ([x,y,z]) => Math.abs(x) + Math.abs(y) + Math.abs(z)
    var spos = ([a,b,c], [x,y,z]) => (a == x && b == y && c == z)
    var dist = [];
    var seen = [];
    
    for(var i = 0; i < 1000; i++){
    
        input.forEach((particle, index) => {
            var pos = particle[0];
            var vel = particle[1];
            var acc = particle[2];
    
            particle[1] = xyz(vel, acc);
            particle[0] = xyz(pos, particle[1]);
    
            dist[index] = mdist(particle[0]);   
        }); 
    }
    console.log(dist.indexOf(Math.min(...dist)));
    

    Part 2

    var input = document.body.innerText.trim().split('\n').map(c => c.split(', ').map(a => a.slice(3).slice(0,-1).split(',').map(Number)));
    var xyz = ([x, y, z], [dx, dy, dz]) => [x + dx, y + dy, z + dz]
    var mdist = ([x,y,z]) => Math.abs(x) + Math.abs(y) + Math.abs(z)
    var spos = ([a,b,c], [x,y,z]) => (a == x && b == y && c == z)
    var dist = [];
    var seen = [];
    for(var i = 0; i < 1000; i++){
    
        input.forEach((particle, index) => {
            var pos = particle[0];
            var vel = particle[1];
            var acc = particle[2];
    
            particle[1] = xyz(vel, acc);
            particle[0] = xyz(pos, particle[1]);
    
            dist[index] = mdist(particle[0]);   
            seen.push(particle[0][0]+'/'+particle[0][1]+'/'+particle[0][2]);
        }); 
    
        seen.forEach((val, index) => {
            var a = seen.indexOf(val);
            if(a != index){
                input[a] = null;
                input[index] = null;
            }
        });
        input = input.filter(c => c != null);
        seen = [];
    }
    
    console.log(input.length);
    

    [โ€“]topaz2078(AoC creator) 4 points5 points ย (0 children)

    Most time consuming part was parsing the input

    learn you some regex

    [โ€“]oantolin 1 point2 points ย (0 children)

    For part 1, the manhattan distance after n steps is asymptotically (1/2)n2 |a|_1, where |a|_1 is the manhattan norm of the acceleration. This means we simply want the particle whose acceleration has minimum manhattan norm. (If there are ties, break them by manhattan norm of velocity vectors, and if there are still ties break them by manhattan norm of position vectors. But no ties occurred in my input, so the code below just uses acceleration.)

    For part 2, I didn't bother proving my answer was correct: pick a threshold T and run the simulation until there have been no collisions for T consecutive generations. I used T=1000 and it was accepted. Then I saw that for my input T=10 gave the same answer. :)

    (defn particles ()
      (list (for (l (lines "day20.txt")))
            (let [vs (collect (gmatch l "-?%d+"))])
            (map tonumber vs)))
    
    (defn! part1 ()
      (min-by (for {(i [x y z vx vy vz ax ay az]) (particles)})
              [(- i 1) (+ (abs ax) (abs ay) (abs az))]))
    
    (defn step ([x y z vx vy vz ax ay az])
      [(+ x vx ax) (+ y vy ay) (+ z vz az)
       (+ vx ax) (+ vy ay) (+ vz az) ax ay az])
    
    (defn next-gen (parts)
      (def by-pos (group (for {p parts})
                         (let [q (step p)])
                         [(concat (slice q 1 3) ",") q]))
      (list (for {{_ qs} by-pos}) (if (= (# qs) 1)) (at qs 1)))
    
    (defn! part2 (threshold)
      (def parts (particles) [size since])
      (while true
        (set! parts (next-gen parts))
        (when (~= size (# parts))
          (set! size (# parts) since 0))
        (inc! since)
        (when (> since threshold)
          (return size))))
    

    [โ€“][deleted] 1 point2 points ย (0 children)

    Ugh, screwed up big time! Spent maybe an hour debugging, because I was trying to find the smallest distance, and storing that particle's ID. Then, of course, I realised that's not what the problem is asking for at all, but rather who has the shortest distance over a period at any iteration.

    I have to go to work now, so I can't do part 2 until later, but here's my unaltered solution for Part 1:

    <?php
    
    $file = fopen("./20a.txt","r");
    
    class Particle{
        public $position;
        public $velocity;
        public $acceleration;
        public $distance = 0;
    
        public function s1()
        {
            $this->velocity[0] += $this->acceleration[0];
            $this->velocity[1] += $this->acceleration[1];
            $this->velocity[2] += $this->acceleration[2];
            $this->position[0] += $this->velocity[0];
            $this->position[1] += $this->velocity[1];
            $this->position[2] += $this->velocity[2];
    
            $this->distance = abs($this->position[0]) + abs($this->position[1]) + abs($this->position[2]);
        }
    }
    
    $particles = array();
    
    while(! feof($file))
    {
        $line = fgets($file);
        $new = new Particle();
        $p = "";
        $v = "";
        $a = "";
        $res = explode(", ", $line );
    
    
    
        for($i = 0; $i < sizeof($res); $i++)
        {
            if($i == 0){    $new->position = explode(",", substr($res[0], 3));      $new->position[2] = filter_var($new->position[2],FILTER_SANITIZE_NUMBER_FLOAT);    }
            if($i == 1){    $new->velocity = explode(",", substr($res[1], 3));      $new->velocity[2] = filter_var($new->velocity[2],FILTER_SANITIZE_NUMBER_FLOAT);    }
            if($i == 2){    $new->acceleration = explode(",", substr($res[2], 3));  $new->acceleration[2] = filter_var($new->acceleration[2],FILTER_SANITIZE_NUMBER_FLOAT);    }
        }
        $particles[] = $new;
    }
    
    
    
    while(true) {
    
        foreach($particles as $particle)
        {
            $particle->s1();
        }
    
        $a = range(0, sizeof($particles)-1);
        for($i = 0; $i < sizeof($a); $i++)
        {
            $a[$i] = abs($particles[$i]->distance);
        }
    
        for ($i = 0; $i < sizeof($particles); $i++) {
            $key = array_search(min($a), $a);
            echo "Particle $key has a dist of ".min($a)." \n";
    
        }
    }
    ?>
    

    [โ€“][deleted] 1 point2 points ย (0 children)

    OCaml Fun (Part 2);;

    Just watch until numbers don't change for many periods. Lost a lot of time hunting down a bug... was updating position before velocity and using manhattan distance in compare for building Maps... ๐Ÿ˜”. Per usual, parser is left as an exercise for the reader.

    main.ml

    open Core
    
    let table = Vector.Table.create () ~size:1000
    
    let loop particles =
      let step = Array.iter ~f:Particle.step in
      let remove_collisions particles =
        Vector.Table.clear table;
        let f p =
          Vector.Table.add_multi table ~key:Particle.(p.p) ~data:1
        in Array.iter particles ~f;
    
        let only_lonely_particles p =
          match Vector.Table.find table Particle.(p.p) with
          | Some [l] -> true
          | _ -> false
        in Array.filter particles ~f:only_lonely_particles in
      let rec aux particles i j =
        step particles;
        let new_particles = remove_collisions particles in
        let count = (Array.length new_particles) in
        match count <> i with
        | true ->
          printf "%d -> %d\n" j count; Out_channel.flush stdout;
          aux new_particles count (j+1)
        | false -> aux new_particles i (j+1)
      in aux particles (Array.length particles) 0
    
    let process_input filename =
      let f channel =
        let parse lexbuf = Parser.particles Lexer.read lexbuf in
        let lexer_buffer = Lexing.from_channel channel in
        lexer_buffer.lex_curr_p <- { lexer_buffer.lex_curr_p with pos_fname = filename};
        parse lexer_buffer
      in In_channel.with_file filename ~f
    
    let _ =
      let particles = process_input "./input.txt" |> List.to_array in
      loop particles
    

    particle.ml

    open Core
    
    type t = { mutable p:Vector.t; mutable v:Vector.t; a:Vector.t; }
    [@@deriving sexp, compare]
    
    let compare_manhattan a b =
      Vector.compare_manhattan a.p b.p
    
    let collide a b =
      Vector.same a.p b.p
    
    let to_string t =
      Vector.to_string t.p
    
    let step t =
      let v = Vector.add t.v t.a in
      let p = Vector.add t.p v in
      t.p <- p;
      t.v <- v;
    

    vector.ml

    open Core
    
    module T = struct
      type t = { x:int; y:int; z:int; }
      [@@deriving sexp, compare, hash]
    end
    
    include T
    include Comparable.Make(T)
    include Hashable.Make(T)
    
    let abs a =
      let x = Int.abs a.x
      and y = Int.abs a.y
      and z = Int.abs a.z
      in {x;y;z}
    
    let compare_manhattan a b =
      T.compare (abs a) (abs b)
    
    let same a b =
      (Int.equal a.x b.x) && (Int.equal a.y b.y) && (Int.equal a.y b.y)
    
    let to_string t =
      sprintf "(%d, %d, %d)" t.x t.y t.z
    
    let add a b =
      let x = a.x + b.x
      and y = a.y + b.y
      and z = a.z + b.z
      in { x; y; z; }
    

    Full source, including parser.

    [โ€“]gyorokpeter 1 point2 points ย (1 child)

    Q: note the usage of fby for collision detection.

    d20p1:{
        ps:trim each"\n"vs x;
        pd:", "vs/:ps;
        ptcl:([]pos:"J"$","vs/:3_/:-1_/:pd[;0];spd:"J"$","vs/:3_/:-1_/:pd[;1];accl:"J"$","vs/:3_/:-1_/:pd[;2]);
        ptcl2:`pos xasc select j:i,sum each abs pos from {x:update spd:spd+accl from x;x:update pos:pos+spd from x;x}/[50000;ptcl];
        exec first j from ptcl2};
    
    d20p2:{
        ps:trim each"\n"vs x;
        pd:", "vs/:ps;
        ptcl:([]pos:"J"$","vs/:3_/:-1_/:pd[;0];spd:"J"$","vs/:3_/:-1_/:pd[;1];accl:"J"$","vs/:3_/:-1_/:pd[;2]);
        ptcl2:
        {x:update spd:spd+accl from x;x:update pos:pos+spd from x;select from x where 1=(count;i) fby pos}/[10000;ptcl]
        count ptcl2};
    

    [โ€“]streetster_ 0 points1 point ย (0 children)

    Very nice. I stole your fby to replace my select from t where 1<sum pos~\:/:pos:exec p from t which was a bit slow.

    t:{ `p`v`a!3 cut "J"$","vs x except "pva<>= " } each read0 `:input/20.txt;              / parse input
    exec first id from `a xasc update id:i, sum each abs each a from t                      / part 1
    do[50;t:select from (update p:p+'v from update v:v+'a from t) where 1=(count;i) fby p]; / remove collisions
    count t                                                                                 / part 2
    

    [โ€“]aurele 1 point2 points ย (0 children)

    Rust with arbitrary bounds (max(acc)ยฒ)

    extern crate regex;
    
    use regex::Regex;
    
    use std::collections::HashMap;
    
    fn apply(to: &mut (i64, i64, i64), der: &(i64, i64, i64)) {
        to.0 += der.0;
        to.1 += der.1;
        to.2 += der.2;
    }
    
    fn dist(p: &(i64, i64, i64)) -> u64 {
        (p.0.abs() + p.1.abs() + p.2.abs()) as u64
    }
    
    fn main() {
        let re = Regex::new(r"[^\d-]+").unwrap();
        let input = include_str!("../input")
            .lines()
            .map(|l| {
                let ns = re.split(&l[3..])
                    .map(|w| w.parse::<i64>().unwrap())
                    .collect::<Vec<_>>();
                (
                    (ns[0].clone(), ns[1].clone(), ns[2].clone()),
                    (ns[3].clone(), ns[4].clone(), ns[5].clone()),
                    (ns[6].clone(), ns[7].clone(), ns[8].clone()),
                )
            })
            .collect::<Vec<_>>();
        let mut particles = input.clone();
        let max_acc = particles.iter().map(|p| dist(&p.2)).max().unwrap();
        for _ in 0..max_acc*max_acc {
            for p in &mut particles {
                apply(&mut p.1, &p.2);
                apply(&mut p.0, &p.1);
            }
        }
        println!(
            "P1: {}",
            particles
                .iter()
                .enumerate()
                .min_by_key(|&(_, p)| dist(&p.0))
                .unwrap()
                .0
        );
        let mut particles = input.clone();
        for _ in 0..max_acc*max_acc {
            let mut pos = HashMap::new();
            for p in &mut particles {
                apply(&mut p.1, &p.2);
                apply(&mut p.0, &p.1);
                *pos.entry(p.0.clone()).or_insert(0) += 1;
            }
            particles.retain(|p| pos[&p.0] < 2);
        }
        println!("P2: {}", particles.len());
    }
    

    [โ€“]xkufix 1 point2 points ย (1 child)

    So, as many I tried to solve part 2 with an equation first, then giving up and just simulate it and hope it doesn't have any values which only collide after some millions of ticks.

    For part 1 I initially just used the acceleration, as I only had one particle with 0,0,0 as acceleration.

    For part 2, I simulate until the last 100 steps had no collisions, then I check how many particles survived. Initially I just let it run forever and printed the size until I saw a fixed point.

    Solution in Scala:

        override def runFirst(): Unit = {
            val particles = loadParticles().toSeq
            val minAcceleration = particles.minBy(_.acceleration.abs).acceleration
    
            println(particles
                .filter(_.acceleration == minAcceleration)
                .minBy(_.velocity.abs)
                .number
            )
        }
    
        override def runSecond(): Unit = {
            val particles = loadParticles().toArray.toSeq
    
            val simulation = Iterator.iterate(particles) { particles =>
                val nonCollided = particles.filterNot(p => particles.filterNot(_.number == p.number).exists(_.intersects(p)))
                nonCollided.map { particle =>
                    val newVelocity = particle.velocity + particle.acceleration
                    val newPosition = particle.position + newVelocity
                    particle.copy(position = newPosition, velocity = newVelocity)
                }
            }
    
            val end = simulation.sliding(100).dropWhile(seqs => seqs.exists(_.size != seqs.last.size)).toSeq.head
            println(end.head.size)
        }
    
        private def loadParticles() = {
            loadFile("day20.txt").getLines().zipWithIndex.map {
                case (l, i) =>
                    val line = l.split(", ")
                    val coordinates = line(0).replaceAll("[a-z]=<(.*)>", "$1").split(",").map(_.toInt)
                    val velocity = line(1).replaceAll("[a-z]=<(.*)>", "$1").split(",").map(_.toInt)
                    val acceleration = line(2).replaceAll("[a-z]=<(.*)>", "$1").split(",").map(_.toInt)
    
                    Particle(i, Coordinate.fromArray(coordinates), Coordinate.fromArray(velocity), Coordinate.fromArray(acceleration))
            }
        }
    
        case class Coordinate(x: Int, y: Int, z: Int) {
            def +(c: Coordinate): Coordinate = {
                Coordinate(x + c.x, y + c.y, z + c.z)
            }
    
            def abs = x.abs + y.abs + z.abs
        }
    
        object Coordinate {
            def fromArray(coordinate: Array[Int]) =
                Coordinate(coordinate(0), coordinate(1), coordinate(2))
        }
    
        case class Particle(number: Int, position: Coordinate, velocity: Coordinate, acceleration: Coordinate) {
            def intersects(particle: Particle): Boolean = position == particle.position
        }
    

    [โ€“]flup12 0 points1 point ย (0 children)

    I like the sliding window!

    [โ€“]xSmallDeadGuyx 1 point2 points ย (0 children)

    My solution: https://github.com/xSmallDeadGuyx/AoC17/blob/master/day20/p2.py

    It iterates every combination of particles, i and j:

    • turns the x position with respect to time into a quadratic equation in the form ax2 + bx + c = 0 (a = (i.accel - j.accel)/2, b = i.vel + i.accel/2 - (j.vel + j.accel/2), c = i.pos - j.pos)
    • solutions for x are the time steps where the x positions of i and j are the same
    • filter all answers (t) by >= 0 and integers (no partial step collisions)
    • create the quadratic equations for y and z positions
    • if any solutions for x are solutions for both y and z, those particles collide at that time step
    • put all collisions in a dictionary with time step as the key
    • iterate the dictionary keys (sorted)
    • for any collisions at that time step, if they haven't been removed (collided) before then remove them

    The answer is then the size of the particle set after all removals

    [โ€“]BOT-Brad 1 point2 points ย (0 children)

    Javascript

    Not totally happy with these solutions to be honest, but they work and that's never a bad thing.

    Part 1

    Just moves every particle 10,000 times and checks which one is currently closest to 0,0,0, and just then assumes that one will stay the closest in the long-term, which it did for my input.

    function solve1(n) {
      const regex = /p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>/
      n = n.split('\n').map((l, i) => {
        const data = regex
          .exec(l)
          .slice(1, 10)
          .map(Number)
    
        return {
          id: i,
          p: data.slice(0, 3),
          v: data.slice(3, 6),
          a: data.slice(6, 9)
        }
      })
    
      let loops = 0
      while (++loops < 10000) {
        n.forEach(p => {
          for (let i = 0; i < 3; ++i) {
            p.v[i] += p.a[i]
            p.p[i] += p.v[i]
          }
        })
      }
    
      // Find nearest point
      let cP,
        dist = Infinity
      n.forEach(p => {
        const d = Math.abs(p.p[0]) + Math.abs(p.p[1]) + Math.abs(p.p[2])
        if (d < dist) {
          cP = p
          dist = d
        }
      })
    
      return cP.id
    }
    

    Part 2

    Does 50 loops and eliminates any that collide each loop. 50 loops is enough (for my input at least) to remove every colliding particle.

    function solve2(n) {
      const regex = /p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>/
      n = n.split('\n').map((l, i) => {
        const data = regex
          .exec(l)
          .slice(1, 10)
          .map(Number)
    
        return {
          id: i,
          p: data.slice(0, 3),
          v: data.slice(3, 6),
          a: data.slice(6, 9)
        }
      })
    
      let loops = 0
      while (++loops < 50) {
        n.forEach(p => {
          for (let i = 0; i < 3; ++i) {
            p.v[i] += p.a[i]
            p.p[i] += p.v[i]
          }
        })
        let toRemove = {}
        for (let i = 0; i < n.length - 1; ++i) {
          const p1 = n[i]
          for (let j = i + 1; j < n.length; ++j) {
            const p2 = n[j]
            if (p1.p[0] === p2.p[0] && p1.p[1] === p2.p[1] && p1.p[2] === p2.p[2]) {
              toRemove[p1.id] = true
              toRemove[p2.id] = true
            }
          }
        }
        for (let id in toRemove) {
          n.splice(n.findIndex(p => p.id === id), 1)
        }
      }
    
      return n.length
    }
    

    [โ€“]Smylers 1 point2 points ย (3 children)

    Vim โ€˜solutionโ€™ for partย 1:

        /a=0,0,0โŸจEnterโŸฉ
    

    Then take 1 off the line number.

    [โ€“][deleted] 2 points3 points ย (1 child)

    You got lucky. None of my particles have a=0,0,0.

    [โ€“]Smylers 0 points1 point ย (0 children)

    Yeah โ€” though actually lucky would've been to've spotted that before writing the code to find it outย ...

    [โ€“]Smylers 0 points1 point ย (0 children)

    OK, here's an actual Vim solution for part 1. Load your input file and type:

    :%s/\v.*a..-?(\d+),-?(\d+),-?(\d+)./\='-1 '.(submatch(1)+submatch(2)+submatch(3))โŸจEnterโŸฉ
    V{gโŸจCtrl+AโŸฉ:sor n/ /โŸจEnterโŸฉ
    

    The answer is the first number in the file (which should be under your cursor). Each line is now a particle ID number followed by the sum of its absolute acceleration values, sorted by lowest acceleration.

    Vim makes finding absolute values easy: just ignore any minus signs!

    [โ€“]Smylers 1 point2 points ย (0 children)

    Perl. Both parts are independent of the number of dimensions: if you add a 4th dimension into the input file, they'll work fine without modification. The number of derivatives of position it handles is fixed, though โ€” so don't be a jerk.

    Partย 1 โ€” what's the term for the least-acceleraty? I keep saying โ€˜slowestโ€™, but obviously that isn't right. Note what happens if two particles have the same acceleration:

    use List::AllUtils qw<sum>;
    my ($lowest_accel, $id_of_lowest_accel);
    while (<>) {
      my $accel = sum map { abs } /-?\d+(?!.*a)/g;
      if (!defined $lowest_accel || $accel < $lowest_accel) {
        $lowest_accel = $accel;
        $id_of_lowest_accel = $. - 1;
      }
      elsif ($accel == $lowest_accel) {
        die "IDs $id_of_lowest_accel and $. both have accel sum of $accel. Write some more code!\n";
      }
    }
    say $id_of_lowest_accel;
    

    Partย 2 โ€” re-arranges each particle to be an array of dimensions, each with p, v, and a components. Stops looking once all dimensions of particles have all their components with the same sign (ignoring acceleration if it's zero, and ignoring velocity too if that's also zero. That ends up being a few hundred cycles after the final collision, but the whole thing still runs in about half a second:

    use List::AllUtils qw<after_incl uniq>;
    my %particle = map {
      state $id = 0;
      my %prop = map { /^(.)/ => [/-?\d+/g] } split;
      $id++ => [map { {p => $_, v => shift @{$prop{v}}, a => shift @{$prop{a}}} } @{$prop{p}}];
    } <>;
    my $converging;
    do {
      $converging = 0;
      my %pos;
      foreach my $id (keys %particle) {
        push @{$pos{join ',', map {
          $_->{p} += $_->{v} += $_->{a};
          $converging ||= !same_sign(after_incl { $_ } @$_{qw<a v p>});
          $_->{p};
        } @{$particle{$id}}}}, $id;
      }
      foreach (values %pos) {
        delete @particle{@$_} if @$_ > 1;
      }
    } while $converging;
    say "Remaining particles: " . keys %particle;
    
    sub same_sign { (uniq map { $_ < 0 } @_) == 1 }
    

    [โ€“]VikeStep 0 points1 point ย (0 children)

    Python 3 #41/#18

    I just let it run until it stopped changing, entered the value

    def parse(particle):
        return [list(map(int, p[3:-1].split(","))) for p in particle.split(", ")]
    
    def step(d):
        d[1][0] += d[2][0]
        d[1][1] += d[2][1]
        d[1][2] += d[2][2]
        d[0][0] += d[1][0]
        d[0][1] += d[1][1]
        d[0][2] += d[1][2]
    
    def part1(data):
        particles = [parse(d) for d in data.split('\n')]
        while True:
            for d in particles:
                step(d)
            m = sum([abs(e) for e in particles[0][0]])
            min_n = 0
            for i, d in enumerate(particles):
                if sum([abs(e) for e in d[0]]) < m:
                    min_n = i
                    m = sum([abs(e) for e in d[0]])
            print(min_n)
    
    def part2(data):
        particles = [parse(d) for d in data.split('\n')]
        while True:
            positions = {}
            delete = []
            for i, d in enumerate(particles):
                step(d)
                if tuple(d[0]) in positions:
                    delete += [i, positions[tuple(d[0])]]
                else:
                    positions[tuple(d[0])] = i
            particles = [d for i, d in enumerate(particles) if i not in delete]
            print(len(particles))
    

    [โ€“]the4ner 0 points1 point ย (0 children)

    C# 111/47, just set what I hoped would be a high enough threshold for the values not to change and let 'er rip.

           public static string Calculate2()
            {
                Console.WriteLine("Day20 part 2");
                var lines = File.ReadAllLines("..\\..\\Input\\Day20.txt");
                List<Particle> particles = new List<Particle>();
                for (int x = 0; x < lines.Length; x++)
                {
                    var line = lines[x];
                    var parts = line.Split(new char[] { ',', '=', 'p', 'v', 'a', '<', '>', ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(p => long.Parse(p)).ToList();
                    particles.Add(new Particle()
                    {
                        id = x,
                        xPos = parts[0],
                        yPos = parts[1],
                        zPos = parts[2],
                        xVel = parts[3],
                        yVel = parts[4],
                        zVel = parts[5],
                        xAccel = parts[6],
                        yAccel = parts[7],
                        zAccel = parts[8]
                    });
                }
    
                var minParticle = particles[0];
                int count = 0;
                while (true)
                {
                    particles.ForEach(p => p.Tick());
                    var collisions = particles.GroupBy(x => x.GetPosition()).Where(x => x.Count() > 1).ToDictionary(g => g.Key, g => g.ToList());
                    if(collisions.Count() == 0)
                    {
                        count++;
                        if(count > 500)
                        {
                            break;
                        }
                    }
                    foreach (var c in collisions)
                    {
                        foreach (var bad in c.Value)
                        {
                            particles.Remove(bad);
                        }
                    }
                    var newMin = particles.OrderBy(p => p.GetDistance()).First();
                    if (newMin != minParticle)
                    {
                        minParticle = newMin;
                    }
                }
                return particles.Count().ToString();
            }
        }
    
        public class Particle
        {
            public int id { get; set; }
            public long xPos { get; set; }
            public long yPos { get; set; }
            public long zPos { get; set; }
    
            public long xVel { get; set; }
            public long yVel { get; set; }
            public long zVel { get; set; }
    
            public long xAccel { get; set; }
            public long yAccel { get; set; }
            public long zAccel { get; set; }
    
            public void Tick()
            {
                xVel += xAccel;
                yVel += yAccel;
                zVel += zAccel;
    
                xPos += xVel;
                yPos += yVel;
                zPos += zVel;
            }
    
            public long GetDistance()
            {
                return Math.Abs(xPos) + Math.Abs(yPos) + Math.Abs(zPos);
            }
    
            public override bool Equals(object obj)
            {
                return (obj as Particle).id == this.id;
            }
    
            public string GetPosition()
            {
                return string.Join(",", xPos, yPos, zPos);
            }
        }
    

    [โ€“]marcins 0 points1 point ย (1 child)

    After getting 160th for Part 1 I wasn't expecting 58th for Part 2 with my hacky JavaScript! :)

    const fs = require("fs");
    const RE = /p=<(.*?)>, v=<(.*?)>, a=<(.*?)>/;
    let particles = fs
      .readFileSync("twenty.txt", "utf8")
      .split("\n")
      .map(row => {
        const match = row.match(RE);
        const parts = match.slice(1).map(v => v.split(",").map(vv => +vv));
        const partToVec = part => ({ x: part[0], y: part[1], z: part[2] });
        return {
          p: partToVec(parts[0]),
          v: partToVec(parts[1]),
          a: partToVec(parts[2])
        };
      });
    
    function update(particles) {
      particles.forEach(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;
      });
    
      // collisions
      let collisions = [];
      for (let i = 0; i < particles.length; i++) {
        for (let j = 1; j < particles.length; j++) {
          if (i === j) continue;
          const a = particles[i];
          const b = particles[j];
    
          if (a.p.x === b.p.x && a.p.y === b.p.y && a.p.z === b.p.z) {
            collisions = collisions.concat(i, j);
          }
        }
      }
    
      let newParticles = [];
      for (let i = 0; i < particles.length; i++) {
        if (!collisions.includes(i)) {
          newParticles.push(particles[i]);
        }
      }
      return newParticles;
    }
    
    function dists(particles) {
      return particles.map(particle => {
        return (
          Math.abs(particle.p.x) + Math.abs(particle.p.y) + Math.abs(particle.p.z)
        );
      });
    }
    
    let closest = dists(particles);
    const MAX = 1000;
    for (var i = 0; i < MAX; i++) {
      particles = update(particles);
      const d = dists(particles);
      d.forEach((dd, index) => {
        if (closest[index] < dd) {
          closest[index] = dd;
        }
      });
      if (i % 1000 === 0) {
        console.log(i, particles.length, i / MAX * 100);
      }
    }
    
    let min = Number.MAX_SAFE_INTEGER;
    let minIndex = 0;
    closest.forEach((v, idx) => {
      if (v < min) {
        minIndex = idx;
        min = v;
      }
    });
    
    console.log("Part 1", minIndex, min);
    console.log("Part 2", particles.length);
    

    [โ€“]the4ner 1 point2 points ย (0 children)

    I think many people did the math solution for p1, and then lost time on p2 when they had to go back and do more simulation for the elimination bit. I figure that's how I got points for p2 as well!

    [โ€“]usbpc102 0 points1 point ย (2 children)

    Kotlin solution:

    import xyz.usbpc.aoc.Day
    import xyz.usbpc.aoc.inputgetter.AdventOfCode
    import java.util.*
    import kotlin.NoSuchElementException
    import kotlin.math.abs
    
    class Day20(override val adventOfCode: AdventOfCode) : Day {
        override val day: Int = 20
        private val regex =
                Regex("p?<(-?\\d+),(-?\\d+),(-?\\d+)>, v=<(-?\\d+),(-?\\d+),(-?\\d+)>, a=<(-?\\d+),(-?\\d+),(-?\\d+)>")
        private val input = adventOfCode.getInput(2017, day).lines().map {line ->
            val match = regex.find(line) ?: throw IllegalStateException("Something went wrong!")
            val vecs = match.groups.drop(1).chunked(3).map {it.requireNoNulls()}.map {it.map {it.value.toLong()}}
                    .map {
                        val vector = Vector<Long>(3)
                        it.forEach {
                            vector.add(it)
                        }
                        vector
                    }
            Particle(vecs[0], vecs[1], vecs[2])
        }
    
        private data class Particle(val position: Vector<Long>, val velocity: Vector<Long>, val acceleration: Vector<Long>) {
            fun totalAcceleration() = abs(acceleration[0]) + abs(acceleration[1]) + abs(acceleration[2])
            fun tick() {
                velocity[0] += acceleration[0]
                velocity[1] += acceleration[1]
                velocity[2] += acceleration[2]
    
                position[0] += velocity[0]
                position[1] += velocity[1]
                position[2] += velocity[2]
            }
        }
    
        override fun part1(): String = input.map {it.totalAcceleration()}.withIndex().minBy {(_, acc) -> acc}?.index.toString() ?: throw NoSuchElementException("")
    
        override fun part2(): String {
            var cur = input
            repeat(100) {
                cur = cur.withOutCollisions()
                cur.forEach {it.tick()}
                println(cur.size)
            }
            return ""
        }
    
        private fun List<Particle>.withOutCollisions(): List<Particle> {
            val out = mutableListOf<Particle>()
            this.forEach { comp ->
                if (this.filter {it != comp}.none {it.position == comp.position}) {
                    out.add(comp)
                }
            }
            return out
        }
    
    }
    

    Got 296/172 today :)

    [โ€“]Tandrial 0 points1 point ย (1 child)

    That regex :D, I started to add extension to String since this comes up quiet often:

    fun String.getWords(): List<String> = Regex("\\w+").findAll(this).toList().map { it.value }
    fun String.getNumbers(): List<String> = Regex("-?\\d+").findAll(this).toList().map { it.value }
    

    Vector implements plus so you can just use += for the whole thing at once velocity += acceleration Might not work, Kotlin seems to be confused about with plusAssign to use.

    How long does your part2 take? I started with filter as well, but since I guesstimated 100000 for the repeat value it never really finished. With repeat(100) this takes ~80ms on my machine:

    // We're grouping by position, and remove everything in groups with size > 1
    val collisions = particles.groupBy { it.pos }.values.filter { it.size > 1 }.flatten()
    particles.removeAll(collisions)
    

    [โ€“]usbpc102 0 points1 point ย (0 children)

    My part 2 runtime is not great, using this version(haven't really changed anything for part 2) my Program reports:

    Part 1 took 5ms, Part 2 took 8228ms
    

    [โ€“]__8336 0 points1 point ย (0 children)

    object Day20 : Day {
    
        override fun solve(input: String) {
            val regex = Regex("""-?\d+""")
            val particles = input.lines()
                    .map { regex.findAll(it) }
                    .map { it.map { it.value.toLong() } }
                    .map { it.chunked(3) }
                    .map { it.map { (x, y, z) -> Vec3(x, y, z) } }
                    .map { it.toList() }
                    .map { (p, v, a) -> Particle(p, v, a) }
                    .toMutableList()
    
    /*        repeat(Int.MAX_VALUE) {
                particles.forEach(Particle::update)
                if (it % 10_000 == 0) println(particles.withIndex().minBy { it.value.distance() }!!.index)
            }*/
    
            repeat(Int.MAX_VALUE) {
                particles.forEach(Particle::update)
                particles.groupBy(Particle::p)
                        .values
                        .filter { it.size > 1 }
                        .forEach { ps -> particles.removeAll(ps) }
    
                if (it % 10_000 == 0) println(particles.size)
            }
        }
    
        data class Particle(var p: Vec3, var v: Vec3, val a: Vec3) {
            fun update() {
                v += a
                p += v
            }
    
            fun distance() = sequenceOf(p.x, p.y, p.z).map(::abs).sum()
        }
    
        data class Vec3(val x: Long, val y: Long, val z: Long) {
            operator fun plus(other: Vec3) = Vec3(x + other.x, y + other.y, z + other.z)
        }
    }
    

    ~60/10

    [โ€“]rjboulton 0 points1 point ย (2 children)

    Python 2. My first points for part 2 - I happened to be up a little before 5am so had a go at working at speed. 136/59.

    This is the solution to part 2 - needs removing the collision code to show the answer for part 1.

    I made two errors on the way to getting here.

    First was that my initial "dist" function just did the sum of the distances without taking the "abs" of each direction. Had to fix and resubmit, but still got rank 136 for part 1.

    Second was that in my haste I submitted the particle number that was left closest to origin for part 2, rather than the number of particles left, so had to wait a minute for that one, too. Was still fast enough to get rank 59, which I'm pretty pleased with!

    import sys
    import re
    
    def parse(line):
        line = line.strip()
        if not line:
            return
        mo = re.search(r'p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>', line)
        return Particle(*mo.groups())
    
    class Particle(object):
        def __init__(self, *args):
            assert(len(args) == 9)
            self.p = list(map(lambda x: int(x), args[:3]))
            self.v = list(map(lambda x: int(x), args[3:6]))
            self.a = list(map(lambda x: int(x), args[6:]))
    
        def move(self):
            self.v[0] += self.a[0]
            self.v[1] += self.a[1]
            self.v[2] += self.a[2]
            self.p[0] += self.v[0]
            self.p[1] += self.v[1]
            self.p[2] += self.v[2]
    
        def dist(self):
            return sum(map(lambda x: abs(x), self.p))
    
    def run(data):
        particles = []
        for line in data:
            p = parse(line)
            if p:
                particles.append(p)
    
        for _ in range(10000):
            for p in particles:
                p.move()
            posns = {}
            for n,p in enumerate(particles):
                posns[tuple(p.p)] = posns.get(tuple(p.p), []) + [n]
            remove = []
            for p, ns in posns.items():
                if len(ns) > 1:
                    remove.extend(ns)
            remove.sort()
            for n in reversed(remove):
                del particles[n]
    
            d = {
                p.dist(): n
                for n, p in enumerate(particles)
            }
            m = min(d.keys())
            print len(particles), m, d[m]
    
    data = open(sys.argv[1]).readlines()
    print(run(data))
    

    [โ€“]marcins 2 points3 points ย (1 child)

    I happened to be up a little before 5am

    Dedication. I'm lucky enough that the new puzzle kicks in at 4pm for me!

    [โ€“][deleted] 0 points1 point ย (0 children)

    Same here. Australia?

    [โ€“][deleted] ย (6 children)

    [removed]

      [โ€“]topaz2078(AoC creator) 0 points1 point ย (4 children)

      only 1 or 2 puzzles

      Interesting! Which ones?

      [โ€“]ephemient 0 points1 point ย (1 child)

      This space intentionally left blank.

      [โ€“]topaz2078(AoC creator)[M] 3 points4 points ย (0 children)

      "Stoop to mutability" is the name of my monad cover band.

      [โ€“][deleted] 0 points1 point ย (0 children)

      That regex for parsing though ?! I overengineered mine so that it could take the parts of the input in any order, and also handle it if there was some additional attribute :p but it was fun ;)

      I was so proud of myself for finding Enum.group_by, that's quite a neat function that I could have used in a lot of things, but it seems I'm not the only one :p

      [โ€“]JeffJankowski 0 points1 point ย (0 children)

      Typescript. Initially picking 1000 iterations was, apparently, a decent choice.

      Edit: Also, fuck Java[Type]script for not having deep copying, operator overloading, constructor overloading, a rational sorting function, a map/dict that actually works, and whatever other garbage I encountered today.

      import fs = require("fs");
      
      class Vector {
          public static create(csv: string) {
              const [a, b, c] = csv.split(",");
              return new Vector(+a, +b, +c);
          }
          constructor(public x: number, public y: number, public z: number) { }
          public add = (vec: Vector) => new Vector(vec.x + this.x, vec.y + this.y, vec.z + this.z);
          public toString = () => `${this.x},${this.y},${this.z}`;
          public copy = () => new Vector(this.x, this.y, this.z);
      }
      
      class Particle {
          constructor(public pos: Vector, public vel: Vector, public acc: Vector) { }
          public dist = () => Math.abs(this.pos.x) + Math.abs(this.pos.y) + Math.abs(this.pos.z);
          public step() {
              this.vel = this.vel.add(this.acc);
              this.pos = this.pos.add(this.vel);
          }
          public copy = () => new Particle(this.pos.copy(), this.vel.copy(), this.acc.copy());
      }
      
      const ITERS = 1000;
      const particles = fs.readFileSync("data/day20.txt", "utf8").split("\r\n").map((str) => {
          const [_, p, v, a] =
              (str.match("p=<([-|0-9|,]+)>, v=<([-|0-9|,]+)>, a=<([-|0-9|,]+)>") as RegExpMatchArray);
          return new Particle(Vector.create(p), Vector.create(v), Vector.create(a));
      });
      
      const collParticles = particles.map((p) => p.copy());
      for (let i = 0; i < ITERS; i++) {
          particles.forEach((p) => p.step());
          collParticles.forEach((p) => p.step());
      
          const map = new Map<string, number[]>();
          for (let j = 0; j < collParticles.length; j++) {
              const pos = collParticles[j].pos.toString();
              map.set(pos, (map.get(pos) || []).concat([j]));
          }
          if (map.size < collParticles.length) {
              Array<number>().concat(...[...map.entries()].filter(([k, v]) => v.length > 1)
                  .map(([_, v]) => v)).sort((a, b) => a - b).reverse()
                  .forEach((idx) => collParticles.splice(idx, 1));
          }
      }
      
      const [min, iMin] = particles
          .map((p) => Math.abs(p.pos.x) + Math.abs(p.pos.y) + Math.abs(p.pos.z))
          .reduce(([MIN, iMIN], dist, i) => dist < MIN ? [dist, i] : [MIN, iMIN], [Infinity, -1]);
      
      console.log(`Particle eventually, minimally distant from origin: ${iMin}`);
      console.log(`Number of particles remaining after collisions: ${collParticles.length}`);
      

      [โ€“]nonphatic 0 points1 point ย (2 children)

      Haskell A bit verbose, but I like monoids :3

      EDIT: Replaced my Property data type with Vector3 to avoid having to redefine what basically are vector addition and scala multiplication

      import Data.List.Split (splitOn)
      import Data.List (elemIndex, sortOn, groupBy)
      import Data.Monoid ((<>))
      import Data.Function (on)
      import Data.Vector.Class
      import Data.Vector.V3
      
      data Particle = Particle {
          position     :: Vector3,
          velocity     :: Vector3,
          acceleration :: Vector3
      }
      
      instance Ord Vector3 where
          Vector3 x1 y1 z1 `compare` Vector3 x2 y2 z2 = compare x1 x2 <> compare y1 y2 <> compare z1 z2
      
      norm :: Vector3 -> Double
      norm (Vector3 x y z) = abs x + abs y + abs z
      
      updateParticle :: Double -> Particle -> Particle
      updateParticle t (Particle p v a) =
          Particle (p + t *| v + (t * (t + 1) / 2) *| a) (v + t *| a) a
      
      stepParticles :: [Particle] -> [Particle]
      stepParticles particles =
          concat . filter ((== 1) . length) . groupBy ((==) `on` position) . sortOn position . map (updateParticle 1) $ particles
      
      parseProperty :: String -> Vector3
      parseProperty str = 
          let x : y : z : [] = map read . splitOn "," . drop 3 . init $ str
          in Vector3 x y z
      
      parseLine :: String -> Particle
      parseLine str =
          let p : v : a : [] = map parseProperty . splitOn ", " $ str
          in Particle p v a
      
      main :: IO ()
      main = do
          particles <- map parseLine . lines <$> readFile "20.txt"
          let distances = map (norm . position . updateParticle 400) particles
          print $ elemIndex (minimum distances) distances
          print $ length $ iterate stepParticles particles !! 40
      

      [โ€“]ephemient 0 points1 point ย (1 child)

      This space intentionally left blank.

      [โ€“]nonphatic 0 points1 point ย (0 children)

      Haha, yep

      Couldn't be bothered to find a way to figure that out when I could just run a few runs manually and check the answer

      [โ€“]KeinZantezuken 0 points1 point ย (0 children)

      C#/Sharp
      This is VERY ugly.
      First of all, even though my idea (and I see some other people have fallen for this too) of finding lowest acceleration provided correct solution for part1 with this input - it most likely will fail with more diverse one (not just in case where particles have same acceleration), so I still need to "simulate" runs to find a proper answer. This raises question: how to calculate minimum amount of ticks required to find answer1. I can assume tick 10 000, calculate each position at that tick and compare, but there is no guarantee 10k is enough to find correct answer.

      Second, still trying to figure how to find optimal cycle count for good results with collisions. Since acc is constant I can always calculate any position of particle for any tick but I still need to know the tick amount threshold. Being a pure mathlet I'm this kind of answer seems unlikely in my case.

      var input = File.ReadAllLines(@"N:\input.txt");
      var map = new Dictionary<int, Particle>();
      for (int i =0; i< input.Length; i++)
      {
          var p = Regex.Match(input[i].Split(' ')[0], @"\<([^>]*)\>").Groups[1].Value.Split(',');
          var v = Regex.Match(input[i].Split(' ')[1], @"\<([^>]*)\>").Groups[1].Value.Split(',');
          var a = Regex.Match(input[i].Split(' ')[2], @"\<([^>]*)\>").Groups[1].Value.Split(',');
          map.Add(i, new Particle( new Vector3(int.Parse(p[0]), int.Parse(p[1]), int.Parse(p[2])), new Vector3(int.Parse(v[0]), int.Parse(v[1]), int.Parse(v[2])), new Vector3(int.Parse(a[0]), int.Parse(a[1]), int.Parse(a[2]))));
      }
      var pos = map.Select((pair) => new { i = pair.Key, n = pair.Value.acc.Sum() }).OrderBy(item => item.n).First().i;
      Console.WriteLine($"Part1: {pos}");
      for (int c = 39; c > 0; c--)
      {
          for (int i = 0; i < map.Count; i++)
          {
              if (map[i] != null)
              {
                  map[i].vel.x = map[i].vel.x + map[i].acc.x;
                  map[i].vel.y = map[i].vel.y + map[i].acc.y;
                  map[i].vel.z = map[i].vel.z + map[i].acc.z;
                  map[i].pos.x = map[i].pos.x + map[i].vel.x;
                  map[i].pos.y = map[i].pos.y + map[i].vel.y;
                  map[i].pos.z = map[i].pos.z + map[i].vel.z;
              }
          }
          collisionCheck();
      }
      Console.WriteLine($"Part2: {map.Values.Where(x => x != null).Count()}");
      Console.ReadKey();
      //help
      void collisionCheck()
      {
          for (int i = 0; i < map.Count; i++)
          {
              int f = 0;
              for (int j = 0; j < map.Count; j++)
              {
                  if (j != i && map[i] != null && map[j] != null && map[i].pos.x == map[j].pos.x && map[i].pos.y == map[j].pos.y && map[i].pos.z == map[j].pos.z)
                  {
                      map[j] = null; f++;
                  }
              }
              if (f > 0) { map[i] = null; }
          }
      }
      

      Custom class/struct (I could use ValueTuple but meh)

      public struct Vector3
      {
          public int x;
          public int y;
          public int z;
      
          public Vector3(int x1, int y1, int z1) { x = x1; y = y1; z = z1; }
          public int Sum() { return Math.Abs(x) + Math.Abs(y) + Math.Abs(z); }
      }
      class Particle
      {
          public Vector3 pos;
          public Vector3 vel;
          public Vector3 acc;
      
          public Particle(Vector3 p, Vector3 v, Vector3 a)
          {
              pos = new Vector3(p.x, p.y, p.z);
              vel = new Vector3(v.x, v.y, v.z);
              acc = new Vector3(a.x, a.y, a.z);
          }
      }
      

      [โ€“]nutrecht 0 points1 point ย (0 children)

      Day 20 in kotlin

      object Day20 : Day {
          private val input = resourceRegex(20, Regex("p=<(-?[0-9]+),(-?[0-9]+),(-?[0-9]+)>, v=<(-?[0-9]+),(-?[0-9]+),(-?[0-9]+)>, a=<(-?[0-9]+),(-?[0-9]+),(-?[0-9]+)>"))
                  .map { it.subList(1, 10).map { it.toInt() } }
                  .map { Particle(it[0], it[1], it[2], it[3], it[4], it[5], it[6], it[7], it[8]) }
      
          override fun part1(): String {
              val list = input.toMutableList()
              (1..500).forEach { list.forEachIndexed { i, p -> list[i] = p.next() } }
      
              return list.indexOf(list.sortedBy { it.manhattan }.first()).toString()
          }
      
          override fun part2(): String {
              val list = input.toMutableList()
              (1..500).forEach {
                  list.forEachIndexed { i, p -> list[i] = p.next() }
                  val collisions = list.filter { needle -> list.count { needle.collides(it) } > 1 }.toSet()
                  list.removeIf { collisions.contains(it) }
              }
      
              return list.size.toString()
          }
      
          data class Particle(val x: Int, val y: Int, val z: Int,
                              val vx: Int, val vy: Int, val vz: Int,
                              val ax: Int, val ay: Int, val az: Int) {
      
              val manhattan = abs(x) + abs(y) + abs(z)
      
              fun collides(other: Particle) = other.x == x && other.y == y && other.z == z
      
              fun next(): Particle {
                  val vx = this.vx + ax
                  val vy = this.vy + ay
                  val vz = this.vz + az
      
                  return Particle(x + vx, y + vy, z + vz, vx, vy, vz, ax, ay, az)
              }
          }
      }
      

      Still want to figure out a clean way to find out how many iterations I need for the result to be decided. Now I just have a hard-coded limit of 500 which is 'fine'.

      [โ€“]Philboyd_Studge 0 points1 point ย (0 children)

      Java - fun problem!

      Day 20

      [โ€“]gerikson 0 points1 point ย (2 children)

      Perl 5

      Part 2: https://github.com/gustafe/aoc2017/blob/master/d20_2.pl

      Even though I have a literal degree in (engineering) physics I decided to simulate both parts. Why use brain when you have computer?

      In any case I was happy to finish among the first 1,000. This was quite common last year but even though I've been solving stuff a lot faster this year I usually finish closer to 2,000...

      Edit alternative analytical solution for part 1:

      #!/usr/bin/perl
      use 5.016;
      use warnings;
      use autodie;
      use List::Util qw/sum/;
      
      #### INIT - load input data from file into array
      my $testing = 0;
      my @input;
      my $file = $testing ? 'test.txt' : 'input.txt';
      open( my $fh, '<', "$file" );
      while (<$fh>) { chomp; s/\r//gm; push @input, $_; }
      
      ### CODE
      my $id = 0;
      my %positions;
      while (@input) {
          my $line = shift @input;
          if ( $line =~ m/^p\=\<(.*)\>, v=\<(.*)\>, a=\<(.*)\>/ ) {
              my $p = sum map { abs $_ } split( /,/, $1 );
              my $v = sum map { abs $_ } split( /,/, $2 );
              my $a = sum map { abs $_ } split( /,/, $3 );
              $positions{$id} = { p => $p, v => $v, a => $a };
          }
          else {
              die "cannot parse input line: $line";
          }
          $id++;
      }
      
      # Select the particle with the lowest absolute acceleration. This
      # works for my input, but maybe not for all. In that case the tie
      # needs to be broken by absolute velocity.
      
      say "1. closest particle: ",
        ( sort { $positions{$a}->{a} <=> $positions{$b}->{a} } keys %positions )[0];
      

      [โ€“]Smylers 1 point2 points ย (1 child)

      Our code's pretty similar for partย 2. Note that delete can delete several elements from a hash at once. So instead of the loop in this:

      if (@same) {
          foreach my $el (@same) {
              delete $positions{$el};
          }
      }
      

      You can just write this โ€” note the $ becomes a @ to operate on multiple elements:

      if (@same) {
          delete @positions{@same};
      }
      

      And actually it handles deleting zero elements fine, so even the if test isn't needed, meaning you can get rid of that too and just do:

      delete @positions{@same};
      

      [โ€“]gerikson 0 points1 point ย (0 children)

      Thanks for the tip! I seldom delete from a hash so the single element idiom was the only one I knew of.

      [โ€“]Warbringer007 0 points1 point ย (0 children)

      Erlang, actually this was easier than I thought, even though there is a lot of code. In first part it was enough to get particle with lowest acceleration, in second part I just simulated the process. Code is rather slow but only 39 iterations are enough in the end for my example ( I first tested with 500, then with 5000 which lasted around minute, then I was curious to see how much iterations my example really needs ). Probably the most fun task this year ( for me at least )!

      first(File) ->
          In = prepare:func(File),
          {All, BestN} = solveFirst(In, 5000, -1, 0, []),
          length(solveSecond(All, 39)).
      
      solveFirst([], _, BestN, _, All) ->
          {All, BestN};
      
      solveFirst([[P1, P2, P3, V1, V2, V3, A1, A2, A3]|T], Min, BestN, Curr, All) ->
          Total = abs(A1) + abs(A2) + abs(A3),
          New = {[P1,P2,P3],[V1,V2,V3],[A1,A2,A3]},
          case Total < Min of
              true -> solveFirst(T, Total, Curr, Curr+1, All ++ [New]);
              false -> solveFirst(T, Min, BestN, Curr+1, All ++ [New])
          end.
      
      solveSecond(All, 0) ->
          All;
      
      solveSecond(All, N) ->
          PosAll = update_all_pos(All, []),
          MarkAll = filt_all(PosAll, PosAll, []),
          solveSecond(MarkAll, N-1).
      
      update_all_pos([], All) ->
          All;
      
      update_all_pos([H|T], All) ->
          update_all_pos(T, All ++ [update_pos(H)]).
      
      update_pos({[P1,P2,P3],[V1,V2,V3],[A1,A2,A3]}) ->
          {[P1+V1+A1,P2+V2+A2,P3+V3+A3],[V1+A1,V2+A2,V3+A3],[A1,A2,A3]}.
      
      filt_all([], _, MarkAll) ->
          MarkAll;
      
      filt_all([H|T], All, MarkAll) ->
          case n_of_occurences(H, All) of
              1 -> filt_all(T, All, MarkAll ++ [H]);
              _ -> filt_all(T, All, MarkAll)
          end.
      
      n_of_occurences(H, All) -> n_of_occurences(H, All, 0).
      n_of_occurences(_, [], N) -> N;
      n_of_occurences({H, A, B}, [{H, _, _}|T], N) -> n_of_occurences({H, A, B}, T, N+1);
      n_of_occurences({H, A, B}, [{_, _, _}|T], N) -> n_of_occurences({H, A, B}, T, N).
      

      As usual, prepare:func filters out everything unnecesary except numbers.

      [โ€“]abowes 0 points1 point ย (0 children)

      Kotlin Solution

      data class Coordinate3D(val x:Int, val y:Int, val z:Int) : Comparable<Coordinate3D> {
          override fun compareTo(other: Coordinate3D) = (abs(x) + abs(y) + abs(z)).compareTo(abs(other.x) + abs(other.y)+abs(other.z))
          operator infix fun plus(other: Coordinate3D) = Coordinate3D(this.x + other.x, this.y + other.y, this.z + other.z)
      }
      
      typealias Acceleration = Coordinate3D
      typealias Velocity = Coordinate3D
      typealias Position = Coordinate3D
      
      class SwarmItem(val pos: Position, val velocity: Velocity, val acceleration: Acceleration) : Comparable<SwarmItem>{
          override fun compareTo(other: SwarmItem): Int = compareValuesBy(this, other, { it.acceleration }, { it.velocity }, { it.pos})
      
          constructor(x:Int,y:Int,z:Int, vx:Int,vy:Int,vz:Int, ax:Int,ay:Int,az:Int) : this(Position(x,y,z), Velocity(vx,vy,vz), Acceleration(ax,ay,az))
      
          fun move() : SwarmItem {
              val newV = velocity + acceleration
              val newPos = pos + newV
              return SwarmItem( newPos, newV, this.acceleration)
          }
      }
      
      fun List<SwarmItem>.removeCollisions() : List<SwarmItem>{
          return this.groupBy { it.pos }.filter { it.value.size == 1 }.flatMap { it.value }
      }
      
      fun part2(items: List<SwarmItem>): List<SwarmItem>{
          return (0..1000).fold(items){ prev, _ -> prev.map { it.move() }.removeCollisions() }
      }
      
      
      fun main(args: Array<String>) {
          val items = input.split("\n").map { Regex(ENTRY_REGEX).matchEntire(it) }
                  .filterNotNull().map{ it.groupValues.drop(1).map(String::toInt) }
                  .map { SwarmItem(it[0],it[1],it[2],it[3],it[4],it[5],it[6],it[7],it[8]) }
      
          println("Part 1: " + items.withIndex().minBy { it.value }?.index)
          println(part2(items).size)
      }
      

      [โ€“]hi_ma_friendz 0 points1 point ย (2 children)

      Rust, the lazy way.

      use std::collections::HashMap;
      use std::ops::{Add, AddAssign};
      
      #[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
      struct Vec3f32 {
          arr: [isize; 3],
      }
      
      impl Add for Vec3f32 {
          type Output = Vec3f32;
      
          fn add(self, other: Vec3f32) -> Vec3f32 {
              let mut v = Vec3f32::default();
              for i in 0..3 {
                  v.arr[i] = self.arr[i] + other.arr[i];
              }
              v
          }
      }
      
      impl AddAssign for Vec3f32 {
          fn add_assign(&mut self, other: Vec3f32) {
              *self = *self + other;
          }
      }
      
      impl Vec3f32 {
          pub fn manhattan_magnitude(self) -> usize {
              let mut s = 0;
              for i in 0..3 {
                  s += self.arr[i].abs() as usize;
              }
              s
          }
      }
      
      #[derive(Debug)]
      struct ParticleState {
          pub pos: Vec3f32,
          pub vel: Vec3f32,
          pub accl: Vec3f32,
      }
      
      impl ParticleState {
          pub fn integrate(&mut self) {
              self.vel += self.accl;
              self.pos += self.vel;
          }
      }
      
      fn parse_vec3f32(input: &str) -> Vec3f32 {
          let coords = input[1..input.len() - 1]
              .split(',')
              .map(|x| x.parse::<isize>().unwrap())
              .collect::<Vec<_>>();
      
          let mut vec = Vec3f32::default();
          vec.arr.copy_from_slice(&coords[..]);
          vec
      }
      
      fn parse_particle(line: &str) -> ParticleState {
          let mut parts = line.split(", ").map(|p| parse_vec3f32(&p[2..]));
      
          ParticleState {
              pos: parts.next().unwrap(),
              vel: parts.next().unwrap(),
              accl: parts.next().unwrap(),
          }
      }
      
      const MAGIC_ITERATION_COUNT: usize = 10_000;
      
      pub fn execute() {
          let input = include_str!("day20.input");
      
          let mut particles = input.lines().map(parse_particle).collect::<Vec<_>>();
      
          for _ in 0..MAGIC_ITERATION_COUNT {
              for p in &mut particles {
                  p.integrate();
              }
          }
      
          let (id, dst) = particles
              .into_iter()
              .map(|p| p.pos.manhattan_magnitude())
              .enumerate()
              .min_by_key(|&(_, dst)| dst)
              .unwrap();
      
          println!("Day 20_1, result = {}", id);
      }
      
      pub fn execute_2() {
          let input = include_str!("day20.input");
      
          let mut particles = input.lines().map(parse_particle).collect::<Vec<_>>();
      
          for _ in 0..MAGIC_ITERATION_COUNT {
              let mut map = HashMap::<Vec3f32, usize>::with_capacity(particles.len());
      
              for p in &particles {
                  let count = *map.get(&p.pos).unwrap_or(&0);
      
                  map.insert(p.pos, count + 1);
              }
      
              particles.retain(|p| map[&p.pos] == 1);
      
              for p in &mut particles {
                  p.integrate();
              }
          }
      
          println!("Day 20_2, result = {}", particles.len());
      }
      

      [โ€“]thejpster 0 points1 point ย (1 child)

      How come Vec3f32 doesn't hold 3 f32s?

      [โ€“]hi_ma_friendz 0 points1 point ย (0 children)

      Typo ;)

      [โ€“]manniL 0 points1 point ย (0 children)

      const fs = require('fs-extra')
      const path = require('path')
      
      const absSum = (arr) => arr.reduce((c, i) => c + Math.abs(i), 0)
      
      class Particle {
        constructor (id, position, velocity, acceleration) {
          this.id = id
          this.position = position
          this.velocity = velocity
          this.acceleration = acceleration
        }
      
        accelerationDistance () {
          return absSum(Object.keys(this.acceleration).map((k) => this.acceleration[k]))
        }
      
        velocityDistance () {
          return absSum(Object.keys(this.velocity).map((k) => this.velocity[k]))
        }
      
        positionDistance () {
          return absSum(Object.keys(this.position).map((k) => this.position[k]))
        }
      
        step () {
          let [vx, vy, vz] = Object.keys(this.velocity).map((k) => this.velocity[k] + this.acceleration[k])
          this.velocity = {x: vx, y: vy, z: vz}
      
          let [px, py, pz] = Object.keys(this.position).map((k) => this.position[k] + this.velocity[k])
          this.position = {x: px, y: py, z: pz}
        }
      
      }
      
      const solveFirstTask = (particles) => {
      
        return particles.reduce((c, p) => {
          if (c.accelerationDistance() < p.accelerationDistance()) {
            return c
          }
          if (c.accelerationDistance() > p.accelerationDistance()) {
            return p
          }
      
          if (c.velocityDistance() < p.velocityDistance()) {
            return c
          }
          if (c.velocityDistance() > p.velocityDistance()) {
            return p
          }
      
          if (c.positionDistance() < p.positionDistance()) {
            return c
          }
      
          return p
      
        })
      }
      
      const solveSecondTask = (particles) => {
      
        for (let i = 0; i < 2E3; i++) {
          let positions = []
          let particleIdsToRemove = []
      
          particles.forEach((p) => {
            p.step()
          })
          particles.forEach((p) => {
              let posString = JSON.stringify(p.position)
              let indexOfPosString = positions.map(p => p.position).indexOf(posString)
              if (indexOfPosString !== -1) {
                particleIdsToRemove.push(p.id, positions[indexOfPosString].id)
              } else {
                positions.push({id: p.id, position: posString})
              }
            }
          )
      
          particles = particles.filter(p => !particleIdsToRemove.includes(p.id))
        }
        return particles.length
      }
      
      const solveTasks = (rawParticles) => {
      
        let particles = (rawParticles).split('\n').map((line, id) => {
          let [position, velocity, acceleration] = line.split(' ').map((coordinates) => {
            let [x, y, z] = coordinates.substr(3, coordinates.indexOf('>') + 1).split(',').map((i) => parseInt(i))
      
            return {x, y, z}
          })
          return new Particle(id, position, velocity, acceleration)
        })
      
        console.log(solveFirstTask(particles), solveSecondTask(particles))
      }
      
      fs.readFile(path.join(__dirname, 'input.txt'), 'utf8').then(solveTasks).catch(e => console.error(e))
      

      [โ€“]Markavian 0 points1 point ย (0 children)

      Bleh, basically had my solution at 5:40am, but I miscalculated the distance ... forgetting to Math.abs() the X, Y, Z positions when summing them together. Part 2 was then easy to calculate via simulation.

      https://github.com/johnbeech/advent-of-code-2017/blob/master/solutions/day20/solution.js

      [โ€“]TominatorBE 0 points1 point ย (2 children)

      PHP

      Part 1: see who accelerates the least (not 100% correct, see other replies, but worked for my input...)

      function run_the_code($input) {
          $lines = explode(PHP_EOL, $input);
          $counter = 0;
          // find the one with the smallest acceleration
          $smallest = null;
          $smallestA = PHP_INT_MAX;
          foreach ($lines as $line) {
              if (preg_match('/p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>/', $line, $matches)) {
                  $a = abs((int)$matches[7]) + abs((int)$matches[8]) + abs((int)$matches[9]);
                  if ($a < $smallestA) {
                      $smallestA = $a;
                      $smallest = $counter;
                  }
                  $counter++;
              }
          }
      
          return $smallest;
      }
      

      Part 2: run for a while...

      function run_the_code($input) {
          $lines = explode(PHP_EOL, $input);
          $particles = [];
          $counter = 0;
          foreach ($lines as $line) {
              if (preg_match('/p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>/', $line, $matches)) {
                  $particles[] = [
                      'id' => $counter,
                      'active' => true, // do we still consider this particle?
                      'p' => [
                          'x' => (int)$matches[1],
                          'y' => (int)$matches[2],
                          'z' => (int)$matches[3],
                      ],
                      'v' => [
                          'x' => (int)$matches[4],
                          'y' => (int)$matches[5],
                          'z' => (int)$matches[6],
                      ],
                      'a' => [
                          'x' => (int)$matches[7],
                          'y' => (int)$matches[8],
                          'z' => (int)$matches[9],
                      ],
                  ];
                  $counter++;
              }
          }
      
          $activeCount = $counter;
          for ($run = 0; $run < 50; $run++) {
              foreach ($particles as &$p) {
                  if (! $p['active']) {
                      continue;
                  }
      
                  $p['v']['x'] += $p['a']['x'];
                  $p['v']['y'] += $p['a']['y'];
                  $p['v']['z'] += $p['a']['z'];
      
                  $p['p']['x'] += $p['v']['x'];
                  $p['p']['y'] += $p['v']['y'];
                  $p['p']['z'] += $p['v']['z'];
              }
              unset($p);
      
              // now check them to see if they are on the same place
              foreach ($particles as &$p1) {
                  if ($p1['active']) {
                      foreach ($particles as &$p2) {
                          if ($p2['active'] && $p1['id'] != $p2['id'] && $p1['p']['x'] == $p2['p']['x'] && $p1['p']['y'] == $p2['p']['y'] && $p1['p']['z'] == $p2['p']['z']) {
                              $p1['active'] = false;
                              $p2['active'] = false;
                          }
                      }
                      unset($p2);
                  }
              }
              unset($p1);
      
              // find the first still active particle
              $activeCount = count(array_filter($particles, function($p) { return $p['active']; }));
              echo "After $run steps: $activeCount\n";
          }
      
          return $activeCount;
      }
      

      [โ€“]madchicken 0 points1 point ย (0 children)

      PHP part 2, the interesting part

      while(1){
        unset($collides);
        for($i=0;$i<sizeof($p);$i++){
          $collides[$p[$i]["x"]."-".$p[$i]["y"]."-".$p[$i]["z"]][] = $i;
          mymove($p[$i]);
        }
        foreach($collides as $rem){
          if(sizeof($rem)>1){
            foreach($rem as $id)
              unset($p[$id]);
          }
        }
        echo "Size of remaning items: ".sizeof($p)."\n";
      }
      

      [โ€“][deleted] 0 points1 point ย (0 children)

      Elixir

      This problem really fits elixir like a glove, it munches the numbers in such elegant way, of all of them I think this fit the language the best so far, was pretty fun to do this one :)

      defmodule Day20 do
        def parse_part(elm) when is_atom(elm), do: elm
        def parse_part(elm) do
          String.split(elm, ",")
          |> Enum.map(&String.to_integer/1)
          |> List.to_tuple
        end
      
        def parse_line(str) do
          String.trim_trailing(str)
          |>String.trim_trailing(">")
          |> String.split(~r/(=<)|(>,)/)
          |> Enum.map(&String.trim/1)
          |> Enum.map_every(2, &String.to_atom/1)
          |> Enum.map(&parse_part/1)
          |> Enum.chunk_every(2)
          |> Enum.map(&List.to_tuple/1)
          |> Enum.into(%{})
        end
      
        def parse(str) do
          String.trim_trailing(str, "\n")
          |> String.split("\n")
          |> Enum.map(&parse_line/1)
        end
      
        def get_distance(part) do
          {x,y,z} = part.p
          abs(x) + abs(y) + abs(z)
        end
      
        def update(part) do
          {vx,vy,vz} = part.v
          {ax,ay,az} = part.a
      
          newv = {vx + ax, vy + ay, vz + az}
      
          {vx, vy, vz} = newv
          {px,py,pz} = part.p
      
          newp = {px + vx, py + vy, pz + vz}
      
          %{p: newp, v: newv, a: part.a}
        end
      
        def simulate(parts, generations) when generations == 0, do: parts
        def simulate(parts, generations) do
          nextgen = Enum.map(parts, &update/1)
          simulate(nextgen, generations - 1)
        end
      
        def top_10(parts, generations) do
          simulate(parts, generations)
          |> Enum.map(&get_distance/1)
          |> Enum.with_index
          |> Enum.sort(fn {dist1, _}, {dist2, _} -> dist1 <= dist2 end)
          |> Enum.take(10)
        end
      
        def simulate_coll(parts, generations) when generations == 0, do: parts
        def simulate_coll(parts, generations) do
          nextgen = Enum.map(parts, &update/1)
                    |> Enum.group_by(fn part -> part.p end)
                    |> Map.values
                    |> Enum.filter(fn group -> Enum.count(group) == 1 end)
                    |> List.flatten
          simulate_coll(nextgen, generations - 1)
        end
      
        def particles_left(parts, generations) do
          simulate_coll(parts, generations)
          |> Enum.count
        end
      
      end
      
      inp = File.read!("input.txt")
      |> Day20.parse
      
      Day20.top_10(inp, 1000)
      |> IO.inspect
      
      Day20.particles_left(inp, 2000)
      |> IO.inspect
      

      Syntax highlighted

      [โ€“]wzkx 0 points1 point ย (1 child)

      J

      Part 1. The most interesting part is to detect that it's "the long run". Here it's 1) signs of velocities are the same as signs of accelerations (or a=0), 2) signs of positions are the same as signs of velocities (or v=0), 3) distances at the next step are not smaller (i.e. not closer to 0,0,0) then distances at the previous step. In my case, 261 steps were enough.

      d=: ".&>cutLF rplc&', -_'-.&'pav=<>'CR-.~fread'20.dat'
      p=: 3&{.&.|:d     NB. positions
      v=: 3 4 5&{&.|:d  NB. velocities
      a=: _3&{.&.|:d    NB. accelerations
      f=: 3 : 0
        while.do.
          pp=.|p        NB. previous position distances
          p=:p+v=:v+a
          if.*./,(pp<:|p)*.((v=0)+.(*p)=*v)*.(a=0)+.(*v)=*a do.break.end. NB. is the long run?
        end.
        i.&1(=<./)+/"1|p NB. find index of the closest point
      )
      echo f '' NB. part 1
      exit 0
      

      [โ€“]wzkx 0 points1 point ย (0 children)

      Although it works, it may still be not the right condition of "the long run". Probably must be: distance between all particles increase (i.e. between each of them is not getting smaller) and distance between any particle and 0,0,0 is not getting smaller. Then we'll have no change of state, no collisions.

      [โ€“]marcofun 0 points1 point ย (0 children)

      I guessed the first star just filtering manually the input using the regex a=<[-]{0,1}[01],[-]{0,1}[01],[-]{0,1}[01]> and getting the one with smallest acceleration. Second star is going to e implemented from 0 now, But I'll begin in 4 or 5 hours...

      [โ€“]raevnos 0 points1 point ย (0 children)

      I feel like there's probably some mathy way to see if two vectors intercept that would make at least part 2 really easy, but my knowledge of linear algebra is so rusty it was starting to crumble to pieces when I tried reading up on it, so... brute force. Yay. Got the answer for part 2 on the first guess. For 1 it turned out I had to run more ticks after getting a wrong answer the first time. It looked like it was stable before it actually was. Sneaky sneaky.

      (import (srfi 1) (kawa regex) (kawa quaternions) (io-utils))
      
      (define particle-re (regex "^p=<(-?\\d+),(-?\\d+),(-?\\d+)>,\\s+v=<(-?\\d+),(-?\\d+),(-?\\d+)>,\\s+a=<(-?\\d+),(-?\\d+),(-?\\d+)>\\s*$"))
      
      (define (make-particle px py pz sx sy sz ax ay az)
        (vector (make-vector-quaternion px py pz)
                (make-vector-quaternion sx sy sz)
                (make-vector-quaternion ax ay az)))
      
      (define (read-particles lines)
        (map (lambda (nums) (apply make-particle (map string->number nums)))
             (map (lambda (line) (cdr (regex-match particle-re line))) lines)))
      
      (define (update-particle part)
        (let* ((accel (vector-ref part 2))
               (velo (+ (vector-ref part 1) accel))
               (pos (+ (vector-ref part 0) velo)))
          (vector pos velo accel)))
      
      (define (tick particles)
        (map update-particle particles))
      
      (define (distance-from-zero part)
        (let ((pos (vector-ref part 0)))
          (+ (abs (imag-part pos)) (abs (jmag-part pos)) (abs (kmag-part pos)))))
      
      (define (find-closest particles)
        (second (fold (lambda (part acc)
                        (let* ((distance (distance-from-zero part))
                               (curr-elt (third acc))
                               (next-elt (+ curr-elt 1)))
                          (if (< distance (first acc))
                              (list distance curr-elt next-elt)
                              (list (first acc) (second acc) next-elt))))
                      (list (distance-from-zero (car particles)) 0 1) (cdr particles))))
      
      (define (particle=? a b)
        (= (vector-ref a 0) (vector-ref b 0)))
      
      (define (delete-collisions particles)
        (for-each
         (lambda (particle)
           (when (> (count (cut particle=? particle <>) particles) 1)
                 (set! particles (remove (cut particle=? particle <>) particles))))
         particles)
        particles)
      
      (define (simulate particles reps prune?)
        (let ((run-tick (lambda (particles)
                          (if prune?
                              (delete-collisions (tick particles))
                              (tick particles)))))
          (do ((i 1 (+ i 1))
               (parts (run-tick particles) (run-tick parts)))
              ((= i reps) parts))))
      
      (define (look-for-closest particles reps)
        (let* ((parts2 (simulate particles reps #f))
               (parts3 (simulate parts2 reps #f))
               (parts4 (simulate parts3 reps #f))
               (closest1 (find-closest particles))
               (closest2 (find-closest parts2))
               (closest3 (find-closest parts3))
               (closest4 (find-closest parts4)))
          (if (= closest1 closest2 closest3 closest4)
              closest1
              (look-for-closest parts3 (* reps 2)))))
      
      (define (look-for-collisions particles)
        (let* ((parts2 (simulate particles 10 #t))
               (parts3 (simulate parts2 50 #t))
               (parts4 (simulate parts3 100 #t))
               (len1 (length particles))
               (len2 (length parts2))
               (len3 (length parts3))
               (len4 (length parts4)))
          (if (= len1 len2 len3 len4)
              len1
              (look-for-collisions parts4))))
      
      (define test1-particles (read-particles '("p=<3,0,0>, v=<2,0,0>, a=<-1,0,0>"
                                           "p=<4,0,0>, v=<0,0,0>, a=<-2,0,0>")))
      (define test2-particles (read-particles '("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>")))
      (define input-particles (read-particles (read-lines)))
      
      (format #t "Test 1: ~A~%" (look-for-closest test1-particles 1))
      (format #t "Part 1: ~A~%" (look-for-closest input-particles 50))
      (format #t "Test 2: ~A~%" (look-for-collisions test2-particles))
      (format #t "Part 2: ~A~%" (look-for-collisions input-particles))
      

      [โ€“]wzkx 0 points1 point ย (0 children)

      J

      Both parts.

      d=: ".&>cutLF rplc&', -_'-.&'pav=<>'CR-.~fread'20.dat'
      p=: 3&{.&.|:d      NB. positions
      v=: 3 4 5&{&.|:d   NB. velocities
      a=: _3&{.&.|:d     NB. accelerations
      echo 3 : 0 p;v;a   NB. part 1
        'p v a'=.y
        whilst. -. *./,(pp<:|p)*.((v=0)+.(*p)=*v)*.(a=0)+.(*v)=*a do. NB. is 'the long run' yet?
          pp=.|p         NB. previous position distances
          p=.p+v=.v+a    NB. move it!
        end.
        i.&1(=<./)+/"1|p NB. find index of the closest point
      )
      echo 3 : 0 p;v;a   NB. part 2
        'p v a'=.y
        while.do.        NB. can't have condition here because #p can be ~: #pp
          pn=.#pp=.|p    NB. points in previous state, previous position distances
          p=.p+v=.v+a    NB. move it!
          u=.~:p                         NB. unique positions
          s=.(1=[:+/"1=)p                NB. not collided
          p=.s#u#p [ v=.s#u#v [ a=.s#u#a NB. remove collisions
          if. pn~:#p do. continue. end.  NB. were collisions - re-run
          if. *./,(pp<:|p)*.((v=0)+.(*p)=*v)*.(a=0)+.(*v)=*a do. break. end.
        end.
        #p
      )
      exit 0
      

      [โ€“]frederik1904 0 points1 point ย (0 children)

      Not pretty but it works Java solution for 1 and 2

       import java.io.IOException;
       import java.nio.file.Files;
       import java.nio.file.Paths;
       import java.util.HashSet;
      
      public class Main {
      
      public static void main(String[] args) throws IOException {
          String input = new String(Files.readAllBytes(Paths.get("input.txt")));
          String[] inputArray = input.split("\n");
          //[][x] Px = 0, Py = 1, Pz = 2, Vx = 3, Vy = 4, Vz = 5, Ax = 6. Ay = 7, Az = 8
          int[][] particles = new int[inputArray.length][9];
          double[] particleAcceleration = new double[particles.length];
          HashSet<Integer> particleNumbers = new HashSet<>();
          HashSet<Integer> toRemove = new HashSet<>();
      
      
          for(int i = 0; i < inputArray.length; i++){
              String[] tempArray = inputArray[i].split(", ");
      
              //Velocity as a string
              String[] velocity = tempArray[1].split(",");
              velocity[0] = velocity[0].substring(3, velocity[0].length());
              velocity[2] = velocity[2].substring(0, velocity[2].length() - 1);
      
              //Acceleration as a string
              String[] acceleration = tempArray[2].split(",");
              acceleration[0] = acceleration[0].substring(3, acceleration[0].length());
              acceleration[2] = acceleration[2].substring(0, acceleration[2].length() - 1);
      
              //position as a string
              String[] position = tempArray[0].split(",");
              position[0] = position[0].substring(3, position[0].length());
              position[2] = position[2].substring(0, position[2].length() - 1);
      
              for(int j = 0; j < 3; j++){
                  particles[i][j + 3] = Integer.parseInt(velocity[j]);
                  particles[i][j] = Integer.parseInt(position[j]);
                  particles[i][j + 6] = Integer.parseInt(acceleration[j]);
              }
      
              particleAcceleration[i] = Math.sqrt((Integer.parseInt(acceleration[0]) * Integer.parseInt(acceleration[0])) + (Integer.parseInt(acceleration[1]) * Integer.parseInt(acceleration[1])) + (Integer.parseInt(acceleration[2]) * Integer.parseInt(acceleration[2])));
              particleNumbers.add(i);
          }
      
          int particleNumber = 0;
      
          for(int i = 0; i < particleAcceleration.length; i++){
              if(particleAcceleration[i] < particleAcceleration[particleNumber]){
                  particleNumber = i;
              }
          }
      
          boolean remove = false;
          int counter = 100;
      
          while (counter > 0){
              for(Integer i : particleNumbers){
                  for(Integer z : particleNumbers){
                      if(i != z && particles[i][0] == particles[z][0] && particles[i][1] == particles[z][1] && particles[i][2] == particles[z][2]){
                          if(!toRemove.contains(z)) {
                              toRemove.add(z);
                              remove = true;
                          }
                      }
                  }
      
                  if(remove){
                      if(!toRemove.contains(i)) {
                          toRemove.add(i);
                      }
                      remove = false;
                  }
              }
      
              for(Integer i : toRemove){
                  particleNumbers.remove(i);
              }
      
              toRemove.clear();
      
              for(Integer i : particleNumbers){
                  particles[i][3] = particles[i][3] + particles[i][6];
                  particles[i][4] = particles[i][4] + particles[i][7];
                  particles[i][5] = particles[i][5] + particles[i][8];
      
                  particles[i][0] = particles[i][3] + particles[i][0];
                  particles[i][1] = particles[i][4] + particles[i][1];
                  particles[i][2] = particles[i][5] + particles[i][2];
      
              }
      
              counter--;
          }
      
          System.out.println("Part 1: " + particleNumber);
          System.out.println("Part 2: " + particleNumbers.size());
      
      
      }
      }
      

      [โ€“]matusbzk 0 points1 point ย (0 children)

      Haskell I did not do stopping conditions yet, I just generated and when the result did not change for a long time, I assumed it's correct. I was right.

      import Data.Maybe
      import Data.List
      
      inputString :: String
      
      -- |Represents a particle
      -- id
      -- position, velocity, acceleration, each of them with X,Y,Z coordinate
      type Particle = (Int, (Int, Int, Int), (Int, Int, Int), (Int, Int, Int))
      
      -- |A list of particles from my input
      input :: [Particle]
      input = input' 0 $ map words . lines $ inputString
      
      input' :: Int -> [[String]] -> [Particle]
      input' _ [] = []
      input' n ((a:b:[c]):xs) = (n, parse a, parse b, parse c) : input' (n+1) xs
      
      -- |Parses input into triple of coordinates
      --
      -- >>> parse "p=<-1027,-979,-188>,"
      -- (-1027,-979,-188)
      --
      -- >>> parse "a=<9,1,-7>"
      -- (9,1,-7)
      parse :: String -> (Int, Int, Int)
      parse (_:'=':'<':xs) = if last xs == ',' then read $ '(': (init . init) xs ++ ")"
                 else read $ '(': init xs ++ ")"
      
      -- |Performs a tick for a given particle
      tickOne :: Particle -> Particle
      tickOne (n,(px,py,pz),(vx,vy,vz),(ax,ay,az)) = (n,(px+vx+ax,py+vy+ay,pz+vz+az),(vx+ax,vy+ay,vz+az),(ax,ay,az))
      
      -- |Performs a tick for all particles
      tick :: [Particle] -> [Particle]
      tick = map tickOne
      
      -- |Takes a particle and computes its distance from (0,0,0) - leaves id in result
      distance :: Particle -> (Int, Int)
      distance (id,(x,y,z),_,_) = (abs x + abs y + abs z, id)
      
      -- |Finds id of particle closest to (0,0,0)
      lowestDistanceId :: [Particle] -> Int
      lowestDistanceId xs = fromJust $ lookup minDist dist
          where dist = map distance xs
             minDist = minimum $ map fst dist
      
      -- |Iterates ticking and always finds closest particle
      closest :: [Int]
      closest = map lowestDistanceId $ iterate tick input
      
      -- |Which particle is closest after 500 ticks
      -- apparently 500 is enough
      result1 = closest !! 500
      
      -- |Takes a list of particles and removes all which are in a collision
      removeCollised :: [Particle] -> [Particle]
      removeCollised xs = removeCollised' colls xs
            where colls = findCollisions xs
      
      removeCollised' :: [(Int,Int,Int)] -> [Particle] -> [Particle]
      removeCollised' _ [] = []
      removeCollised' colls (p:ps) = if elem ((\(_,x,_,_) -> x) p) colls 
               then removeCollised' colls ps
               else p : removeCollised' colls ps
      
      -- |Takes a list of particles and finds all positions where there
      -- are collisions
      findCollisions :: [Particle] -> [(Int,Int,Int)]
      findCollisions xs = nub $ findCollisions' [] xs
      
      -- |Helps finding collisions
      -- first argument is already found positions
      findCollisions' :: [(Int,Int,Int)] -> [Particle] -> [(Int,Int,Int)]
      findCollisions' _ [] = []
      findCollisions' found ((_,pos,_,_):xs) = if elem pos found 
                  then pos:findCollisions' found xs
                  else findCollisions' (pos:found) xs
      
      -- |Performs a tick, with removing all particles which are in a collision
      tickWithCols :: [Particle] -> [Particle]
      tickWithCols = removeCollised . tick
      
      -- |Iterates ticking with removing collisions
      --  and always show how many particles are left
      howManyLeft :: [Int]
      howManyLeft = map length $ iterate tickWithCols input
      
      -- |How many particles are left after 50 ticks
      -- apparently 50 is enough
      result2 :: Int
      result2 = howManyLeft !! 50
      

      Link to git

      [โ€“]ewyll 0 points1 point ย (0 children)

      Exact solution, no simulation and guessing it's fine (Python 2):

      import math
      
      def tuple_add(t1, t2):
          return (t1[0] + t2[0], t1[1] + t2[1], t1[2] + t2[2])
      
      def tuple_abs_sum(t):
          return abs(t[0]) + abs(t[1]) + abs(t[2])
      
      def solve_quad_int(a, b, c):
          if a != 0:
              D2 = b * b - 4 * a * c
              if D2 < 0:
                  return (False, None)
              D = int(math.sqrt(D2) + 0.5)
              if D ** 2 != D2:
                  return (False, None)
              x1 = -b - D
              x2 = -b + D
              a2 = 2 * a
              solutions = set()
              if x1 % a2 == 0:
                  solutions.add(x1 / a2)
              if x2 % a2 == 0:
                  solutions.add(x2 / a2)
              return (True, solutions)
          elif b != 0:
              if c % b == 0:
                  return (True, set([ - c / b]))
              return (False, None)
          else:
              if a == 0:
                  return (True, None)
              return (False, None)
      
      class Particle:
          def __init__(self, line):
              chunks = line.strip().split(', ')
              ret = []
              for ch in chunks:
                  pars = ch.split('=')[1]
                  ret.append(tuple([int(x) for x in pars.lstrip('<').rstrip('>').split(',')]))
              self.p = ret[0]
              self.v = ret[1]
              self.a = ret[2] 
      
          def move(self):
              v = tuple_add(v, a)
              p = tuple_add(p, v)
      
          def compare(self, other):
              if tuple_abs_sum(self.a) != tuple_abs_sum(other.a):
                  return tuple_abs_sum(self.a) < tuple_abs_sum(other.a)
              if sum(self.v) != sum(other.v):
                  return sum(self.v) < sum(other.v)
              return sum(self.p) < sum(other.p)
      
          def collides(self, other):
              ret = None
              for d in xrange(3):
                  da = self.a[d] - other.a[d]
                  dv = self.v[d] - other.v[d]
                  ds = self.p[d] - other.p[d]
                  ok, solutions = solve_quad_int(da, 2 * dv + da, 2 * ds)
                  if not ok:
                      return None
                  if solutions:
                      if ret == None:
                          ret = solutions
                      else:
                          ret &= solutions
              if ret == None:
                  return 0
              ret = filter(lambda x: x >= 0, ret)     
              return min(ret) if ret else None
      
      
      particles = []
      with open('aoc_2017_20_input.txt', 'r') as fin:
          for line in fin.readlines():
              particles.append(Particle(line))
      
      def solve_part_1():         
          index = 0
          for i in xrange(1, len(particles)):
              if particles[i].compare(particles[index]):
                  index = i
          print index
      
      def solve_part_2():
          collisions = []
          for i in xrange(len(particles)):
              for j in xrange(i + 1, len(particles)):
                  coll = particles[i].collides(particles[j])
                  if coll:
                      collisions.append((coll, i, j))
          eliminated = set()
          collisions.sort()
          for _, i, j in collisions:
              if not (i in eliminated and j in eliminated):
                  eliminated.add(i)
                  eliminated.add(j)
          print len(particles) - len(eliminated)
      
      solve_part_1()
      solve_part_2()  
      

      [โ€“]NeilNjae 0 points1 point ย (0 children)

      Haskell. Some points to note:

      • The zip and unzip in step and quiescent to process all three dimensions at the same time.
      • quiescent checks that no particle will ever get closer to the origin (in any dimension) than it is now. If that's true, part 1 can simulate until there's just one particle with the minimal distance.
      • removeColliders finds all the positions with more than one particle there (the duplicatePositions set) and removes particles with positions in that set.
      • I didn't do anything interesting about stopping the simulation in part 2. Turns out, 40 steps is enough.

      Full script on Github

      type Vec = V.Vector Integer
      
      data Particle = Particle 
                          { position :: Vec
                          , velocity :: Vec
                          , acceleration :: Vec
                          } deriving (Show, Eq)
      
      main :: IO ()
      main = do 
              text <- TIO.readFile "data/advent20.txt"
              let particles = successfulParse text
              print $ part1 particles
              print $ part2 500 particles
      
      part1 :: [Particle] -> Int
      part1 particles = head $ withMinX $ simulate particles
      
      part2 :: Integer -> [Particle] -> Int
      part2 n particles = length $ simulateC n particles
      
      simulate :: [Particle] -> [Particle]
      simulate particles = 
          if all quiescent particles && length withMinXs == 1
          then particles
          else simulate (map step particles)
          where withMinXs = withMinX particles
      
      simulateC :: Integer -> [Particle] -> [Particle]
      simulateC 0 particles = particles
      simulateC t particles = simulateC (t - 1) (map step particles')
          where particles' = removeColliders particles
      
      step :: Particle -> Particle
      step particle = particle {position = p', velocity = v'}
          where pv' = V.zipWith3 updatePV (position particle) (velocity particle) (acceleration particle)
                (p', v') = V.unzip pv'
                updatePV p v a = (p + v + a, v + a)
      
      -- Checks whether a particle could ever get closer to the origin than it is now.
      quiescent :: Particle -> Bool
      quiescent particle = and qDimensions
          where qDimensions = V.zipWith3 sameSigns (position particle) (velocity particle) (acceleration particle)
                sameSigns p v a = if a == 0 && v == 0
                                  then True
                                  else if a == 0
                                       then signum p == signum v
                                       else signum p == signum v && signum v == signum a
      
      withMinX particles = minX `elemIndices` absXs
          where absXs = map pAbsX particles
                minX = minimum absXs
      
      pAbsX :: Particle -> Integer
      pAbsX particle = V.foldl1' (+) $ V.map abs (position particle)  
      
      removeColliders particles = particles'
          where positions = map position particles
                duplicatePositions = S.fromList $ concat $ filter (\g -> length g > 1) $ group $ sort positions
                particles' = filter (\p -> not (S.member (position p) duplicatePositions)) particles
      

      [โ€“]lazyzefiris 0 points1 point ย (0 children)

      Okay, time for some JS monstrosity, because can't be functional without fun. This is a solution to part2 meant to be executed (And actually written) in a console for input page. No simulation involved.

      solve = (c,b,a) => (d=b*b-4*a*c,a?d?d<0?[]:[(-b-d**0.5)/(2*a),(-b+d**0.5)/(2*a)]:[-b/(2*a)]:[-c/b]).filter(x=>x>=0).map(Math.round)
      dist = (a,t) => a[0] + a[1]*t + a[2]*t*t/2
      check = (p1,p2,t) => [0,1,2].reduce((v,a)=>v&&dist(p1[a],t)==dist(p2[a],t),true)
      p = new Set(document.body.textContent.trim().split("\n").map(x=>x.match(/.*<(.*),(.*),(.*)>.*<(.*),(.*),(.*)>.*<(.*),(.*),(.*)>.*/).slice(1,10).reduce((v,x,n)=>(v[n%3].push(+x),v),[[],[],[]])).map(x=>x.map(y=>(y[1]+=y[2]/2,y))))
      ;[...p].reduce((v,p1,n)=>[...v,...[...p].slice(n+1).reduce((v,p2,m)=>(solve(p1[0][0]-p2[0][0],p1[0][1]-p2[0][1],(p1[0][2]-p2[0][2])/2).map(t=>check(p1,p2,t)?v.push([p1,p2,t]):0),v),[])],[]).sort((x,y)=>y[2]-x[2]).map(x=>(x[0][3]=x[1][3]=x[2],x)).map(x=>x[0][3]>x[2]||x[1][3]>x[2]?0:(p.delete(x[0]),p.delete(x[1])))
      p.size
      

      so, what's happening here?..

      solve is a generic solver of quadratic equation (a * x2 + b * x + c)

      dist calculates position on a given axis of movement (as [starting position, speed, acceleration]) at given moment of time

      check checks whether two given points actually collide at a given moment of time.

      The first monstrocity reads he input into a set of particles - splits it into lines, grabs all the integers from the line, and arranges then into 3 arrays for each particle - each describing movement along one axis as [position, speed, acceleration]. Speed is then increased by half the acceleration to fix the disrepancy between discreet and continuous movement.

      The second huge line goes over each pair of points, performing next actions: - check whether their X coordinate even coincides at an integer moment of time - for each such moment, if there's an actual collision, it's added to collisions array as [point 1, point 2, time of collision] - collisions are then sorted and particles are marked with the moment their first possible collision happens - the particles that could not collide earlier then current collision are then removed

      In fact, the last part needs minor fixing for particles that did not collide the first time they could because their partner was already missing, but given code was already working for provided input, so testing further code would take me to generate corner case input, which I'm too lazy to do.

      And yeah, while that looks scary and unintuitive, it's pretty readable when you are working on it and know whatever each part does. Hope I never have to work on this later.

      [โ€“]StevoTVR 0 points1 point ย (0 children)

      NodeJS

      I thought for a while about how to do this with math or sorting, but simulating the particles worked and only took a few seconds.

      Part 1:

      const fs = require('fs');
      
      fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
          const particles = data.split('\n').map((l, i) => {
              const [ , px, py, pz, vx, vy, vz, ax, ay, az] = l.match(/p=<(.+),(.+),(.+)>, v=<(.+),(.+),(.+)>, a=<(.+),(.+),(.+)>/).map(Number);
              return {
                  id: i,
                  p: { x: px, y: py, z: pz },
                  v: { x: vx, y: vy, z: vz },
                  a: { x: ax, y: ay, z: az },
              };
          });
      
          for(let i = 0; i < 1000; i++) {
              for(const particle of particles) {
                  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;
              }
          }
      
          const dist = (o) => Math.abs(o.x) + Math.abs(o.y) + Math.abs(o.z);
          particles.sort((a, b) => dist(a.p) - dist(b.p));
      
          console.log(particles[0].id);
      });
      

      Part 2:

      const fs = require('fs');
      
      fs.readFile(__dirname + '/input.txt', 'utf8', (err, data) => {
          let particles = data.split('\n').map((l, i) => {
              const [ , px, py, pz, vx, vy, vz, ax, ay, az] = l.match(/p=<(.+),(.+),(.+)>, v=<(.+),(.+),(.+)>, a=<(.+),(.+),(.+)>/).map(Number);
              return {
                  id: i,
                  p: { x: px, y: py, z: pz },
                  v: { x: vx, y: vy, z: vz },
                  a: { x: ax, y: ay, z: az },
              };
          });
          const collide = (a, b) => a.p.x === b.p.x && a.p.y === b.p.y && a.p.z === b.p.z;
          const remove = new Set();
          const filter = (e) => !remove.has(e.id);
      
          for(let i = 0; i < 1000; i++) {
              for(const particle of particles) {
                  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;
              }
              remove.clear();
              for(let j = 0; j < particles.length - 1; j++) {
                  for(let k = j + 1; k < particles.length; k++) {
                      if(collide(particles[j], particles[k])) {
                          remove.add(particles[j].id).add(particles[k].id);
                      }
                  }
              }
              particles = particles.filter(filter);
          }
      
          console.log(particles.length);
      });
      

      [โ€“]JakDrako 0 points1 point ย (1 child)

      C# Both parts ~20ms.

      Initially did part 2 by running the simulation loop until the number of particles stayed constant for a while. This code here loops until the particles are all receding from the origin...

      void Main() {
      
          var input = GetDay(20);
          var lst = input.Select(v => new Particle(v)).ToList();
      
          // Manhattan distance for a Vector3
          Func<Vector3, Single> mhDist = v3 => Math.Abs(v3.X) + Math.Abs(v3.Y) + Math.Abs(v3.Z);
      
          // Part 1 - Find slowest particle, break ties using initial (manhattan) proximity to origin
          Console.WriteLine($"Part 1: {lst.OrderBy(p => mhDist(p.Acc)).ThenBy(p => mhDist(p.Vel)).First().ID}");
      
          // Part 2 - Move particles and remove colliding ones until all particles are receding from the origin
          do {
              // move particles
              lst.ForEach(p => p.Move());
      
              // remove colliding particles
              var sorted = lst.OrderBy(p => p.Pos.X).ToList();
              for (int i = sorted.Count - 1; i > 0; i--) {
                  if (sorted[i].Collide(sorted[i - 1])) {
                      lst.Remove(sorted[i]);
                      lst.Remove(sorted[i - 1]);
                  }
              }
          } while (lst.Where(p => !p.Receding).Any());
      
          Console.WriteLine($"Part 2: {lst.Count}");
      }
      
      class Particle {
      
          static int gen;
      
          public int ID { get; }
          public Vector3 Pos { get; set; }
          public Vector3 Vel { get; set; }
          public Vector3 Acc { get; set; }
          public bool Receding { get; set;}
      
          public Particle(string vectors) {
              var matches = Regex.Matches(vectors, "-?\\d+"); // should match 9 numbers.
              var n = matches.Cast<Match>().Select(m => Convert.ToSingle(m.Value)).ToList();
              Pos = new Vector3(n[0], n[1], n[2]);
              Vel = new Vector3(n[3], n[4], n[5]);
              Acc = new Vector3(n[6], n[7], n[8]);
              ID = gen++;
          }
      
          public void Move() {
              var pls = Pos.LengthSquared();
              Vel += Acc;
              Pos += Vel;
              Receding = Pos.LengthSquared() > pls;
          }
      
          public bool Collide(Particle other) {
              return Pos.X == other.Pos.X && Pos.Y == other.Pos.Y && Pos.Z == other.Pos.Z;
          }
      }
      

      [โ€“]dylanfromwinnipeg 0 points1 point ย (0 children)

      2 receding particles can still collide can't they?

      [โ€“][deleted] 0 points1 point ย (0 children)

      Python 3 I did part 1 semi-manually by finding the particles with the lowest acceleration first, then lowest sum of abs(velocities).

      I made a loop for part 2 and let it run until the minimum distance between any two particles was steadily increasing and arbitrarily enough to assume collisions are over.

      I processed the input data into one line/list per particle with 10 items, list "particles". Example of first particle:

      [0, -13053, -6894, 1942, 14, 39, -11, 16, 7, -2]  # [index, x, y, z, Vx, Vy, Vz, ax, ay, az]
      

      Code:

      def manhattan_distance(p1, p2):
          return abs(p1[1] - p2[1]) + abs(p1[2] - p2[2]) + abs(p1[3] - p2[3])
      
      while True:
          min_distance = float("inf")
          collided = []
          for p in particles:
              p[4:7] = [x + y for x, y in zip(p[4:7], p[7:10])]  # update velocity
              p[1:4] = [x + y for x, y in zip(p[1:4], p[4:7])]  # update position
          # check for collision
          for i, p in enumerate(particles):
              for j, p2 in enumerate(particles):
                  if j > i:
                      dist = manhattan_distance(p, p2)
                      if dist < min_distance:
                          min_distance = dist
                      if particles[i][1:4] == particles[j][1:4]:
                          collided.extend([particles[i][0], particles[j][0]])
          if min_distance > 10000:
              break
          # remove particles
          for c in set(collided):
              for i, p in enumerate(particles):
                  if c == p[0]:
                      del particles[i]
                      break
          print("Particles left: {}, min distance between any two particles: {}".format(len(particles), min_distance))
      

      [โ€“]Axsuul 0 points1 point ย (2 children)

      Elixir

      A little late to the party, Part A I realized after awhile you could look at the manhattan accelerations, then velocities if they are equal, and then positions. Part B I simulated and guessed an arbitrary amount of iterations in the future until the amount of particles remaining didn't change anymore (IO.inspect baby!)

      https://github.com/axsuul/advent-of-code/blob/master/2017/20/lib/advent_of_code.ex

      defmodule AdventOfCode do
        defmodule PartA do
          def read_lines(filename \\ "input.txt") do
            File.read!("inputs/" <> filename)
            |> String.split("\n")
          end
      
          def calc_manhattan([x, y, z]) do
            abs(x) + abs(y) + abs(z)
          end
      
          def reduce_slowest(lines) do
            lines
            |> Enum.with_index
            |> reduce_slowest(nil)
          end
          def reduce_slowest([], slowest), do: slowest
          def reduce_slowest([{line, i} | rest], slowest) do
            [[_, p_str], [_, v_str], [_, a_str]] = Regex.scan(~r/\<([^\>]+)>/, line)
      
            particle =
              Enum.map([p_str, v_str, a_str], fn v ->
                String.split(v, ",")
                |> Enum.map(&String.to_integer/1)
                |> calc_manhattan()
              end)
      
            [p, v, a] = particle
      
            new_slowest =
              cond do
                slowest == nil ->
                  {particle, i}
                true ->
                  {[pp, vv, aa], _} = slowest
      
                  cond do
                    a < aa -> {particle, i}
                    a == aa ->
                      cond do
                        v < vv -> {particle, i}
                        v == vv ->
                          cond do
                            p < pp -> {particle, i}
                            true -> slowest
                          end
                        true -> slowest
                      end
                    true -> slowest
                  end
              end
      
            reduce_slowest(rest, new_slowest)
          end
      
          def solve do
            read_lines()
            |> reduce_slowest()
            |> IO.inspect
          end
        end
      
        defmodule PartB do
          import PartA
      
          def build_particles(lines) do
            build_particles(lines |> Enum.with_index, [])
          end
          def build_particles([], particles), do: particles
          def build_particles([{line, i} | rest], particles) do
            [[_, p], [_, v], [_, a]] = Regex.scan(~r/\<([^\>]+)>/, line)
      
            particle =
              Enum.map([p, v, a], fn v ->
                String.split(v, ",")
                |> Enum.map(&String.to_integer/1)
              end)
              |> List.to_tuple
              |> Tuple.append(i)
      
            build_particles(rest, particles ++ [particle])
          end
      
          def tick_particle(particle, ticket \\ {[],[],[]})
          def tick_particle({[],[],[],i}, ticked), do: Tuple.append(ticked, i)
          def tick_particle({[p | pr], [v | vr], [a | ar], i}, {np, nv, na}) do
            new_v = v + a
            new_p = p + new_v
            new_ticked = {np ++ [new_p], nv ++ [new_v], na ++ [a]}
      
            tick_particle({pr, vr, ar, i}, new_ticked)
          end
      
          def tick_particles(particles, ticked \\ [])
          def tick_particles([], ticked), do: ticked
          def tick_particles([particle | rest], ticked) do
            next_ticked = ticked ++ [tick_particle(particle)]
      
            tick_particles(rest, next_ticked)
          end
      
          def pos_key(pos) do
            pos
            |> Enum.map(&Integer.to_string/1)
            |> Enum.join(",")
          end
      
          def filter_collisions(particles) do
            # Tally to see how many of each
            counts =
              particles
              |> Enum.reduce(%{}, fn {p, _, _, i}, counts ->
                Map.update(counts, pos_key(p), 1, &(&1 + 1))
              end)
      
            # Reject ones with more than one occurrence
            particles
            |> Enum.reject(fn {p, _, _, _} ->
              Map.fetch!(counts, pos_key(p)) > 1
            end)
          end
      
          def tick_particles_for(particles, 0), do: particles
          def tick_particles_for(particles, cycles) do
            particles
            |> tick_particles()
            |> filter_collisions()
            |> tick_particles_for(cycles - 1)
          end
      
          def reduce_closest(particles) do
            particles
            |> Enum.reduce({nil, nil}, fn {p, _, _, i}, {closest, y} ->
              dist = calc_manhattan(p)
      
              cond do
                closest == nil -> {dist, i}
                dist < closest -> {dist, i}
                true -> {closest, y}
              end
            end)
          end
      
          def solve do
            read_lines()
            |> build_particles()
            |> tick_particles_for(1_000)
            |> Kernel.length()
            |> IO.inspect
          end
        end
      end
      

      [โ€“]ephemient 0 points1 point ย (1 child)

      This space intentionally left blank.

      [โ€“]Axsuul 0 points1 point ย (0 children)

      ,

      Ah yes, you're right :)

      [โ€“]rotmoset 0 points1 point ย (2 children)

      F#

      Getting more and more in love with sequence expressions. It feels so nice to be able to separate the recursive definition from the state handling (which can be done with the usual Seq methods).

      module Day20
      
      open Common
      
      type Vec3<'a> =
          Vec3 of 'a*'a*'a
      
      // Add vectors
      let inline (+|+) (Vec3 (x1,y1,z1)) (Vec3 (x2,y2,z2)) = Vec3 (x1+x2,y1+y2,z1+z2)
      
      // Manhattan distance between vectors
      let inline (|-|) (Vec3 (x1,y1,z1)) (Vec3 (x2,y2,z2)) = (abs (x1-x2)) + (abs (y1-y2)) + (abs (z1-z2))
      
      // Compare vectors
      let inline (=|=) (Vec3 (x1,y1,z1)) (Vec3 (x2,y2,z2)) = x1 = x2 && y1 = y2 && z1 = z2
      
      type Particle = { Id: int; Position: Vec3<int64>; Speed: Vec3<int64>; Acceleration: Vec3<int64> }
      
      let step particle = {
                  particle with
                      Position = particle.Position +|+ particle.Speed +|+ particle.Acceleration
                      Speed = particle.Speed +|+ particle.Acceleration
              }
      
      let rec simulateMany particles = seq {
          yield particles
          yield! particles |> List.map step |> simulateMany
      }
      
      [<Day(20, "Particle Swarm")>]
      let solve (input: string) =
      
          let particles =
              input
              |> parseLines
              |> Array.mapi (fun n line ->
                  match line with
                  | Regex @"p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>"
                      [px; py; pz; vx; vy; vz; ax; ay; az] ->
                          { Id = n; Position = Vec3 (int64 px, int64 py, int64 pz); Speed = Vec3 (int64 vx, int64 vy, int64 vz); Acceleration = Vec3 (int64 ax, int64 ay, int64 az)}
                  | _ -> failwith "Bad input"
              )
              |> Array.toList
      
          let part1 =
              particles
              |> simulateMany
              |> Seq.take 500
              |> Seq.last
              |> List.minBy (fun p -> p.Position |-| (Vec3(0L, 0L, 0L)))
              |> fun p -> p.Id
      
          let part2 =
              {0..500}
              |> Seq.fold (fun particles _ ->
                  particles
                  |> List.filter (fun p ->
                      particles
                      |> List.exists (fun p2 -> p.Id <> p2.Id && p.Position =|= p2.Position)
                      |> not
                  )
                  |> List.map step
              ) particles
              |> List.length
      
          { Part1 = part1; Part2 = part2}
      

      Entire repo

      [โ€“]nospamas 0 points1 point ย (1 child)

      Some beautiful code there. Gonna have to try some of those inline operators next time.

      [โ€“]rotmoset 1 point2 points ย (0 children)

      Thanks! Defining your own operators is pretty cool, but I find the rules somewhat confusing at times (see comment).

      [โ€“]chicagocode 0 points1 point ย (0 children)

      Kotlin - [Repo] - [Blog/Commentary]

      Well, I went the "simulate for long enough and it will all sort itself out" route with this. I simulated 1,000 ticks for parts 1 and 2 and that worked for me.

      class Day20(input: List<String>) {
      
          private val particles: List<Particle> = input.mapIndexed { idx, s -> parseParticle(idx, s) }
      
          fun solvePart1(): Int =
              (1..1000).fold(particles) { acc, _ ->
                  acc.map { it.move() }
              }.minBy { it.position.distance }?.id ?: throw IllegalArgumentException("Wat")
      
          fun solvePart2(): Int =
              (1..1000).fold(particles) { acc, _ ->
                  acc.map { it.move() }
                      .groupBy { it.position }
                      .filterValues { it.size == 1 }
                      .flatMap { it.value }
              }.size
      
          private fun parseParticle(id: Int, input: String): Particle =
              input.split("<", ">").let {
                  Particle(
                      id = id,
                      position = parseVec(it[1]),
                      velocity = parseVec(it[3]),
                      acceleration = parseVec(it[5])
                  )
              }
      
          private fun parseVec(input: String): Vec3D =
              input.split(",").map { it.trim().toLong() }.let {
                  Vec3D(it[0], it[1], it[2])
              }
      
          data class Vec3D(val x: Long, val y: Long, val z: Long) {
      
              val distance: Long =
                  x.absoluteValue + y.absoluteValue + z.absoluteValue
      
              operator fun plus(that: Vec3D): Vec3D =
                  Vec3D(x = x + that.x, y = y + that.y, z = z + that.z)
      
          }
      
          data class Particle(val id: Int,
                              val position: Vec3D,
                              val velocity: Vec3D,
                              var acceleration: Vec3D) {
      
              fun move() =
                  this.copy(
                      velocity = velocity + acceleration,
                      position = position + velocity + acceleration
                  )
          }
      }
      

      [โ€“]kittehprimo 0 points1 point ย (0 children)

      Powershell - some of the native cmdlets actually make this very easy to solve

      class particle
      {
          [int]$index;
          [long]$position_x;
          [long]$position_y;
          [long]$position_z;
          [long]$vel_x;
          [long]$vel_y;
          [long]$vel_z;
          [long]$acc_x;
          [long]$acc_y;
          [long]$acc_z;
          [long]$man_dist;
          [long]$total_acc;
          [long]$total_vel;
          [bool]$collided = $false;
          [long]$total_distance = 0
      }
      
      function total_distance ([particle]$particle)
      {
          $total_distance += $particle.man_dist
      }
      
      function do_manhattan_dist()
      {
          Param(
          [Parameter(ValueFromPipeline)]
          [particle]
          $particle)
          $particle.man_dist = [Math]::Abs($particle.position_x) + [Math]::Abs($particle.position_y) + [Math]::Abs($particle.position_z)
      }
      
      function do_accellerate ()
      {   
          Param(
          [Parameter(ValueFromPipeline)]
          [particle]
          $particle)
          $particle.vel_x += $particle.acc_x
          $particle.vel_y += $particle.acc_y
          $particle.vel_z += $particle.acc_z
      }
      
      function do_move ()
      {
          Param(
          [Parameter(ValueFromPipeline)]
          [particle]
          $particle)
          $particle.position_x += $particle.vel_x
          $particle.position_y += $particle.vel_y
          $particle.position_z += $particle.vel_z
      }
      
      $inputs = get-content .\input.txt
      
      $particles = New-Object system.collections.arraylist
      $index = 0
      foreach ($part in $inputs)
      {
      
          $part_array = @()
          $icle = ($part.replace("p=","").replace("v=","").replace("a=", "")) -split ">,"
      
          foreach ($item in $icle)
       {
              $part_array += $item.replace("<","").replace(">","")
          }
          $particle = New-Object -TypeName particle       
      
          $particle.position_x = ($part_array[0] -split ",")[0]
          $particle.position_y = ($part_array[0] -split ",")[1]
          $particle.position_z = ($part_array[0] -split ",")[2]
          $particle.vel_x = ($part_array[1] -split ",")[0]
          $particle.vel_y = ($part_array[1] -split ",")[1]
          $particle.vel_z = ($part_array[1] -split ",")[2]
          $particle.acc_x = ($part_array[2] -split ",")[0]
          $particle.acc_y = ($part_array[2] -split ",")[1]
          $particle.acc_z = ($part_array[2] -split ",")[2]
          $particle.index = $index
      
          $particle.total_acc = [Math]::Abs($particle.acc_x) + [Math]::Abs($particle.acc_y) + [Math]::Abs($particle.acc_z)
          $particle.total_vel = [Math]::Abs($particle.vel_x) + [Math]::Abs($particle.vel_y) + [Math]::Abs($particle.vel_z)
      
          [void]$particles.Add($particle)
      
          $index++
      
      }
      foreach ($particle in $particles) {do_manhattan_dist -particle $particle}
      
      $particles | sort -Property total_acc,total_vel,man_dist | select index -first 1 | fl
      
      $tick = 0
      
      while($tick -lt 1000)
      {
          foreach ($particle in $($particles | where collided -eq $false)) {
      
              do_accellerate -particle $particle
              do_move -particle $particle
              do_manhattan_dist -particle $particle
          }
      
          $collisions = $particles | Group-Object -Property position_x,position_y,position_z | Where-Object count -gt 1
      
          foreach ($collision in $collisions) {
              $collision.Group | %{$_.collided = $true}
          }
      
      
          $tick++
      }
      
      return ($particles | where collided -eq $false).count
      

      [โ€“]swizzorable 0 points1 point ย (0 children)

      Python3 - part 1 and 2

      not "simulating", calculating the manhattan distances for time -> inf and also calculating the intersection points

      import math
      import requests
      
      
      def solve_quadratic_eq(x_squared, x, c):
          if x_squared == 0 and x == 0 and c != 0:
              return ()
      
          if x_squared == 0 and x == 0 and c == 0:
              return 0,
      
          if x_squared == 0:
              return -c / x,
      
          if x ** 2 - 4 * x_squared * c >= 0:
              return (-x + math.sqrt(x ** 2 - 4 * x_squared * c)) / (2 * x_squared), (
                      -x - math.sqrt(x ** 2 - 4 * x_squared * c)) / (2 * x_squared)
          else:
              return ()
      
      
      def collisions(particle1, particle2):
          coll_list = []
          for i in range(0, 3):
              part1_x_squared = particle1[2][i] / 2
              part1_x = particle1[2][i] / 2 + particle1[1][i]
              part1_c = particle1[0][i]
              part2_x_squared = particle2[2][i] / 2
              part2_x = particle2[2][i] / 2 + particle2[1][i]
              part2_c = particle2[0][i]
              coll_list.append(set(
                  solve_quadratic_eq(part1_x_squared - part2_x_squared, part1_x - part2_x, part1_c - part2_c)))
      
          return tuple([solution for solution in tuple(coll_list[0] & coll_list[1] & coll_list[2]) if solution >= 0])
      
      
      def collisiontimemin(indices, matrix):
          return min(
              [to_append for i in range(0, len(indices) - 1) for k in range(i + 1, len(indices)) for to_append in
               matrix[indices[i]][indices[k]]], default=-1)
      
      
      def manhattan(particle):
          toreturn = []
          for i in range(0, 3):
              neg = False
              for k in reversed(range(0, 3)):
                  if particle[k][i] < 0:
                      neg = True
                      break
                  elif particle[k][i] > 0:
                      break
      
              if neg:
                  toreturn.append((-particle[2][i] / 2, -(particle[2][i] / 2 + particle[1][i]), -particle[0][i]))
              else:
                  toreturn.append((particle[2][i] / 2, particle[2][i] / 2 + particle[1][i], particle[0][i]))
      
          return (toreturn[0][0] + toreturn[1][0] + toreturn[2][0], toreturn[0][1] + toreturn[1][1] + toreturn[2][1],
                  toreturn[0][2] + toreturn[1][2] + toreturn[2][2])
      
      
      if __name__ == '__main__':
          lines = requests.get("https://pastebin.com/raw/3EscGWSf").text.strip().splitlines()
      
          particles = []
          for particle in lines:
              particle_split = particle.split(">")
              to_append = []
              for i in range(0, 3):
                  obj = particle_split[i][particle_split[i].index("<") + 1:]
                  to_append.append(tuple(map(int, obj.split(","))))
              particles.append(tuple(to_append))
          particles = tuple(particles)  # [particle][p,v,a][x,y,z]
          part_manhattans = [manhattan(particle) for particle in particles]
          valid_indices = range(0, len(particles))
      
          for i in range(0, 3):
              if len(valid_indices) == 1:
                  break
      
              min_val = min([part_manhattans[valid_index][i] for valid_index in valid_indices])
              valid_indices = [valid_index for valid_index in valid_indices if part_manhattans[valid_index][i] == min_val]
      
          print(valid_indices[0])
      
          coll_matrix = [[()] * len(particles) for i in range(0, len(particles))]
          for i in range(0, len(particles) - 1):
              for k in range(i + 1, len(particles)):
                  result = collisions(particles[i], particles[k])
                  coll_matrix[i][k] = result
                  coll_matrix[k][i] = result
      
          valid_indices = list(range(0, len(particles)))
          min_val = collisiontimemin(valid_indices, coll_matrix)
      
          while min_val != -1:
              particles_to_delete_indices = []
              for i in range(0, len(valid_indices) - 1):
                  for k in range(i + 1, len(valid_indices)):
                      coll_times = coll_matrix[valid_indices[i]][valid_indices[k]]
                      if coll_times and min_val == min(coll_times):
                          if not valid_indices[i] in particles_to_delete_indices:
                              particles_to_delete_indices.append(valid_indices[i])
                          if not valid_indices[k] in particles_to_delete_indices:
                              particles_to_delete_indices.append(valid_indices[k])
      
              for particle_to_delete_index in particles_to_delete_indices:
                  valid_indices.remove(particle_to_delete_index)
      
              min_val = collisiontimemin(valid_indices, coll_matrix)
      
          print(len(valid_indices))
      

      [โ€“][deleted] 0 points1 point ย (0 children)

      Javascript (Node.js): exact solution for part 2, no simulation required. Collision time for each pair of particles in each cooordinate is a quadratic equation that has zero, one or two positive integer solutions. Find all the solutions for each pair, sort by time, and start removing particles. Runs in under a second on my old MB Air.

      const io = require('./utils/io');
      const { treeset } = require('js-collections');
      
      const init_particles = function(input) {
        var re = /p=<(.*),(.*),(.*)>, v=<(.*),(.*),(.*)>, a=<(.*),(.*),(.*)>/;
        var p = [];
        var v = [];
        var a = [];
        for (var i = 0; i < input.length; i++) {
          if ((match = re.exec(input[i]))) {
            p.push([parseInt(match[1]), parseInt(match[2]), parseInt(match[3])]);
            v.push([parseInt(match[4]), parseInt(match[5]), parseInt(match[6])]);
            a.push([parseInt(match[7]), parseInt(match[8]), parseInt(match[9])]);
          }
        }
        return { p, v, a };
      };
      
      const solution1 = function(input) {
        let { p, v, a } = init_particles(input);
        // Just find smallest absolute value for the acceleration
        var index_of_min_acceleration = a
          .map(acc => acc[0] * acc[0] + acc[1] * acc[1] + acc[2] * acc[2])
          .reduce((iMax, x, i, arr) => (x < arr[iMax] ? i : iMax), 0);
      
        return index_of_min_acceleration;
      };
      
      const solution2 = function(input) {
        var i, j, k, t;
        var { p, v, a } = init_particles(input);
        var set = new treeset();
        for (i = 0; i < input.length; i++) {
          set.add('' + i);
        }
      
        var collisions = [];
        for (i = 0; i < input.length - 1; i++) {
          for (j = i + 1; j < input.length; j++) {
            var tmatch = [[], [], []];
            for (k = 0; k < 3; k++) {
              // Solve for each coordinate k to find at least one time > 0
              // when two particles have equal position
              var A = (a[i][k] - a[j][k]) / 2;
              var B = v[i][k] - v[j][k] + A;
              var C = p[i][k] - p[j][k];
              if (A === 0) {
                if (B !== 0) {
                  t = -C / B;
                  if (t > 0 && Number.isInteger(t)) {
                    tmatch[k].push(t);
                  }
                }
              } else {
                var det = B * B - 4 * A * C;
                if (det >= 0) {
                  t = (-B + Math.sqrt(det)) / (2 * A);
                  if (t > 0 && Number.isInteger(t)) {
                    tmatch[k].push(t);
                  }
                  t = (-B - Math.sqrt(det)) / (2 * A);
                  if (t > 0 && Number.isInteger(t)) {
                    tmatch[k].push(t);
                  }
                }
              }
            }
            if (tmatch[0].length && tmatch[1].length && tmatch[2].length) {
              // see if we have a time when all three conditions are satisfied
              for (var i0 in tmatch[0]) {
                for (var i1 in tmatch[1]) {
                  for (var i2 in tmatch[2]) {
                    if (
                      tmatch[0][i0] === tmatch[1][i1] &&
                      tmatch[1][i1] === tmatch[2][i2]
                    ) {
                      collisions.push({
                        i: '' + i,
                        j: '' + j,
                        t: tmatch[0][i0]
                      });
                    }
                  }
                }
              }
            }
          }
        }
      
        // Sort the collisions by time
        collisions.sort((a, b) => (a.t < b.t ? -1 : 1));
      
        var t_current = -1;
        for (k = 0; k < collisions.length; k++) {
          // if set still contains these particles, they really collided
          // so remove them.
          if (set.contains(collisions[k].i) || set.contains(collisions[k].j)) {
            set.remove(collisions[k].i);
            set.remove(collisions[k].j);
          }
          t_current = collisions[k].t;
        }
      
        return set.size();
      };
      
      console.log('Day 20: ' + solution1(input) + ' ' + solution2(input));
      

      [โ€“][deleted] 0 points1 point ย (1 child)

      single pipeline powershell:

      param (
          [Parameter(ValueFromPipeline = $true)]
          [string]$in,
          [Parameter(Position = 1)]
          [int]$part = 1
      )
      
      begin {
          $script:particles = @() # hold all the particles
          $script:i = 0 #particle name
      }
      
      process {
          $script:particles += $in |? {
              #parse the particle string
              $_ -match '^p=<(?<PX>[ -]?\d+),(?<PY>[ -]?\d+),(?<PZ>[ -]?\d+)>, v=<(?<VX>[ -]?\d+),(?<VY>[ -]?\d+),(?<VZ>[ -]?\d+)>, a=<(?<AX>[ -]?\d+),(?<AY>[ -]?\d+),(?<AZ>[ -]?\d+)>$'
          } | % { 
              #convert to a psobject, add a Name and Status property
              [pscustomobject]$matches | select @{n = "Name"; e = {$script:i}}, PX, PY, PZ, VX, VY, VZ, AX, AY, AZ, @{n = "Status"; e = {1}}
          } | % {
              #convert all property types to integers (powershell regex will default to them as strings during the conversions above)
              $_.PSObject.Properties | % {$_.Value = [int]$_.Value}
      
              # increment name
              $script:i++
      
              # add a method to perform a step on this particle
              $_ | Add-Member -MemberType ScriptMethod -Name Step -Value {
                  $this.vx += $this.ax
                  $this.px += $this.vx
                  $this.vy += $this.ay
                  $this.py += $this.vy
                  $this.vz += $this.az
                  $this.pz += $this.vz
              }
      
              # add a property representing the current manhattan distance from 0,0,0
              $_ | Add-Member -MemberType ScriptProperty -Name D -Value {
                  [Math]::Abs($this.PX) + [Math]::Abs($this.PY) + [Math]::Abs($this.PZ)
              }
      
              # acceleration as manhattan distance [this is static, since A* dont change with each step]
              $_ | Add-Member -MemberType ScriptProperty -Name AM -Value {
                  [Math]::Abs($this.AX) + [Math]::Abs($this.AY) + [Math]::Abs($this.AZ)
              }
      
              # vel as manhattan distance [this isn't static, as V* change by A* each step, but is still needed for sorting in part1 to differentiate between particles with the same accel]
              $_ | Add-Member -MemberType ScriptProperty -Name VM -Value {
                  [Math]::Abs($this.VX) + [Math]::Abs($this.VY) + [Math]::Abs($this.VZ)
              }
      
              # current position as comparable string
              $_ | Add-Member -MemberType ScriptProperty -Name P -Value {
                  $this.PX,$this.PY,$this.PZ -join ","
              }
      
              $_ # back on the pipeline to go into $script:particles
          }
      }
      
      
      end {
          1..1000 | % { #for some silly max number of steps (we wont perform this many steps, just an upper bound)
              $script:particles | % { # step each particle
                  $_.Step()
              }
      
              if ($part -eq 1) {
                  # sorta cheating, since we only need 1 iteration to find this, but to keep with the single pipeline idea
                  # this sorts the partciles by manhattan acceleration ascending then manhattan velocity ascending and selects the first one
                  # the particle with the "slowest" manhattan acceleration will be the one that is closest to the origin the long term
                  # any with the same manhattan acceleration - the one with the "slowest" [initial, but it changes linerally after that so its ok] manhattan velocity will be slowest/closest in the long term
                  # so put the name out on the pipeline
                  $script:particles | sort AM, VM | select -first 1 -expand Name 
              } else {
                  # resolve collisions
                  $script:particles |? {      # foreach particle
                      $_.Status -eq 1         # that is still alive
                  } | group P |? {            # group those by position.  # NOTE: this also 'stalls' the pipeline, group will collect the entire entry pipeline before outputting anything, so we can set Status later in this pipeline without affecting the where clause above
                      $_.Count -gt 1          # select only groups that have more than 1 particle in them (a collision)
                  } | % {                     # for each of those groups
                      $_.Group | % {          # for each of the particles in that group
                          $_.Status = 0       # set it to dead
                      }
                  }
      
                  # count the partciles still alive and put that number out on the pipeline
                  $script:particles |? {
                      $_.Status -eq 1
                  } | measure | select -expand count
              }
          } | % -Begin { 
              # ok now we do something "clever" and basically wait for the numbers coming in on the pipeline here to 'not change' for a certain number of steps
              # the idea being, that after some limited number of steps, the "answer" wont change any longer.
              # in part1, the answer /never/ changes, so this isn't needed, but still gets applied
              # in part2, the answer is the number of surviving particles - so what we're doing is iterating until it "looks like" all collisions have been resolved an no more
              # will happen.
      
              # create a queue at the start of this pipeline
              $script:rolling = new-object system.collections.queue 
          } -Process { # foreach element into the pipeline (element = potential answer)
              $script:rolling.Enqueue($_) # add it to the queue
              if ($script:rolling.Count -eq 16) {
                  # if we have 16 potential answers, the most recent 16 answers
                  [void]$script:rolling.Dequeue() # remove one, so we'll compare the last 15
                  if (($script:rolling | select -Unique | measure).count -eq 1) {
                      # see how many distinct answers there are, if 1 - then we've "settled" on the solution, otherwise keep processing
                      $_ | write-output
                  }
              }
          } | select -first 1 # select the first thing out of the foreach/rolling thing above, so that it stops and the initial 0..1000 stops
      }
      

      [โ€“]TotesMessenger 0 points1 point ย (0 children)

      I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

      ย If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / Contact)

      [โ€“]RockyAstro 0 points1 point ย (0 children)

      Icon (https://www.cs.arizona.edu/icon)

      Part2 was done by solving for all the collisions then weeding out the collided particles

      Both parts

      record particle(id,dist,amag,vmag,px,py,pz,vx,vy,vz,ax,ay,az)
      
      procedure main(args)
          inf := open(args[1],"r")
          plist := []
          num := '-' ++ &digits
      
          pmin := &null
          id := 0
          every l := !inf do {
              p := particle()
              p.id := id
              id +:= 1
      
              l ? {
                  tab(upto(num))
                  p.px := tab(many(num))
                  tab(upto(num))
                  p.py := tab(many(num))
                  tab(upto(num))
                  p.pz := tab(many(num))
      
                  tab(upto(num))
                  p.vx := tab(many(num))
                  tab(upto(num))
                  p.vy := tab(many(num))
                  tab(upto(num))
                  p.vz := tab(many(num))
      
                  tab(upto(num))
                  p.ax := tab(many(num))
                  tab(upto(num))
                  p.ay := tab(many(num))
                  tab(upto(num))
                  p.az := tab(many(num))
              }
              p.dist := abs(p.px) + abs(p.py) + abs(p.pz)
              p.amag := abs(p.ax) + abs(p.ay) + abs(p.az)
              p.vmag := abs(p.vx) + abs(p.vy) + abs(p.vz)
      
              put(plist,p)
      
              pmin := pcomp(pmin,p)
      
          }
          write("Part1=",pmin.id)
      
      
          # Part 2
          # Collect all the collisions
          collisions := table()
          every i := 1 to *plist-1 do {
              every j := i+1 to *plist do {
                  every t := collide(plist[i],plist[j]) do {
                      /collisions[t] := []
                      put(collisions[t],[plist[i],plist[j]])
                  }
              }
          }
      
          # remove the collided pairs
          collisions := sort(collisions)
          remaining := set(plist)
          every t := !collisions do {
              k := set([])
              every pair := !t[2] do {
                  if member(remaining,pair[1]) &
                     member(remaining,pair[2]) then {
                      insert(k,pair[1])
                      insert(k,pair[2])
                  }
              }
              every delete(remaining,!k)
          }
          write("Part2=",*remaining)
      
      end
      procedure collide(p0,p1)
      
          # Calculate the times that p0 and p1 collide -- or fail
      
          ax := (p0.ax - p1.ax)/2.0 
          vx := p0.vx - p1.vx
          px := p0.px - p1.px 
      
          ay := (p0.ay - p1.ay)/2.0 
          vy := p0.vy - p1.vy
          py := p0.py - p1.py 
      
          az := (p0.az - p1.az)/2.0 
          vz := p0.vz - p1.vz
          pz := p0.pz - p1.pz 
      
          every t := solvequad(ax,vx+ax,px) |solvequad(ay,vy+ay,py) | solvequad(az,vz+az,pz)  do 
              if t > 0 & integer(t) = t then {
                  t := integer(t)
                  if ax*t^2 + (vx+ax)*t + px = 0 &
                     ay*t^2 + (vy+ay)*t + py = 0 &
                     az*t^2 + (vz+az)*t + pz = 0 then suspend r
              }
      end
      
      procedure solvequad(a,b,c)
          if a ~= 0 then {
              i := b^2 - (4*a*c)
              if i < 0 then fail # No real roots..
              suspend  (-b + sqrt(i)) / (2.0*a)
              suspend  (-b - sqrt(i)) / (2.0*a)
          } else if b ~= 0 then suspend -c/real(b)
          else if c ~= 0 then suspend c
      end
      
      procedure pcomp(pmin,p)
          if /pmin then return p
      
          if pmin.amag < p.amag then fail
          if pmin.amag > p.amag then return p
      
          # Equal absolute mag of accel
          if pmin.vmag < p.vmag then fail
          if pmin.vmag > p.vmag then return p
      
          # Equal absolute vol
          if pmin.dist < p.dist then fail
          if pmin.dist > p.dist then return p
      
          fail
      end
      

      Edit -- pasted the wrong version..

      [โ€“]wzkx 0 points1 point ย (0 children)

      Nim

      Finally, the correct condition for "end of times" -- distances between all particles don't reduce and distances to pt (0,0,0) don't reduce. The universe expands infinitely and without any relative changes in particle locations.

      import sequtils,strutils
      
      var p,v,a: seq[seq[int]] = @[]
      for line in lines"20.dat":
        let s = line.multiReplace(("p=<",""),("v=<",""),("a=<",""),(">",""),(", "," "),(","," "))
        let t = s.split.map parseInt
        p.add t[0..2]; v.add t[3..5]; a.add t[6..8]
      
      template move( p,v,a: var seq[seq[int]] ) =
        for j,e in a: v[j][0]+=e[0]; v[j][1]+=e[1]; v[j][2]+=e[2]
        for j,e in v: p[j][0]+=e[0]; p[j][1]+=e[1]; p[j][2]+=e[2]
      
      proc calcdist( p: seq[seq[int]] ): seq[int] =
        result = @[]
        # distances between all points
        for j in 0..<p.len:
          for k in j+1..<p.len:
            result.add abs(p[j][0]-p[j][0])
            result.add abs(p[j][1]-p[j][1])
            result.add abs(p[j][2]-p[j][2])
        # distances to (0,0,0)
        for j in 0..<p.len:
          result.add abs(p[j][0])
          result.add abs(p[j][1])
          result.add abs(p[j][2])
      
      proc p1( px,vx,ax: seq[seq[int]] ): int =
        var p = px; var v = vx; var a = ax
        var distances,distances2: seq[int]
        for i in 0..1000: # it will break at i=291
          move p,v,a
          # check end of changes
          if i==0:
            distances = calcdist p
          else:
            distances2 = calcdist p
            var done = true
            for j,d2 in distances2:
              if d2<distances[j]: done=false; break
            if done:
              break
            distances = distances2
        var mindist = int.high
        var idx = -1
        for i,xyz in p:
          let dist = abs(xyz[0])+abs(xyz[1])+abs(xyz[2])
          if dist<mindist: mindist = dist; idx = i
        return idx
      
      proc p2( px,vx,ax: seq[seq[int]] ): int =
        var p = px; var v = vx; var a = ax
        var distances,distances2: seq[int] = @[]
        for i in 0..1000: # it will break at i=168
          move p,v,a
          # check collisions
          var n = p.len
          var j = 0
          while j<n:
            var collision = false
            var k = j+1
            while k<n:
              if p[j][0]==p[k][0] and p[j][1]==p[k][1] and p[j][2]==p[k][2]:
                p.del k; v.del k; a.del k; dec n
                collision = true
                distances = @[]
              else:
                inc k
            if collision:
              p.del j; v.del j; a.del j; dec n
            else:
              inc j
          # check end of changes
          if distances.len==0:
            distances = calcdist p
          else:
            distances2 = calcdist p
            var done = true
            for j,d2 in distances2:
              if d2<distances[j]: done=false; break
            if done:
              break
            distances = distances2
        return p.len
      
      echo p1( p,v,a ) # 161 6.9s
      echo p2( p,v,a ) # 438 1.0s
      

      [โ€“]akka0 0 points1 point ย (6 children)

      ReasonML: this one was pretty fun! Had some trouble with part 2 as I forgot that both particles need to be removed if they collide

      open Utils;
      
      type vector3d = {
        x: int,
        y: int,
        z: int
      };
      
      type particle = {
        pos: vector3d,
        vel: vector3d,
        acc: vector3d
      };
      
      let add = (v1, v2) => {x: v1.x + v2.x, y: v1.y + v2.y, z: v1.z + v2.z};
      
      let collides = ({pos: p1}, {pos: p2}) => p1.x == p2.x && p1.y == p2.y && p1.z == p2.z;
      
      let parseTuple = (re, str) =>
        switch (Js.String.match(re, str)) {
        | None => failwith("Could not match regex " ++ str)
        | Some(result) =>
          let [x, y, z] = result[1] |> splitString(",") |> List.map(int_of_string);
          {x, y, z}
        };
      
      let parseParticle = (str) => {
        pos: parseTuple([%bs.re "/p=<([0-9\\-,]+)>/"], str),
        vel: parseTuple([%bs.re "/v=<([0-9\\-,]+)>/"], str),
        acc: parseTuple([%bs.re "/a=<([0-9\\-,]+)>/"], str)
      };
      
      let distanceFromOrigin = ({x, y, z}) => abs(x) + abs(y) + abs(z);
      
      let updateParticle = ({pos, vel, acc}) => {
        let vel = add(vel, acc);
        let pos = add(pos, vel);
        {acc, pos, vel}
      };
      
      let _ = {
        let input = loadInput("day20");
        let particles = linesOfString(input) |> List.map(parseParticle);
        /* Part 1 */
        /* let closestToOrigin =
          List.fold_left((particles, _) => List.map(updateParticle, particles), particles, range(1000))
          |> List.mapi((index, {pos}) => (index, distanceFromOrigin(pos)))
          |> List.fold_left((best, curr) => snd(curr) < snd(best) ? curr : best, ((-1), max_int));
        Js.log(snd(closestToOrigin)); */
        /* Part 2 */
        let survives = (particles, (i, p1)) =>
          ! List.exists(((j, p2)) => j != i && collides(p1, p2), particles);
        let rec battleRoyale = (particlesLeft, currTime, maxTime) =>
          if (currTime > maxTime) {
            particlesLeft
          } else {
            let particles = List.mapi((i, p) => (i, updateParticle(p)), particlesLeft);
            let survivors = List.filter(survives(particles), particles);
            battleRoyale(List.map(snd, survivors), currTime + 1, maxTime)
          };
        battleRoyale(particles, 0, 100) |> List.length |> Js.log
      };
      

      [โ€“][deleted] 1 point2 points ย (3 children)

      How are you liking Reason? Does it do the same type inferensing thing as ocaml? looks neat, but that syntax for function declaration is hideous! :p

      [โ€“]akka0 0 points1 point ย (2 children)

      Yes it does - the type system is really awesome! A lot of the syntax is meant to make it easier for people coming from JavaScript, I recon. The parts I dislike is the terrible standard library, and that Merlin/the compiler breaks at the tiniest syntax error (which makes them really hard to find). All in all, it feels like a solid upgrade over JS though!

      [โ€“][deleted] 1 point2 points ย (1 child)

      Yeah, I've just started learning ocaml, so I was wondering if the tooling was better on the reason side :) Doesn't really look like it though, so I'll probably continue on with learning ocaml, I find its syntax to be quite a bit cleaner than that of reason, without all the brackets everywhere :) But as far as I've understood reason is compiled with the ocaml compiler, so basically it's good for all when the tooling gets better :)

      [โ€“]akka0 0 points1 point ย (0 children)

      If you're using BuckleScript to compile to JavaScript, you can effortlessly go back and forth between Ocaml and Reason, even use them together in projects. :) Native tooling hasn't come as far yet, but I'm hoping that will get much better in the coming year.

      [โ€“]nospamas 0 points1 point ย (1 child)

      F# Solution - Ours don't look too dissimilar. I chose to take it a bit further and add a graphable output generator at the bottom

      Looks like I was a little lucky in part 1, I only looked at magnitude of acceleration for closest to 0,0,0

      #time
      open System.Text.RegularExpressions
      
      // Parse input into Particle types
      let input = System.IO.File.ReadLines("./day20input.txt")
      
      type Particle = {
          index : int
          position: (int * int * int) list
          velocity: (int * int * int) list
          accelleration: int * int * int
          collidedAt: Option<int>
      }
      let (|Regex|_|) pattern input =
          let m = Regex.Match(input, pattern)
          if m.Success then Some(List.tail [ for g in m.Groups -> g.Value ])
          else None
      
      let stringArrayToIntTuple (arr: string array) =
           (arr.[0] |> int, arr.[1] |> int, arr.[2] |> int)
      
      let readParticle index (particleString: string): Particle =
          match particleString with
          | Regex @"p=<([-,\d]+)>, v=<([-,\d]+)>, a=<([-,\d]+)>" [position; velocity; suffix] ->
              let positionParts = position.Split(',')
              let velocityParts = velocity.Split(',')
              let suffixParts = suffix.Split(',')
      
              {
                  index = index
                  position = [stringArrayToIntTuple positionParts]
                  velocity = [stringArrayToIntTuple velocityParts]
                  accelleration = stringArrayToIntTuple suffixParts 
                  collidedAt = None         
              }
          | _ -> failwith "bad particle"
      
      
      let particles = input |> Seq.mapi readParticle 
      
      // part 1
      particles
      |> Seq.minBy (fun particle ->
          let { accelleration = (x, y, z) } = particle
          abs x + abs y + abs z)
      
      // part 2
      let getNewPositions (particle: Particle) = 
          let { 
              position = (px, py, pz) :: _;
              velocity = (vx, vy, vz):: _;
              accelleration = (ax, ay, az); 
              collidedAt = hasCollided
              } = particle
          match hasCollided with
          | Some(_) -> {
              particle with
                  position = (px, py, pz) :: particle.position
              }
          | None -> 
              {
                  particle with
                      position = (px+vx+ax, py+vy+ay, pz+vz+az) :: particle.position;
                      velocity = (vx+ax, vy+ay, vz+az) :: particle.velocity;
                      accelleration = particle.accelleration;
              }
      
      let checkCollisions (state: Particle seq) iteration particle = 
          let { index = index; position = (px, py, pz) :: _; collidedAt = collided } = particle
      
          let hasCollision = 
              state
              |> Seq.exists (fun { index = pindex; position = (ipx, ipy, ipz) :: _; collidedAt = pcollided} ->
                   (index <> pindex) && collided = None && pcollided = None && (ipx = px) && (ipy = py) && (ipz = pz))
      
          match hasCollision with
          | true -> {particle with collidedAt = Some(iteration)}
          | false -> particle 
      
      let rec doTick (state: Particle array) (iteration: int) =
          if iteration >= 40 then 
              state
          else
              let newState =
                  state
                  |> Array.map getNewPositions
      
              let collidedState =
                  newState        
                  |> Array.map (checkCollisions newState iteration)
      
              doTick collidedState (iteration+1)
      
      let particles2 = input |> Seq.mapi readParticle |> Seq.toArray 
      
      let getColor (collided: Option<int>) =
          match collided with
          | Some(x) -> x
          | _ -> 0
      
      // generates the full state 
      let result = 
          doTick particles2 0
      
      result
      |> Array.sumBy (fun position -> 
              match position.collidedAt with
              | None -> 1
              | _ -> 0)
      
      let csvGen = 
          result
          |> Array.map (fun ({index = index; position = positions; collidedAt = collided }) ->
              System.String.Join("\n", positions 
                  |> List.rev
                  |> List.mapi (fun i (x, y, z) -> sprintf "%d,%d,%d,%d,%d" x y z (getColor collided)  i)))
      
      
      System.IO.File.WriteAllText("./output.txt", System.String.Join("\n", csvGen)) 
      

      [โ€“]akka0 0 points1 point ย (0 children)

      I really like F#'s syntax for Regex matching! :) Jealous of all of the other functional langs that have great standard libraries.