diff options
| -rw-r--r-- | aoc-2020-gleam/gleam.toml | 1 | ||||
| -rw-r--r-- | aoc-2020-gleam/manifest.toml | 4 | ||||
| -rw-r--r-- | aoc-2020-gleam/src/days/day14.gleam | 180 |
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 +} |