This documentation provides an educational guide to a Rust program that simulates antennas and their antinode patterns. The program explores spatial computations and uses various Rust features including iterators, collections, and custom data structures.
The program simulates radio antennas distributed across a city grid. When pairs of antennas interact, they create “antinodes” - specific locations in the city where radio waves interfere. The goal is to identify these antinodes based on harmonics (multiplication factors that affect the distance and placement of antinodes).
The key insight is that antinodes are positioned at specific relative distances from antenna pairs, and these distances depend on the harmonics being considered.
The program builds on a Location type that represents a 2D coordinate with methods for calculating distances and relative movements:
// From the Location module (not shown in the code snippets)
pub struct Location(pub usize, pub usize);
impl Location {
// Calculates the distance between two locations
pub fn distance(&self, other: &Location) -> (usize, usize) { ... }
// Moves a location by a relative offset
pub fn move_relative(&self, (dx, dy): (isize, isize)) -> Option<Location> { ... }
}
This fundamental building block provides the spatial reasoning capabilities needed for the antenna simulation.
The Antenna struct encapsulates a location and provides methods to calculate antinodes:
#[derive(Debug, Clone, Copy)]
pub(crate) struct Antenna(pub Location);
The simple wrapper design pattern allows us to extend location with antenna-specific behaviors without modifying the original type.
The antinode_pair method computes the two antinodes created by a pair of antennas at a specific harmonic:
pub fn antinode_pair(&self, rhs: Antenna, harmonics: usize) -> [Option<Location>; 2] {
let (dxu, dyu) = self.0.distance(&rhs.0);
let (dx, dy) = ((harmonics * dxu) as isize, (harmonics * dyu) as isize);
match (self.0.0 >= rhs.0.0, self.0.1 >= rhs.0.1) {
(true, true) => [rhs.0.move_relative((-dx, -dy)), self.0.move_relative((dx, dy))],
(true, false) => [rhs.0.move_relative((-dx, dy)), self.0.move_relative((dx, -dy))],
(false, true) => [rhs.0.move_relative((dx, -dy)), self.0.move_relative((-dx, dy))],
(false, false) => [rhs.0.move_relative((dx, dy)), self.0.move_relative((-dx, -dy))],
}
}
The key insights here:
To compute antinodes across multiple harmonics, we create an iterator:
pub fn antinodes(&self, rhs: Antenna, harmonics: RangeInclusive<usize>)
-> impl Iterator<Item = [Option<Location>; 2]> {
harmonics
.map(move |harmonics| self.antinode_pair(rhs, harmonics))
}
This demonstrates a functional programming approach by:
The City struct models the entire grid with antennas:
pub(crate) struct City {
city: Field<char>,
antennas: HashMap<char, Vec<Antenna>>
}
This design shows:
city) from the logical components (antennas)The FromStr implementation shows how to construct a City from a text representation:
impl FromStr for City {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
let city = s.parse::<Field<char>>()?;
let antennas: HashMap<char, Vec<Antenna>> = city.iter()
.enumerate()
.filter(|&(_, c)| c.ne(&'.'))
.fold(HashMap::new(), |mut map, (i, &c)| {
let loc = city.index_to_cartesian(i);
map.entry(c)
.and_modify(|antennas| antennas.push(Antenna(loc)))
.or_insert(vec![Antenna(loc)]);
map
});
Ok(City { city, antennas })
}
}
This demonstrates:
The antinodes method in the City structure is the core algorithm:
pub fn antinodes(&self, harmonics: RangeInclusive<usize>) -> impl Iterator<Item = Location> {
self.antennas
.values()
.flat_map(move |antennas| antennas
.iter()
.tuple_combinations()
.flat_map({
let h = harmonics.clone();
move |(a, b)| a
.antinodes(*b, h.clone())
.take_while(|&antinodes| {
match (antinodes[0], antinodes[1]) {
(_, Some(l)) if self.city.get(l).is_some() => true,
(Some(l), _) if self.city.get(l).is_some() => true,
_ => false
}
})
})
)
.flat_map(|antinodes| antinodes.into_iter())
.filter_map(|location|
location.filter(|&location| self.city.get(location).is_some())
)
}
This complex iterator pipeline demonstrates:
tuple_combinations() to generate all pairs of antennastake_while to stop computing when antinodes fall outside the mapThe main function demonstrates how to use the city and measure performance:
fn main() {
let input = std::fs::read_to_string("src/bin/day8/input.txt").unwrap();
let city = input.parse::<City>().expect("Failed to parse City");
let t = Instant::now();
let count = city.antinodes(1..=1).unique().count();
println!("Part 1: {:?} unique locations within the bounds of the map contain an antinode - {:?}", count, t.elapsed());
assert_eq!(247, count);
let t = Instant::now();
let count = city.antinodes(0..=100).unique().count();
println!("Part 2: {:?} unique locations contain an antinode given the effects of resonant harmonics - {:?}", count, t.elapsed());
assert_eq!(861, count);
}
Key aspects:
Instantunique()assert_eqThroughout this program, we see several advanced Rust programming concepts:
Location and Antenna to model domain conceptsFromStr for custom parsingResult and Option types to handle potential failuresThe program effectively uses Rust’s zero-cost abstractions to create a solution that is both expressive and efficient, with a clear separation of concerns between data structures and algorithms.