Swizec Teller - a geek with a hatswizec.com

    Advent of Code Day 15 – Dueling JavaScript Generators

    JavaScript generators are 👌

    Advent of Code Day 15 was basically all about finding the right programming language. It needs built-in support for generators. You don't want to build that from scratch.

    But what's a generator anyway?

    Well, a generator is like an infinite loop that doesn't cause problems. The computer holds it paused in memory and only advances to the next iteration when you say, "Hey, what's the next value?"

    I don't know how it's implemented internally. If I had to guess, I'd say the engine holds the entire state on a stack of some sort and advances values when you ask for the next step. A lot like recursion.

    The full generator for Day 15 looks like this 👇

    function* star2generator(factor, startingValue, denominator) {
    let val = startingValue;
    while (true) {
    val = (val * factor) % 2147483647;
    if (val % denominator === 0) {
    yield val;
    }
    }
    }

    This starts from a startingValue and multiplies val with factor and mods the result with 2147483647 forever. Notice the while(true)? When I say forever, I mean forever.

    But it won't crash your node runtime or your browser. Because function* and yield turn it into a generator that follows the "only execute when called" logic.

    You get the next value like this:

    const A = generator(16807, startA, denomA);
    A.next().value; // some number
    A.next().value; // next number

    The full generator only returns values that are divisible by a denominator. That's from part 2 of Day 15. The first part returned every value.

    If that 2147483647 number looks familiar, it's because that's the highest number you can represent in 32 bits. This is significant because we're going to be doing some bitwise operations and JavaScript can only do those up to 32 bits.

    Numbers are generally represented as 64 bits in JavaScript.

    Wtf are we doing?

    Right, so that's how generators work. The reason we need generators is that the puzzle for Advent of Code Day 15 goes like this

    Take two generators that follow similar logic and see how often the lowest 16 bits of their output match in 40,000,000 tries.

    For Star 2 we make them sync up a little better, check for only 5,000,000 tries

    The generator above can handle both puzzle generators. They only differ in starting value and denominator.

    To count the number of matches, I used this function 👇

    function countMatches({
    startA,
    startB,
    generator,
    denominators = [],
    sampleSize,
    }) {
    const A = generator(16807, startA, denominators[0]),
    B = generator(48271, startB, denominators[1]);
    let judge = 0,
    mask = 0b00000000000000001111111111111111;
    for (let i = 0; i < sampleSize; i++) {
    if ((A.next().value & mask) === (B.next().value & mask)) {
    judge += 1;
    }
    }
    return judge;
    }

    The same function can do both Star 1 and Star 2 of the puzzle depending on input.

    Here's how it works:

    1. Create generators A and B
    2. Start at count of 0 (the judge variable)
    3. Create a mask that takes out the lower 16 bits of a number
    4. Loop until sampleSize
    5. Take next() values from the generators, bitwise AND them with the mask1, compare values
    6. If numbers match, increment judge
    7. When it's done looping, judge is our result

    Solving for Star 1 and Star 2 then becomes a matter of calling the matchCount function with our inputs.

    console.log(
    countMatches({
    startA: 591,
    startB: 393,
    generator: star2generator,
    denominators: [4, 8],
    sampleSize: 5000000
    })
    );

    Boom 💥 puzzle solved in about 20 minutes. 🤙

    And now you know how generators work. Although I still don't know where you'd use them in a web app.

    1. If you're not used to bitwise operations, they're rare in JavaScript, the idea is that bits follow a truth table. 0 & 0 == 0, 0 & 1 == 0, 1 & 0 == 0, 1 & 1 == 1. You can use this to cut away parts of numbers with a mask. For example 0b1010 & 0b0011 == 0b0010. 🤓

    Did you enjoy this article?

    Published on December 15th, 2017 in Front End, Technical,

    Learned something new?
    Read more Software Engineering Lessons from Production

    I write articles with real insight into the career and skills of a modern software engineer. "Raw and honest from the heart!" as one reader described them. Fueled by lessons learned over 20 years of building production code for side-projects, small businesses, and hyper growth startups. Both successful and not.

    Subscribe below 👇

    Software Engineering Lessons from Production

    Join Swizec's Newsletter and get insightful emails 💌 on mindsets, tactics, and technical skills for your career. Real lessons from building production software. No bullshit.

    "Man, love your simple writing! Yours is the only newsletter I open and only blog that I give a fuck to read & scroll till the end. And wow always take away lessons with me. Inspiring! And very relatable. 👌"

    ~ Ashish Kumar

    Join 15,883+ engineers learning lessons from my "raw and honest from the heart" emails.

    ⭐️⭐️⭐️⭐️✨
    4.5 stars average rating

    Have a burning question that you think I can answer? Hit me up on twitter and I'll do my best.

    Who am I and who do I help? I'm Swizec Teller and I turn coders into engineers with "Raw and honest from the heart!" writing. No bullshit. Real insights into the career and skills of a modern software engineer.

    Want to become a true senior engineer? Take ownership, have autonomy, and be a force multiplier on your team. The Senior Engineer Mindset ebook can help 👉 swizec.com/senior-mindset. These are the shifts in mindset that unlocked my career.

    Curious about Serverless and the modern backend? Check out Serverless Handbook, for frontend engineers 👉 ServerlessHandbook.dev

    Want to Stop copy pasting D3 examples and create data visualizations of your own? Learn how to build scalable dataviz React components your whole team can understand with React for Data Visualization

    Want to get my best emails on JavaScript, React, Serverless, Fullstack Web, or Indie Hacking? Check out swizec.com/collections

    Want to brush up on modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    Did someone amazing share this letter with you? Wonderful! You can sign up for my weekly letters for software engineers on their path to greatness, here: swizec.com/blog

    Want to brush up on your modern JavaScript syntax? Check out my interactive cheatsheet: es6cheatsheet.com

    By the way, just in case no one has told you it yet today: I love and appreciate you for who you are ❤️

    Created by Swizec with ❤️