Finish day 14

3 files changed, 184 insertions, 1 deletions

diff --git a/aoc-2020-gleam/gleam.toml b/aoc-2020-gleam/gleam.toml
index 1ac9a67..97cada1 100644
--- a/aoc-2020-gleam/gleam.toml
+++ b/aoc-2020-gleam/gleam.toml
@@ -6,3 +6,4 @@ description = "A Gleam project"
 gleam_stdlib = "~> 0.26"
 gleam_erlang = "~> 0.17"
 gleam_otp = "~> 0.5"
+gleam_bitwise = "~> 1.2"
diff --git a/aoc-2020-gleam/manifest.toml b/aoc-2020-gleam/manifest.toml
index fd44967..288ecfe 100644
--- a/aoc-2020-gleam/manifest.toml
+++ b/aoc-2020-gleam/manifest.toml
@@ -2,12 +2,14 @@
 # You typically do not need to edit this file
 
 packages = [
+  { name = "gleam_bitwise", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_bitwise", source = "hex", outer_checksum = "6064699EFBABB1CA392DCB193D0E8B402FB042B4B46857B01E6875E643B57F54" },
   { name = "gleam_erlang", version = "0.18.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "C69F59D086AD50B80DE294FB0963550630971C9DC04E92B1F7AEEDD2C0BE226C" },
-  { name = "gleam_otp", version = "0.5.3", build_tools = ["gleam"], requirements = ["gleam_erlang", "gleam_stdlib"], otp_app = "gleam_otp", source = "hex", outer_checksum = "6E705B69464237353E0380AC8143BDB29A3F0BF6168755D5F2D6E55A34A8B077" },
+  { name = "gleam_otp", version = "0.5.3", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_erlang"], otp_app = "gleam_otp", source = "hex", outer_checksum = "6E705B69464237353E0380AC8143BDB29A3F0BF6168755D5F2D6E55A34A8B077" },
   { name = "gleam_stdlib", version = "0.27.0", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "9DBDD21B48C654182CDD8AA15ACF85E8E74A0438583C68BD7EF08BE89F999C6F" },
 ]
 
 [requirements]
+gleam_bitwise = "~> 1.2"
 gleam_erlang = "~> 0.17"
 gleam_otp = "~> 0.5"
 gleam_stdlib = "~> 0.26"
diff --git a/aoc-2020-gleam/src/days/day14.gleam b/aoc-2020-gleam/src/days/day14.gleam
new file mode 100644
index 0000000..11111cb
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day14.gleam
@@ -0,0 +1,180 @@
+import gleam/io
+import gleam/int
+import gleam/map.{Map}
+import gleam/list
+import gleam/pair
+import gleam/string as str
+import gleam/iterator as iter
+import gleam/bitwise as bit
+import ext/resultx as resx
+import util/input_util
+import util/graph
+import util/parser as p
+
+const bits: Int = 36
+
+type Instr {
+  SetMem(address: Int, value: Int)
+  ChangeMask(mask: String)
+}
+
+type Program =
+  List(Instr)
+
+type Memory =
+  Map(Int, Int)
+
+type Mask =
+  String
+
+type State =
+  #(Memory, Mask)
+
+fn parse_program(input: List(String)) -> Program {
+  let instr_parser =
+    p.or(
+      p.literal("mask = ")
+      |> p.proceed(with: p.any_str_greedy())
+      |> p.map(with: ChangeMask),
+      p.literal("mem[")
+      |> p.proceed(with: p.int())
+      |> p.skip(p.literal("] = "))
+      |> p.then(p.int())
+      |> p.map2(with: SetMem),
+    )
+
+  input
+  |> list.map(with: fn(line) {
+    line
+    |> p.parse_entire(with: instr_parser)
+    |> resx.assert_unwrap
+  })
+}
+
+fn apply_mask(value: Int, mask: Mask) -> Int {
+  let or_mask =
+    mask
+    |> str.replace(each: "X", with: "0")
+    |> int.base_parse(2)
+    |> resx.assert_unwrap
+
+  let and_mask =
+    mask
+    |> str.replace(each: "X", with: "1")
+    |> int.base_parse(2)
+    |> resx.assert_unwrap
+
+  value
+  |> bit.or(or_mask)
+  |> bit.and(and_mask)
+}
+
+fn execute_program(
+  program: Program,
+  interpreter: fn(State, Instr) -> State,
+) -> Int {
+  list.fold(
+    over: program,
+    from: #(map.new(), "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"),
+    with: interpreter,
+  )
+  |> pair.first
+  |> map.values
+  |> int.sum
+}
+
+fn memory_locations(from address: Int, with mask: String) -> List(Int) {
+  let address =
+    address
+    |> int.to_base_string(2)
+    |> resx.assert_unwrap
+    |> str.pad_left(to: bits, with: "0")
+    |> str.to_graphemes
+    |> list.zip(str.to_graphemes(mask))
+    |> list.map(with: fn(pair) {
+      let #(a, m) = pair
+      case m {
+        "0" -> a
+        "1" -> "1"
+        "X" -> "X"
+      }
+    })
+    |> str.concat
+
+  #("", address)
+  |> graph.dfs(with: fn(prev) {
+    let #(done, queue) = prev
+    case str.pop_grapheme(queue) {
+      Error(Nil) -> iter.empty()
+      Ok(#(head, rest)) ->
+        case head {
+          "0" | "1" -> iter.single(#(done <> head, rest))
+          "X" -> iter.from_list([#(done <> "0", rest), #(done <> "1", rest)])
+        }
+    }
+  })
+  |> iter.map(with: pair.first)
+  |> iter.filter(for: fn(res) { str.length(res) == bits })
+  |> iter.map(with: fn(res) {
+    res
+    |> int.base_parse(2)
+    |> resx.assert_unwrap
+  })
+  |> iter.to_list
+}
+
+fn part1(input: List(String)) -> Int {
+  input
+  |> parse_program
+  |> execute_program(fn(acc, instr) {
+    let #(memory, mask) = acc
+    case instr {
+      SetMem(address, value) -> {
+        #(
+          map.insert(
+            into: memory,
+            for: address,
+            insert: apply_mask(value, mask),
+          ),
+          mask,
+        )
+      }
+      ChangeMask(new_mask) -> #(memory, new_mask)
+    }
+  })
+}
+
+fn part2(input: List(String)) -> Int {
+  input
+  |> parse_program
+  |> execute_program(fn(acc, instr) {
+    let #(memory, mask) = acc
+    case instr {
+      SetMem(address, value) -> {
+        #(
+          memory_locations(from: address, with: mask)
+          |> list.fold(
+            from: memory,
+            with: fn(memory, address) {
+              map.insert(into: memory, for: address, insert: value)
+            },
+          ),
+          mask,
+        )
+      }
+      ChangeMask(new_mask) -> #(memory, new_mask)
+    }
+  })
+}
+
+pub fn main() -> Nil {
+  let test = input_util.read_lines("test14")
+  let assert 51 = part1(test)
+  let assert 208 = part2(test)
+
+  let input = input_util.read_lines("day14")
+  io.debug(part1(input))
+  io.debug(part2(input))
+
+  Nil
+}