1 Day 1: Finding Headquarters
Read the description of today’s puzzle. Here is my input.
My solution’s code ended up being a bit cumbersome. I’m still new at functional programming, and it shows. I have some ideas for how to improve it, but I need to catch up on the next few days of puzzles first!
<day01-constants> <day01-describers> <day01-turn> <day01-walk> <day01-follow> <day01-parse> <day01-answer> <day01-q2-setup> <day01-test>
1.1 How Far Away is Easter Bunny HQ?
The program will conceptualize a person walking along a grid of city streets, and a list of instructions. Each instruction is two things: a turn-hand (i.e. "turn to the right...") plus a block-count ("...and go 3 blocks"). After each instruction we will be facing a new direction and have new x and y coordinates. I’m going call every combination of those three things a street-position.
We’ll take the compass directions and assign them values 1 through 4 in clockwise order: north is 1, east is 2, etc. A left-hand turn always means subtracting 1 from the current direction: e.g., facing west (4) and turning left (-1) naturally results in facing south (4 - 1 = 3). Of course turning "right" from 4 (west) should result in 1 (north), not 5. Same for turning "left" from 1 (north), which should result in 4 (west), not zero. I’ve added a couple of constants (make-west and make-north) which we’ll use later on to make that operation a little more readable.
(require racket rackunit) (provide (all-defined-out)) (struct street-position (facing x y) #:transparent) (struct instruction (turn-hand block-count) #:transparent) (define-values (make-west north east south west make-north) (values 0 1 2 3 4 5)) (define-values (left-hand right-hand) (values -1 1)) (define start (street-position north 0 0)) (define input-string (file->string "day01input.txt"))
1.1.1 Some debugging functions
The constants and functions below are not necessary to the solution of the problem. They’re just there to print information on the screen about a particular position or instruction.
(define cardinals (hash north "North" south "South" east "East" west "West")) (define hands (hash left-hand "Left-hand" right-hand "Right-hand")) (define (describe-position posn) (let* [(facing (format "Facing: ~a" (hash-ref cardinals (street-position-facing posn)))) (coords (format "At Row: ~a, Col: ~a" (street-position-y posn) (street-position-x posn)))] (format "~a; ~a" facing coords))) (define (describe-instruction instr) (format "Make a ~a turn and go ~a blocks." (hash-ref hands (instruction-turn-hand instr)) (instruction-block-count instr)))
1.1.2 Turning and Walking
Now that we can keep track of position, direction, and instructions, it’s time to start combining them.
Our first function turn-direction will take a starting position and an instruction (which includes a left- or right-hand indicator) and do only the turning part of the instruction; that is, it will return the new position with nothing changed except the facing direction. Since our compass directions and our turn-hands are just integers this amounts to a simple addition operation. I just manually check to see if the new direction is either 0 (make-west) or 5 (make-north) and change it to west or north accordingly. (There is a much quicker way to do this mathmatically using modulo; see Improvements for more information.)
(define (turn-direction start-position instr) (let*[(start-facing (street-position-facing start-position)) (which-hand (instruction-turn-hand instr)) (turned (+ start-facing which-hand)) (turned (cond [(= turned make-west) west] [(= turned make-north) north] [else turned]))] (displayln (format "Making a ~a turn" (hash-ref hands which-hand))) (street-position turned (street-position-x start-position) (street-position-y start-position))))
Our walk function takes a street-position and an instruction, and returns a new street-position indicating the new coordinates.
(define (walk start-pos instr) (let* [(start-x (street-position-x start-pos)) (start-y (street-position-y start-pos)) (direction (street-position-facing start-pos)) (blocks (instruction-block-count instr)) (finish-x (cond [(equal? direction east) (+ start-x blocks)] [(equal? direction west) (- start-x blocks)] [else start-x])) (finish-y (cond [(equal? direction north) (+ start-y blocks)] [(equal? direction south) (- start-y blocks)] [else start-y]))] (displayln (format "Walking ~a ~a blocks" (hash-ref cardinals direction) blocks)) (street-position direction finish-x finish-y)))
We have everything we need to follow a list of instructions. We’ll do it recursively.
If the function gets a list of instructions that has only one item in it, it follows both the turn and walk portions of the instruction and returns a new position.
If the list has more than one instruction, the function calls itself with only the first one, and then calls itself again with the rest of the list.
(define (follow-instructions start-position instr-list) (cond [(equal? 1 (length instr-list)) (let* [(whither (first instr-list)) (turned-posn (turn-direction start-position whither))] (walk turned-posn whither))] [else (follow-instructions (follow-instructions start-position (list (first instr-list))) (rest instr-list))]))
1.1.3 Parsing the input
The string->instruction function will take a string of the kind supplied by the problem and turn it into a proper instruction: e.g., "L3" becomes (instruction -1 3).
(define (string->instruction str) (let* [(blocks (string->number (substring str 1))) (hand (if (equal? #\R (first (string->list str))) right-hand left-hand))] (instruction hand blocks)))
Now we can take any string, split it out into a list of instructions, and follow those instructions to the end. Once you know the coordinates of the endpoint, finding the distance from the start-point is simple: just add the absolute values of each coordinate.
(define (q1 str) (define steps (map string->instruction (string-split str ", "))) (define destination (follow-instructions start steps)) (displayln (describe-position destination)) (+ (abs (street-position-x destination)) (abs (street-position-y destination))))
1.2 How far away is the first location you visit twice?
To handle this, I decided to create a pedestrian struct to hold both a list of all the street-positions visited so far as well as a current position.
I also made a function places-on-the-way which compares two street-positions and returns a list of all positions between them, except for the starting position. I was aided by the discovery of Racket’s built-in cartesian-product function.
This solution is very inefficient in that it still follows the entire list of instructions before checking to find the first revisited one.
(struct pedestrian (places-visited position) #:transparent) (define (places-on-the-way start-posn end-posn) (let* [(x-min (min (street-position-x start-posn) (street-position-x end-posn))) (y-min (min (street-position-y start-posn) (street-position-y end-posn))) (x-max (max (street-position-x start-posn) (street-position-x end-posn))) (y-max (max (street-position-y start-posn) (street-position-y end-posn))) (x-range (range x-min (+ x-max 1))) (y-range (range y-min (+ y-max 1))) (facedir (street-position-facing end-posn)) (start-coords (list (street-position-x start-posn) (street-position-y start-posn))) (coordlist (remove start-coords (cartesian-product x-range y-range)))] (for/list ([each-coord (in-list coordlist)]) (street-position facedir (first each-coord) (second each-coord))))) (define (q2-follow-instructions walker instr-list) (cond [(= 1 (length instr-list)) (let* [(whither (first instr-list)) (start-position (pedestrian-position walker)) (turned-pos (turn-direction start-position whither)) (end-position (walk turned-pos whither)) (new-places-visited (places-on-the-way start-position end-position)) (all-places-visited (append (pedestrian-places-visited walker) new-places-visited))] (pedestrian all-places-visited end-position))] [else (q2-follow-instructions (q2-follow-instructions walker (list (first instr-list))) (rest instr-list))])) (define (q2 str) (define steps (map string->instruction (string-split str ", "))) (define walker (q2-follow-instructions (pedestrian (list start) start) steps)) (define first-revisited (check-duplicates (pedestrian-places-visited walker) (lambda (a b) (and (= (street-position-x a) (street-position-x b)) (= (street-position-y a) (street-position-y b)))))) (if first-revisited (+ (abs (street-position-x first-revisited)) (abs (street-position-y first-revisited))) "No places visited more than once!"))
1.3 Improvements
I find Racket’s struct to be very verbose. E.g., given a street-position named pos, other languages would let you type pos.x to get the x element of the struct, but Racket makes you express this as (street-position-x pos). I exacerbated this by giving my structs names that were overly long. But I also think Racket has better, more concise ways than struct for organizing this problem. I think I’ll try another approach next time.
I could probably also have made my functions more concise by digging into the use of for/fold. Will look into that for future problems.
My turn-direction function did its thing rather ponderously. Using the modulo function you can create a mathematical expression which always results in a correct value between 1 and 4.
> (define (better-turn facing which-hand) (+ 1 (modulo (+ facing -1 which-hand) 4))) > (better-turn 2 -1) 1
> (better-turn 1 -1) 4
> (better-turn 4 1) 1
1.4 Testing Day 1
(module+ test (check-equal? (q1 "R2, L3") 5) (check-equal? (q1 "R2, R2, R2") 2) (check-equal? (q1 "R5, L5, R5, R3") 12) (check-equal? (q1 input-string) 262) (check-equal? (q2 "R8, R4, R4, R8") 4) (check-equal? (q2 input-string) 131))