From 3f2cbe77b652fa33005cc4262ba2a4d15e15666f Mon Sep 17 00:00:00 2001
From: Ummon <greg.burri@gmail.com>
Date: Thu, 21 Dec 2017 08:12:26 +0100
Subject: [PATCH] Day 20

---
 AdventOfCode2017/AdventOfCode2017.fsproj |  6 +-
 AdventOfCode2017/Day20.fs                | 85 ++++++++++++++++++++++++
 AdventOfCode2017/Program.fs              |  5 ++
 Tests/Day20 tests.fs                     | 32 +++++++++
 Tests/Tests.fsproj                       |  1 +
 5 files changed, 128 insertions(+), 1 deletion(-)
 create mode 100644 AdventOfCode2017/Day20.fs
 create mode 100644 Tests/Day20 tests.fs

diff --git a/AdventOfCode2017/AdventOfCode2017.fsproj b/AdventOfCode2017/AdventOfCode2017.fsproj
index 81703e0..0229b06 100644
--- a/AdventOfCode2017/AdventOfCode2017.fsproj
+++ b/AdventOfCode2017/AdventOfCode2017.fsproj
@@ -25,7 +25,7 @@
     <PlatformTarget>AnyCPU</PlatformTarget>
     <DocumentationFile>bin\$(Configuration)\$(AssemblyName).XML</DocumentationFile>
     <Prefer32Bit>true</Prefer32Bit>
-    <StartArguments>19</StartArguments>
+    <StartArguments>20</StartArguments>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
     <DebugType>pdbonly</DebugType>
@@ -78,6 +78,7 @@
     <Compile Include="Day18Part1.fs" />
     <Compile Include="Day18Part2.fs" />
     <Compile Include="Day19.fs" />
+    <Compile Include="Day20.fs" />
     <Compile Include="Program.fs" />
     <None Include="App.config" />
     <Content Include="Data\day01.input">
@@ -137,6 +138,9 @@
     <Content Include="Data\day19.input">
       <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
     </Content>
+    <Content Include="Data\day20.input">
+      <CopyToOutputDirectory>PreserveNewest</CopyToOutputDirectory>
+    </Content>
     <Content Include="packages.config" />
   </ItemGroup>
   <ItemGroup>
diff --git a/AdventOfCode2017/Day20.fs b/AdventOfCode2017/Day20.fs
new file mode 100644
index 0000000..c7179b6
--- /dev/null
+++ b/AdventOfCode2017/Day20.fs
@@ -0,0 +1,85 @@
+module AdventOfCode2017.Day20
+
+open System
+
+type Vec =
+    { X : float; Y : float; Z : float }
+    with
+        member this.SquareNorm = this.X ** 2. + this.Y ** 2. + this.Z ** 2.
+
+type Particule =
+    { Pos : Vec; V : Vec; A : Vec }
+
+let parseInput (input : string[]) : Particule[] =
+    input
+    |> Array.map (
+        fun line ->
+            let raw = line.Split ([| 'p'; 'v'; 'a'; '='; '<'; '>'; ' '; ',' |], StringSplitOptions.RemoveEmptyEntries)
+            {
+                Pos = { X = float raw.[0]; Y = float raw.[1]; Z = float raw.[2] }
+                V   = { X = float raw.[3]; Y = float raw.[4]; Z = float raw.[5] }
+                A   = { X = float raw.[6]; Y = float raw.[7]; Z = float raw.[8] }
+            }
+    )
+
+let nearestZero (particules : Particule[]) : int =
+    particules |> Array.indexed |> Array.minBy (fun (_, p) -> p.A.SquareNorm, p.V.SquareNorm, p.Pos.SquareNorm) |> fst
+
+let collide (p1 : Particule) (p2 : Particule) : int64 option =
+    let t a b c d e f =
+        let denom = 2. * (c - f)
+        if denom = 0. then
+            (d - a) / (b - e)
+        else
+            let root = (2. * b + c - 2. * e - f) ** 2. - 8. * (a - d) * (c - f)
+            if root < 0. then
+                Double.PositiveInfinity
+            else
+                let f sign = (-2. * b - c + 2. * e + f + sign * sqrt root) / denom
+                max (f 1.) (f -1.)
+
+    let ts =
+        [
+            t p1.Pos.X p1.V.X p1.A.X p2.Pos.X p2.V.X p2.A.X
+            t p1.Pos.Y p1.V.Y p1.A.Y p2.Pos.Y p2.V.Y p2.A.Y
+            t p1.Pos.Z p1.V.Z p1.A.Z p2.Pos.Z p2.V.Z p2.A.Z
+        ]
+        |> List.filter (Double.IsNaN >> not)
+
+    if ts |> List.isEmpty then
+        Some 0L
+    elif ts |> List.exists (fun t -> Double.IsInfinity t || t < 0.) then
+        None
+    else
+        let tsInt = ts |> List.map (fun t -> t * 10. |> int64) // Rounding.
+        let h = tsInt |> List.head
+        if tsInt |> List.tail |> List.forall ((=) h) then
+            Some h
+        else
+            None
+
+let nbAlive (particules : Particule[]) : int =
+    let nbDestroyed =
+        [
+            for i = 0 to particules.Length - 1 do
+                for j = i + 1 to particules.Length - 1 do
+                    let p1, p2 = particules.[i], particules.[j]
+                    match collide p1 p2 with
+                    | Some t ->
+                        yield t, i
+                        yield t, j
+                    | _ -> ()
+        ]
+        |> List.groupBy (fun (t, _) -> t)
+        |> List.sortBy (fun (t, _) -> t)
+        |> List.map snd
+        |> List.fold (
+            fun destroyedParticules particules ->
+                let collidedParticules = (particules |> List.map snd |> Set.ofList) - destroyedParticules
+                if collidedParticules |> Set.count > 1 then
+                    destroyedParticules + collidedParticules
+                else
+                    destroyedParticules
+        ) Set.empty
+        |> Set.count
+    particules.Length - nbDestroyed
diff --git a/AdventOfCode2017/Program.fs b/AdventOfCode2017/Program.fs
index 8123d7b..adf50dd 100644
--- a/AdventOfCode2017/Program.fs
+++ b/AdventOfCode2017/Program.fs
@@ -88,6 +88,10 @@ let day19 () =
     let word, length = Day19.followThePath input
     sprintf "part1 = %A, part2 = %A" word length
 
+let day20 () =
+    let input = File.ReadAllLines "Data/day20.input" |> Day20.parseInput
+    sprintf "part1 = %A, part2 = %A" (Day20.nearestZero input) (Day20.nbAlive input)
+
 let doDay (n : int) =
     let sw = Diagnostics.Stopwatch ()
     sw.Start ()
@@ -112,6 +116,7 @@ let doDay (n : int) =
         | 17 -> day17 ()
         | 18 -> day18 ()
         | 19 -> day19 ()
+        | 20 -> day20 ()
         | _ -> raise <| NotImplementedException ()
     printfn "Result of day %i: %s (time : %i ms)" n result sw.ElapsedMilliseconds
 
diff --git a/Tests/Day20 tests.fs b/Tests/Day20 tests.fs
new file mode 100644
index 0000000..27cc33f
--- /dev/null
+++ b/Tests/Day20 tests.fs	
@@ -0,0 +1,32 @@
+namespace AdventOfCode2017.Tests
+
+open System
+open Xunit
+open Xunit.Abstractions
+open Swensen.Unquote
+
+open AdventOfCode2017
+
+type ``Day20 tests`` (output : ITestOutputHelper) =
+
+    [<Fact>]
+    let ``(Part1) From web page`` () =
+        let input =
+            [|
+                "p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0>"
+                "p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0>"
+            |] |> Day20.parseInput
+
+        Day20.nearestZero input =! 0
+
+    [<Fact>]
+    let ``(Part2) From web page`` () =
+        let input =
+            [|
+                "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>"
+            |] |> Day20.parseInput
+
+        Day20.nbAlive input =! 1
\ No newline at end of file
diff --git a/Tests/Tests.fsproj b/Tests/Tests.fsproj
index 73549e4..1987918 100644
--- a/Tests/Tests.fsproj
+++ b/Tests/Tests.fsproj
@@ -74,6 +74,7 @@
     <Compile Include="Day17 tests.fs" />
     <Compile Include="Day18 tests.fs" />
     <Compile Include="Day19 tests.fs" />
+    <Compile Include="Day20 tests.fs" />
     <Content Include="App.config" />
     <Content Include="packages.config" />
   </ItemGroup>
-- 
2.45.2