day 20 gleam

1 files changed, 144 insertions, 41 deletions

diff --git a/aoc2023/src/day20/solve.gleam b/aoc2023/src/day20/solve.gleam
index 449cdeb..9192dac 100644
--- a/aoc2023/src/day20/solve.gleam
+++ b/aoc2023/src/day20/solve.gleam
@@ -1,16 +1,18 @@
 import adglent.{First, Second}
-import gleam/io
+import gleam/bool
 import gleam/dict.{type Dict}
+import gleam/io
+import gleam/iterator.{type Iterator, type Step, Next}
+import gleam/list
 import gleam/queue.{type Queue}
+import gleam/set
 import gleam/string
-import gleam/list
-import gleam/bool
 
 type Node {
   Broadcaster(children: List(String))
   Flipflop(children: List(String), state: Power)
   Conjunction(children: List(String), state: Dict(String, TonePitch))
-  Ground(children: List(String))
+  Ground
 }
 
 type Tone {
@@ -27,6 +29,16 @@ type TonePitch {
   High
 }
 
+type State {
+  State(
+    nodes: Dict(String, Node),
+    low: Int,
+    high: Int,
+    cycle: Int,
+    sentry_nodes: Dict(String, Int),
+  )
+}
+
 fn flip_power(p: Power) -> Power {
   case p {
     On -> Off
@@ -41,6 +53,22 @@ fn flip_flop_pitch(p: Power) -> TonePitch {
   }
 }
 
+fn combinator_pitch(state) {
+  case list.unique(dict.values(state)) {
+    [High] -> Low
+    _ -> High
+  }
+}
+
+fn get_children(node) {
+  case node {
+    Flipflop(children: cs, ..) -> cs
+    Conjunction(children: cs, ..) -> cs
+    Broadcaster(children: cs) -> cs
+    Ground -> []
+  }
+}
+
 fn parse_node(input: String) -> #(String, Node) {
   let assert [full_name, children_str] = string.split(input, on: " -> ")
   let children = string.split(children_str, on: ", ")
@@ -49,7 +77,7 @@ fn parse_node(input: String) -> #(String, Node) {
     "%" <> name -> #(name, Flipflop(children: children, state: Off))
     "&" <> name -> #(name, Conjunction(children: children, state: dict.new()))
     "broadcaster" -> #("broadcaster", Broadcaster(children: children))
-    name -> #(name, Ground([]))
+    name -> #(name, Ground)
   }
 }
 
@@ -57,13 +85,23 @@ fn to_initial_state(nodes: List(#(String, Node))) -> Dict(String, Node) {
   let node_dict = dict.from_list(nodes)
   let node_names = dict.keys(node_dict)
 
+  let node_dict =
+    node_dict
+    |> dict.values
+    |> list.map(get_children)
+    |> list.concat
+    |> set.from_list
+    |> set.drop(dict.keys(node_dict))
+    |> set.to_list
+    |> list.fold(node_dict, fn(acc, n) { dict.insert(acc, n, Ground) })
+
   use name, node <- dict.map_values(node_dict)
   case node {
     Conjunction(state: _, children: chs) ->
       node_names
       |> list.filter(fn(n) {
         let assert Ok(node) = dict.get(node_dict, n)
-        list.contains(node.children, any: name)
+        list.contains(get_children(node), any: name)
       })
       |> list.map(fn(n) { #(n, Low) })
       |> dict.from_list()
@@ -72,43 +110,74 @@ fn to_initial_state(nodes: List(#(String, Node))) -> Dict(String, Node) {
   }
 }
 
-fn press_button_once(
-  initial: #(Dict(String, Node), Int, Int),
-  queue: Queue(Tone),
-) {
-  let #(nodes, high, low) = initial
+fn add_to_queue(from, children, pitch, queue) {
+  use acc, c <- list.fold(children, queue)
+  queue.push_back(acc, Tone(from: from, to: c, pitch: pitch))
+}
+
+fn add_tones(state: State, nodes, pitch, n) {
+  case pitch {
+    Low ->
+      State(..state, nodes: nodes, low: state.low + n, cycle: state.cycle + 1)
+    High ->
+      State(..state, nodes: nodes, high: state.high + n, cycle: state.cycle + 1)
+  }
+}
+
+fn press_button_once(initial: State, queue: Queue(Tone)) {
+  let State(nodes: nodes, ..) = initial
+
   use <- bool.guard(queue.is_empty(queue), initial)
-  let assert Ok(#(Tone(from_name, to_name, pitch) as tone, rest)) =
+  let assert Ok(#(Tone(from_name, to_name, pitch), rest)) =
     queue.pop_front(queue)
-  io.debug(tone)
+
   let assert Ok(to_node) = dict.get(nodes, to_name)
   case to_node {
-    Broadcaster(children) ->
-      list.fold(children, rest, fn(acc, c) {
-        queue.push_back(acc, Tone(from: to_name, to: c, pitch: pitch))
-      })
-      |> press_button_once(initial, _)
-      
-    Conjunction(state: state, children: children) -> todo
+    Broadcaster(children) -> {
+      let new_state =
+        add_tones(initial, nodes, pitch, list.length(children) + 1)
+
+      let new_queue = add_to_queue(to_name, children, pitch, rest)
+      press_button_once(new_state, new_queue)
+    }
+
+    Conjunction(state: state, children: children) -> {
+      let new_state =
+        state
+        |> dict.insert(from_name, pitch)
+
+      let updated_nodes =
+        Conjunction(state: new_state, children: children)
+        |> dict.insert(nodes, to_name, _)
+
+      let pitch_out = combinator_pitch(new_state)
+
+      let new_state =
+        add_tones(initial, updated_nodes, pitch_out, list.length(children))
+        |> check_for_interesting_node(from_name, pitch_out)
+
+      add_to_queue(to_name, children, pitch_out, rest)
+      |> press_button_once(new_state, _)
+    }
+
+    Flipflop(..) if pitch == High ->
+      press_button_once(State(..initial, cycle: initial.cycle + 1), rest)
 
-    Flipflop(..) if pitch == High -> press_button_once(initial, rest)
     Flipflop(state: state, children: children) -> {
       let updated_nodes =
-        dict.insert(
-          nodes,
-          to_name,
-          Flipflop(state: flip_power(state), children: children),
-        )
-      let updated_queue =
-        list.fold(children, rest, fn(acc, c) {
-          queue.push_back(
-            acc,
-            Tone(from: to_name, to: c, pitch: flip_flop_pitch(state)),
-          )
-        })
-      press_button_once(#(updated_nodes, 0, 0), updated_queue)
+        Flipflop(state: flip_power(state), children: children)
+        |> dict.insert(nodes, to_name, _)
+
+      let pitch_out = flip_flop_pitch(state)
+      let new_state =
+        add_tones(initial, updated_nodes, pitch_out, list.length(children))
+
+      add_to_queue(to_name, children, flip_flop_pitch(state), rest)
+      |> press_button_once(new_state, _)
     }
-    Ground(..) -> press_button_once(initial, rest)
+
+    Ground(..) ->
+      press_button_once(State(..initial, cycle: initial.cycle + 1), rest)
   }
 }
 
@@ -119,17 +188,51 @@ pub fn part1(input: String) {
     |> list.map(parse_node)
     |> to_initial_state()
 
-  press_button_once(
-    #(initial_state, 0, 1),
-    [Tone("button", "broadcaster", Low)]
-    |> queue.from_list,
+  iterator.iterate(
+    from: State(initial_state, 0, 0, 1, dict.new()),
+    with: press_button_once(_, queue.from_list([
+      Tone("button", "broadcaster", Low),
+    ])),
   )
+  |> iterator.at(1000)
+  |> fn(s) {
+    let assert Ok(State(high: high, low: low, ..)) = s
+    high * low
+  }
+  |> string.inspect
+}
 
-  "1"
+fn check_for_interesting_node(state, name, pitch_out) {
+  case name, pitch_out {
+    "rk", High | "cd", High | "zf", High | "qx", High ->
+      State(
+        ..state,
+        sentry_nodes: dict.insert(state.sentry_nodes, name, state.cycle),
+      )
+    _, _ -> state
+  }
 }
 
 pub fn part2(input: String) {
-  todo as "Implement solution to part 2"
+  let initial_state =
+    input
+    |> string.split(on: "\n")
+    |> list.map(parse_node)
+    |> to_initial_state()
+
+  iterator.iterate(
+    from: State(initial_state, 0, 0, 1, dict.new()),
+    with: press_button_once(_, queue.from_list([
+      Tone("button", "broadcaster", Low),
+    ])),
+  )
+  |> iterator.drop_while(fn(s) { dict.size(s.sentry_nodes) < 4 })
+  |> iterator.step
+  |> fn(s: Step(State, Iterator(State))) {
+    let assert Next(goal, _rest) = s
+    goal.sentry_nodes
+  }
+  |> string.inspect
 }
 
 pub fn main() {