

#lang scribble/lp2



@(require scribble/manual aocracket/helper)






@aoctitle[3]






@defmodule[aocracket/day03]






@link["http://adventofcode.com/day/3"]{The puzzle}. Our @linkrp["day03input.txt"]{input} is a string made of the characters @litchar{^v<>} that represent north, south, west, and east. Taken together, the string represents a path through an indefinitely large grid.






In essence, this a twodimensional version of the elevator problem in @secref{Day_1}.









@chunk[<day03>



<day03setup>



<day03q1>



<day03q1complex>



<day03q2>



<day03test>]






@isection{How many grid cells are visited?}






In the elevator problem, we modeled the parentheses that represented up and down as @racket[1] and @racket[1]. We'll proceed the same way here, but we'll assign Cartesian coordinates to each possible move — @racket['(0 1)] for north, @racket['(1 0)] for west, and so on.






For dualvalued data, whether to use @seclink["pairs" #:doc '(lib "scribblings/guide/guide.scrbl")]{pairs or lists} is largely a stylistic choice. Ask: what will you do with the data next? That will often suggest the most natural representation. In this case, the way we create each cell in the path is by adding the x and y coordinates of the current cell to the next move. So it ends up being convenient to model these cells as lists rather than pairs, so we can add them with a simple @racket[(map + currentcell nextmove)]. (Recall that when you use @iracket[map] with multiple lists, it pulls one element from each list in parallel.)






Once the whole cell path is computed, the answer is found by removing duplicate cells and counting how many remain.






@chunk[<day03setup>



(require racket rackunit)



(provide (alldefinedout))



]






@chunk[<day03q1>



(define (string>cells str)



(define start '(0 0))



(matchdefine (list east north west south) '((1 0) (0 1) (1 0) (0 1)))



(define moves (for/list ([s (inlist (regexpmatch* #rx"." str))])



(case s



[(">") east]



[("^") north]



[("<") west]



[("v") south])))



(for/fold ([cellssofar (list start)])



([nextmove (inlist moves)])



(define currentcell (car cellssofar))



(define nextcell (map + currentcell nextmove))



(cons nextcell cellssofar)))






(define (q1 str)



(length (removeduplicates (string>cells str))))]






@subsection{Alternate approach: complex numbers}






Rather than use Cartesian coordinates, we could rely on Racket's builtin support for complex numbers to trace the path in the complex plane. Complex numbers have a real and an imaginary part — e.g, @racket[3+4i] — and thus, represent points in a plane just as well as Cartesian coordinates. The advantage is that complex numbers are atomic values, not lists. We can add them normally, without resort to @racket[map]. (It's not essential for this problem, but math jocks might remember that complex numbers can be rotated 90 degrees counterclockwise by multiplying by @tt{+i}.)






Again, the problem has nothing to do with complex numbers inherently. Like pairs and lists, they're just another option for encoding dualvalued data.






@chunk[ <day03q1complex>



(define (string>complexcells str)



(define start 0)



(define east 1)



(define moves (for/list ([s (inlist (regexpmatch* #rx"." str))])



(* east (expt +i (case s



[(">") 0]



[("^") 1]



[("<") 2]



[("v") 3])))))



(for/fold ([cellssofar (list start)])



([nextmove (inlist moves)])



(define currentcell (car cellssofar))



(define nextcell (+ currentcell nextmove))



(cons nextcell cellssofar)))






(define (q1complex str)



(length (removeduplicates (string>complexcells str))))



]






@section{How many grid cells are visited if the path is split?}






By ``split'', the puzzle envisions two people starting at the origin, with one following the oddnumbered moves, and the other following the evennumbered moves. So there are two paths instead of one. The question remains the same: how many cells are visited by one path or the other?






The solution works the same as before — the only new task is to split the input into two strings, and then send them through our existing @racket[string>cells] function.






@chunk[<day03q2>



(define (splitoddsandevens str)



(definevalues (oddchars evenchars)



(for/fold ([oddssofar empty][evenssofar empty])



([c (instring str)][i (innaturals)])



(if (even? i)



(values oddssofar (cons c evenssofar))



(values (cons c oddssofar) evenssofar))))



(values (stringappend* (map ~a (reverse oddchars)))



(stringappend* (map ~a (reverse evenchars)))))






(define (q2 str)



(definevalues (oddstr evenstr) (splitoddsandevens str))



(length (removeduplicates



(append (string>cells oddstr) (string>cells evenstr)))))



]






@section{Testing Day 3}






@chunk[<day03test>



(module+ test



(define inputstr (file>string "day03input.txt"))



(checkequal? (q1 inputstr) 2565)



(checkequal? (q1complex inputstr) 2565)



(checkequal? (q2 inputstr) 2639))]



