Advent of Code F# – Day 25

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 25

See details of the challenge here.

Today’s input looks like this:

cpy a d
cpy 7 c
cpy 362 b
inc d
dec b
jnz b -2

At last, we’re at the end of this year’s Advent of Code challenges, and today’s challenge is another twist of the assembunny code we’ve seen a few times this year, most recently on Day 23.

Ad before, let’s define the instruction set as a union type and make short work of the parsing the input file.

One notable difference to today’s challenge though is that we’re no longer interested in the value of the registers but the output from executing the program.

So instead of returning the registers we’ll use a sequence comprehension to return the output values as an infinite, and lazy sequence instead.

(ps. I initially wrote the execute function with a nested recursive function, but on second thought the problem feels more concisely expressed as a while loop so I rewrote it as such)

To wrap up today’s challenge (part 2 just requires you to click a link to wrap up your AOC journey for another year) we need to find the first value of n that will yield pairs of [ 0, 1 ] indefinitely. Of course you can’t be sure that the pattern repeats indefinitely without deeper understanding of the pattern of change in the register values (perhaps it’d be a better approach rather than the trial-and-error route I have gone with). I have gone with 1000 values all following that pattern = repeating indefinitely, but turns out the answer is the same even when you use Seq.take 10.

So there it is folks, another year and another set of wonderfully enjoyable challenges. With you all a happy new year and see you soon!

 

Links

Advent of Code F# – Day 24

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 24

See details of the challenge here.

Today’s challenge is a mix of Breadth-First Search (or Level Order Tree Traversal) and the Travelling Salesman Problem.

First, let’s parse the input file into a 2D array to make it easier for us to work with.

My first attempt at solving this challenge with the same BSF approach that has been so useful in this year’s AOC challenges proved unsuccessful. Unlike previous challenges, today’s problem can involve backtracking so we can’t rely on a naive cache of positions we have passed through thus far.

However, we can still use BSF to find out the shortest distance between any two numbered nodes.

From here, we can build up a dictionary of the distance between every pair of numbered nodes and turn this BSF problem into a Travelling Salesman Problem and find the path through all the numbered nodes with the lowest total distance.

Now we can solve part 1 of the challenge with a simple recursive function.

This solution ran in 109ms on my laptop, including the time to build up the distances between pairs of nodes.

 

Part 2

Of course, if you leave the cleaning robot somewhere weird, someone is bound to notice.

What is the fewest number of steps required to start at 0, visit every non-0 number marked on the map at least once, and then return to 0?

A slight twist on part 1, but we can use the same approach as before but simply stipulate that when all numbered nodes have been traversed we also take into account the distance from the last node back to number 0.

This ran in 113ms on my laptop, including the time to build up the distance between pairs of nodes (or, 14ms if reusing the existing pairDistances)

 

Links

Advent of Code F# – Day 23

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 23

See details of the challenge here.

Today’s input looks like this:

cpy a b
dec b
cpy a d
cpy 0 a
cpy b c
inc a

..

Today’s challenge is an extension to Day 12, where we have introduced a new instruction for toggle (tgl). To make toggling logic simpler let’s introduce a union type to represent the different instructions we can receive and write a function parse them.

Next, let’s add a toggle function to toggle a given instruction and modify the execute function from Day 12 to work with the union type and support the new tgl instruction as well.

Now we can solve part 1.

let part1 = (execute [ “a”, 7 ] inputs).[“a”]

 

Part 2

The safe doesn’t open, but it does make several angry noises to express its frustration.

You’re quite sure your logic is working correctly, so the only other thing is… you check the painting again. As it turns out, colored eggs are still eggs. Now you count 12.

As you run the program with this new input, the prototype computer begins to overheat. You wonder what’s taking so long, and whether the lack of any instruction more powerful than “add one” has anything to do with it. Don’t bunnies usually multiply?

Anyway, what value should actually be sent to the safe?

As the description eludes to, if we use 12 as initial input it might take a while to run.. and the naive approach of just executing the logic as before, ie

let part2 = (execute [ “a”, 12 ] inputs).[“a”]

took a good 4 minutes to run on my 2015 MBP.

If you add a few printfn statements and you’ll a few blocks of instructions that repeat for many cycles, eg.

cpy b c
inc a
dec c
jnz c -2
dec d
jnz d -5

you can add a short-circuit when you see this happen and replace it with the equivalent of a = b * d (as the description eluded to).

 

Links

Advent of Code F# – Day 22

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 22

See details of the challenge here.

Today’s input looks like this:

root@ebhq-gridcenter# df -h
Filesystem                           Size    Used     Avail    Use%
/dev/grid/node-x0-y0     87T     71T     16T       81%
/dev/grid/node-x0-y1     93T     72T      21T       77%
/dev/grid/node-x0-y2     87T     67T      20T       77%
/dev/grid/node-x0-y3     89T     65T      24T       73%
/dev/grid/node-x0-y4     93T     67T      26T       72%

Of the information presented to us we only need the x & y position of the node, its size and amount of space used. Everything else can either be derived from these or are not needed for this challenge.

For part 1 of the challenge, if we sort the array of nodes by the amount of available space in descending order, then for each of the elements we only need to iterate through the sorted array for as long as the available space is >= the used space of the current node. Hence reducing the average time complexity from O(n2) to O(n * log n).

 

Part 2

Now that you have a better understanding of the grid, it’s time to get to work.

Your goal is to gain access to the data which begins in the node with y=0 and the highest x (that is, the node in the top-right corner).

For example, suppose you have the following grid:

Filesystem            Size  Used  Avail  Use%
/dev/grid/node-x0-y0   10T    8T     2T   80%
/dev/grid/node-x0-y1   11T    6T     5T   54%
/dev/grid/node-x0-y2   32T   28T     4T   87%
/dev/grid/node-x1-y0    9T    7T     2T   77%
/dev/grid/node-x1-y1    8T    0T     8T    0%
/dev/grid/node-x1-y2   11T    7T     4T   63%
/dev/grid/node-x2-y0   10T    6T     4T   60%
/dev/grid/node-x2-y1    9T    8T     1T   88%
/dev/grid/node-x2-y2    9T    6T     3T   66%

In this example, you have a storage grid 3 nodes wide and 3 nodes tall. The node you can access directly, node-x0-y0, is almost full. The node containing the data you want to access, node-x2-y0 (because it has y=0 and the highest x value), contains 6 terabytes of data – enough to fit on your node, if only you could make enough space to move it there.

Fortunately, node-x1-y1 looks like it has enough free space to enable you to move some of this data around. In fact, it seems like all of the nodes have enough space to hold any node’s data (except node-x0-y2, which is much larger, very full, and not moving any time soon). So, initially, the grid’s capacities and connections look like this:

( 8T/10T) --  7T/ 9T -- [ 6T/10T]
    |           |           |
  6T/11T  --  0T/ 8T --   8T/ 9T
    |           |           |
 28T/32T  --  7T/11T --   6T/ 9T

The node you can access directly is in parentheses; the data you want starts in the node marked by square brackets.

In this example, most of the nodes are interchangable: they’re full enough that no other node’s data would fit, but small enough that their data could be moved around. Let’s draw these nodes as .. The exceptions are the empty node, which we’ll draw as _, and the very large, very full node, which we’ll draw as #. Let’s also draw the goal data as G. Then, it looks like this:

(.) .  G
 .  _  .
 #  .  .

The goal is to move the data in the top right, G, to the node in parentheses. To do this, we can issue some commands to the grid and rearrange the data:

  • Move data from node-y0-x1 to node-y1-x1, leaving node node-y0-x1empty:
    (.) _  G
     .  .  .
     #  .  .
    
  • Move the goal data from node-y0-x2 to node-y0-x1:
    (.) G  _
     .  .  .
     #  .  .
    
  • At this point, we’re quite close. However, we have no deletion command, so we have to move some more data around. So, next, we move the data from node-y1-x2 to node-y0-x2:
    (.) G  .
     .  .  _
     #  .  .
    
  • Move the data from node-y1-x1 to node-y1-x2:
    (.) G  .
     .  _  .
     #  .  .
    
  • Move the data from node-y1-x0 to node-y1-x1:
    (.) G  .
     _  .  .
     #  .  .
    
  • Next, we can free up space on our node by moving the data from node-y0-x0 to node-y1-x0:
    (_) G  .
     .  .  .
     #  .  .
    
  • Finally, we can access the goal data by moving the it from node-y0-x1to node-y0-x0:
    (G) _  .
     .  .  .
     #  .  .
    

So, after 7 steps, we’ve accessed the data we want. Unfortunately, each of these moves takes time, and we need to be efficient:

What is the fewest number of steps required to move your goal data to node-x0-y0?

If you visualize the grid then the solution becomes pretty clear and one that we can actually work out by hand.

Here, the target node is marked as red, the empty node green (which is initially at position (7, 17)), and the very large, very full nodes are marked as black. We want to move the empty node all the way to (35, 0) so we can start moving the target node at (36, 0) horizontally towards (0, 0).

We can again use the Level Order Tree Traversal approach we have seen so many times this AOC for the first part. First, let’s transform the Node[] into a 2D array first to make our task easier.

The trick for the traversal part of the problem is to avoid passing through the same coordinate more than once, a problem that can be easily rectified with a cache of positions that we have already passed through.

Once the empty node is at (35, 0) we can commence the second part of the problem – to move the data in the target node to (0, 0). Every time we move the data to the empty node on the left, we’ll have to move the empty node in front of it again, which means going down, left, left and then up, so that means a total of 5 moves for every step towards (0, 0). Except, when the data is at (1, 0), which requires only one move.

Which means, there’s a total of 5 * 35 + 1 move left ONCE we have move the empty node to (35, 0).

In case you’re wondering why I left out the “+ 1” on line 33, it’s because the path that’s returned by findPaths includes the starting position (7, 17), so really line 33 should have read let part2 = path.Length – 1 + 35 * 5 + 1

 

Links

Advent of Code F# – Day 21

ps. look out for all my other solutions for Advent of Code challenges here.

 

Day 21

See details of the challenge here.

Today’s input looks like this:

swap position 2 with position 7
swap letter f with letter a
swap letter c with letter a
rotate based on position of letter g
rotate based on position of letter f
rotate based on position of letter b
swap position 3 with position 6
swap letter e with letter c
swap letter f with letter h

First, let’s model the different instructions we’ll need to process with union types.

Then, we can use the same Regex active pattern we used in Day 10 to help us parse the input file into the Instruction type.

Now let’s add a few functions to do the actual scrambling:

Most of these are straight forward, but there is one thing I’d like to touch on as it might not be obvious – the first line of the reverse function : let n = n % input.Length.

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

To solve part 1 we just need to apply the instructions we parsed earlier on our input.

let part1 = “abcdefgh”.ToCharArray() |> apply instructions

 

Part 2

You scrambled the password correctly, but you discover that you can’t actually
modify the password file on the system. You’ll need to un-scramble one of the
existing passwords by reversing the scrambling process.

What is the un-scrambled version of the scrambled password fbgdceah?

On first thought, it seemed we could reverse the scrambling process by finding the inverse of each of the steps and apply the input in reverse order. For example, the inverse of Reverse, SwapPos and SwapLetter instructions are themselves; the inverse of Rotate(Left, 3) is Rotate(Right, 3) and vice versa; the inverse of Move(1, 3) is Move(3, 1).

But… how do we find the inverse of RotateBasedOn? We will need to know the exact no. of spaces to shift left, there’s no easy way to do it based on the character and the right-shifted result alone. You could, however, go at it from a different angle and try out all possible inputs that would have given us the output that we have – by shifting Left by 1 to input.Length no. of spaces.

That said, given the length of the password we need to unscramble, there are only 40320 permutations of the letters abcdefgh. A brute force approach is feasible and possibly easier in this case, and that’s the approach I decided to go with. For that, I need a function to return all permutations of the letters abcdefgh.

I found a nice implementation of such function on fssnip courtesy of Rick Minerich and to solve part 2 we just need to find the permutation that gives us the scrambled password “fbgdceah”.

 

(ps. if you’re interested in how the first approach would look, I decided to implement it as well just for fun)

 

Links