TASK
Implementation
Snowflake IDs derive their uniqueness from the machine_id component. With 10 bits, you can have 1024 unique machines generating IDs without any coordination.
Your task is to verify uniqueness and ordering across multiple nodes:
- Extract machine_id from Maelstrom node_id (e.g., "n3" -> machine_id 3)
- Generate IDs and verify they are unique within a node
- Implement a
verify_idshandler that checks a list of IDs for uniqueness and ordering
Request: {"type": "verify_ids", "msg_id": 1, "ids": [100, 200, 300, 200]}
Response: {"type": "verify_ids_ok", "in_reply_to": 1, "count": 4, "unique": 3, "is_sorted": false, "duplicates": [200]}Sample Test Cases
Verify sorted unique IDsTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"verify_ids","msg_id":2,"ids":[10,20,30]}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "verify_ids_ok", "count": 3, "unique": 3, "is_sorted": true, "duplicates": [], "in_reply_to": 2, "msg_id": 1}}
Detect duplicates in ID listTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"verify_ids","msg_id":2,"ids":[10,20,10,30]}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "verify_ids_ok", "count": 4, "unique": 3, "is_sorted": false, "duplicates": [10], "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
Each node uses its own machine_id extracted from the node_id
Hint 2▾
IDs from different nodes are unique because the machine_id bits differ
Hint 3▾
Within a single node, IDs must be monotonically increasing
Hint 4▾
Across nodes, IDs are only roughly sorted due to clock differences
Hint 5▾
Use the decompose function to verify machine_id extraction
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
multi-node coordinationuniqueness verificationmonotonicityID distribution
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
import time
CUSTOM_EPOCH_MS = 1704067200000
SEQUENCE_BITS = 12
MACHINE_BITS = 10
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1
class SnowflakeGenerator:
def __init__(self, machine_id):
self.machine_id = machine_id
self.sequence = 0
self.last_timestamp = -1
def current_time_ms(self):
return int(time.time() * 1000) - CUSTOM_EPOCH_MS
def generate(self):
ts = self.current_time_ms()
if ts == self.last_timestamp:
self.sequence += 1
if self.sequence > MAX_SEQUENCE:
while ts <= self.last_timestamp:
ts = self.current_time_ms()
self.sequence = 0
else:
self.sequence = 0
self.last_timestamp = ts
return ((ts << (MACHINE_BITS + SEQUENCE_BITS))
| (self.machine_id << SEQUENCE_BITS) | self.sequence)
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.generator = None