From f4b819976344ca0c3e0379e6555f36a0ebcb505c Mon Sep 17 00:00:00 2001
From: Skye Im
Date: Tue, 15 Nov 2022 17:51:56 +0100
Subject: skairunner: Make fibonacci generator

---
 entries/skairunner/src/main.rs | 112 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 112 insertions(+)
 create mode 100644 entries/skairunner/src/main.rs

(limited to 'entries/skairunner/src')

diff --git a/entries/skairunner/src/main.rs b/entries/skairunner/src/main.rs
new file mode 100644
index 0000000..704c66a
--- /dev/null
+++ b/entries/skairunner/src/main.rs
@@ -0,0 +1,112 @@
+use std::collections::HashMap;
+
+/// According to the protobuf specifications, 2^29-1 is the largest field number allowed.
+/// 1 is the smallest field number allowed.
+const MAX_FIELD_NUMBER: i32 = 536_870_911;
+
+const PROTOBUF_TYPES: &[&'static str] = &[
+    "double", "float", "int32", "int64", "uint32", "uint64", "sint64", "fixed32", "fixed64",
+    "sfixed32", "sfixed64", "bool", "string", "bytes",
+];
+
+/// According to protobuf specifications,
+/// fields 19000 thru 19999 are used by the compiler
+/// and are therefore illegal.
+fn field_number_is_illegal(n: i32) -> bool {
+    19000 <= n && n <= 19999 || n <= 0
+}
+
+fn init_memo() -> HashMap<i32, i32> {
+    let mut memo = HashMap::new();
+    memo.insert(0, 0);
+    memo.insert(1, 1);
+    memo
+}
+
+fn fib(n: i32, memo: &mut HashMap<i32, i32>) -> Option<i32> {
+    if let Some(number) = memo.get(&n) {
+        return Some(*number);
+    }
+    let f_n = memo.get(&(n - 1))? + memo.get(&(n - 2))?;
+    memo.insert(n, f_n);
+
+    Some(f_n)
+}
+
+fn format_submessage(n: i32, memo: &mut HashMap<i32, i32>, name: &str) -> String {
+    let number = fib(n, memo);
+    match number {
+        None => String::new(),
+        Some(number) => {
+            if field_number_is_illegal(number) {
+                String::new()
+            } else {
+                format!("    Fibonacci{} {} = {};\n", n, name, number)
+            }
+        }
+    }
+}
+
+fn message_frame(n: i32, memo: &mut HashMap<i32, i32>) -> String {
+    let n_0 = fib(n, memo)
+        .map(|number| {
+            if field_number_is_illegal(number) {
+                format!(
+                    "    // There should be a fibonacci number here, but {} is illegal",
+                    number
+                )
+            } else {
+                // Pick a semi-random type for the fib field
+                let type_name = PROTOBUF_TYPES[number as usize % PROTOBUF_TYPES.len()];
+                format!("    {} number = {};", type_name, number)
+            }
+        })
+        .unwrap_or_default();
+
+    let (n_minus_2, n_minus_1) = if n == 3 {
+        (String::new(), format_submessage(n - 1, memo, "prev"))
+    } else if n != 2 {
+        (
+            format_submessage(n - 2, memo, "prevprev"),
+            format_submessage(n - 1, memo, "prev"),
+        )
+    } else {
+        (String::new(), String::new())
+    };
+
+    format!(
+        "message Fibonacci{} {{\n\
+    {}{}{}
+}}",
+        n, n_minus_2, n_minus_1, n_0
+    )
+}
+
+fn main() {
+    let mut memo = init_memo();
+    let mut i = 1;
+    println!("syntax = \"proto3\";\n");
+    loop {
+        if fib(i, &mut memo) >= Some(MAX_FIELD_NUMBER) {
+            break;
+        }
+        println!("{}\n", message_frame(i, &mut memo));
+        i += 1;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_small_fibs() {
+        let mut memo = init_memo();
+        assert_eq!(fib(0, &mut memo), Some(0));
+        assert_eq!(fib(1, &mut memo), Some(1));
+        assert_eq!(fib(2, &mut memo), Some(1));
+        assert_eq!(fib(3, &mut memo), Some(2));
+        assert_eq!(fib(4, &mut memo), Some(3));
+        assert_eq!(fib(5, &mut memo), Some(5));
+    }
+}
-- 
cgit v1.2.3-70-g09d2