advent2017-day20.fs

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Input data
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

type Vector = (int64 * int64 * int64)
type Particle = {
    position: Vector
    velocity: Vector
    acceleration: Vector
}

let parseVector id (value: string) =
    let trimmedValue = value.Trim()
    if trimmedValue.[0] <> id then raise (InvalidOperationException "Invalid ID when parsing vector")
    let onlyValue = value.Substring(3, trimmedValue.Length - 4)
    let parts = onlyValue.Split(',') |> Array.map int64
    (parts.[0], parts.[1], parts.[2])

let parse filename =
    File.ReadAllLines(filename)
    |> Seq.map
        (fun line ->
            let vectors = line.Split([| ", " |], StringSplitOptions.None)
            let position = parseVector 'p' vectors.[0]
            let velocity = parseVector 'v' vectors.[1]
            let acceleration = parseVector 'a' vectors.[2]
            { position = position; velocity = velocity; acceleration = acceleration })
    |> List.ofSeq
            
let data = parse "queries/Advent/Advent2017-day20.txt"


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Problem A
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

let manhattanDistance (x: int64, y: int64, z: int64) = Math.Abs(x) + Math.Abs(y) + Math.Abs(z)

let addVectors (x1: int64, y1: int64, z1: int64) (x2: int64, y2: int64, z2: int64) =
    (x1 + x2, y1 + y2, z1 + z2)

let rec tick toDo (particles: Particle list) =
    if toDo = 0L then
        let distances =
            particles
            |> List.map (fun p -> manhattanDistance p.position)
        let min = distances |> List.min
        distances |> List.findIndex ((=) min)
    else
        let updatedParticles =
            particles
            |> List.map
                (fun p ->
                    let newVelocity = addVectors p.velocity p.acceleration
                    let newPosition = addVectors p.position newVelocity
                    { p with position = newPosition; velocity = newVelocity })
        tick (toDo-1L) updatedParticles
        
(tick 500L data).Dump("Particle that stays the closest")


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Problem B
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

let rec removeCollisions (particles: Particle list) (positions: Set<Vector>) =
    match particles with
    | head::tail ->
        let collisionWithPrevious = positions |> Set.contains head.position
        let positionsForNext = if collisionWithPrevious then positions else positions |> Set.add head.position
        let (updatedPartitions, collisions) = removeCollisions tail positionsForNext // recursion (not tail-recursive)
        let collisionWithNext = (not collisionWithPrevious) && collisions |> Set.contains head.position // if we are already colliding with previous, we don't care if we are also colliding with next
        let updatedCollisions = if collisionWithPrevious then collisions |> Set.add head.position else collisions
        let returnPartitions = if collisionWithPrevious || collisionWithNext then updatedPartitions else head::updatedPartitions // decide whether to keep or remove "head"
        (returnPartitions,updatedCollisions)
    | [] -> ([], Set.empty<Vector>)

let rec tickCollisions toDo (particles: Particle list) =
    if toDo = 0L then particles.Length
    else
        let updatedParticles =
            particles
            |> List.map
                (fun p ->
                    let newVelocity = addVectors p.velocity p.acceleration
                    let newPosition = addVectors p.position newVelocity
                    { p with position = newPosition; velocity = newVelocity })
        let (updatedParticlesWithoutCollisions, _) = removeCollisions updatedParticles Set.empty<Vector>
        tickCollisions (toDo-1L) updatedParticlesWithoutCollisions
        
(tickCollisions 500L data).Dump("Non-colliding particles")