Dueling Generators — Rust — #adventofcode Day 15


	
	
		
			
				eRambler

					
					
					
				
				


				
				
					
						
						home
						
						about
						
						series
						
						tags
						
						talks
						
						rdm resources
						
					

				

				
			
		

	




	
	
		
			
				
					Dueling Generators — Rust — #adventofcode Day 15


				

			

			
				
					


    Date:
    2017-12-15



    
    
        Series:
        Advent of Code 2017
    




    Tags:
    
        [Technology]
    
        [Learning]
    
        [Advent of Code]
    
        [Rust]
    




				

				
					

    
    
        
            
                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.

→ Full code on GitHub

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 & reactions haven't loaded yet. You might have JavaScript disabled but that's cool 😎.
    




            
    

    
        Comments

    

    

    
        Powered by Cactus Comments 🌵
    



            
        

    




		
	

	
	
		
			
				
    
        me elsewhere ::
        
        
            
            
            
                
            
            keyoxide
            |
        
            
            
            
                
            
            keybase
            |
        
            
            
            
                
            
            mastodon
            |
        
            
            
            
                
            
            matrix
            |
        
            
            
            
                
            
            twitter
            |
        
            
            
            
                
            
            github
            |
        
            
            
            
                
            
            gitlab
            |
        
            
            
            
                
            
            orcid
            |
        
            
            
            
                
            
            pypi
            |
        
            
            
            
                
            
            linkedin
            
        
    

    



				
					© 2021
					Jez Cope
					| Built by: Hugo
					| Theme: Mnemosyne
				

				
					
						
							Build status: 
						
					

				
				
					

					
Except where noted, this work is licensed under a Creative Commons Attribution 4.0 International License.