unique ids challenge

5 files changed, 177 insertions, 2 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 3451de6..2f2ae17 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,6 +3,12 @@
 version = 3
 
 [[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
 name = "common"
 version = "0.1.0"
 dependencies = [
@@ -20,12 +26,35 @@ dependencies = [
 ]
 
 [[package]]
+name = "getrandom"
+version = "0.2.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "be4136b2a15dd319360be1c07d9933517ccf0be8f16bf62a3bee4f0d618df427"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
 name = "itoa"
 version = "1.0.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38"
 
 [[package]]
+name = "libc"
+version = "0.2.147"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b4668fb0ea861c1df094127ac5f1da3409a82116a4ba74fca2e58ef927159bb3"
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
+
+[[package]]
 name = "proc-macro2"
 version = "1.0.66"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -44,6 +73,36 @@ dependencies = [
 ]
 
 [[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
 name = "ryu"
 version = "1.0.15"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -96,3 +155,19 @@ name = "unicode-ident"
 version = "1.0.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "301abaae475aa91687eb82514b328ab47a211a533026cb25fc3e519b86adfc3c"
+
+[[package]]
+name = "unique_ids"
+version = "0.1.0"
+dependencies = [
+ "common",
+ "rand",
+ "serde",
+ "serde_json",
+]
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
diff --git a/Cargo.toml b/Cargo.toml
index 359448b..5ec9429 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,5 +1,6 @@
 [workspace]
 members = [
+    "common",
 	"echo",
-    "common"
+    "unique_ids"
 ]
diff --git a/Justfile b/Justfile
index 940098a..c5ebfda 100644
--- a/Justfile
+++ b/Justfile
@@ -1,3 +1,7 @@
 test-echo:
     cargo build --bin echo
-    maelstrom test -w echo --bin target/debug/echo --node-count 1 --time-limit 10
\ No newline at end of file
+    maelstrom test -w echo --bin target/debug/echo --node-count 1 --time-limit 10
+
+test-unique-ids:
+    cargo build --bin unique_ids
+    maelstrom test -w unique-ids --bin target/debug/unique_ids --time-limit 30 --rate 1000 --node-count 3 --availability total --nemesis partition
diff --git a/unique_ids/Cargo.toml b/unique_ids/Cargo.toml
new file mode 100644
index 0000000..e7424bf
--- /dev/null
+++ b/unique_ids/Cargo.toml
@@ -0,0 +1,12 @@
+[package]
+name = "unique_ids"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+serde = { version = "1.0.185", features = ["derive"] }
+serde_json = "1.0.105"
+common = { path = "../common/" }
+rand = "0.8.5"
diff --git a/unique_ids/src/main.rs b/unique_ids/src/main.rs
new file mode 100644
index 0000000..3787033
--- /dev/null
+++ b/unique_ids/src/main.rs
@@ -0,0 +1,83 @@
+use std::{
+    io,
+    time::{SystemTime, UNIX_EPOCH},
+};
+
+use common::{run_with, Handler};
+use rand::{rngs::StdRng, Rng, SeedableRng};
+use serde::{Deserialize, Serialize};
+
+fn main() {
+    run_with::<UniqueIdsHandler>(io::stdin(), io::stdout())
+}
+
+#[derive(Debug, Serialize, Deserialize)]
+#[serde(tag = "type")]
+enum UniqueIdsBody {
+    #[serde(rename = "generate")]
+    Generate { msg_id: usize },
+
+    #[serde(rename = "generate_ok")]
+    GenerateOk {
+        msg_id: usize,
+        in_reply_to: usize,
+        id: u128,
+    },
+}
+
+type RngMethod = StdRng;
+
+struct UniqueIdsHandler {
+    rng: RngMethod,
+    next_msg_id: usize,
+}
+
+impl Handler for UniqueIdsHandler {
+    type Body = UniqueIdsBody;
+
+    fn init(_node_id: String, _node_ids: Vec<String>, _msg_id: usize) -> Self {
+        Self {
+            rng: RngMethod::from_entropy(), // TODO: This could be seeded from the node ID
+            next_msg_id: 1,
+        }
+    }
+
+    fn handle(
+        &mut self,
+        header: common::msg::MessageHeader,
+        body: Self::Body,
+        writer: &mut common::MsgWriter<impl std::io::Write>,
+    ) -> () {
+        match body {
+            UniqueIdsBody::Generate { msg_id } => {
+                let id = self.gen_id();
+                writer.write(
+                    header.src,
+                    &UniqueIdsBody::GenerateOk {
+                        msg_id: self.next_msg_id,
+                        in_reply_to: msg_id,
+                        id,
+                    },
+                );
+
+                self.next_msg_id += 1;
+            }
+            UniqueIdsBody::GenerateOk { .. } => (),
+        };
+    }
+}
+
+impl UniqueIdsHandler {
+    fn gen_id(&mut self) -> u128 {
+        // Time since UNIX epoch in milliseconds
+        let now = SystemTime::now();
+        let time_millis: u128 = now.duration_since(UNIX_EPOCH).unwrap().as_millis();
+
+        // 80 bits of randomness
+        let rand1: u16 = self.rng.gen();
+        let rand2: u64 = self.rng.gen();
+        let rand: u128 = rand1 as u128 | ((rand2 as u128) << 64);
+
+        (time_millis << 80) | rand
+    }
+}