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



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)



Advent of Code F# – Day 20

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


Day 20

See details of the challenge here.

Today’s input looks like this:


First, let’s read the input into a list of tuples representing the lower-upper bound ranges.

Notice that I’ve also gone through the trouble of sorting the input by the lower bounds. This way, as we iterate through the ranges we can build up an overal range where:

  • the lower bound is 0
  • the upper bound is the highest upper bound value we have processed so far

and where there are gaps between the current upper bound and the lower bound in the next range, those are the allowed IPs values.

eg. for my input the first 3 ranges are:

(0, 1888888)

(1888889, 1904062)

(1900859, 2087697)

  1. after processing (0, 1888888) the overall range is 0-1888888
  2. (1888889, 1904062) forms a continuous range after 1888888, so the overall range is now 0-1904062
  3. (1900859, 2087697) overlaps with the overall range on the lower bound, that’s ok, the overall range is now 0-2087697

no gaps were found in the 3 ranges so far.

Suppose the next range is (2087700, 2100000), then a gap would appear and we will have 2 allowed IPs: 2087698 and 2087699.

To put that into code, here’s a findAllowedIPs function that will process all the sorted list of ranges and yield all the allowed IPs as a lazy sequence. ps. for part 2 where we need to find the no. of allowed IPs this is a O(n) solution where n is the no. of blacklist ranges.

To solve part 1, we need the first allowed IP.

let part1 = findAllowedIPs input |> Seq.head


Part 2

How many IPs are allowed by the blacklist?

let part2 = findAllowedIPs input |> Seq.length



Advent of Code F# – Day 19

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


Day 19

See details of the challenge here.

I initially approached today’s challenge as a dynamic programming exercise, but it quickly transpired that there’s a much better way to do it once I realised that part 1 is in fact the Josephus Problem and there’s a simple solution to it.

To understand the above, watch the YouTube video in the links section below.


Part 2

Realizing the folly of their present-exchange rules, the Elves agree to instead
steal presents from the Elf directly across the circle. If two Elves are across
the circle, the one on the left (from the perspective of the stealer) is stolen
from. The other rules remain unchanged: Elves with no presents are removed from
the circle entirely, and the other elves move in slightly to keep the circle
evenly spaced.

For example, with five Elves (again numbered 1 to 5):

  • The Elves sit in a circle; Elf 1 goes first:
5   2
 4 3
  • Elves 3 and 4 are across the circle; Elf 3’s present is stolen, being the one to
    the left. Elf 3 leaves the circle, and the rest of the Elves move in:
  1           1
5   2  -->  5   2
 4 -          4
  • Elf 2 steals from the Elf directly across the circle, Elf 5:
  1         1 
-   2  -->     2
  4         4 
  • Next is Elf 4 who, choosing between Elves 1 and 2, steals from Elf 1:
 -          2  
    2  -->
 4          4
  • Finally, Elf 2 steals from Elf 4:
    -->  2  

So, with five Elves, the Elf that sits starting in position 2 gets all the

With the number of Elves given in your puzzle input, which Elf now gets all the

I’m not aware of this variation to the Josephus Problem, but I’d wager that there would be some pattern to the results similar to part 1, so I put together a dynamic programming solution to get some outputs. (ps. the solution is not good enough for the input as it’ll take too long to return)

With the help of this I can see a pattern emerging:

n : answer

1 : 1
2 : 2
3 : 3
4 : 1
5 : 2
6 : 3
7 : 5
8 : 7
9 : 9
10 : 1
11 : 2
12 : 3
13 : 4
14 : 5
15 : 6
16 : 7
17 : 8
18 : 9
19 : 11
20 : 13
21 : 15
22 : 17
23 : 19
24 : 21
25 : 23
26 : 25
27 : 27
28 : 1
29 : 2
30 : 3

  • where n is a power of 3 then the answer is itself
  • else n can be expressed as m + l where m is a power of 3
  • where l <= m (eg. n = 5 = 3 + 2 where m = 3 and l = 2) then the answer is just l
  • else the answer is m + (l – m) * 2 (eg. n = 7 = 3 + 4 where m = 3 and l = 4 and m + (l – m) * 2 = 5)



Advent of Code F# – Day 18

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


Day 18

See details of the challenge here.

To solve both part 1 and 2: