What a crooked way to compute the next straight string (advent of code 11)

Question

This year I have been participating in the Advent of Code series of challenges, and it just so happened that I'd be doing them in Javascript. Not my usual weapon of choice, but I do have some experience in it.

Day 11 asks us to find the next valid password given a set of three requirements. The idea is that you'd be incrementing the given password until it matched all three criteria, but I wanted to do something more efficient. But the task "find the next string that has a straight of length three" turned out a bit more difficult than I anticipated, and the code happened to be a bit more convoluted than I'd like, whooping 38% of the whole challenge.

A straight is defined as

like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn't count.

My main concern is that my code isn't "obviously bug-free" and that the logic is hard to follow. How can I clean my logic up without sacrificing performance? Of course, reviewers are welcome to comment on other aspects of the code as well.

So, here we go:

//jshint esversion: 6

function nextChar(x){return String.fromCharCode(x.charCodeAt(0)+1);}
var requirements = [
  {name: "straight3", nextMatch: function nextMatch(str){
    var prefix = str;
    while(prefix.length > 2){
      if(prefix === straighten(prefix)) return str;
      prefix = prefix.slice(0,-1);
    }
    prefix = str;
    while(true){
      if(prefix.length <= str.length - 3){
        return str.replace(/(.)([z]*)...$/, function(_, c, zs){
          return nextChar(c) + zs.replace(/z/g, 'a') + "abc";
        });
      } else if(prefix.match(/[yz]..$|xz.$/)) prefix = prefix.slice(0,-1);
      else if(str < straighten(prefix)) {
        var rv = straighten(prefix);
        while(straighten(rv).slice(0,-1) === straighten(rv.slice(0,-1))) rv = rv.slice(0,-1)
        while(rv.length < str.length) rv += 'a';
        return rv;
      } else {
        prefix = prefix.replace(/.(?=..$)/, nextChar).replace(/..$/, "aa");
        while(prefix.length < str.length) prefix += 'a';
        return nextMatch(prefix);
      }
    }
    function straighten(str){
      var ord = str.slice(-3).charCodeAt(0);
      return str.slice(0,-3) + String.fromCharCode(ord, ord+1, ord+2);
    }
  }},
  {name: "noIOL", nextMatch: function(x){
    return x.replace(/([iol])(.*)$/g, function(_, c, xs){
      return nextChar(c) + xs.replace(/./g, 'a');
    });
  }},
  {name: "twoPairs", nextMatch: function(str){
    if(str.match(/(.)\1.*(.)\2/)) return str;
    else if(str.match(/(.)\1../)){
      var rv = str.slice(0,-2) + nextPair(str.slice(-2));
      return rv.replace(/(.)\1\1$/, "$1$1a");
    } else {
      var rv = str.slice(0,-4) + nextPair(str.slice(-4,-2)) + "aa";
      return rv.replace(/(.)\1\1aa$/,"$1$1aaa");
    }
    function nextPair(x){
      if(x[0] > x[1]) return x[0] + x[0];
      else return nextChar(x[0]) + nextChar(x[0]);
    }
  }}
];

var pwd = "hxbxxzaa";
var toSat = requirements.length;
while(toSat){
  var oldPwd = pwd;
  pwd = requirements[0].nextMatch(pwd);
  if(pwd === oldPwd){
    toSat --;
  }else{
    toSat = requirements.length;
    console.log(oldPwd + " -> " + requirements[0].name + " -> " + pwd);
  }
  if(pwd.match(/[^a-z]/)) throw "oops";
  requirements.push(requirements.shift());
}
console.log(pwd);

Answer 1

First of all, I can't tell if your code is simply matching some password with the rules, generating one, or generating the next valid one. It's best if you split the operations into small functions so that it's easy to read through. I'd expect a function like generateNextPossiblePassword(pwd) somewhere that goes like:

var newPassword = generateNextPossiblePassword(OLD_PASSWORD);

The code also needs some formatting. You have an object which you are one-lining, then some you expand. Just ran this through JSBeautifier and it looks better than the one posted. Much readable.

As far as I understand, you're just generating passwords and checking if it passes the requirements. Generating should be a straightforward function:

function generateNextPossiblePassword(oldPassword){...}

var potentialPassword = generateNextPossiblePassword('abcdefgh'); //abcdffaa

Now, you don't have to pack everything in the generateNextPossiblePassword function. You can split the operation into generateNextString and checkIfStringIsValidPassword. That way, generateNextString can focus on string generation while checkIfStringIsValidPassword is the actual function that checks the validity.

function generateNextString(str){...}

function doesPasswordPassAllTests(str){...}

function generateNextPossiblePassword(pwd){
  var potentialPwd = generateNextString(pwd);
  var isValidPwd = doesPasswordPassAllTests(potentialPwd);

  // If the value passes, return. Otherwise, call again.
  // Yep, recursion. Lesser temporary counter variables.
  return isValidPwd ? potentialPwd : generateNextPossiblePassword(potentialPwd);
}

Checking against requirements is simply an every operation. every runs the callback for each item. If everything returns true, the result of every is true. If it finds one false, it immediately bails out and the operation results in a false.

Also note that the checks are functions which are then put into an array. This makes it easy to just define a function, then if we ever want to add it, we just pop in its name in the array. Your array isn't very bulky, just references to the functions.

// They take in a password, and simply return true or false
function checkForStraight(pwd){...}

function checkForInvalidLetters(pwd){...}

function checkForTwoPairs(pwd){...}

function doesPasswordPassAllTests(pwd){
  return passwordTests.every(function(test){
    return test(pwd);
  });
}

var passwordTests = [
  checkForStraight,
  checkForInvalidLetters,
  checkForTwoPairs,
];

var passwordPassesAllTests = doesPasswordPassAllTests(NEW_PASSWORD);

I renamed noIOL to checkForInvalidLetters. That's because I, O and L are arbitrary. A more general way to classify this would be character restriction, hence the new name.

By now, we've simplified your code. You can then worry about writing the logic and squeeze performance. Now that they're split, you can optimize them individually. For instance, you can optimize generateNextString to generate passwords as close to the rules as possible to avoid excessive cycles. The checks may easily be regex checks or even just regular string parsing.

It's also very readable. You can easily fold the function blocks in your IDE, only revealing their very meaningful names. Additionally, it's really easy to test each function.

function generateNextPossiblePassword(oldPassword){...}

function generateNextString(str){...}

function doesPasswordPassAllTests(pwd){...}

function checkForStraight(pwd){...}

function checkForInvalidLetters(pwd){...}

function checkForTwoPairs(pwd){...}

var passwordTests = [
  checkForStraight,
  checkForInvalidLetters,
  checkForTwoPairs,
];

var newPassword = generateNextPossiblePassword(OLD_PASSWORD);

Answer 2

The official reddit thread has really nice solutions: https://www.reddit.com/r/adventofcode/comments/3wbzyv/day_11_solutions/

Here's the best javascript one imo:

var pwd = 'cqjxjnds';

while(!/(abc|bcd|cde|def|efg|fgh|pqr|qrs|rst|stu|tuv|uvw|vwx|wxy|xyz)/.test(pwd)
  || /[ilo]/.test(pwd)
  || !/(.)\1.*(.)\2/.test(pwd)
) {
  pwd = (parseInt(pwd, 36) + 1).toString(36).replace(/0/, 'a');
}

console.log(pwd);

In general, if you find yourself writing solutions of more than 15 lines for these, you can probably improve your approach.