From dc32c2a8cbcf712715279ee6a11cd22bec49f066 Mon Sep 17 00:00:00 2001 From: Ummon Date: Mon, 18 Dec 2017 16:00:39 +0100 Subject: [PATCH] Day 18 --- AdventOfCode2017/AdventOfCode2017.fsproj | 7 +- AdventOfCode2017/Day18Part1.fs | 54 +++++++++++++++ AdventOfCode2017/Day18Part2.fs | 84 ++++++++++++++++++++++++ AdventOfCode2017/Program.fs | 5 ++ Tests/Day18 tests.fs | 41 ++++++++++++ Tests/Tests.fsproj | 1 + 6 files changed, 191 insertions(+), 1 deletion(-) create mode 100644 AdventOfCode2017/Day18Part1.fs create mode 100644 AdventOfCode2017/Day18Part2.fs create mode 100644 Tests/Day18 tests.fs diff --git a/AdventOfCode2017/AdventOfCode2017.fsproj b/AdventOfCode2017/AdventOfCode2017.fsproj index 16d2ffd..2d2f009 100644 --- a/AdventOfCode2017/AdventOfCode2017.fsproj +++ b/AdventOfCode2017/AdventOfCode2017.fsproj @@ -25,7 +25,7 @@ AnyCPU bin\$(Configuration)\$(AssemblyName).XML true - 16 + 18 pdbonly @@ -75,6 +75,8 @@ + + @@ -128,6 +130,9 @@ PreserveNewest + + PreserveNewest + diff --git a/AdventOfCode2017/Day18Part1.fs b/AdventOfCode2017/Day18Part1.fs new file mode 100644 index 0000000..7bdf670 --- /dev/null +++ b/AdventOfCode2017/Day18Part1.fs @@ -0,0 +1,54 @@ +module AdventOfCode2017.Day18Part1 + +open System + +type From = + | FromReg of char + | FromValue of int64 + +type Instruction = + | Sound of From + | Set of char * From + | Add of char * From + | Mul of char * From + | Mod of char * From + | Recover of char + | Jump of From * From + +let parseInput (lines : string[]) : Instruction[] = + let readFrom (str : string) = if Char.IsLetter str.[0] then FromReg str.[0] else FromValue (int64 str) + lines + |> Array.map ( + fun line -> + match line.Split ' ' with + | [| "snd"; v |] -> Sound (readFrom v) + | [| "set"; reg; v |] -> Set (reg.[0], readFrom v) + | [| "add"; reg; v |] -> Add (reg.[0], readFrom v) + | [| "mul"; reg; v |] -> Mul (reg.[0], readFrom v) + | [| "mod"; reg; v |] -> Mod (reg.[0], readFrom v) + | [| "rcv"; reg |] -> Recover reg.[0] + | [| "jgz"; v1; v2 |] -> Jump (readFrom v1, readFrom v2) + | _ -> failwithf "Can't parse line: %s" line + ) + +type Register = Map + +let run (instructions : Instruction[]) = + let rec exec (register : Register) (cursor : int) (lastSoundPlayed : int64) : int64 = + let get = function FromReg reg -> register |> Map.tryFind reg |> Option.defaultValue 0L | FromValue v -> v + let set (reg : char) (v : int64) = register |> Map.add reg v + + match instructions.[cursor] with + | Sound from -> exec register (cursor + 1) (get from) + | Set (reg, from) -> exec (set reg (get from)) (cursor + 1) lastSoundPlayed + | Add (reg, from) -> exec (set reg (get (FromReg reg) + get from)) (cursor + 1) lastSoundPlayed + | Mul (reg, from) -> exec (set reg (get (FromReg reg) * get from)) (cursor + 1) lastSoundPlayed + | Mod (reg, from) -> exec (set reg (get (FromReg reg) % get from)) (cursor + 1) lastSoundPlayed + | Recover reg -> + if lastSoundPlayed <> 0L && get (FromReg reg) <> 0L then + lastSoundPlayed + else + exec register (cursor + 1) lastSoundPlayed + | Jump (from1, from2) -> exec register (cursor + if get from1 > 0L then get from2 |> int else 1) lastSoundPlayed + + exec Map.empty 0 0L diff --git a/AdventOfCode2017/Day18Part2.fs b/AdventOfCode2017/Day18Part2.fs new file mode 100644 index 0000000..58cbf84 --- /dev/null +++ b/AdventOfCode2017/Day18Part2.fs @@ -0,0 +1,84 @@ +module AdventOfCode2017.Day18Part2 + +open System +open System.Threading + +type From = + | FromReg of char + | FromValue of int64 + +type Instruction = + | Receive of char + | Send of From + | Set of char * From + | Add of char * From + | Mul of char * From + | Mod of char * From + | Jump of From * From + +let parseInput (lines : string[]) : Instruction[] = + let readFrom (str : string) = if Char.IsLetter str.[0] then FromReg str.[0] else FromValue (int64 str) + lines + |> Array.map ( + fun line -> + match line.Split ' ' with + | [| "snd"; v |] -> Send (readFrom v) + | [| "set"; reg; v |] -> Set (reg.[0], readFrom v) + | [| "add"; reg; v |] -> Add (reg.[0], readFrom v) + | [| "mul"; reg; v |] -> Mul (reg.[0], readFrom v) + | [| "mod"; reg; v |] -> Mod (reg.[0], readFrom v) + | [| "rcv"; reg |] -> Receive reg.[0] + | [| "jgz"; v1; v2 |] -> Jump (readFrom v1, readFrom v2) + | _ -> failwithf "Can't parse line: %s" line + ) + +type Register = Map + +type Agent (instructions : Instruction[], id : int) as this = + let mutable nbSent = 0 + let finishedEvent = new AutoResetEvent false + let mailbox = + new MailboxProcessor ( + fun inbox -> + let rec exec (register : Register) (cursor : int) : Async = + let get = function FromReg reg -> register |> Map.tryFind reg |> Option.defaultValue 0L | FromValue v -> v + let set (reg : char) (v : int64) = register |> Map.add reg v + async { + match instructions.[cursor] with + | Send from -> + nbSent <- nbSent + 1 + this.Other.Value.Post (get from) + return! exec register (cursor + 1) + | Set (reg, from) -> return! exec (set reg (get from)) (cursor + 1) + | Add (reg, from) -> return! exec (set reg (get (FromReg reg) + get from)) (cursor + 1) + | Mul (reg, from) -> return! exec (set reg (get (FromReg reg) * get from)) (cursor + 1) + | Mod (reg, from) -> return! exec (set reg (get (FromReg reg) % get from)) (cursor + 1) + | Receive reg -> + let! value = inbox.TryReceive 100 + match value with + | Some value -> return! exec (set reg value) (cursor + 1) + | None -> finishedEvent.Set () |> ignore + | Jump (from1, from2) -> + return! exec register (cursor + if get from1 > 0L then get from2 |> int else 1) + } + exec (Map.ofList [ 'p', int64 id ]) 0 + ) + + member val Other : MailboxProcessor option = None with get, set + member this.Start () = mailbox.Start () + member this.Mailbox = mailbox + member this.NbSent = + finishedEvent.WaitOne () |> ignore + nbSent + +let run (instructions : Instruction[]) = + let agent0 = Agent (instructions, 0) + let agent1 = Agent (instructions, 1) + + agent0.Other <- Some agent1.Mailbox + agent1.Other <- Some agent0.Mailbox + + agent0.Start () + agent1.Start () + + agent1.NbSent \ No newline at end of file diff --git a/AdventOfCode2017/Program.fs b/AdventOfCode2017/Program.fs index 299f276..f845472 100644 --- a/AdventOfCode2017/Program.fs +++ b/AdventOfCode2017/Program.fs @@ -79,6 +79,10 @@ let day17 () = let input = File.ReadAllText "Data/day17.input" |> int sprintf "part1 = %A, part2 = %A" (Day17.spinLock1 input) (Day17.spinLock2 input) +let day18 () = + let input = File.ReadAllLines "Data/day18.input" + sprintf "part1 = %A, part2 = %A" (Day18Part1.run (Day18Part1.parseInput input)) (Day18Part2.run (Day18Part2.parseInput input)) + let doDay (n : int) = let sw = Diagnostics.Stopwatch () sw.Start () @@ -101,6 +105,7 @@ let doDay (n : int) = | 15 -> day15 () | 16 -> day16 () | 17 -> day17 () + | 18 -> day18 () | _ -> raise <| NotImplementedException () printfn "Result of day %i: %s (time : %i ms)" n result sw.ElapsedMilliseconds diff --git a/Tests/Day18 tests.fs b/Tests/Day18 tests.fs new file mode 100644 index 0000000..4a5576e --- /dev/null +++ b/Tests/Day18 tests.fs @@ -0,0 +1,41 @@ +namespace AdventOfCode2017.Tests + +open System +open Xunit +open Xunit.Abstractions +open Swensen.Unquote + +open AdventOfCode2017 + +type ``Day18 tests`` (output : ITestOutputHelper) = + + [] + let ``(Part1) From web page`` () = + let input = + [| + "set a 1" + "add a 2" + "mul a a" + "mod a 5" + "snd a" + "set a 0" + "rcv a" + "jgz a -1" + "set a 1" + "jgz a -2" + |] + Day18Part1.run (Day18Part1.parseInput input) =! 4L + + [] + let ``(Part2) From web page`` () = + let input = + [| + "snd 1" + "snd 2" + "snd p" + "rcv a" + "rcv b" + "rcv c" + "rcv d" + |] + Day18Part2.run (Day18Part2.parseInput input) =! 3 \ No newline at end of file diff --git a/Tests/Tests.fsproj b/Tests/Tests.fsproj index c9a9bd6..32cfbf5 100644 --- a/Tests/Tests.fsproj +++ b/Tests/Tests.fsproj @@ -72,6 +72,7 @@ + -- 2.45.2