day 22 gleam complete

8 files changed, 335 insertions, 11 deletions

diff --git a/aoc2023/gleam.toml b/aoc2023/gleam.toml
index 5b60622..8190aef 100644
--- a/aoc2023/gleam.toml
+++ b/aoc2023/gleam.toml
@@ -1,6 +1,6 @@
 name = "aoc2023"
 version = "0.1.0"
-gleam = ">= 0.32.0"
+gleam = ">= 0.33.0"
 
 # Fill out these fields if you intend to generate HTML documentation or publish
 # your project to the Hex package manager.
@@ -11,7 +11,7 @@ gleam = ">= 0.32.0"
 # links = [{ title = "Website", href = "https://gleam.run" }]
 
 [dependencies]
-gleam_stdlib = "~> 0.32"
+gleam_stdlib = "~> 0.33"
 simplifile = "~> 1.0"
 gleam_erlang = "~> 0.23"
 gleam_community_maths = "~> 1.0"
@@ -19,5 +19,4 @@ gleam_otp = "~> 0.8"
 pqueue = "~> 2.0"
 
 [dev-dependencies]
-gleeunit = "~> 1.0"
 adglent = "~> 1.2"
diff --git a/aoc2023/manifest.toml b/aoc2023/manifest.toml
index a6f708a..900b5c0 100644
--- a/aoc2023/manifest.toml
+++ b/aoc2023/manifest.toml
@@ -2,18 +2,17 @@
 # You typically do not need to edit this file
 
 packages = [
-  { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["glint", "gleam_community_ansi", "snag", "gleam_erlang", "gleam_stdlib", "gleam_http", "gleam_otp", "tom", "gap", "simplifile", "gleam_httpc"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" },
-  { name = "gap", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_ansi"], otp_app = "gap", source = "hex", outer_checksum = "5E369751DB547BFBDA7735878DC04DA31FCA3112193D61D5D7566010C7C8BA98" },
-  { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_colour"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" },
+  { name = "adglent", version = "1.2.0", build_tools = ["gleam"], requirements = ["glint", "gleam_http", "gleam_stdlib", "simplifile", "gleam_erlang", "gap", "gleam_httpc", "snag", "gleam_community_ansi", "tom", "gleam_otp"], otp_app = "adglent", source = "hex", outer_checksum = "A20D35001061F8AD602E3B92FB3AC0E1E4EEC642AD2AAE0ACEAD3A85F37DA7F0" },
+  { name = "gap", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_community_ansi", "gleam_stdlib"], otp_app = "gap", source = "hex", outer_checksum = "5E369751DB547BFBDA7735878DC04DA31FCA3112193D61D5D7566010C7C8BA98" },
+  { name = "gleam_community_ansi", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_stdlib"], otp_app = "gleam_community_ansi", source = "hex", outer_checksum = "8B5A9677BC5A2738712BBAF2BA289B1D8195FDF962BBC769569976AD5E9794E1" },
   { name = "gleam_community_colour", version = "1.2.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_colour", source = "hex", outer_checksum = "036C206886AFB9F153C552700A7A0B4D2864E3BC96A20C77E5F34A013C051BE3" },
   { name = "gleam_community_maths", version = "1.0.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_community_maths", source = "hex", outer_checksum = "1B9DB313E94A0E4674CA84C5D29F45ECFE211BFB38ABBD8B23737395F47D08B3" },
   { name = "gleam_erlang", version = "0.23.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_erlang", source = "hex", outer_checksum = "C21CFB816C114784E669FFF4BBF433535EEA9960FA2F216209B8691E87156B96" },
   { name = "gleam_http", version = "3.5.2", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleam_http", source = "hex", outer_checksum = "AECDA43AFD523D07A8F09068598A6E271C505278A0CB6F9C7A2E4365EAE8D11E" },
   { name = "gleam_httpc", version = "2.1.1", build_tools = ["gleam"], requirements = ["gleam_http", "gleam_stdlib"], otp_app = "gleam_httpc", source = "hex", outer_checksum = "06AC1CA52C9BAA66C9D5C0303B2BF34E39AA1546BB96AEE496E4B06D513AB8C7" },
-  { name = "gleam_otp", version = "0.8.0", build_tools = ["gleam"], requirements = ["gleam_erlang", "gleam_stdlib"], otp_app = "gleam_otp", source = "hex", outer_checksum = "18EF8242A5E54BA92F717C7222F03B3228AEE00D1F286D4C56C3E8C18AA2588E" },
+  { name = "gleam_otp", version = "0.8.0", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_erlang"], otp_app = "gleam_otp", source = "hex", outer_checksum = "18EF8242A5E54BA92F717C7222F03B3228AEE00D1F286D4C56C3E8C18AA2588E" },
   { name = "gleam_stdlib", version = "0.33.0", build_tools = ["gleam"], requirements = [], otp_app = "gleam_stdlib", source = "hex", outer_checksum = "539E37A2AA5EBE8E75F4B74755E4CC604BD957C3000AC8D705A2024886A2738B" },
-  { name = "gleeunit", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "gleeunit", source = "hex", outer_checksum = "D3682ED8C5F9CAE1C928F2506DE91625588CC752495988CBE0F5653A42A6F334" },
-  { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_community_colour", "gleam_community_ansi", "gleam_stdlib", "snag"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" },
+  { name = "glint", version = "0.13.0", build_tools = ["gleam"], requirements = ["gleam_stdlib", "gleam_community_ansi", "gleam_community_colour", "snag"], otp_app = "glint", source = "hex", outer_checksum = "46E56049CD370D61F720D319D0AB970408C9336EEB918F08B5DCB1DCE9845FA3" },
   { name = "pqueue", version = "2.0.7", build_tools = ["rebar3"], requirements = [], otp_app = "pqueue", source = "hex", outer_checksum = "8B0204BB202335890E4E7F9B99A8EC0B84DDB8513EE298EB180EE9B3BCB4C859" },
   { name = "simplifile", version = "1.0.0", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "simplifile", source = "hex", outer_checksum = "0BD6F0E7DA1A7E11D18B8AD48453225CAFCA4C8CFB4513D217B372D2866C501C" },
   { name = "snag", version = "0.2.1", build_tools = ["gleam"], requirements = ["gleam_stdlib"], otp_app = "snag", source = "hex", outer_checksum = "8FD70D8FB3728E08AC425283BB509BB0F012BE1AE218424A597CDE001B0EE589" },
@@ -25,7 +24,6 @@ adglent = { version = "~> 1.2" }
 gleam_community_maths = { version = "~> 1.0" }
 gleam_erlang = { version = "~> 0.23" }
 gleam_otp = { version = "~> 0.8" }
-gleam_stdlib = { version = "~> 0.32" }
-gleeunit = { version = "~> 1.0" }
+gleam_stdlib = { version = "~> 0.33" }
 pqueue = { version = "~> 2.0" }
 simplifile = { version = "~> 1.0" }
diff --git a/aoc2023/src/day21/.gitignore b/aoc2023/src/day21/.gitignore
new file mode 100644
index 0000000..ae40cea
--- /dev/null
+++ b/aoc2023/src/day21/.gitignore
@@ -0,0 +1 @@
+input.txt
\ No newline at end of file
diff --git a/aoc2023/src/day21/solve.gleam b/aoc2023/src/day21/solve.gleam
new file mode 100644
index 0000000..4d5c246
--- /dev/null
+++ b/aoc2023/src/day21/solve.gleam
@@ -0,0 +1,25 @@
+import adglent.{First, Second}
+import gleam/io
+
+pub fn part1(input: String) {
+  todo as "Implement solution to part 1"
+}
+
+pub fn part2(input: String) {
+  todo as "Implement solution to part 2"
+}
+
+pub fn main() {
+  let assert Ok(part) = adglent.get_part()
+  let assert Ok(input) = adglent.get_input("21")
+  case part {
+    First ->
+      part1(input)
+      |> adglent.inspect
+      |> io.println
+    Second ->
+      part2(input)
+      |> adglent.inspect
+      |> io.println
+  }
+}
diff --git a/aoc2023/src/day22/.gitignore b/aoc2023/src/day22/.gitignore
new file mode 100644
index 0000000..ae40cea
--- /dev/null
+++ b/aoc2023/src/day22/.gitignore
@@ -0,0 +1 @@
+input.txt
\ No newline at end of file
diff --git a/aoc2023/src/day22/solve.gleam b/aoc2023/src/day22/solve.gleam
new file mode 100644
index 0000000..b1c360f
--- /dev/null
+++ b/aoc2023/src/day22/solve.gleam
@@ -0,0 +1,202 @@
+import adglent.{First, Second}
+import gleam/bool
+import gleam/dict.{type Dict}
+import gleam/int
+import gleam/io
+import gleam/list
+import gleam/option.{None, Some}
+import gleam/regex
+import gleam/result
+import gleam/set.{type Set}
+import gleam/string
+
+type Point {
+  Point(x: Int, y: Int, z: Int)
+}
+
+fn down_one(p: Point) -> Point {
+  Point(..p, z: p.z - 1)
+}
+
+type Block {
+  Block(index: Int, from: Point, to: Point)
+}
+
+fn compare_blocks(b1: Block, b2: Block) {
+  int.compare(b1.to.z, b2.to.z)
+}
+
+type Space =
+  Dict(Point, Block)
+
+type AllBlocks =
+  Dict(Block, List(Point))
+
+type BlockTree =
+  Dict(Int, Set(Int))
+
+fn parse_block(index: Int, input: String) -> Block {
+  let assert Ok(re) = regex.from_string("(.*),(.*),(.*)~(.*),(.*),(.*)")
+
+  let assert [scan] = regex.scan(with: re, content: input)
+
+  let assert [x1, y1, z1, x2, y2, z2] =
+    scan.submatches
+    |> option.all
+    |> option.unwrap([])
+    |> list.map(int.parse)
+    |> result.values
+  Block(index: index, from: Point(x1, y1, z1), to: Point(x2, y2, z2))
+}
+
+fn cross_section_at_level(b: Block, z: Int) -> List(Point) {
+  use x <- list.flat_map(list.range(b.from.x, b.to.x))
+  use y <- list.map(list.range(b.from.y, b.to.y))
+  Point(x, y, z)
+}
+
+fn place_block(space: Space, b: Block, z: Int) -> Space {
+  let now_occupied = {
+    use x <- list.flat_map(list.range(b.from.x, b.to.x))
+    use y <- list.flat_map(list.range(b.from.y, b.to.y))
+    use z <- list.map(list.range(z, z + b.to.z - b.from.z))
+    #(Point(x, y, z), b)
+  }
+
+  dict.merge(space, dict.from_list(now_occupied))
+}
+
+fn find_lowest_level(space: Space, b: Block) -> Space {
+  do_find_lowest(space, b, b.from.z)
+}
+
+fn do_find_lowest(space: Space, b: Block, z: Int) -> Space {
+  let is_intersecting =
+    list.any(cross_section_at_level(b, z), dict.has_key(space, _))
+
+  case z, is_intersecting {
+    0, _ -> place_block(space, b, 1)
+    _, True -> place_block(space, b, z + 1)
+    _, False -> do_find_lowest(space, b, z - 1)
+  }
+}
+
+fn to_block_positions(space: Space) -> AllBlocks {
+  use acc, point, index <- dict.fold(space, dict.new())
+  use points <- dict.update(acc, index)
+  case points {
+    Some(ps) -> [point, ..ps]
+    None -> [point]
+  }
+}
+
+fn above_blocks(blocks: AllBlocks) -> BlockTree {
+  use acc, block, points <- dict.fold(blocks, dict.new())
+  use _ <- dict.update(acc, block.index)
+  {
+    use above_block, above_points <- dict.filter(blocks)
+    above_block.index != block.index
+    && list.any(above_points, fn(p) { list.contains(points, down_one(p)) })
+  }
+  |> dict.keys
+  |> list.map(fn(b) { b.index })
+  |> set.from_list
+}
+
+fn below_blocks(blocktree: BlockTree) -> BlockTree {
+  use acc, block, _ <- dict.fold(blocktree, dict.new())
+  use _ <- dict.update(acc, block)
+  {
+    use _, aboves <- dict.filter(blocktree)
+    set.contains(aboves, block)
+  }
+  |> dict.keys
+  |> set.from_list
+}
+
+fn vulnerable_blocks(below_tree: BlockTree) -> List(Int) {
+  use block <- list.filter(dict.keys(below_tree))
+  use bs <- list.any(dict.values(below_tree))
+  !{ set.size(bs) == 0 } && { set.size(set.delete(bs, block)) == 0 }
+}
+
+pub fn part1(input: String) {
+  let settled_blocks =
+    input
+    |> string.split("\n")
+    |> list.index_map(parse_block)
+    |> list.sort(compare_blocks)
+    |> list.fold(dict.new(), find_lowest_level)
+
+  let block_positions = to_block_positions(settled_blocks)
+  let above_blocks = above_blocks(block_positions)
+  let below_blocks = below_blocks(above_blocks)
+
+  let vulnerable_blocks = vulnerable_blocks(below_blocks)
+
+  list.length(dict.keys(block_positions))
+  - list.length(vulnerable_blocks)
+  |> string.inspect
+}
+
+fn all_falling_blocks(n: Int, above: BlockTree, below: BlockTree) {
+  let starting_set = set.insert(set.new(), n)
+  do_falling_blocks(starting_set, starting_set, above, below)
+}
+
+fn do_falling_blocks(
+  fallen: Set(Int),
+  blocks: Set(Int),
+  above: BlockTree,
+  below: BlockTree,
+) -> Int {
+  use <- bool.guard(set.size(blocks) == 0, set.size(fallen) - 1)
+
+  let blocks_above =
+    {
+      use block <- list.flat_map(set.to_list(blocks))
+      let assert Ok(supports) = dict.get(above, block)
+      use support <- list.filter(set.to_list(supports))
+      let assert Ok(supportings) = dict.get(below, support)
+      use supporting <- list.all(set.to_list(supportings))
+      set.contains(fallen, supporting)
+    }
+    |> set.from_list()
+
+  set.union(fallen, blocks_above)
+  |> do_falling_blocks(blocks_above, above, below)
+}
+
+pub fn part2(input: String) {
+  let settled_blocks =
+    input
+    |> string.split("\n")
+    |> list.index_map(parse_block)
+    |> list.sort(compare_blocks)
+    |> list.fold(dict.new(), find_lowest_level)
+
+  let block_positions = to_block_positions(settled_blocks)
+  let above_blocks = above_blocks(block_positions)
+  let below_blocks = below_blocks(above_blocks)
+
+  let vulnerable_blocks = vulnerable_blocks(below_blocks)
+
+  list.map(vulnerable_blocks, all_falling_blocks(_, above_blocks, below_blocks))
+  |> int.sum
+  |> string.inspect
+}
+
+pub fn main() {
+  let assert Ok(part) = adglent.get_part()
+  let assert Ok(input) = adglent.get_input("22")
+  case part {
+    First ->
+      part1(input)
+      |> adglent.inspect
+      |> io.println
+    Second ->
+      part2(input)
+      |> adglent.inspect
+      |> io.println
+  }
+}
diff --git a/aoc2023/test/day21/day21_test.gleam b/aoc2023/test/day21/day21_test.gleam
new file mode 100644
index 0000000..5f46808
--- /dev/null
+++ b/aoc2023/test/day21/day21_test.gleam
@@ -0,0 +1,38 @@
+import gleam/list
+import showtime/tests/should
+import adglent.{type Example, Example}
+import day21/solve
+
+type Problem1AnswerType =
+  String
+
+type Problem2AnswerType =
+  String
+
+/// Add examples for part 1 here:
+/// ```gleam
+///const part1_examples: List(Example(Problem1AnswerType)) = [Example("some input", "")]
+/// ```
+const part1_examples: List(Example(Problem1AnswerType)) = []
+
+/// Add examples for part 2 here:
+/// ```gleam
+///const part2_examples: List(Example(Problem2AnswerType)) = [Example("some input", "")]
+/// ```
+const part2_examples: List(Example(Problem2AnswerType)) = []
+
+pub fn part1_test() {
+  part1_examples
+  |> should.not_equal([])
+  use example <- list.map(part1_examples)
+  solve.part1(example.input)
+  |> should.equal(example.answer)
+}
+
+pub fn part2_test() {
+  part2_examples
+  |> should.not_equal([])
+  use example <- list.map(part2_examples)
+  solve.part2(example.input)
+  |> should.equal(example.answer)
+}
diff --git a/aoc2023/test/day22/day22_test.gleam b/aoc2023/test/day22/day22_test.gleam
new file mode 100644
index 0000000..1760ece
--- /dev/null
+++ b/aoc2023/test/day22/day22_test.gleam
@@ -0,0 +1,60 @@
+import gleam/list
+import showtime/tests/should
+import adglent.{type Example, Example}
+import day22/solve
+
+type Problem1AnswerType =
+  String
+
+type Problem2AnswerType =
+  String
+
+/// Add examples for part 1 here:
+/// ```gleam
+///const part1_examples: List(Example(Problem1AnswerType)) = [Example("some input", "")]
+/// ```
+const part1_examples: List(Example(Problem1AnswerType)) = [
+  Example(
+    "1,0,1~1,2,1
+0,0,2~2,0,2
+0,2,3~2,2,3
+0,0,4~0,2,4
+2,0,5~2,2,5
+0,1,6~2,1,6
+1,1,8~1,1,9",
+    "5",
+  ),
+]
+
+/// Add examples for part 2 here:
+/// ```gleam
+///const part2_examples: List(Example(Problem2AnswerType)) = [Example("some input", "")]
+/// ```
+const part2_examples: List(Example(Problem2AnswerType)) = [
+  Example(
+    "1,0,1~1,2,1
+0,0,2~2,0,2
+0,2,3~2,2,3
+0,0,4~0,2,4
+2,0,5~2,2,5
+0,1,6~2,1,6
+1,1,8~1,1,9",
+    "7",
+  ),
+]
+
+pub fn part1_test() {
+  part1_examples
+  |> should.not_equal([])
+  use example <- list.map(part1_examples)
+  solve.part1(example.input)
+  |> should.equal(example.answer)
+}
+
+pub fn part2_test() {
+  part2_examples
+  |> should.not_equal([])
+  use example <- list.map(part2_examples)
+  solve.part2(example.input)
+  |> should.equal(example.answer)
+}