Solve part 1 of day 20

8 files changed, 184 insertions, 47 deletions

diff --git a/aoc-2020-gleam/src/days/day03.gleam b/aoc-2020-gleam/src/days/day03.gleam
index a3ab7b0..6a5ca5c 100644
--- a/aoc-2020-gleam/src/days/day03.gleam
+++ b/aoc-2020-gleam/src/days/day03.gleam
@@ -3,11 +3,11 @@ import gleam/io
 import gleam/int
 import gleam/result as res
 import gleam/string as str
-import gleam/function as fun
 import gleam/iterator as iter
 import gleam/set.{type Set}
 import ext/intx
 import ext/iteratorx as iterx
+import util/grid
 import util/input_util
 import util/pos2.{type Pos2}
 
@@ -24,20 +24,7 @@ type Area {
 fn parse_area(from text: String) -> Area {
   let lines = str.split(text, on: "\n")
 
-  let trees =
-    list.index_fold(over: lines, from: set.new(), with: fn(prev, line, y) {
-      line
-      |> str.to_graphemes
-      |> list.index_map(with: fn(grapheme, x) {
-        case grapheme {
-          "#" -> Ok(#(x, y))
-          _ -> Error(Nil)
-        }
-      })
-      |> list.filter_map(with: fun.identity)
-      |> set.from_list
-      |> set.union(prev)
-    })
+  let trees = grid.parse_grid(text, with: fn(x, y) { #(x, y) })
   let assert Ok(cycle) =
     lines
     |> list.first
@@ -47,12 +34,12 @@ fn parse_area(from text: String) -> Area {
   Area(trees, cycle, height)
 }
 
-fn has_tree(in area: Area, at pos: Pos2) -> Bool {
-  set.contains(area.trees, #(pos.0 % area.cycle, pos.1))
+fn has_tree(in area: Area, at t: Pos2) -> Bool {
+  set.contains(area.trees, #(pos2.x(t) % area.cycle, pos2.y(t)))
 }
 
-fn is_valid(pos: Pos2, in area: Area) -> Bool {
-  intx.is_between(pos.1, 0, and: area.height - 1)
+fn is_valid(p: Pos2, in area: Area) -> Bool {
+  intx.is_between(pos2.y(p), 0, and: area.height - 1)
 }
 
 fn tree_count(in area: Area, with slope: Pos2) -> Int {
diff --git a/aoc-2020-gleam/src/days/day17.gleam b/aoc-2020-gleam/src/days/day17.gleam
index e17439c..ad6e22e 100644
--- a/aoc-2020-gleam/src/days/day17.gleam
+++ b/aoc-2020-gleam/src/days/day17.gleam
@@ -1,31 +1,11 @@
 import gleam/io
-import gleam/list
 import gleam/bool
-import gleam/string as str
 import gleam/set.{type Set}
+import util/grid
 import util/input_util
 import util/pos3
 import util/pos4
 
-fn parse_grid(input: String, with constructor: fn(Int, Int) -> a) -> Set(a) {
-  input
-  |> str.split(on: "\n")
-  |> list.index_map(with: fn(line, y) {
-    line
-    |> str.to_graphemes
-    |> list.index_map(with: fn(grapheme, x) {
-      case grapheme {
-        "#" -> [constructor(x, y)]
-        "." -> []
-        _ -> panic
-      }
-    })
-    |> list.flatten
-  })
-  |> list.flatten
-  |> set.from_list
-}
-
 fn cycle(
   grid: Set(a),
   with neighbours: fn(a) -> Set(a),
@@ -60,14 +40,14 @@ fn cycle(
 
 fn part1(input: String) -> Int {
   input
-  |> parse_grid(with: fn(x, y) { #(x, y, 0) })
+  |> grid.parse_grid(with: fn(x, y) { #(x, y, 0) })
   |> cycle(with: pos3.neighbours26, by: 6)
   |> set.size
 }
 
 fn part2(input: String) -> Int {
   input
-  |> parse_grid(with: fn(x, y) { #(x, y, 0, 0) })
+  |> grid.parse_grid(with: fn(x, y) { #(x, y, 0, 0) })
   |> cycle(with: pos4.neighbours80, by: 6)
   |> set.size
 }
diff --git a/aoc-2020-gleam/src/days/day20.gleam b/aoc-2020-gleam/src/days/day20.gleam
new file mode 100644
index 0000000..12f1964
--- /dev/null
+++ b/aoc-2020-gleam/src/days/day20.gleam
@@ -0,0 +1,107 @@
+import gleam/io
+import gleam/int
+import gleam/list
+import gleam/dict
+import gleam/set.{type Set}
+import ext/intx
+import ext/listx
+import ext/resultx as resx
+import ext/genericx as genx
+import util/grid
+import util/input_util
+import util/pos2.{type Pos2}
+import util/parser as p
+
+const tile_size = 10
+
+type Tile {
+  Tile(id: Int, filled: Set(Pos2))
+}
+
+fn edge_ids(tile: Tile) -> List(Int) {
+  let extract = fn(filter, map) {
+    tile.filled
+    |> set.to_list
+    |> list.filter(keeping: filter)
+    |> list.map(with: fn(pos) { int.bitwise_shift_left(1, map(pos)) })
+    |> int.sum
+  }
+
+  let dedup = fn(edge_id) {
+    int.min(
+      edge_id,
+      edge_id
+      |> intx.reverse_bits(tile_size),
+    )
+  }
+
+  [
+    extract(fn(b) { pos2.y(b) == 0 }, pos2.x),
+    extract(fn(b) { pos2.x(b) == 9 }, pos2.y),
+    extract(fn(b) { pos2.y(b) == 9 }, pos2.x),
+    extract(fn(b) { pos2.x(b) == 0 }, pos2.y),
+  ]
+  |> list.map(with: dedup)
+}
+
+fn parse_tiles(input: String) -> List(Tile) {
+  let tile_parser =
+    p.literal("Tile ")
+    |> p.proceed(with: p.int())
+    |> p.skip(p.literal(":\n"))
+    |> p.then(p.any_str_of_len(tile_size * tile_size + { tile_size - 1 }))
+    |> p.map2(fn(id, content) {
+      Tile(
+        id,
+        content
+        |> grid.parse_grid(with: fn(x, y) { #(x, y) }),
+      )
+    })
+
+  let assert Ok(tiles) =
+    input
+    |> p.parse_entire(
+      with: tile_parser
+      |> p.sep1(by: p.nlnl())
+      |> p.skip_ws,
+    )
+  tiles
+}
+
+fn part1(input: String) -> Int {
+  let tiles = parse_tiles(input)
+
+  let counts =
+    tiles
+    |> list.flat_map(with: edge_ids)
+    |> listx.counts
+
+  tiles
+  |> list.filter(keeping: fn(tile) {
+    tile
+    |> edge_ids
+    |> list.map(with: fn(edge_id) {
+      counts
+      |> dict.get(edge_id)
+      |> resx.assert_unwrap
+    })
+    |> listx.count(satisfying: genx.equals(_, 1))
+    |> genx.equals(2)
+  })
+  |> list.map(with: fn(tile) { tile.id })
+  |> int.product
+}
+
+fn part2() -> Nil {
+  todo
+}
+
+pub fn main() -> Nil {
+  let testing = input_util.read_text("test20")
+  let assert 20_899_048_083_289 = part1(testing)
+
+  let input = input_util.read_text("day20")
+  io.debug(part1(input))
+
+  Nil
+}
diff --git a/aoc-2020-gleam/src/ext/intx.gleam b/aoc-2020-gleam/src/ext/intx.gleam
index 077b4f2..5c9bcc0 100644
--- a/aoc-2020-gleam/src/ext/intx.gleam
+++ b/aoc-2020-gleam/src/ext/intx.gleam
@@ -1,4 +1,5 @@
 import gleam/int
+import gleam/bool
 import gleam/order.{Eq, Gt, Lt}
 
 pub fn is_between(number: Int, min: Int, and max: Int) {
@@ -9,7 +10,7 @@ pub fn ceil_divide(dividend: Int, by divisor: Int) -> Int {
   { dividend + divisor - 1 } / divisor
 }
 
-fn gcd(a: Int, b: Int) -> Int {
+pub fn gcd(a: Int, b: Int) -> Int {
   case b == 0 {
     True -> a
     False -> gcd(b, a % b)
@@ -22,3 +23,15 @@ pub fn lcm(a: Int, b: Int) -> Int {
     Lt -> { b / gcd(a, b) } * a
   }
 }
+
+fn do_reverse_bits(val: Int, rev: Int, length: Int) -> Int {
+  use <- bool.guard(when: length == 0, return: rev)
+  let lsb = int.bitwise_and(val, 1)
+  let val = int.bitwise_shift_right(val, 1)
+  let rev = int.bitwise_shift_left(rev, 1)
+  do_reverse_bits(val, int.bitwise_or(rev, lsb), length - 1)
+}
+
+pub fn reverse_bits(val: Int, length: Int) -> Int {
+  do_reverse_bits(val, 0, length)
+}
diff --git a/aoc-2020-gleam/src/ext/iteratorx.gleam b/aoc-2020-gleam/src/ext/iteratorx.gleam
index 0e59f17..6c7838d 100644
--- a/aoc-2020-gleam/src/ext/iteratorx.gleam
+++ b/aoc-2020-gleam/src/ext/iteratorx.gleam
@@ -1,3 +1,6 @@
+import gleam/int
+import gleam/result as res
+import gleam/dict.{type Dict}
 import gleam/iterator.{type Iterator, Next} as iter
 
 pub fn length(iterator: Iterator(a)) -> Int {
@@ -11,6 +14,19 @@ pub fn count(iterator: Iterator(a), satisfying predicate: fn(a) -> Bool) -> Int
   |> length
 }
 
+pub fn counts(iterator: Iterator(a)) -> Dict(a, Int) {
+  iterator
+  |> iter.fold(from: dict.new(), with: fn(acc, value) {
+    acc
+    |> dict.insert(
+      value,
+      dict.get(acc, value)
+      |> res.unwrap(or: 0)
+      |> int.add(1),
+    )
+  })
+}
+
 pub fn filter_map(
   iterator: Iterator(a),
   with mapper: fn(a) -> Result(b, c),
@@ -25,8 +41,5 @@ pub fn filter_map(
 }
 
 pub fn unfold_infinitely(from state: a, with fun: fn(a) -> a) -> Iterator(a) {
-  iter.unfold(
-    from: state,
-    with: fn(s) { Next(element: s, accumulator: fun(s)) },
-  )
+  iter.unfold(from: state, with: fn(s) { Next(element: s, accumulator: fun(s)) })
 }
diff --git a/aoc-2020-gleam/src/ext/listx.gleam b/aoc-2020-gleam/src/ext/listx.gleam
index 2ca8648..0a3d7c3 100644
--- a/aoc-2020-gleam/src/ext/listx.gleam
+++ b/aoc-2020-gleam/src/ext/listx.gleam
@@ -1,6 +1,7 @@
 import gleam/pair
 import gleam/iterator as iter
 import gleam/result as res
+import gleam/dict.{type Dict}
 import ext/iteratorx as iterx
 
 pub fn count(list: List(a), satisfying predicate: fn(a) -> Bool) -> Int {
@@ -9,6 +10,12 @@ pub fn count(list: List(a), satisfying predicate: fn(a) -> Bool) -> Int {
   |> iterx.count(satisfying: predicate)
 }
 
+pub fn counts(list: List(a)) -> Dict(a, Int) {
+  list
+  |> iter.from_list
+  |> iterx.counts
+}
+
 fn set_helper(list: List(a), value: a, index: Int, counter: Int) -> List(a) {
   case list {
     [] -> []
diff --git a/aoc-2020-gleam/src/util/grid.gleam b/aoc-2020-gleam/src/util/grid.gleam
new file mode 100644
index 0000000..a091be5
--- /dev/null
+++ b/aoc-2020-gleam/src/util/grid.gleam
@@ -0,0 +1,22 @@
+import gleam/list
+import gleam/string as str
+import gleam/set.{type Set}
+
+pub fn parse_grid(lines: String, with constructor: fn(Int, Int) -> a) -> Set(a) {
+  lines
+  |> str.split("\n")
+  |> list.index_map(with: fn(line, y) {
+    line
+    |> str.to_graphemes
+    |> list.index_map(with: fn(grapheme, x) {
+      case grapheme {
+        "#" -> [constructor(x, y)]
+        "." -> []
+        _ -> panic
+      }
+    })
+    |> list.flatten
+  })
+  |> list.flatten
+  |> set.from_list
+}
diff --git a/aoc-2020-gleam/src/util/pos2.gleam b/aoc-2020-gleam/src/util/pos2.gleam
index 0b6256c..3f478ac 100644
--- a/aoc-2020-gleam/src/util/pos2.gleam
+++ b/aoc-2020-gleam/src/util/pos2.gleam
@@ -8,6 +8,14 @@ pub type Pos2 =
 
 pub const zero = #(0, 0)
 
+pub fn x(pos: Pos2) -> Int {
+  pos.0
+}
+
+pub fn y(pos: Pos2) -> Int {
+  pos.1
+}
+
 pub fn directions8() -> Set(Pos2) {
   set.from_list({
     use x <- list.flat_map(over: [-1, 0, 1])