Dueling Generators — Rust — #adventofcode Day 15
Series
This post is part of the series Advent of Code 2017
- Reflections on #aoc2017
- The Halting Problem — Python — #adventofcode Day 25
- Electromagnetic Moat — Rust — #adventofcode Day 24
- Coprocessor Conflagration — Haskell — #adventofcode Day 23
- Sporifica Virus — Rust — #adventofcode Day 22
- Fractal Art — Python — #adventofcode Day 21
- Particle Swarm — Python — #adventofcode Day 20
- A Series of Tubes — Rust — #adventofcode Day 19
- Duet — Haskell — #adventofcode Day 18
- Spinlock — Rust/Python — #adventofcode Day 17
- Permutation Promenade — Julia — #adventofcode Day 16
- > Dueling Generators — Rust — #adventofcode Day 15 <
- Disk Defragmentation — Haskell — #adventofcode Day 14
- Packet Scanners — Haskell — #adventofcode Day 13
- Digital Plumber — Python — #adventofcode Day 12
- Hex Ed — Python — #adventofcode Day 11
- Knot Hash — Haskell — #adventofcode Day 10
- Stream Processing — Haskell — #adventofcode Day 9
- I Heard You Like Registers — Python — #adventofcode Day 8
- Recursive Circus — Ruby — #adventofcode Day 7
- Memory Reallocation — Python — #adventofcode Day 6
- A Maze of Twisty Trampolines — C++ — #adventofcode Day 5
- High Entropy Passphrases — Python — #adventofcode Day 4
- Spiral Memory — Go — #adventofcode Day 3
- Corruption Checksum — Python — #adventofcode Day 2
- Inverse Captcha — Coconut — #adventofcode Day 1
- Advent of Code 2017: introduction
Today’s challenge introduces two pseudo-random number generators which are trying to agree on a series of numbers. We play the part of the “judge”, counting the number of times their numbers agree in the lowest 16 bits.
Ever since I used Go to solve day 3, I’ve had a hankering to try the other new kid on the memory-safe compiled language block, Rust. I found it a bit intimidating at first because the syntax wasn’t as close to the C/C++ I’m familiar with and there are quite a few concepts unique to Rust, like the use of traits. But I figured it out, so I can tick another language of my to-try list.
I also implemented a version in Python for comparison: the Python version is more concise and easier to read but the Rust version runs about 10× faster.
First we include the std::env “crate” which will let us get access to commandline arguments, and define some useful constants for later.
use std::env;
const M: i64 = 2147483647;
const MASK: i64 = 0b1111111111111111;
const FACTOR_A: i64 = 16807;
const FACTOR_B: i64 = 48271;
gen_next generates the next number for a given generator’s sequence. gen_next_picky does the same, but for the “picky” generators, only returning values that meet their criteria.
fn gen_next(factor: i64, current: i64) -> i64 {
return (current * factor) % M;
}
fn gen_next_picky(factor: i64, current: i64, mult: i64) -> i64 {
let mut next = gen_next(factor, current);
while next % mult != 0 {
next = gen_next(factor, next);
}
return next;
}
duel runs a single duel, and returns the number of times the generators agreed in the lowest 16 bits (found by doing a binary & with the mask defined above). Rust allows functions to be passed as parameters, so we use this to be able to run both versions of the duel using only this one function.
fn duel<F, G>(n: i64, next_a: F, mut value_a: i64, next_b: G, mut value_b: i64) -> i64
where
F: Fn(i64) -> i64,
G: Fn(i64) -> i64,
{
let mut count = 0;
for _ in 0..n {
value_a = next_a(value_a);
value_b = next_b(value_b);
if (value_a & MASK) == (value_b & MASK) {
count += 1;
}
}
return count;
}
Finally, we read the start values from the command line and run the two duels. The expressions that begin |n| are closures (anonymous functions, often called lambdas in other languages) that we use to specify the generator functions for each duel.
fn main() {
let args: Vec<String> = env::args().collect();
let start_a: i64 = args[1].parse().unwrap();
let start_b: i64 = args[2].parse().unwrap();
println!(
"Duel 1: {}",
duel(
40000000,
|n| gen_next(FACTOR_A, n),
start_a,
|n| gen_next(FACTOR_B, n),
start_b,
)
);
println!(
"Duel 2: {}",
duel(
5000000,
|n| gen_next_picky(FACTOR_A, n, 4),
start_a,
|n| gen_next_picky(FACTOR_B, n, 8),
start_b,
)
);
}
Webmentions
You can respond to this post, "Dueling Generators — Rust — #adventofcode Day 15", by:
liking, boosting or replying to a tweet or toot that mentions it; or
sending a webmention from your own site to https://erambler.co.uk/blog/day-15/
Comments
Powered by Cactus Comments 🌵