From d28eaa8f239e948aedb5fd936909a98a28fcb42d Mon Sep 17 00:00:00 2001
From: Greg Burri <greg.burri@gmail.com>
Date: Sat, 23 Dec 2017 14:37:33 +0100
Subject: [PATCH] Day 22

---
 AdventOfCode2017/AdventOfCode2017.fsproj |  4 +-
 AdventOfCode2017/Day22.fs                | 49 +++++++++++++++++++-----
 AdventOfCode2017/Program.fs              |  4 +-
 Tests/Day22 tests.fs                     | 16 +++++++-
 4 files changed, 57 insertions(+), 16 deletions(-)

diff --git a/AdventOfCode2017/AdventOfCode2017.fsproj b/AdventOfCode2017/AdventOfCode2017.fsproj
index 596b518..1e530b7 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>21</StartArguments>
+    <StartArguments>22</StartArguments>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
     <DebugType>pdbonly</DebugType>
@@ -37,7 +37,7 @@
     <PlatformTarget>AnyCPU</PlatformTarget>
     <DocumentationFile>bin\$(Configuration)\$(AssemblyName).XML</DocumentationFile>
     <Prefer32Bit>true</Prefer32Bit>
-    <StartArguments>21</StartArguments>
+    <StartArguments>22</StartArguments>
   </PropertyGroup>
   <PropertyGroup>
     <MinimumVisualStudioVersion Condition="'$(MinimumVisualStudioVersion)' == ''">11</MinimumVisualStudioVersion>
diff --git a/AdventOfCode2017/Day22.fs b/AdventOfCode2017/Day22.fs
index 21ddf63..1de16e8 100644
--- a/AdventOfCode2017/Day22.fs
+++ b/AdventOfCode2017/Day22.fs
@@ -1,20 +1,49 @@
 module AdventOfCode2017.Day22
 
-type M = Set<int * int>
+type CellState = Weakened | Infected | Flagged | Clean
 
-let parseInput (lines : string[]) : M =
-    (*for i = 0 to lines.Length do
-        for*)
-    Set.empty
+// We dont use a 'Map' because the part 2 is too slow with it: ~1 min instead of 8 s.
+type M = System.Collections.Generic.Dictionary<int * int, CellState>
 
+let parseInput (lines : string[]) : M =
+    let m = M ()
+    for y = 0 to lines.Length - 1 do
+        for x = 0 to lines.[y].Length - 1 do
+            if lines.[y].[x] = '#' then
+                m.Add ((x - lines.[y].Length / 2, -y + lines.Length / 2), Infected)
+    m
 
-let infection (m : M) : int =
+let reverse (dx, dy) = -dx, -dy
+let turnRight = function 1, 0 -> 0, -1 | 0, 1 ->  1, 0 | -1, 0 -> 0, 1  | _ -> -1, 0
+let turnLeft  = turnRight >> reverse
 
-    let rec burst (i, j) (di, dj) n m =
+let infection (rule : CellState -> CellState * ((int * int) -> (int * int))) (nbIterations : int) (m : M) : int =
+    let rec burst (x, y) d n becomeInfected =
         if n = 0 then
-            ()
+            becomeInfected
         else
-            burst (i, j) (di, dj) (n - 1) m
+            let nextState, f =  match m.TryGetValue ((x, y)) with true, state -> rule state | _ -> rule Clean
+            let dx, dy = f d
+            if nextState = Clean then
+                m.Remove (x, y) |> ignore
+            else
+                m.[(x, y)] <- nextState
+            burst (x + dx, y + dy) (dx, dy) (n - 1) (if nextState = Infected then becomeInfected + 1 else becomeInfected)
+
+    burst (0, 0) (0, 1) nbIterations 0
 
-    23
+let infection1 (m : M) =
+    infection (
+        function
+        | Infected -> Clean, turnRight
+        | _ -> Infected, turnLeft
+    ) 10_000 m
 
+let infection2 (m : M) =
+    infection (
+        function
+        | Weakened -> Infected, id
+        | Infected -> Flagged, turnRight
+        | Flagged -> Clean, reverse
+        | Clean -> Weakened, turnLeft
+    ) 10_000_000 m
\ No newline at end of file
diff --git a/AdventOfCode2017/Program.fs b/AdventOfCode2017/Program.fs
index 4fee564..379137e 100644
--- a/AdventOfCode2017/Program.fs
+++ b/AdventOfCode2017/Program.fs
@@ -97,8 +97,8 @@ let day21 () =
     sprintf "part1 = %A, part2 = %A" (Day21.fractalArt input 5) (Day21.fractalArt input 18)
 
 let day22 () =
-    //let input = File.ReadAllLines "Data/day21.input" |> Day21.parseInput
-    sprintf "part1 = %A, part2 = %A" () ()
+    let input = File.ReadAllLines "Data/day22.input" |> Day22.parseInput
+    sprintf "part1 = %A, part2 = %A" (Day22.infection1 input) (Day22.infection2 input)
 
 let doDay (n : int) =
     let sw = Diagnostics.Stopwatch ()
diff --git a/Tests/Day22 tests.fs b/Tests/Day22 tests.fs
index ce41f5f..8578fee 100644
--- a/Tests/Day22 tests.fs	
+++ b/Tests/Day22 tests.fs	
@@ -11,8 +11,20 @@ type ``Day22 tests`` (output : ITestOutputHelper) =
 
     [<Fact>]
     let ``(Part1) From web page`` () =
-        ()
+        let input =
+            [|
+                "..#"
+                "#.."
+                "..."
+            |] |> Day22.parseInput
+        Day22.infection1 input =! 5587
 
     [<Fact>]
     let ``(Part2) From web page`` () =
-        ()
\ No newline at end of file
+        let input =
+            [|
+                "..#"
+                "#.."
+                "..."
+            |] |> Day22.parseInput
+        Day22.infection2 input =! 2511944
\ No newline at end of file
-- 
2.45.2