11
\$\begingroup\$

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);
\$\endgroup\$
5
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ "As far as I understand, you're just generating passwords and checking if it passes the requirements." - Nope. Each requirement has its own filter that generates the next valid password. Then I repeatedly advance the password using each requirement in turn until all of them agree on a single valid password. Your suggestion is to generate the next viable password (how? Just incrementing it generates lots of passwords), then checks it against all requirements. The password generator should be aware of the requirements. \$\endgroup\$ – John Dvorak Dec 13 '15 at 16:38
  • \$\begingroup\$ Good call about factoring the check functions out of the array - that could indeed provide readability. It opens up a slight issue in that you could define a function and then forget to add it to the list of requirements. Not that big of a worry, though. \$\endgroup\$ – John Dvorak Dec 13 '15 at 16:44
  • \$\begingroup\$ I've tried passing my code through JSBeautifier and I'm not exactly sure what it did. Did it just add more whitespace (fair point, I tend to be shy on space characters)? If you mean the extra newlines in requirements, I considered it readable enough as is. \$\endgroup\$ – John Dvorak Dec 13 '15 at 17:04
  • \$\begingroup\$ @JanDvorak The suggestions were for readability and maintainability. True, that generating and checking may have the same rules, the code is totally for different things. You can always optimize later (most of the time you will end up inlining and dropping code, especially when patterns show up). See this Quora post for details quora.com/… \$\endgroup\$ – Joseph Dec 13 '15 at 17:05
  • \$\begingroup\$ So, how does it help me to improve the "generate the next string that has a 3-straight substring" if I remove the "but return the argument unchanged if it already is a 3-straight substring"? I can add duplication by introducing a separate "check" function, but for what benefit? The "engine" isn't the critical part of proving correctness or the least readable part. The "generate the next 3-straight string" is. Should I clarify in the question that that is the hotspot in my code that reviewers should focus on? Nice quora link anyways, thanks - and I think Tikhon Jelvis' answer is a great one. \$\endgroup\$ – John Dvorak Dec 13 '15 at 17:12
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ by "improve your approach" do you mean "pick something much slower and just be done with it"? Sure, I could, but that's not fun :-) Besides, the password generator looks like it could be improved slightly :-) Still, thanks for the link. I'll be sure to check it out. \$\endgroup\$ – John Dvorak Dec 13 '15 at 16:45
  • 2
    \$\begingroup\$ No, I mean write something that is readable and, as you said, "obviously correct." This executes plenty fast to solve the problem in question. "Premature optimization is the root of all evil." Also, on the "fun" scale, that answer wins hand down imo \$\endgroup\$ – Jonah Dec 13 '15 at 16:49
  • \$\begingroup\$ Sure, but the solution you quoted enumerates each solution in turn. While this is readable and fast enough for the challenge, I am looking for something faster. As in, as the requirements scale up, the solution should scale, too. The quoted solution will take a really long time if the starting password happens to be "iaaaaaaa". You can argue that the remaining two requirements only skip O(1) passwords (and so does noIOL most of the time) and constant-time speed up doesn't matter, but pure combinatorial complexity isn't my measure here. \$\endgroup\$ – John Dvorak Dec 13 '15 at 16:58
  • \$\begingroup\$ sorry, i didnt read your OP carefully enough, i see you explicitly didn't want the pure iterative solution \$\endgroup\$ – Jonah Dec 13 '15 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.