Day 2 of doing advent of code using Racket. Let’s go!

Before we discuss my solution, read the problem statement here. Now, for the first puzzle.

Puzzle 1

Parsing

As usual, we need to first start with parsing the input. The input is given as a single line with comma-separated ranges, where each range is of the form "start-end" where both start and end are numbers.

(define (strip string)
  (string-replace string "\n" ""))

(define (parse-range string-range)
  (let([range (string-split string-range "-")])
    (map string->number range)))

(define input (map (compose1 parse-range strip) (string-split (file->string "input.txt") ",")))

Few things to note here:

• I used a few functional-y way of doing things, the first being using map which allows you to apply a “procedure” (as Racket calls functions), to an input list.
• Second, I used compose1 which allows you to compose multiple functions (similar to the mathematical composition operator). If you do compose1 proc1 proc2 then, proc2 is applied first, and proc1 is applied to the output of proc2

After this sequence of operations, input is a list of elements, each of which is a list of two elements '(start, end).

Recursion

Now to think about how to solve the puzzle. The fact that the input contains a list of ranges does not make it any different from a problem where there is only a single range. We can call the function that works on a single range on the list of ranges using map.

So, let’s try writing a procedure for computing the sum of numbers in a single range, that have their digits repeated twice. Again, we want to do this using recursion as it makes writing the racket code super simple!

Note, that for a range (start, end), we can compute the result as,

• if start has digits repeated twice, then start + result(start+1, end)
• else, result(start+1, end)

The base case is simple – if for any range start > end, then return 0.

(define (compute-sum-repeating range)
  (let([first (car range)]
       [second (car (cdr range))]
       [rest (cdr range)])
    (cond
      [(> first second) 0]
      [(repeating-twice? first) (+ first (compute-sum-repeating (cons (+ 1 first) rest)))]
      [else (compute-sum-repeating (cons (+ 1 first) rest))])))

Observe that repeating-twice? is the procedure that actually checks if the digits are repeated twice. Let’s see how we can implement that.

Repeating Twice

Given any number N, figuring out if its digits are repeated twice (like 1010 and not 101) can be difficult to do in its numerical representation. However, in its string representation ("1010"), this is quite easy as we can simply check if the first half of the string is the same as second half. Note that if there are odd number of digits, then we can directly return False.

(define (repeating-twice? number)
  (let*([digits (number->string number)]
        [half (quotient (string-length digits) 2)])
    (cond
      [(odd? (string-length digits)) #f]
      [else (equal? (substring digits 0 half) (substring digits half))])))

The last remaining piece is to call compute-sum-repeating-range on the list of ranges and sum up all values,

(define (compute-sum-repeating-all ranges)
  (foldl + 0 (map (lambda (range) (compute-sum-repeating range)) ranges)))

Note the use of foldl which takes a procedure and its arguments. If foldl is called with N lists, then the procedure should take N+1 arguments where the extra argument is the combined return values so far.

In this case, we pass the + procedure and 0 as the start value, so we essentially sum up all the values.

Solution

We can simply call

(compute-sum-repeating-all input)

Puzzle 2

Puzzle 2 was definitely a little challenging, especially if you constrain yourself to reuse/extend existing functions for puzzle 1. After a bit of thinking, the solution I came up with involved extending the functions for puzzle 1 to take a repeating-n? function as argument. The repeating-n? procedure generalizes the repeating check for any arbitrary number of times that the digits can repeat.

Extending Puzzle 1

Let’s first take a look at how to extend the puzzle 1 procedures, before diving into repeating-n?

(define (compute-sum-repeating range repeating-op?)
  (let([first (car range)]
       [second (car (cdr range))]
       [rest (cdr range)])
    (cond
      [(> first second) 0]
      [(repeating-op? first) (+ first (compute-sum-repeating (cons (+ 1 first) rest) repeating-op?))]
      [else (compute-sum-repeating (cons (+ 1 first) rest) repeating-op?)])))

The only difference is that compute-sum-repeating now takes repeating-op? as argument which it passes down the recursion and also uses in the conditional check (where before, we were using repeating-twice?.) To recover puzzle 1 functionality, all you have to do is to send repeating-twice? as the value for the repeating-op? argument of the above procedure.

Similarly, we can also extend the compute-sum-repeating-all procedure

(define (compute-sum-repeating-all ranges repeating-op?)
  (foldl + 0 (map (lambda (range) (compute-sum-repeating range repeating-op?)) ranges)))

Repeating N times

As N can be variable and unknown, checking if a number has digits repeating N times can be challenging. I wanted to use recursion again to perform this check. First observation was that it would be easy to do these checks if the number was a string. We will refer to the string representation of the number as digits.

The second and more crucial observation was that a number that has N times repeating digits, also has one of its prefix repeated N times. Take for example, "854854854", which has one of its prefixes "854" repeated 3 times. So, I first started with a function to construct all prefixes given digits

(define (all-prefixes digits)
  (for/list ([i (string-length digits)])
    (substring digits 0 i)))

Our first introduction to imperative-style programming in Racket! The for/list is simply a for loop that returns a list by evaluating the expression provided for all values of the iterable i.

This procedure, given "123" would return the list '("" "1" "12"). Note that "123" is excluded (even though it is a valid prefix) as we are only iterating i until (string-length digits), and (substring digits 0 i) excludes i. We do this as the entire number repeating once is not an invalid ID according to the puzzle problem statement.

As long as one of its prefixes is repeated N times, the number is an invalid ID. This hints of an or operation.

(define (repeating-n? number)
  (let*([digits (number->string number)])
    (ormap (lambda (pattern) (repeating-n-digits? digits pattern)) (all-prefixes digits))))

ormap applies map of given procedure on the list, and then takes the or of all the values in the resulting list. The procedure repeating-n-digits? simply takes a prefix pattern and checks if that repeats in digits.

(define (repeating-n-digits? digits pattern)
  (let*([pattern-length (string-length pattern)])
    (cond
      [(equal? digits "") #t]
      [(equal? pattern "") #f]
      [(< (string-length digits) pattern-length) #f]
      [else (and
             (equal? pattern (substring digits 0 pattern-length))
             (repeating-n-digits? (substring digits pattern-length) pattern))])))

repeating-n-digits? is the crux of puzzle 2. Given a pattern (which in our case will be a prefix), it checks if the first substring of input digits of the same length as pattern, is the same as pattern. If not, then it returns #f, else it checks that the same pattern repeats in the rest of the digits. The base case is that if we give an empty string "" for digits then we reached the end of the string, and return #t. The other base case is to return #f if the input pattern is empty "", as this does not mean an invalid ID.

Solution

We have all the pieces to solve both puzzle 1 and puzzle 2 with the same set of procedures. For puzzle 2, we simply call

(compute-sum-repeating-all input repeating-n?)

For puzzle 1, we can call

(compute-sum-repeating-all input repeating-twice?)