2 files changed, 94 insertions(+), 0 deletions(-)

A day20/Cargo.toml
A day20/src/main.rs

@@ 0,0 1,9 @@
+[package]
+name = "day20"
+version = "0.1.0"
+authors = ["Tomasz Kłak <tomasz@tomaszklak.pl>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]

@@ 0,0 1,85 @@
+use std::collections::{HashMap, HashSet};
+
+fn sq(n: u64) -> u64 {
+    (n as f64).sqrt() as u64 + 1
+}
+
+fn divisors_slow(n: u64) -> HashSet<u64> {
+    let mut ret = HashSet::new();
+    ret.insert(n);
+    for i in 1..sq(n) {
+        if n % i == 0 {
+            ret.insert(i);
+            ret.insert(n/i);
+        }
+    }
+    ret.insert(1);
+    ret
+}
+
+fn divisors_slow2(n: u64) -> HashSet<u64> {
+    let mut ret = HashSet::new();
+    ret.insert(n);
+    for i in 1..n/2 {
+        let o = n/i;
+        let ok = n % i == 0;
+        if ok && o <= 50 {
+            ret.insert(i);
+        }
+        if ok && i <= 50 {
+            ret.insert(o);
+        }
+    }
+    ret
+}
+
+fn presents(n: u64) -> u64 {
+    divisors_slow(n).into_iter().map(|v| v * 10).sum()
+}
+
+fn presents2(n: u64) -> u64 {
+    divisors_slow2(n).into_iter().map(|v| v * 11).sum()
+}
+
+fn foo(n: u64) -> HashMap<u64, HashSet<u64>> {
+    let mut h: HashMap<u64, HashSet<u64>> = HashMap::new();
+    for i in 1..=n {
+        for j in 1..=50 {
+            h.entry(i*j).or_default().insert(i);
+        }
+    }
+
+    h
+}
+
+fn main() {
+    assert_eq!(10,  presents(1));
+    assert_eq!(30,  presents(2));
+    assert_eq!(40,  presents(3));
+    assert_eq!(70,  presents(4));
+    assert_eq!(60,  presents(5));
+    assert_eq!(120, presents(6));
+    assert_eq!(80,  presents(7));
+    assert_eq!(150, presents(8));
+    assert_eq!(130, presents(9));
+    assert_eq!(foo(5000)[&1300], dbg!(divisors_slow2(1300)));
+    let min = 29000000;
+    for i in 1.. {
+        let p = presents(i);
+        if p >= min {
+            println!("found: {} - {}", i, p);
+            break
+        }
+    }
+    for i in 700000.. {
+        let p = presents2(i);
+        if p >= min {
+            println!("found: {} - {}", i, p);
+            break
+        }
+    }
+
+
+    // the answer is to high 1451008
+    // part 2 is too high 2636363
+}