Finish day 20

4 files changed, 219 insertions, 32 deletions

diff --git a/aoc-2020-gleam/src/days/day03.gleam b/aoc-2020-gleam/src/days/day03.gleam
index 6a5ca5c..2653d2f 100644
--- a/aoc-2020-gleam/src/days/day03.gleam
+++ b/aoc-2020-gleam/src/days/day03.gleam
@@ -1,6 +1,7 @@
 import gleam/list
 import gleam/io
 import gleam/int
+import gleam/pair
 import gleam/result as res
 import gleam/string as str
 import gleam/iterator as iter
@@ -24,7 +25,7 @@ type Area {
 fn parse_area(from text: String) -> Area {
   let lines = str.split(text, on: "\n")
 
-  let trees = grid.parse_grid(text, with: fn(x, y) { #(x, y) })
+  let trees = grid.parse_grid(text, with: pair.new)
   let assert Ok(cycle) =
     lines
     |> list.first
diff --git a/aoc-2020-gleam/src/days/day20.gleam b/aoc-2020-gleam/src/days/day20.gleam
index 12f1964..7f3d2cd 100644
--- a/aoc-2020-gleam/src/days/day20.gleam
+++ b/aoc-2020-gleam/src/days/day20.gleam
@@ -1,49 +1,40 @@
 import gleam/io
 import gleam/int
 import gleam/list
-import gleam/dict
+import gleam/bool
+import gleam/pair
+import gleam/result as res
+import gleam/dict.{type Dict}
 import gleam/set.{type Set}
+import gleam/function as fun
+import gleam/iterator as iter
 import ext/intx
+import ext/setx
 import ext/listx
 import ext/resultx as resx
 import ext/genericx as genx
+import ext/iteratorx as iterx
 import util/grid
 import util/input_util
+import util/dir.{type Dir, East, North, South, West}
 import util/pos2.{type Pos2}
 import util/parser as p
 
 const tile_size = 10
 
-type Tile {
-  Tile(id: Int, filled: Set(Pos2))
-}
+const monster_pattern = "..................#.\n#....##....##....###\n.#..#..#..#..#..#..."
 
-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
-  }
+const monster_side = 20
 
-  let dedup = fn(edge_id) {
-    int.min(
-      edge_id,
-      edge_id
-      |> intx.reverse_bits(tile_size),
-    )
-  }
+const monster_area = 15
 
-  [
-    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)
+type Tile {
+  Tile(id: Int, filled: Set(Pos2))
 }
 
+type Layout =
+  Dict(Pos2, Tile)
+
 fn parse_tiles(input: String) -> List(Tile) {
   let tile_parser =
     p.literal("Tile ")
@@ -54,7 +45,7 @@ fn parse_tiles(input: String) -> List(Tile) {
       Tile(
         id,
         content
-        |> grid.parse_grid(with: fn(x, y) { #(x, y) }),
+        |> grid.parse_grid(with: pair.new),
       )
     })
 
@@ -68,9 +59,36 @@ fn parse_tiles(input: String) -> List(Tile) {
   tiles
 }
 
-fn part1(input: String) -> Int {
-  let tiles = parse_tiles(input)
+fn socket_at(tile: Tile, dir: Dir) -> Int {
+  let #(filter_fn, filter_eq, map_fn) = case dir {
+    North -> #(pos2.y, 0, pos2.x)
+    East -> #(pos2.x, tile_size - 1, pos2.y)
+    South -> #(pos2.y, tile_size - 1, pos2.x)
+    West -> #(pos2.x, 0, pos2.y)
+  }
+
+  tile.filled
+  |> set.to_list
+  |> list.filter(keeping: fn(pos) { filter_fn(pos) == filter_eq })
+  |> list.map(with: fn(pos) { int.bitwise_shift_left(1, map_fn(pos)) })
+  |> int.sum
+}
+
+fn edge_ids(tile: Tile) -> List(Int) {
+  let dedup = fn(socket) {
+    int.min(socket, intx.reverse_bits(socket, tile_size))
+  }
+
+  [
+    socket_at(tile, North),
+    socket_at(tile, East),
+    socket_at(tile, South),
+    socket_at(tile, West),
+  ]
+  |> list.map(with: dedup)
+}
 
+fn corners(tiles: List(Tile)) -> Set(Int) {
   let counts =
     tiles
     |> list.flat_map(with: edge_ids)
@@ -89,19 +107,170 @@ fn part1(input: String) -> Int {
     |> genx.equals(2)
   })
   |> list.map(with: fn(tile) { tile.id })
+  |> set.from_list
+}
+
+fn flip_pos(pos: Pos2, side: Int) -> Pos2 {
+  let #(x, y) = pos
+  #({ side - 1 } - x, y)
+}
+
+fn rotate_pos(pos: Pos2, side: Int) -> Pos2 {
+  let #(x, y) = pos
+  #({ side - 1 } - y, x)
+}
+
+fn shape_variants(
+  from s0: s,
+  and side: Int,
+  with map: fn(s, fn(Pos2) -> Pos2) -> s,
+) -> List(s) {
+  let s1 = map(s0, rotate_pos(_, side))
+  let s2 = map(s1, rotate_pos(_, side))
+  let s3 = map(s2, rotate_pos(_, side))
+  let f0 = map(s0, flip_pos(_, side))
+  let f1 = map(f0, rotate_pos(_, side))
+  let f2 = map(f1, rotate_pos(_, side))
+  let f3 = map(f2, rotate_pos(_, side))
+  [s0, s1, s2, s3, f0, f1, f2, f3]
+}
+
+fn find_layout(
+  side: Int,
+  corners: Set(Int),
+  layout: Layout,
+  free: List(Tile),
+) -> Result(Layout, Nil) {
+  let selected = dict.size(layout)
+  use <- bool.guard(when: selected == side * side, return: Ok(layout))
+  let #(row, col) = #(selected / side, selected % side)
+
+  let required_top =
+    layout
+    |> dict.get(#(col, row - 1))
+    |> res.map(with: socket_at(_, South))
+
+  let required_left =
+    layout
+    |> dict.get(#(col - 1, row))
+    |> res.map(with: socket_at(_, East))
+
+  free
+  |> list.filter(keeping: fn(candidate) {
+    case { row == 0 || row == side - 1 } && { col == 0 || col == side - 1 } {
+      True -> set.contains(corners, candidate.id)
+      False -> True
+    }
+  })
+  |> list.filter(keeping: fn(candidate) {
+    res.is_error(required_top)
+    || Ok(socket_at(candidate, North)) == required_top
+  })
+  |> list.filter(keeping: fn(candidate) {
+    res.is_error(required_left)
+    || Ok(socket_at(candidate, West)) == required_left
+  })
+  |> list.filter_map(with: fn(candidate) {
+    find_layout(
+      side,
+      corners,
+      dict.insert(into: layout, for: #(col, row), insert: candidate),
+      list.filter(free, keeping: fn(tile) { tile.id != candidate.id }),
+    )
+  })
+  |> list.first
+}
+
+fn flatten_layout(layout: Layout) -> Set(Pos2) {
+  layout
+  |> dict.to_list
+  |> list.flat_map(with: fn(entry) {
+    let #(#(tx, ty), tile) = entry
+    tile.filled
+    |> set.to_list
+    |> list.flat_map(with: fn(pos) {
+      let #(x, y) = pos
+      case x == 0 || x == tile_size - 1 || y == 0 || y == tile_size - 1 {
+        True -> []
+        False -> [
+          #(tx * { tile_size - 2 } + x - 1, ty * { tile_size - 2 } + y - 1),
+        ]
+      }
+    })
+  })
+  |> set.from_list
+}
+
+fn count_monsters(positions: Set(Pos2)) -> Int {
+  let monster_variants =
+    monster_pattern
+    |> grid.parse_grid(with: pair.new)
+    |> shape_variants(and: monster_side, with: setx.map)
+
+  let x_bound =
+    positions
+    |> setx.map(pos2.x)
+    |> set.fold(0, int.max)
+
+  let y_bound =
+    positions
+    |> setx.map(pos2.y)
+    |> set.fold(0, int.max)
+
+  let counts =
+    monster_variants
+    |> list.map(with: fn(variant) {
+      iter.range(-monster_side, y_bound + monster_side)
+      |> iter.flat_map(with: fn(y) {
+        iter.range(-monster_side, x_bound + monster_side)
+        |> iter.map(with: fn(x) {
+          variant
+          |> setx.map(with: pos2.add(_, #(x, y)))
+          |> set.intersection(and: positions)
+          |> set.size
+          == monster_area
+        })
+      })
+      |> iterx.count(satisfying: fun.identity)
+    })
+
+  list.fold(over: counts, from: 0, with: int.max)
+}
+
+fn part1(input: String) -> Int {
+  input
+  |> parse_tiles
+  |> corners
+  |> set.to_list
   |> int.product
 }
 
-fn part2() -> Nil {
-  todo
+fn part2(input: String) -> Int {
+  let tiles = parse_tiles(input)
+  let side = intx.sqrt(list.length(tiles))
+  let assert Ok(layout) =
+    find_layout(
+      side,
+      corners(tiles),
+      dict.new(),
+      list.flat_map(tiles, with: fn(t0) {
+        use tile, transform <- shape_variants(from: t0, and: tile_size)
+        Tile(tile.id, setx.map(tile.filled, with: transform))
+      }),
+    )
+  let positions = flatten_layout(layout)
+
+  set.size(positions) - count_monsters(positions) * monster_area
 }
 
 pub fn main() -> Nil {
   let testing = input_util.read_text("test20")
   let assert 20_899_048_083_289 = part1(testing)
+  let assert 273 = part2(testing)
 
   let input = input_util.read_text("day20")
   io.debug(part1(input))
+  io.debug(part2(input))
 
   Nil
 }
diff --git a/aoc-2020-gleam/src/ext/intx.gleam b/aoc-2020-gleam/src/ext/intx.gleam
index 5c9bcc0..aec513b 100644
--- a/aoc-2020-gleam/src/ext/intx.gleam
+++ b/aoc-2020-gleam/src/ext/intx.gleam
@@ -1,6 +1,8 @@
 import gleam/int
 import gleam/bool
+import gleam/float
 import gleam/order.{Eq, Gt, Lt}
+import ext/resultx as resx
 
 pub fn is_between(number: Int, min: Int, and max: Int) {
   min <= number && number <= max
@@ -35,3 +37,10 @@ fn do_reverse_bits(val: Int, rev: Int, length: Int) -> Int {
 pub fn reverse_bits(val: Int, length: Int) -> Int {
   do_reverse_bits(val, 0, length)
 }
+
+pub fn sqrt(x: Int) {
+  x
+  |> int.square_root
+  |> resx.assert_unwrap
+  |> float.round
+}
diff --git a/aoc-2020-gleam/src/ext/setx.gleam b/aoc-2020-gleam/src/ext/setx.gleam
index 33ebbc3..68d185a 100644
--- a/aoc-2020-gleam/src/ext/setx.gleam
+++ b/aoc-2020-gleam/src/ext/setx.gleam
@@ -1,3 +1,4 @@
+import gleam/list
 import gleam/set.{type Set}
 import gleam/iterator as iter
 import ext/iteratorx as iterx
@@ -8,3 +9,10 @@ pub fn count(set: Set(a), satisfying predicate: fn(a) -> Bool) -> Int {
   |> iter.from_list
   |> iterx.count(satisfying: predicate)
 }
+
+pub fn map(set: Set(a), with fun: fn(a) -> b) -> Set(b) {
+  set
+  |> set.to_list
+  |> list.map(with: fun)
+  |> set.from_list
+}