Advent of Code F# — Day 21

ps. look out for all my oth­er solu­tions for Advent of Code chal­lenges here.

 

Day 21

See details of the chal­lenge here.

Today’s input looks like this:

swap posi­tion 2 with posi­tion 7
swap let­ter f with let­ter a
swap let­ter c with let­ter a
rotate based on posi­tion of let­ter g
rotate based on posi­tion of let­ter f
rotate based on posi­tion of let­ter b
swap posi­tion 3 with posi­tion 6
swap let­ter e with let­ter c
swap let­ter f with let­ter h

First, let’s mod­el the dif­fer­ent instruc­tions we’ll need to process with union types.

Then, we can use the same Regex active pat­tern we used in Day 10 to help us parse the input file into the Instruc­tion type.

Now let’s add a few func­tions to do the actu­al scram­bling:

Most of these are straight for­ward, but there is one thing I’d like to touch on as it might not be obvi­ous — the first line of the reverse func­tion : let n = n % input.Length.

Sup­pose the length of the input array is 4 (eg. [| ‘a’, ‘b’, ‘c’, ‘d’ |]) then shift­ing left or right by 5 spaces is the same as shift­ing by 1.

To solve part 1 we just need to apply the instruc­tions we parsed ear­li­er on our input.

let part1 = “abcdefgh”.ToCharArray() |> apply instruc­tions

 

Part 2

You scram­bled the pass­word cor­rect­ly, but you dis­cov­er that you can’t actu­al­ly
mod­i­fy the pass­word file on the sys­tem. You’ll need to un-scram­ble one of the
exist­ing pass­words by revers­ing the scram­bling process.

What is the un-scram­bled ver­sion of the scram­bled pass­word fbgd­ceah?

On first thought, it seemed we could reverse the scram­bling process by find­ing the inverse of each of the steps and apply the input in reverse order. For exam­ple, the inverse of Reverse, Swap­Pos and SwapLet­ter instruc­tions are them­selves; the inverse of Rotate(Left, 3) is Rotate(Right, 3) and vice ver­sa; the inverse of Move(1, 3) is Move(3, 1).

But… how do we find the inverse of Rotate­Base­dOn? We will need to know the exact no. of spaces to shift left, there’s no easy way to do it based on the char­ac­ter and the right-shift­ed result alone. You could, how­ev­er, go at it from a dif­fer­ent angle and try out all pos­si­ble inputs that would have giv­en us the out­put that we have — by shift­ing Left by 1 to input.Length no. of spaces.

That said, giv­en the length of the pass­word we need to unscram­ble, there are only 40320 per­mu­ta­tions of the let­ters abcde­fgh. A brute force approach is fea­si­ble and pos­si­bly eas­i­er in this case, and that’s the approach I decid­ed to go with. For that, I need a func­tion to return all per­mu­ta­tions of the let­ters abcde­fgh.

I found a nice imple­men­ta­tion of such func­tion on fss­nip cour­tesy of Rick Miner­ich and to solve part 2 we just need to find the per­mu­ta­tion that gives us the scram­bled pass­word “fbgd­ceah”.

 

(ps. if you’re inter­est­ed in how the first approach would look, I decid­ed to imple­ment it as well just for fun)

 

Links