In my previous post, I introduced you to the Advent of Code programming challenge, and explained how I’m going through the days, solving both parts of each puzzle. Continuing on, today we have day 11. In this challenge, Santa’s password has expired and it needs to be reset. Santa changes his password by incrementing the last character until the password passes the security requirements. If the character rolls over, then the previous character is incremented, and the process continues for all of the letters of the password. The password requirements are that it is to be eight lower-case letters, it must have two different sets of non-overlapping pairs of letters, a set of three consecutive letters, and it cannot contain the letters “i”, “l” or “o”. We are given the password that just expired, and the task is to get the next password.

My initial inclination is to do this in a set based manner. This would entail taking 8 sets of letters (one set for each character in the string), and each set consists of 23 letters (excluding the three that it cannot contain). Just perform a cross join between these set of letters 8 times, and you will have every possible letter combination, and then just get the ones that match all of the criteria and get the first one that is greater than the starting password. This is a simple, straightforward approach… until you consider just how much data this is- 238 rows… or over 78 billion combinations. Hmm, that doesn’t bode too well. And a quick test of just 5 sets of those 23 characters, and to get the possible matches for those, takes almost two minutes. So, here is the set-based code that I would have used for getting all of the strings that match the criteria across all 8 letters:

In this code, a virtual tally table is used to create the list of valid characters, and then it gets the position of each possible double-letter combination, and the three-character string of sequential letters that do not include the characters to not use. For the pairs of letters, each pair is examined to determine if that character pair exists in the string, and if so it returns the starting position of the first occurrence of this pair. All of the pairs are cross-applied, which ends up making 23 rows for each input string. To get whether there are two different sets, the code then gets the MIN and MAX for these. The code also checks to see if there are any of the three-character sequences. It just adds the starting positions up for all possible valid three-character sequences – if this is greater than zero, then there is at least one sequence there. The last part of this is the actual check for validity – it has to have a minimum pair that is greater than zero, a maximum pair that is higher than the minimum, and a 3-character sequence that is greater than zero. To get just the next password, just change this final part to a SELECT TOP (1) and add to the WHERE clause “AND Input > @Input”.

So, this turns out to be one of those things that just plain shouldn’t be run in SQL Server – your front-end applications will do a much better job (just because you can do something in SQL Server doesn’t mean that you should do it). However, since this is a one-off programming challenge, I’m going to go into another way where this can be performed in SQL Server. In this next method, I’m going to start with the specified existing password, and just start incrementing the password until we get a valid password. The code that I’m using for this is:

This code starts off by setting a bunch of variables. Into these variables it populates the position of all of the pairs and three-character sequences, and then determines if the password passes the criteria. If it doesn’t, it enters a while loop that increments the password until it does match, and then it exits the loop and returns this new string. This code runs in about 6 seconds, and it produces the correct result.

But can it be made better? Sure, there are a lot of shortcuts that can be coded into this. For instance, if the string doesn’t have any of the requirements, then the shortest string that matches all of the criteria is “aabcc”. The shortest string with the highest pair that can be used is “xxyzz”. So, if the character at position 5 is less than or equal to the position at character 4 and character 4 is no higher than “x”, then the password can be set to end by doubling character 4 (positions 4/5), taking the next two letters (positions 6/7), and then doubling character 7 (at position 8). The problem with this approach is that you have to consider every possible combination of occurrences and locations of these, making this some quite long code. But, in the testing that I did before giving up because of the complexity, it finishes immediately.

For part 2, we need to get the next password. To handle this, I just incremented the last password by one character, and ran the routine again.