

#lang scribble/lp2



@(require scribble/manual aocracket/helper)






@aoctitle[18]






@defmodule[aocracket/day18]






@link["http://adventofcode.com/day/18"]{The puzzle}. Our @linkrp["day18input.txt"]{input} is a 100 × 100 grid describing the initial state of a matrix of lights.









@chunk[<day18>



<day18setup>



<day18q1>



<day18q2>



<day18test>]






@isection{How many lights are on after 100 iterations of the lightswitching rules?}






There are two rules for incrementing the state of the lighting grid:






@itemlist[



@item{A light that's on stays on when 2 or 3 adjacent lights are also on, and otherwise turns off.}



@item{A light that's off turns on if exactly 3 adjacent lights are also on.}



]






These rules are equivalent to an implementation of Conway's @link["https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life"]{Game of Life} (recall that we implemented another Conway algorithm in @secref{Day_10}).






To model our lighting grid, we'll reuse our technique from @secref{Day_6} of using a single vector and translating between Cartesian coordinates and vector indexes. A lit bulb will be represented by @racket[1], an unlit bulb by, you guessed it, @racket[0].






The heavy lifting is in the @racket[iterategrid] function, which steps through each bulb, looks at the eight adjacent bulbs in the previous grid, and determines whether the bulb should be on or off.






As we think about that function, we might notice that life will be easier if we don't have to make special accommodations for bulbs at the edges of the grid, which ordinarily don't have eight adjacent bulbs. So what we'll do is add a margin of bulbs around the perimeter, and leave them in the off position. That way, all the bulbs in our original grid will have an eightbulb neighborhood. So instead of modeling our grid with a 100 × 100 = 10,000 unit vector, we'll use a 102 × 102 = 10,404 unit vector.






After that, it's just a matter of loading our input data into a grid, running @racket[iterategrid] 100 times — a great job for @iracket[for/fold] — and counting the activated bulbs in the resulting grid.






@chunk[<day18setup>



(require racket rackunit)



(provide (alldefinedout))






(define gridside 102)






(define (rowcol>idx row col) (+ (* gridside row) col))



(define (idx>rowcol idx) (quotient/remainder idx gridside))






(define (countlit grid) (apply + (vector>list grid)))






(define bulbon 1)



(define bulboff 0)






(define (input>grid str)



(define gridvec (makevector (* gridside gridside) bulboff))



(for* ([(bulbrow bulbrowidx) (inindexed (stringsplit str))]



[(bulb bulbcolidx) (inindexed (regexpmatch* #rx"." bulbrow))])



(vectorset! gridvec (rowcol>idx (add1 bulbrowidx) (add1 bulbcolidx))



(if (equal? bulb "#") bulbon bulboff)))



gridvec)






(define (bulb+adjacents grid grididx)



(definevalues (row col) (idx>rowcol grididx))



(for*/vector ([r (inrange (sub1 row) (+ row 2))]



[c (inrange (sub1 col) (+ col 2))])



(vectorref grid (rowcol>idx r c))))






(define (iterategrid grid)



(for*/vector ([row (inrange gridside)]



[col (inrange gridside)])



(cond



[(or (= row 0) (= col 0)



(= row (sub1 gridside))



(= col (sub1 gridside)))



bulboff]



[else



(define bulbidx (rowcol>idx row col))



(define bulb (vectorref grid bulbidx))



(define litneighbors



( (countlit (bulb+adjacents grid bulbidx)) bulb))



(cond



[(= bulbon bulb) (if (<= 2 litneighbors 3) bulbon bulboff)]



[(= 3 litneighbors) bulbon]



[else bulboff])])))









]






@chunk[<day18q1>



(define (q1 inputstr)



(define initialgrid (input>grid inputstr))



(define iterations 100)



(define finalgrid (for/fold ([gridsofar initialgrid])



([i (inrange iterations)])



(iterategrid gridsofar)))



(countlit finalgrid))]












@section{How many lights are on after 100 iterations, if the corner bulbs are always lit?}






Same as above, except we turn on the four corner bulbs after parsing the input, and after every iteration.






@chunk[<day18q2>






(define (lightcorners grid)



(vectorset*! grid (rowcol>idx 1 1) bulbon



(rowcol>idx 1 100) bulbon



(rowcol>idx 100 1) bulbon



(rowcol>idx 100 100) bulbon)



grid)






(define (q2 inputstr)



(define initialgrid (lightcorners (input>grid inputstr)))



(define iterations 100)



(define finalgrid (for/fold ([gridsofar initialgrid])



([i (inrange iterations)])



(lightcorners (iterategrid gridsofar))))



(countlit finalgrid))






]












@section{Testing Day 18}






@chunk[<day18test>



(module+ test



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



(checkequal? (q1 inputstr) 821)



(checkequal? (q2 inputstr) 886))]









