On this page:
6.1 What is the the error-corrected message?
6.2 What is the actual message Santa is sending?
6.3 Testing Day 6

6 Day 6: Signals and Noise

Read the description of today’s puzzle. Here is my input.

6.1 What is the the error-corrected message?

(require racket rackunit)
(define input-string (file->string "day06input.txt"))

To solve the puzzle, I need to find the most frequent character in 1st, 2nd, etc., position of each line. This is a pretty straightforward problem, so to compensate, I’m going to give a detailed, tedious explanation of my solution.

Because the problem is so simple, I’m going to do all the work in one function, recover-message. This function will take a list of strings, and an optional comparison function.

Starting with the list of strings representing each line of input, I break each of those strings into a list of characters: "abcd" becomes '(#\a #\b #\c #\d).

I now have a list of lists, where each of the inner lists is a row. I transpose this so the inner lists represent the columns instead, using that one weird old trick of (apply map list lines).

This works because of how the map function handles multiple lists: (map list '(a b c) '(1 2 3)) is equivalent to (list (list 'a 1) (list 'b 2) (list 'c 3)).

Then I remove the duplicate characters from each column and store the results in cols-unique-chars.

Next I iterate over both the original columns list and the new cols-unique-chars list simultaneously with for/list. For each unique character I generate a new two-element list pairing the character with the number of times it appears in that column. So for example, given a list of unique characters like '(#\a #\s #\r #\e), this loop will produce a list of lists that looks like '((#\a 3) (#\s 1) (#\r 1) (#\e 5)). I collect those lists of lists in another list called cols-char-counts.

Finally, I sort each list-of-lists in cols-char-counts with a lambda function that sorts by comparing the second elements in each inner list. This comparison is done using the compare-fn parameter: the default value of this is the > function, so by default it will sort elements in descending order: e.g., the example above becomes '((#\e 5) (#\a 3) (#\s 1) (#\r 1)). Finally I gather up the first element of the first element of each — the most frequent character in every column — into a list called top-chars and combine that final list into a string.

(define (recover-message strs [compare-fn >])
  (define lines (map string->list strs))
  (define columns
    (apply map list lines))
  (define cols-unique-chars
    (for/list ([col (in-list columns)])
              (remove-duplicates col)))
  (define cols-char-counts
    (for/list ([col-chars (in-list cols-unique-chars)]
               [col (in-list columns)])
              (map (lambda(c)
                     (list c (count (curry char=? c) col)))
  (define top-chars
    (map (lambda (col-count)
           (first (first (sort col-count
                               (lambda(a b)
                                 (compare-fn (second a) (second b)))))))
  (list->string top-chars))

(define (q1 str)
  (recover-message (string-split str "\n")))

6.2 What is the actual message Santa is sending?

In part two, it turns out I’m actually supposed to find the least frequent character in each column, rather than the most frequent.

So I want to do the exact same thing as above, except to use < instead of > to compare the character counts at the end. I was clever and wrote recover-message to accept an alternative comparison function, so all there is to do is call it the same way as before but with < as the final parameter.

(define (q2 str)
  (recover-message (string-split str "\n") <))

6.3 Testing Day 6

(module+ test
  (check-equal? (q1 input-string) "dzqckwsd")
  (check-equal? (q2 input-string) "lragovly"))