Solve day 22

2 files changed, 84 insertions, 23 deletions

diff --git a/aoc-2020-gleam/src/days/day22.gleam b/aoc-2020-gleam/src/days/day22.gleam
index 5c72847..b925473 100644
--- a/aoc-2020-gleam/src/days/day22.gleam
+++ b/aoc-2020-gleam/src/days/day22.gleam
@@ -4,16 +4,24 @@ import gleam/list
 import gleam/bool
 import gleam/string as str
 import gleam/function as fun
+import gleam/set.{Set}
 import gleam/order.{Eq, Gt, Lt}
+import gleam/option.{None, Option, Some}
+import ext/boolx
 import ext/resultx as resx
 import util/input_util
 
-type GameState {
-  GameState(player1: List(Int), player2: List(Int))
+type Player {
+  P1
+  P2
 }
 
-fn parse_game_state(input: String) -> GameState {
-  let assert [player1, player2] =
+type Game {
+  Game(p1: List(Int), p2: List(Int))
+}
+
+fn parse_game(input: String) -> Game {
+  let assert [p1, p2] =
     input
     |> str.trim()
     |> str.split("\n\n")
@@ -25,7 +33,7 @@ fn parse_game_state(input: String) -> GameState {
       |> list.map(with: fun.compose(int.parse, resx.assert_unwrap))
     })
 
-  GameState(player1, player2)
+  Game(p1, p2)
 }
 
 fn score(deck: List(Int)) -> Int {
@@ -37,44 +45,87 @@ fn score(deck: List(Int)) -> Int {
   )
 }
 
-fn play_combat_round(previous: GameState) -> Result(GameState, Int) {
-  let assert [top1, ..rest1] = previous.player1
-  let assert [top2, ..rest2] = previous.player2
+fn outcome(game: Game) -> Option(Int) {
+  use <- bool.guard(when: game.p2 == [], return: Some(score(game.p1)))
+  use <- bool.guard(when: game.p1 == [], return: Some(-score(game.p2)))
+  None
+}
 
-  let #(new1, new2) = case int.compare(top1, top2) {
-    Lt -> #(rest1, list.append(rest2, [top2, top1]))
+fn get_winner(score: Int) -> Player {
+  case int.compare(score, 0) {
+    Lt -> P2
     Eq -> panic
-    Gt -> #(list.append(rest1, [top1, top2]), rest2)
+    Gt -> P1
   }
+}
 
-  use <- bool.guard(when: new1 == [], return: Error(score(new2)))
-  use <- bool.guard(when: new2 == [], return: Error(score(new1)))
+fn play_combat_game(game: Game) -> Int {
+  use <- option.lazy_unwrap(outcome(game))
 
-  Ok(GameState(new1, new2))
-}
+  let assert Game([top1, ..rest1], [top2, ..rest2]) = game
 
-fn play_combat_game(initial: GameState) -> Int {
-  case play_combat_round(initial) {
-    Ok(next) -> play_combat_game(next)
-    Error(score) -> score
-  }
+  play_combat_game(case int.compare(top1, top2) {
+    Lt -> Game(rest1, list.append(rest2, [top2, top1]))
+    Eq -> panic
+    Gt -> Game(list.append(rest1, [top1, top2]), rest2)
+  })
 }
 
 fn part1(input: String) -> Int {
   input
-  |> parse_game_state
+  |> parse_game
   |> play_combat_game
   |> int.absolute_value
 }
 
+fn play_recursive_combat(game: Game, seen: Set(Game)) -> Int {
+  use <- option.lazy_unwrap(outcome(game))
+  use <- bool.guard(when: set.contains(seen, game), return: score(game.p1))
+
+  let assert Game([top1, ..rest1], [top2, ..rest2]) = game
+  let seen = set.insert(seen, game)
+
+  let winner = {
+    use <- boolx.guard_lazy(
+      when: list.length(rest1) >= top1 && list.length(rest2) >= top2,
+      return: fn() {
+        Game(list.take(rest1, top1), list.take(rest2, top2))
+        |> play_recursive_combat(set.new())
+        |> get_winner
+      },
+    )
+
+    case int.compare(top1, top2) {
+      Lt -> P2
+      Eq -> panic
+      Gt -> P1
+    }
+  }
+
+  play_recursive_combat(
+    case winner {
+      P1 -> Game(list.append(rest1, [top1, top2]), rest2)
+      P2 -> Game(rest1, list.append(rest2, [top2, top1]))
+    },
+    seen,
+  )
+}
+
+fn part2(input: String) -> Int {
+  input
+  |> parse_game
+  |> play_recursive_combat(set.new())
+  |> int.absolute_value
+}
+
 pub fn main() -> Nil {
   let test = input_util.read_text("test22")
   let assert 306 = part1(test)
-  // let assert 291 = part2(test)
+  let assert 291 = part2(test)
 
   let input = input_util.read_text("day22")
   io.debug(part1(input))
-  // io.debug(part2(input))
+  io.debug(part2(input))
 
   Nil
 }
diff --git a/aoc-2020-gleam/src/ext/boolx.gleam b/aoc-2020-gleam/src/ext/boolx.gleam
new file mode 100644
index 0000000..f3c8b49
--- /dev/null
+++ b/aoc-2020-gleam/src/ext/boolx.gleam
@@ -0,0 +1,10 @@
+pub fn guard_lazy(
+  when requirement: Bool,
+  return consequence: fn() -> t,
+  otherwise alternative: fn() -> t,
+) -> t {
+  case requirement {
+    True -> consequence()
+    False -> alternative()
+  }
+}