I’ve been meaning to revisit Racket for a very long time. It was the functional programming language that was taught in IIT Bombay Programming Paradigms course, which was my favorite computer science course of all time.

When I heard that Advent of Code was starting soon, I thought this was the best time to revisit Racket, and re-learn the language while solving all the puzzles.

Day 1 puzzles (two of them) were straightforward and can be found here. Read the problem statement before proceeding further as I discuss my solution in Racket below.

I wanted to start off with trying to write the fibonacci function in Racket, just for practice. I love that instead of saying how to compute the fibonacci sequence, you can actually write what it is, and that is enough for computation. I dredged this function out of my memory as this was the first thing that was taught in the course.

(define (fib n)
  (cond
    [(= n 1) 1]
    [(= n 2) 1]
    [else (+ (fib (- n 1 )) (fib (- n 2)))]))

Note how I had to define what the base cases are (n = 1 and n = 2), and write the induction (or recursion in this case) for the general case. This is all that is needed for computing the n-th number in the fibonacci sequence.

Now, for the day 1 puzzles. I had to google a bit and frequently refer to the Racket guide, which is brilliant, to refresh my memory on the syntax and the “Racket-y” way of doing things.

Puzzle 1

Parsing

First, I had to parse the txt file containing the puzzle input. I thought this might be an arduous thing to do in a functional language, but Racket makes it super simple to do it in a single-line.

(define input (string-split (file->string "input.txt") "\n"))

file->string simply returns the contents of the entire file in a single string, while string->split splits the string using the given delimiter "\n", resulting in a list of strings. In this case, it results in a list like so '("R10", "L39", ...).

Okay, that was super simple. So, onwards!

Recursion

The Programming Paradigms class taught me one thing quite well – to think functional is to think recursively. So, I tried to find the recursive pattern to solving the first puzzle.

Given a bunch of rotations, if I have to count the number of times we end up at zero at the end of each rotation, then that number is:

• if we start at zero, then it is 1 + number of times we end up at zero in the rest of the rotations (starting from second rotation)
• else, it is the number of times we end up at zero in the rest of the rotations

This recursion seems simple, but it is very powerful as it already describes how to decompose the larger problem into a bunch of sub-problems. Of course, no recursion is complete unless you describe the base case. The base case is super simple, if you have no rotations, then the answer is 0.

(define (count-zeros-at-end rotations num)
  (cond
    [(empty? rotations) 0]
    [(= num 0) (+ 1 (count-zeros-at-end (cdr rotations) (next-num (car rotations) num)))]
    [else (count-zeros-at-end (cdr rotations) (next-num (car rotations) num))]))

Observe that the code can be read very similar to how I described the recursion above! This makes programming in Racket a pure delight.

I have offloaded the tricky part of computing what number we end up at after the rotation to the function next-num which is what I had to tackle next.

Direction to Rotate

Each rotation is of the form "LX" or "RX", where X is a number while L/R describe left/right rotation of the dial. Doing L decrements the number, while R increments the number. Finally, there is a wraparound at 0 and 99.

Before dealing with any of the above complications, I remembered that functions are simply values in Racket. They can be passed around just like numbers/strings throughout the code. If the only difference between L and R is whether we decrement or increment the number, then I can just create a single function that also takes an operator + or - as argument.

(define (next-num rotation num)
  (cond
    [(equal? (substring rotation 0 1) "L") (op-next-num (substring rotation 1) num -)]
    [else (op-next-num (substring rotation 1) num +)]))

Note how I sent + and - as arguments to the function op-next-num. This makes op-next-num a higher order function, which is just a fancy term for a function that takes another function as argument. The logic of next-num is super simple, it just parses the first character in a rotation and sends the appropriate operator to the op-next-num function call.

Next Number after Rotation

Now, we need to tackle the increment/decrement and the wraparound. We can implement the wraparound using a simple conditional function

(define (normalize num)
  (cond
    [(> num 99) (normalize (- num 100))]
    [(< num 0) (normalize (+ num 100))]
    [else num]))

Once again, recursion to the rescue!

We now have all the pieces except the last one, which is op-next-num. The only computation it needs to do besides making the call to normalize is to parse the offset in the rotation as a number. Again, Racket makes it super easy

(define (op-next-num offset num op)
  (let ([new-num (op num (string->number offset))])
    (normalize new-num)))

Solution

This is enough to solve the first puzzle by simply calling

(count-zeros-at-end input 50)

Puzzle 2

The second puzzle is a slight variant of puzzle 1, where instead of counting the number of times we end up on 0 after a rotation, we count the number of times we end up on 0 during/after a rotation.

My initial thought was to quickly construct a new recursion to define what the function to compute this would be. After spending a few minutes, trying to do that while extending the puzzle 1 solution, I realized that going through 0 is the same as ending up on a 0 after a “sub-rotation”, which is a part of the rotation.

So, instead of modifying/extend the code for puzzle 1, I can simply modify the input and reduce puzzle 2 to puzzle 1. Reduction is a very powerful concept!

Deconstructing rotations

To reuse solution for puzzle 1, we simply need to deconstruct the input so that each rotation is a unit rotation. The final result is the same, except now "L5" would be deconstructed into 5 rotations in sequence with each being "L1".

(define (deconstruct-rotations rotations)
  (if (empty? rotations) rotations
      (let ([rest-rotations (cdr rotations)]
            [num (string->number (substring (car rotations) 1))]
            [dir (substring (car rotations) 0 1)])
        (cond
          [(= num 0) (deconstruct-rotations rest-rotations)]
          [else (cons
                 (string-append dir "1")
                 (deconstruct-rotations
                  (cons
                   (string-append dir (number->string (- num 1)))
                   rest-rotations)))]))))

That looks big! But its actually relatively straightforward. The let calls simply define variables in the local scope of the function. The recursion defined here is the key to the function! The base case simply says, if there are no more offsets (num = 0), then simply return the deconstructed version of the rest of the rotations. Else, append "L1" or "R1" (depending on the input direction) to the front of the deconstructed list of the rest of the rotations (including the part of the first that is still left).

This function given input like '("L2", "R3") would deconstruct it into '("L1", "L1", "R1", "R1", "R1").

Solution

The solution is simply calling count-zeros-at-end on the deconstructed input

(count-zeros-at-end (deconstruct-rotations input) 50)