Advent of Code Day 11 Solved in C# and F#

Today we’re helping Santa choose a new password, which basically involves him incrementing his old password until he finds one that meets the draconian corporate password policy rules. Here’s how I solved it:

My initial approach in C# was to treat each password as a base 26 number, converting the string to an integer so I could increment it and then back again. And I didn’t exclusively use Regexes to validate the passwords, opting for a LINQ approach for a couple of them.

Func<string, long> fromBase26String = s => s.Reverse().Aggregate(new { sum = 0L, mult = 1L }, 
    (acc, next) => new { sum = acc.sum + (next - 'a') * acc.mult, mult = acc.mult * 26 }).sum;

var chars = Enumerable.Range('a', 26).Select(n => (char)n).ToArray();
Func<long, string> toBase26String = n =>
{
    var s = ""; do { s = chars[n % 26] + s; n /= 26; } while (n > 0); return s;
};
Func<string, string> incrementPassword = p => toBase26String(fromBase26String(p) + 1);

Func<string, bool> containsIncreasingSequence = s => Enumerable.Range(0,s.Length-2)
    .Select(n => s.Substring(n,3))
    .Any(q => (q[0] + 1 == q[1]) && (q[1] + 1) == q[2]);

Func<string,bool> containsNaughtyLetters = s => s.Any(c => c == 'i' || c == 'o' || c == 'l');
Func<string,bool> containsTwoNonOverlappingPairs = s => Regex.IsMatch(s, @"(\w)\1.*(\w)\2");

Func<string,bool> isValidPassword = pw => !containsNaughtyLetters(pw) && 

Func<string, string> findNextPassword = start =>
{
    var startVal = fromBase26String(start);
     return Enumerable.Range(1, 10000000)
             .Select(n => startVal + n)
             .Select(n => toBase26String(n))
             .First(p => isValidPassword(p)); };


findNextPassword("vzbxkghb").Dump("a");// vzbxxyzz
findNextPassword("vzbxxyzz").Dump("b"); // vzcaabcc

So for F# I decided to go for a different approach, and after seeing a very elegant Ruby solution that used Ruby’s built in succ method, which is perfect for this problem, I created an F# successor function, and a succseq function which emits a sequence of password candidates.

I used Regular Expressions for the password validation, but built the run checker pattern thanks to Seq.windowed, to let us slide a 3 element window over the input sequence.

Anyway, whilst I’m still an F# beginner, I think that I am finally seeing some real improvements and am taking advantage of more of the language features. (Although no doubt Sehnsucht who has offered me lots of helpful advice in the past will find plenty of ways to improve on this ).

let inc = "abcdefghjkmnpqrstuvwxyz" |> Seq.pairwise |> dict
let (&) c s = sprintf "%c%s" c s 
let nextc (c,str) ch = match c, ch with | 0, n -> 0, n & str | 1, 'z' -> 1, "a" + str | 1, n -> 0, inc.[n] & str
let succ = Seq.rev >> Seq.fold nextc (1,"") >> snd
let succseq = Seq.unfold (fun f -> Some (f, succ f)) >> Seq.skip 1

let (=~) s p = Regex.IsMatch(s,p)
let run = [|'a'..'z'|] |> Seq.windowed 3 |> Seq.map String |> String.concat "|"
let isValid (p:string) = p =~ @"(\w)\1.*(\w)\2" && p =~ run
let findNext = succseq >> Seq.find isValid
 
findNext "abcdefgh" |> (=) "abcdffaa" |> Dump
findNext "vzbxkghb" |> (=) "vzbxxyzz" |> Dump
findNext "vzbxxyzz" |> (=) "vzcaabcc" |> Dump