# Advent of Code 2017, Day 2

This is my solution for Day 2 of this year’s Advent of Code.

You may also enjoy browsing the Day 2 solutions megathread on Reddit.

## PROBLEM

The spreadsheet consists of rows of apparently-random numbers. To make sure the recovery process is on the right track, they need you to calculate the spreadsheet’s checksum. For each row, determine the difference between the largest value and the smallest value; the checksum is the sum of all of these differences.

For example, given the following spreadsheet:

```5 1 9 5
7 5 3
2 4 6 8
```

The first row’s largest and smallest values are 9 and 1, and their difference is 8.

The second row’s largest and smallest values are 7 and 3, and their difference is 4.

The third row’s difference is 6.

In this example, the spreadsheet’s checksum would be 8 + 4 + 6 = 18.

## SOLUTION

```(define (line->list line)
;; String -> List
(in-port (make-string-input-port line)))
(map string->number fields))))

;; File -> List[List[Number]]
(call-with-input-file file
(lambda (port)
(results '()))
(if (eof-object? line)
results
(loop (read-line port) (cons line results)))))))

(define (main prog+args)
(write (apply + (map
(lambda (row)
(let* ((xs (line->list row))
(min (apply min xs))
(max (apply max xs)))
(- max min)))
rows)))
(newline)))
```

# Advent of Code 2017, Day 1

This is my solution for Day 1 of this year’s Advent of Code.

You may also enjoy browsing the Day 1 solutions megathread on Reddit.

## PROBLEM

The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.

For example:

• 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.

• 1111 produces 4 because each digit (all 1) matches the next.

• 1234 produces 0 because no digit matches the next.

• 91212129 produces 9 because the only digit that matches the next one is the last digit, 9.

## SOLUTION

```(define captcha-input "5994521226795838")

(define (gather-matches s)
;; String -> List
(let ((in-port (make-string-input-port s)) (count 0) (head #f) (vals '()))
(let loop ((cur (read-char in-port)) (next (peek-char in-port)) (count count) (vals vals))
(if (eof-object? next)
(cons cur vals)
vals)
(cond ((= count 0)
(begin
(loop cur next (+ 1 count) vals)))
((char=? cur next)
(loop (read-char in-port) (peek-char in-port) (+ 1 count) (cons cur vals)))
(else (loop (read-char in-port) (peek-char in-port) (+ 1 count) vals)))))))

(define (main prog+args)
(matches* (map (lambda (c) (string->number (string c))) matches))
(sum (apply + matches*)))
(begin
(format #t "MATCHES*: ~A~%" matches*)
(format #t "SUM: ~A~%" sum))))
```

# Advent of Code, Day 3

In this post I’ll describe my solution for Day 3 of the Advent of Code.

## Problem Description

Day 3: Perfectly Spherical Houses in a Vacuum

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (‘^’), south (‘v’), east (‘>’), or west (‘<‘). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

For example:

‘>’ delivers presents to 2 houses: one at the starting location, and one to the east.

‘^>v<‘ delivers presents to 4 houses in a square, including twice to the house at his starting/ending location.

‘^v^v^v^v^v’ delivers a bunch of presents to some very lucky children at only 2 houses.

## Solution

Broadly speaking, my solution consisted of:

• Reading the directions file to determine the largest x and y values of the grid
• Making a shaped array using those dimensions (specifically, we double the array dimensions to allow for movement up, down, forward, and back)
• Starting in the center of the shaped array, follow the instructions from the “map” and mark every house (called a “position” in the code) if it hasn’t already been visited
• Every time we visit a house we haven’t already visited, we bump a counter

Here’s the Scheme code that accomplishes those steps:

```;; read in the string
;; sum the ^ and v chars to get the height of the matrix (graph)
;; sum the < and > chars to get the width of the matrix (graph)

(define (north? ch) (char=? ch #\^))
(define (south? ch) (char=? ch #\v))
(define (east? ch) (char=? ch #\>))
(define (west? ch) (char=? ch #\<))

(define (make-shape width height)
;; Int Int Int -> Shape
(shape 0 width 0 height))

;; Pathname -> Shape
(with-input-from-file file
(lambda ()
(let loop ((width 0)
(height 0)
(min-width  0)
(max-width 0)
(min-height 0)
(max-height 0)
(if (eof-object? ch)
(make-shape
(* 2 (- max-width min-width))
(* 2 (-  max-height min-height)))
(cond ((north? ch)
(loop width (+ height 1)
min-width max-width
(min min-height height)
(max max-height height)
((south? ch)
(loop width (- height 1)
min-width max-width
(min min-height height)
(max max-height height)
((east? ch)
(loop (+ width 1) height
(min min-width width)
(max max-width width)
min-height max-height
((west? ch)
(loop (- width 1) height
(min min-width width)
(max max-width width)
min-height max-height
(else (error "WHOA"))))))))

;; We make a shaped, multi-dimensional array (SRFI-25) in the size
;; it's determined we need by our earlier check.

(define (make-grid shape)
;; Shape -> Array
(make-array shape #f))

;; The POSITION data type

(define-record-type position
(make-position x y)
position?
(x position-x set-position-x!)
(y position-y set-position-y!))

(define (array-center arr)
;; Array -> Position
(let ((len-x (array-length arr 0))
(len-y (array-length arr 1)))
(make-position (/ len-x 2)
(/ len-y 2))))

(define (make-relative-position x y ch)
;; Int Int Char -> Position
(let ((vals '()))
(cond ((north? ch)
(set! vals (list (+ x 1) y)))
((south? ch)
(set! vals (list (- x 1) y)))
((east? ch)
(set! vals (list x (- y 1))))
((west? ch)
(set! vals (list x (+ y 1))))
(else (set! vals (list x y))))
(make-position (first vals)
(second vals))))

(define (visited? arr x y)
;; Array Int Int -> Bool
(array-ref arr x y))

(define (set-visited! arr x y)
;; Array Int Int -> Undefined
(array-set! arr x y #t))

(define (visit-locations arr file)
;; Pathname -> Int
(let ((visited-count 0))
(with-input-from-file file
(lambda ()
(current-position (array-center arr)))
(if (eof-object? ch)
visited-count
(begin
(let* ((current-x (position-x current-position))
(current-y (position-y current-position))
(next-position
(make-relative-position current-x current-y ch)))
(if (not (visited? arr current-x current-y))
(begin
(set! visited-count (+ visited-count 1))
(set-visited! arr current-x current-y)
next-position))
visited-count))

;; eof
```

Once this code is loaded up in the REPL, you can use it as shown below. (Note that the answer shown at the end isn’t real to avoid a spoiler.)

```(set! *the-array* (make-grid (read-shape-file (expand-file-name "~/Code/personal/advent-of-code/03.dat"))))
'#{Array:srfi-9-record-type-descriptor}

> (array-size *the-array*)
42588

> (array-center *the-array*)
'#{Position}

> (visit-locations *the-array* *the-file*)
12345
```

# Advent of Code, Day 2

This post describes my solution for Day 2 of the Advent of Code.

## Problem Description

First, the problem description (copied from the website):

Day 2: I Was Told There Would Be No Math

The elves are running low on wrapping paper, and so they need to submit an order for more. They have a list of the dimensions (length l, width w, and height h) of each present, and only want to order exactly as much as they need.

Fortunately, every present is a box (a perfect right rectangular prism), which makes calculating the required wrapping paper for each gift a little easier: find the surface area of the box, which is 2 x l x w + 2 x w x h + 2 x h x l. The elves also need a little extra paper for each present: the area of the smallest side.

For example:

• A present with dimensions 2x3x4 requires 2 x 6 + 2 x 12 + 2 x 8 = 52 square feet of wrapping paper plus 6 square feet of slack, for a total of 58 square feet.
• A present with dimensions 1x1x10 requires 2 x 1 + 2 x 10 + 2 x 10 = 42 square feet of wrapping paper plus 1 square foot of slack, for a total of 43 square feet.

All numbers in the elves’ list are in feet. How many total square feet of wrapping paper should they order?

## Solution

Once again, we’ll be working in Scheme.

For this problem, I decided to create a “box” data type. In addition to the automatically generated accessors (thanks SRFI-9!), I wrote several procedures to perform calculations on boxes, namely:

• `SURFACE-AREA`: Calculate the box’s surface area.
• `SMALLEST-SIDE`: Determine which of the box’s sides has the smallest surface area (the extra material makes it easier to wrap).

`WRAPPING-PAPER` is just a “wrapper” (pun intended) around the first two.

`LINE->BOX`, `READ-BOXES`, and `SUM-BOXES` are all about parsing the input file contents and shuffling them into the box data type that we use to do the actual calculation. The only part that required a bit of thought was the line with `STRING-TOKENIZE` in `LINE->BOX`. In Perl I’d use `my @params = split /x/, \$line` without even thinking, but I was less familiar with Scheme’s facility for solving this problem, so it took a few minutes to puzzle out the right part of Scheme’s “API”. (`STRING-TOKENIZE` was helpfully provided by SRFI-13.)

Abstract data types FTW! I’ll be using them more as the month’s challenges progress.

```;; ,open srfi-9 srfi-13 sort

(define-record-type box
(make-box l w h)
box?
(l box-length set-box-length!)
(w box-width set-box-width!)
(h box-height set-box-height!))

(define (surface-area box)
;; Box -> Int
(let ((l (box-length box))
(w (box-width box))
(h (box-height box)))
(+ (* 2 l w)
(* 2 w h)
(* 2 h l))))

(define (smallest-side box)
;; Box -> Int
(define (smallest-two xs)
;; List -> List
(let ((sorted (sort-list xs <)))
(list (first sorted)
(second sorted))))
(let ((l (box-length box))
(w (box-width box))
(h (box-height box)))
(apply * (smallest-two (list l w h)))))

(define (wrapping-paper box)
;; Box -> Int
(let ((minimum (surface-area box))
(extra (smallest-side box)))
(+ minimum extra)))

(define (line->box line)
;; String -> Box
(define (line->lon s)
;; String -> List<Number>
(let ((xs (string-tokenize s (char-set-complement (char-set #\x)))))
(map string->number xs)))
(let* ((dims (line->lon line)))
(let ((l (first dims))
(w (second dims))
(h (third dims)))
(make-box l w h))))

;; Pathname -> List<Box>
(with-input-from-file file
(lambda ()
(ys '()))
(if (eof-object? line)
ys
(loop
(cons (line->box line) ys)))))))

(define (sum-boxes boxes)
;; List<Box> -> Int
(let ((xs (map wrapping-paper boxes)))
(apply + xs)))

;; eof
```

# Advent of Code, Day 1

Advent of Code is a site that provides a programming problem for every day in December leading up to Christmas.

I’ve become a little obsessed with it over the last few days, and thought I’d write up my results. So far I’ve been working in Scheme.

Here’s the Day 1 problem description:

## Day 1: Not Quite Lisp

Santa was hoping for a white Christmas, but his weather machine’s “snow” function is powered by stars, and he’s fresh out! To save Christmas, he needs you to collect fifty stars by December 25th.

Collect stars by helping Santa solve puzzles. Two puzzles will be made available on each day in the advent calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. Good luck!

Here’s an easy puzzle to warm you up.

Santa is trying to deliver presents in a large apartment building, but he can’t find the right floor – the directions he got are a little confusing. He starts on the ground floor (floor 0) and then follows the instructions one character at a time.

An opening parenthesis, (, means he should go up one floor, and a closing parenthesis, ), means he should go down one floor.

The apartment building is very tall, and the basement is very deep; he will never find the top or bottom floors.

For example:

• `(())` and `()()` both result in floor 0.
• `(((` and `(()(()(` both result in floor 3.
• `))(((((` also results in floor 3.
• `())` and `))(` both result in floor -1 (the first basement level).
• `)))` and `)())())` both result in floor -3.

To what floor do the instructions take Santa?

The file of instructions looks something like this (but much larger):

`()()((((()(((())(()(()((((((()(()(((())))((()(((()))((())(()((()`

Here’s the (reasonably straight-forward) Scheme code. It basically just iterates through the input file, bumping a counter up or down based on the type of paren read from the input port. The definitions of `UP-FLOOR?` and `DOWN-FLOOR?` weren’t really necessary, but they made the main procedure a little easier to read.

```(define (up-floor? x)
(char=? x #\())

(define (down-floor? x)
(char=? x #\)))

(define (find-floor file)
(with-input-from-file file
(lambda ()
(let loop ((floor-number 0)