diff options
| -rw-r--r-- | entries/skairunner/.gitignore | 2 | ||||
| -rw-r--r-- | entries/skairunner/Cargo.lock | 7 | ||||
| -rw-r--r-- | entries/skairunner/Cargo.toml | 8 | ||||
| -rw-r--r-- | entries/skairunner/README.md | 24 | ||||
| -rw-r--r-- | entries/skairunner/src/main.rs | 112 |
5 files changed, 153 insertions, 0 deletions
diff --git a/entries/skairunner/.gitignore b/entries/skairunner/.gitignore new file mode 100644 index 0000000..4ca5251 --- /dev/null +++ b/entries/skairunner/.gitignore @@ -0,0 +1,2 @@ +target/* +*.proto diff --git a/entries/skairunner/Cargo.lock b/entries/skairunner/Cargo.lock new file mode 100644 index 0000000..71dd1ab --- /dev/null +++ b/entries/skairunner/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "skairunner" +version = "0.1.0" diff --git a/entries/skairunner/Cargo.toml b/entries/skairunner/Cargo.toml new file mode 100644 index 0000000..4b3d98c --- /dev/null +++ b/entries/skairunner/Cargo.toml @@ -0,0 +1,8 @@ +[package] +name = "skairunner" +version = "0.1.0" +edition = "2021" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/entries/skairunner/README.md b/entries/skairunner/README.md new file mode 100644 index 0000000..1d98b17 --- /dev/null +++ b/entries/skairunner/README.md @@ -0,0 +1,24 @@ +# What is it + +A Fibonacci generator that produces a valid Protobuf3 file. + +Each message is Fibonacci#, where # is the number in the sequence (i.e. f(#)). +The field "number" has a field number corresponding to the value of f(#) and a random type. + +The field `prevprev` has the type of the message corresponding to f(n-2) and has a field number of the value of f(n-2). +Similarly, the field "prev" has the type of the message for f(n-1) and the field number of f(n-1). + +Fibonacci1 does not have `prevprev`/`prev` because field numbers have to be greater than 0. +Fibonacci2 does not have `prevprev` for the same reason, while `prev` is omitted because duplicate field numbers are forbidden and f(1) = f(2). +Fibonacci3 does not have `prevprev` either. + +The last sequence number generated is 43, because after that the field numbers become too large and are illegal. + +## Running +With `cargo` installed on your system, `cargo run` will compile and output the protobuf file to stdout. + +To verify that the protobuf compiles, something like +``` +cargo run > fib.proto && protoc -odescriptors.proto fib.proto +``` +should work. Note that you will need `protoc` to do that.
\ No newline at end of file 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)); + } +} |