952 Atbash Cipher
Functional Programming
Tutorial
The Problem
Implement the Atbash cipher: map each letter to its reverse in the alphabet (a→z, b→y, ..., z→a), pass digits through unchanged, and discard all other characters. For encoding, group the result into five-character chunks separated by spaces. Decoding strips spaces and applies the same bijective mapping. Implement both an iterator pipeline version and a recursive grouping variant.
🎯 Learning Outcomes
atbash_char(c) -> Option<char> as a pure character mapping using b'z' - (c as u8 - b'a').to_lowercase().chars().filter_map(atbash_char) for encoding.chunks(5) on a collected Vec<char> to group into five-character blocks.chunks(5)Code Example
fn atbash_char(c: char) -> Option<char> {
if c.is_ascii_lowercase() {
Some((b'z' - (c as u8 - b'a')) as char)
} else if c.is_ascii_digit() {
Some(c)
} else {
None
}
}
pub fn encode(input: &str) -> String {
let chars: Vec<char> = input
.to_lowercase()
.chars()
.filter_map(atbash_char)
.collect();
chars
.chunks(5)
.map(|chunk| chunk.iter().collect::<String>())
.collect::<Vec<_>>()
.join(" ")
}Key Differences
| Aspect | Rust | OCaml |
|---|---|---|
| Character arithmetic | b'z' - (c as u8 - b'a') | Char.code 'z' - (Char.code c - Char.code 'a') |
| Chunking | .chunks(5) on Vec<char> | Recursive split or List.filteri |
| String from chars | .collect::<String>() | String.of_seq or String.concat "" (List.map ...) |
| Join with separator | .join(" ") on Vec<String> | String.concat " " |
| Involution proof | The same atbash_char decodes | Identical |
Atbash is a substitution cipher where encode and decode are identical functions. The .filter_map idiom cleanly expresses "apply transformation, drop invalid characters" in a single pass.
OCaml Approach
let atbash_char c =
if c >= 'a' && c <= 'z' then
Some (Char.chr (Char.code 'z' - (Char.code c - Char.code 'a')))
else if c >= '0' && c <= '9' then Some c
else None
let encode input =
let chars =
String.to_seq (String.lowercase_ascii input)
|> Seq.filter_map atbash_char
|> List.of_seq
in
let rec group = function
| [] -> []
| cs ->
let (chunk, rest) = List.filteri (fun i _ -> i < 5) cs,
List.filteri (fun i _ -> i >= 5) cs in
String.concat "" (List.map (String.make 1) chunk) :: group rest
in
String.concat " " (group chars)
let decode input =
String.to_seq input
|> Seq.filter (fun c -> c <> ' ')
|> Seq.filter_map atbash_char
|> String.of_seq
OCaml's Seq.filter_map is the lazy equivalent of Rust's .filter_map(). String.of_seq collects a char Seq.t into a string directly — no intermediate Vec<char>.
Full Source
#![allow(clippy::all)]
// Atbash cipher: maps a→z, b→y, ..., z→a. Digits pass through. Groups into 5-char chunks.
fn atbash_char(c: char) -> Option<char> {
if c.is_ascii_lowercase() {
Some((b'z' - (c as u8 - b'a')) as char)
} else if c.is_ascii_digit() {
Some(c)
} else {
None
}
}
pub fn encode(input: &str) -> String {
let chars: Vec<char> = input
.to_lowercase()
.chars()
.filter_map(atbash_char)
.collect();
chars
.chunks(5)
.map(|chunk| chunk.iter().collect::<String>())
.collect::<Vec<_>>()
.join(" ")
}
pub fn decode(input: &str) -> String {
input
.chars()
.filter(|c| !c.is_whitespace())
.filter_map(atbash_char)
.collect()
}
pub fn encode_recursive(input: &str) -> String {
let chars: Vec<char> = input
.to_lowercase()
.chars()
.filter_map(atbash_char)
.collect();
fn group(chars: &[char]) -> Vec<String> {
if chars.is_empty() {
return vec![];
}
let (chunk, rest) = chars.split_at(chars.len().min(5));
let mut result = vec![chunk.iter().collect::<String>()];
result.extend(group(rest));
result
}
group(&chars).join(" ")
}
/* Output:
encode("Testing, 1 2 3, testing.") = "gvhgr mt123 gvhgr mt"
decode("gvhgr mt123 gvhgr mt") = "testing123testing"
encode_recursive("Testing, 1 2 3, testing.") = "gvhgr mt123 gvhgr mt"
encode("Hello, World!") = "svool dliow"
decode("svool") = "hello"
*/Deep Comparison
OCaml vs Rust: Atbash Cipher
Side-by-Side Code
OCaml
let atbash_char c =
if c >= 'a' && c <= 'z' then
Some (Char.chr (Char.code 'z' - (Char.code c - Char.code 'a')))
else if c >= '0' && c <= '9' then Some c
else None
let encode s =
let chars = String.to_seq (String.lowercase_ascii s)
|> Seq.filter_map atbash_char
|> List.of_seq in
let rec group = function
| [] -> []
| cs ->
let chunk = List.filteri (fun j _ -> j < 5) cs in
let rest = List.filteri (fun j _ -> j >= 5) cs in
String.init (List.length chunk) (List.nth chunk)
:: group rest
in
String.concat " " (group chars)
Rust (idiomatic)
fn atbash_char(c: char) -> Option<char> {
if c.is_ascii_lowercase() {
Some((b'z' - (c as u8 - b'a')) as char)
} else if c.is_ascii_digit() {
Some(c)
} else {
None
}
}
pub fn encode(input: &str) -> String {
let chars: Vec<char> = input
.to_lowercase()
.chars()
.filter_map(atbash_char)
.collect();
chars
.chunks(5)
.map(|chunk| chunk.iter().collect::<String>())
.collect::<Vec<_>>()
.join(" ")
}
Rust (functional/recursive — mirrors OCaml grouping)
pub fn encode_recursive(input: &str) -> String {
let chars: Vec<char> = input
.to_lowercase()
.chars()
.filter_map(atbash_char)
.collect();
fn group(chars: &[char]) -> Vec<String> {
if chars.is_empty() {
return vec![];
}
let (chunk, rest) = chars.split_at(chars.len().min(5));
let mut result = vec![chunk.iter().collect::<String>()];
result.extend(group(rest));
result
}
group(&chars).join(" ")
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Character map | val atbash_char : char -> char option | fn atbash_char(c: char) -> Option<char> |
| Encode | val encode : string -> string | fn encode(input: &str) -> String |
| Decode | val decode : string -> string | fn decode(input: &str) -> String |
| Optional char | char option | Option<char> |
| Character sequence | char Seq.t | impl Iterator<Item = char> |
Key Insights
chunks vs filteri:** OCaml has no direct List.chunks so the code uses List.filteri with index predicates (j < 5, j >= 5) to emulate it — O(n²) for each chunk. Rust's slice::chunks is a zero-allocation lazy iterator that yields contiguous sub-slices — idiomatic and O(1) per chunk boundary.'z' - (c - 'a') formula. OCaml works with Char.code (int) and converts back with Char.chr. Rust casts char to u8, does byte arithmetic, and casts back to char — more explicit about the ASCII-only domain of the operation.atbash(atbash(x)) = x, both encode and decode call the same atbash_char function. decode only differs by filtering whitespace first (to ignore grouping spaces), then applying the same map. This is cleaner than duplicating the mapping logic.filter_map is universal:** OCaml's Seq.filter_map and Rust's Iterator::filter_map have identical semantics: apply a function that returns Option, keep only Some values, unwrap them. The OCaml |> pipeline and Rust's method chain are stylistically equivalent.collect vs String.init / String.concat:** OCaml builds each chunk string with String.init (List.length chunk) (List.nth chunk) — indexing into a list, which is O(n) per character. Rust iterates the &[char] chunk directly with .iter().collect::<String>(), which is O(n) total and allocates exactly once per chunk.When to Use Each Style
**Use idiomatic Rust (chunks) when:** you need to group data into fixed-size windows — it is the standard idiom, clearer to read, and the most performant approach.
**Use recursive Rust (split_at) when:** you are explicitly demonstrating the OCaml parallel, teaching the recursive decomposition pattern, or when the grouping logic has variable chunk sizes that make chunks unsuitable.
Exercises
atbash_char to handle full Unicode alphabetic ranges.encode_no_spaces that skips the grouping step.decode(encode(s)) == normalize(s) for all alphanumeric strings.b'a' + (c as u8 - b'a' + 13) % 26.SubstitutionCipher struct that takes an arbitrary mapping [char; 26] and implements both encode and decode.