pwc075 / task 1 + 2

3 files changed, 113 insertions, 0 deletions

diff --git a/challenge-075/xkr47/rust/Cargo.toml b/challenge-075/xkr47/rust/Cargo.toml
new file mode 100644
index 0000000000..36125a484c
--- /dev/null
+++ b/challenge-075/xkr47/rust/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "pwd-075"
+version = "0.1.0"
+authors = ["Jonas Berlin <xkr47@outerspace.dyndns.org>"]
+edition = "2018"
+
+[dependencies]
+
+[[bin]]
+name = "ch-1"
+path = "ch-1.rs"
+
+[[bin]]
+name = "ch-2"
+path = "ch-2.rs"
diff --git a/challenge-075/xkr47/rust/ch-1.rs b/challenge-075/xkr47/rust/ch-1.rs
new file mode 100644
index 0000000000..f9af5f7562
--- /dev/null
+++ b/challenge-075/xkr47/rust/ch-1.rs
@@ -0,0 +1,51 @@
+fn main() {
+    let c = vec![1, 2, 4];
+    let s = 6;
+
+    let o: Vec<Vec<u32>> = doit(&c, s);
+
+    assert_eq!(o, vec![
+        vec![1, 1, 1, 1, 1, 1],
+        vec![1, 1, 1, 1, 2],
+        vec![1, 1, 2, 2],
+        vec![1, 1, 4],
+        vec![2, 2, 2],
+        vec![2, 4],
+    ]);
+}
+
+fn doit(c: &[u32], s: u32) -> Vec<Vec<u32>> {
+    println!("C = {:?}", c);
+    println!("S = {}", s);
+    let o = doit_inner(c, s);
+    println!("There are {} possible ways to make sum {}.", o.len(), s);
+    println!("{:#?}", o);
+    o
+}
+
+fn doit_inner(c: &[u32], s: u32) -> Vec<Vec<u32>> {
+    if s == 0 {
+        return vec![vec![]];
+    }
+    let first_coin = c[0];
+    let rest = &c[1..];
+    (0..=s / first_coin).rev().flat_map(|num| {
+        let first_coin_sum = first_coin * num;
+        if rest.len() == 0 {
+            // last coin, must have exact match
+            return if first_coin_sum == s {
+                vec![vec![first_coin; num as usize]]
+            } else {
+                vec![]
+            };
+        }
+        let mut rest = doit(rest, s - first_coin_sum);
+        rest.iter_mut()
+            .map(|sub| {
+                let mut v = vec![first_coin; num as usize];
+                v.append(sub);
+                v
+            })
+            .collect::<Vec<Vec<u32>>>()
+    }).collect()
+}
diff --git a/challenge-075/xkr47/rust/ch-2.rs b/challenge-075/xkr47/rust/ch-2.rs
new file mode 100644
index 0000000000..8c6067b304
--- /dev/null
+++ b/challenge-075/xkr47/rust/ch-2.rs
@@ -0,0 +1,47 @@
+fn main() {
+    let a = vec![2, 1, 4, 5, 3, 7];
+    let o = doit(&a);
+    assert_eq!(o, 12);
+
+    let a = vec![3, 2, 3, 5, 7, 5];
+    let o = doit(&a);
+    assert_eq!(o, 15);
+}
+
+fn doit(a: &[u32]) -> u64 {
+    println!("Input: {:?}", a);
+    print_histogram(a);
+    let o = do_max_rect(a);
+    println!("Output: {:?}", o);
+    o
+}
+
+fn do_max_rect(a: &[u32]) -> u64 {
+    a.iter().enumerate().fold((0, u32::MAX), |(max_rect_so_far, max_height), (idx, this_height)| {
+        let new_max_height = max_height.min(*this_height);
+        let width = idx as u64 + 1;
+        let mut new_max_rect_so_far = max_rect_so_far.max(width * new_max_height as u64);
+        if *this_height > new_max_height {
+            // value increased, potential new rect starting, spawn parallel scan
+            new_max_rect_so_far = new_max_rect_so_far.max(do_max_rect(&a[idx..]));
+        }
+        (new_max_rect_so_far, new_max_height)
+    }).0 // 0 == max_rect_so_far
+}
+
+fn print_histogram(a: &[u32]) {
+    let max_height = *a.iter().max().unwrap_or(&0);
+    let len = format!("{}", max_height).len();
+    for height in (1..=max_height).rev() {
+        print!("{0:1$}", height, len);
+        a.iter().for_each(|i| print!("{0:1$}{2}", "", len, if *i >= height { '#' } else { ' ' }));
+        println!();
+    }
+    print!("{:>1$}", "_", len);
+    a.iter().for_each(|i| print!("{0:1$}_", "", len));
+    println!();
+
+    print!("{:1$}", "", len);
+    a.iter().for_each(|i| print!(" {0:1$}", i, len));
+    println!();
+}