Swizec Teller - a geek with a hatswizec.com

    Fun javascript feature

    Not only was my nondeterministic turing machine implementationway too long at 20 lines, it was also wrong. Shortly after @dionyziz reported a bug and it took me until last night to get around to fixing it.

    class NP

    The problem was that when I was passing tapes for each possible step into the next iteration of the algorithm the good old "everything is a reference" javascript feature bit me in the arse. Because of this all the tapes looked exactly like the tape belonging to the last state inspected and so when you moved the instructions around a bit you could make my implementation fail without actually changing the actual turing machine.

    Fixing it was a simple matter of strategically using underscore's clone function to make sure ever inspected state is acting on its own version of the tape.

    And since the fix was so simple and I didn't feel like studying the subject that has been the bane of my existence for the past two years, I decided to try codegolfing the algorithm a bit. Doing so I accidentally came upon what is possibly javascript's funnest feature.

    var δ = function (S, s, e) {
    var π = _.keys,
    Θ = {},
    k,
    i,
    λ,
    μ,
    ι,
    Σ = _.size,
    β,
    ψ;
    if (π(s).indexOf(e) >= 0) return !0;
    for (k in s) {
    (i = s[k][0]), (λ = s[k][1]), (ψ = S[k][λ[i]] || S[k].B);
    for (ι = 0; ψ, ι < Σ(ψ); ) {
    (μ = ψ[ι++]),
    (β = _.clone(λ)),
    β.splice(i, 1, μ.w),
    (Θ[μ.n] = [i + μ.m, β]);
    }
    }
    return Σ(Θ) ? δ(S, Θ, e) : !!0;
    };

    Glorious 252 characters of nondeterministic turing machine right there! I'd say 252 bytes, but it's not, look at all those shiny unicode characters!

    Turns out even though javascript legally only allows numbers, letters and the $ and _ signs for variable names ... using almost any imaginable unicode character is also legal. Perhaps slightly difficult to type, but definitely a useful feature for making more expressive code.

    Especially when codegolfing or implementing physics or maths.

    Not sure I'll ever be using this again though ... oh and here's a slightly more readable version:

    var δ = function (S, s, e) {
    var π = _.keys,
    Θ = {},
    k,
    i,
    λ,
    μ,
    ι,
    Σ = _.size,
    β,
    ψ;
    if (π(s).indexOf(e) >= 0) return !0;
    for (k in s) {
    (i = s[k][0]), (λ = s[k][1]), (ψ = S[k][λ[i]] || S[k].B);
    for (ι = 0; ψ, ι < Σ(ψ); ) {
    μ = ψ[ι++];
    β = _.clone(λ);
    β.splice(i, 1, μ.w);
    Θ[μ.n] = [i + μ.m, β];
    }
    }
    return Σ(Θ) ? δ(S, Θ, e) : !!0;
    };

    Before you ask, machine instructions look like this and you can find a script for running all of this over at my github.

    Enhanced by Zemanta

    Did you enjoy this article?

    Published on December 7th, 2011 in Algorithm, JavaScript, Languages, Non-deterministic Turing machine, Programming, Turing machine, Uncategorized,

    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 ❤️