day19 part2

1 files changed, 26 insertions, 33 deletions

diff --git a/2024/day19.rs b/2024/day19.rs
index 5060dff..e695aeb 100644
--- a/2024/day19.rs
+++ b/2024/day19.rs
@@ -1,7 +1,7 @@
 #![allow(dead_code)]
 #![allow(unused_variables)]
 #![allow(unused_mut)]
-use std::collections::HashSet;
+use std::collections::HashMap;
 use std::env;
 use std::fs::File;
 use std::io::Read;
@@ -22,31 +22,26 @@ fn dfs(design: &str, tokens: &Vec<&str>) -> i64 {
     return 0;
 }
 
-//fn bfs(design: &str, tokens: &Vec<&str>) -> i64 {
-//    let mut hs_new: HashSet<(i64, &str)> = HashSet::new();
-//    hs_new.insert((1,design));
-//
-//    let mut ret = 0;
-//    loop {
-//        let mut hs = hs_new.clone();
-//        hs_new.clear();
-//
-//        for (n,d) in hs.clone() {
-//            for t in tokens {
-//                if &d == t {
-//                    ret += 1;
-//                } else if d.starts_with(t) {
-//                    hs_new.insert((n+1,&d[t.len()..]));
-//                }
-//            }
-//        }
-//
-//        println!("{:?}", hs);
-//        if hs_new.len() == 0 {
-//            return ret;
-//        }
-//    }
-//}
+fn dfs2<'a>(design: &'a str, tokens: &Vec<&str>, lut: &mut HashMap<&'a str, i64>) -> i64 {
+    if design.len() == 0 {
+        return 1;
+    }
+
+    if let Some(n) = lut.get(design) {
+        return *n;
+    }
+
+    let mut ret = 0;
+    for t in tokens {
+        if design.starts_with(t) {
+            let s = &design[t.len()..];
+            let n = dfs2(s, tokens, lut);
+            lut.insert(s, n);
+            ret += n;
+        }
+    }
+    return ret;
+}
 
 fn main() {
     let args: Vec<String> = env::args().collect();
@@ -76,15 +71,13 @@ fn main() {
     let mut res2 = 0;
     for d in designs {
         res1 += dfs(d, &tokens);
-        //println!("{}", d);
-        //let ret = bfs(d, &tokens);
-        //res2 += ret;
-        //println!("{}", ret);
-    }
 
+        let mut lut: HashMap<&str, i64> = HashMap::new();
+        res2 += dfs2(d, &tokens, &mut lut);
+    }
 
     println!("res1: {}", res1);
     println!("res2: {}", res2);
-    //assert_eq!(res1, 240);
-    //assert_eq!(res2, );
+    assert_eq!(res1, 240);
+    assert_eq!(res2, 848076019766013);
 }