docs/Advent_of_Code_2017_December_2nd.md

   1 # Advent of Code 2017
   2
   3 ## December 2nd
   4
   5 For each row, determine the difference between the largest value and the smallest value; the checksum is the sum of all of these differences.
   6
   7 For example, given the following spreadsheet:
   8
   9     5 1 9 5
  10     7 5 3
  11     2 4 6 8
  12
  13 * The first row's largest and smallest values are 9 and 1, and their difference is 8.
  14 * The second row's largest and smallest values are 7 and 3, and their difference is 4.
  15 * The third row's difference is 6.
  16
  17 In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18.
  18
  19
  20 ```python
  21 from notebook_preamble import J, V, define
  22 ```
  23
  24 I'll assume the input is a Joy sequence of sequences of integers.
  25
  26     [[5 1 9 5]
  27      [7 5 3]
  28      [2 4 6 8]]
  29
  30 So, obviously, the initial form will be a `step` function:
  31
  32     AoC2017.2 == 0 swap [F +] step
  33
  34 This function `F` must get the `max` and `min` of a row of numbers and subtract.  We can define a helper function `maxmin` which does this:
  35
  36
  37 ```python
  38 define('maxmin [max] [min] cleave')
  39 ```
  40
  41
  42 ```python
  43 J('[1 2 3] maxmin')
  44 ```
  45
  46     3 1
  47
  48
  49 Then `F` just does that then subtracts the min from the max:
  50
  51     F == maxmin -
  52
  53 So:
  54
  55
  56 ```python
  57 define('AoC2017.2 [maxmin - +] step_zero')
  58 ```
  59
  60
  61 ```python
  62 J('''
  63
  64 [[5 1 9 5]
  65  [7 5 3]
  66  [2 4 6 8]] AoC2017.2
  67
  68 ''')
  69 ```
  70
  71     18
  72
  73
  74 ...find the only two numbers in each row where one evenly divides the other - that is, where the result of the division operation is a whole number. They would like you to find those numbers on each line, divide them, and add up each line's result.
  75
  76 For example, given the following spreadsheet:
  77
  78     5 9 2 8
  79     9 4 7 3
  80     3 8 6 5
  81
  82 *    In the first row, the only two numbers that evenly divide are 8 and 2; the result of this division is 4.
  83 *    In the second row, the two numbers are 9 and 3; the result is 3.
  84 *    In the third row, the result is 2.
  85
  86 In this example, the sum of the results would be 4 + 3 + 2 = 9.
  87
  88 What is the sum of each row's result in your puzzle input?
  89
  90
  91 ```python
  92 J('[5 9 2 8] sort reverse')
  93 ```
  94
  95     [9 8 5 2]
  96
  97
  98
  99 ```python
 100 J('[9 8 5 2] uncons [swap [divmod] cons] dupdip')
 101 ```
 102
 103     [8 5 2] [9 divmod] [8 5 2]
 104
 105
 106
 107     [9 8 5 2] uncons [swap [divmod] cons F] dupdip G
 108       [8 5 2]            [9 divmod]      F [8 5 2] G
 109
 110
 111
 112
 113 ```python
 114 V('[8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip')
 115 ```
 116
 117                                           • [8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip
 118                                   [8 5 2] • [9 divmod] [uncons swap] dip dup [i not] dip
 119                        [8 5 2] [9 divmod] • [uncons swap] dip dup [i not] dip
 120          [8 5 2] [9 divmod] [uncons swap] • dip dup [i not] dip
 121                                   [8 5 2] • uncons swap [9 divmod] dup [i not] dip
 122                                   8 [5 2] • swap [9 divmod] dup [i not] dip
 123                                   [5 2] 8 • [9 divmod] dup [i not] dip
 124                        [5 2] 8 [9 divmod] • dup [i not] dip
 125             [5 2] 8 [9 divmod] [9 divmod] • [i not] dip
 126     [5 2] 8 [9 divmod] [9 divmod] [i not] • dip
 127                        [5 2] 8 [9 divmod] • i not [9 divmod]
 128                                   [5 2] 8 • 9 divmod not [9 divmod]
 129                                 [5 2] 8 9 • divmod not [9 divmod]
 130                                 [5 2] 1 1 • not [9 divmod]
 131                             [5 2] 1 False • [9 divmod]
 132                  [5 2] 1 False [9 divmod] •
 133
 134
 135 ## Tricky
 136
 137 Let's think.
 138
 139 Given a *sorted* sequence (from highest to lowest) we want to
 140 * for head, tail in sequence
 141     * for term in tail:
 142         * check if the head % term == 0
 143             * if so compute head / term and terminate loop
 144             * else continue
 145
 146 ### So we want a `loop` I think
 147
 148     [a b c d] True [Q] loop
 149     [a b c d] Q    [Q] loop
 150
 151 `Q` should either leave the result and False, or the `rest` and True.
 152
 153        [a b c d] Q
 154     -----------------
 155         result 0
 156
 157        [a b c d] Q
 158     -----------------
 159         [b c d] 1
 160
 161 This suggests that `Q` should start with:
 162
 163     [a b c d] uncons dup roll<
 164     [b c d] [b c d] a
 165
 166 Now we just have to `pop` it if we don't need it.
 167
 168     [b c d] [b c d] a [P] [T] [cons] app2 popdd [E] primrec
 169     [b c d] [b c d] [a P] [a T]                 [E] primrec
 170
 171 -------------------
 172
 173     w/ Q == [% not] [T] [F] primrec
 174
 175             [a b c d] uncons
 176             a [b c d] tuck
 177     [b c d] a [b c d] uncons
 178     [b c d] a b [c d] roll>
 179     [b c d] [c d] a b Q
 180     [b c d] [c d] a b [% not] [T] [F] primrec
 181
 182     [b c d] [c d] a b T
 183     [b c d] [c d] a b / roll> popop 0
 184
 185     [b c d] [c d] a b F                   Q
 186     [b c d] [c d] a b pop swap uncons ... Q
 187     [b c d] [c d] a       swap uncons ... Q
 188     [b c d] a [c d]            uncons ... Q
 189     [b c d] a c [d]                   roll> Q
 190     [b c d] [d] a c Q
 191
 192     Q == [% not] [/ roll> popop 0] [pop swap uncons roll>] primrec
 193
 194     uncons tuck uncons roll> Q
 195
 196
 197 ```python
 198 J('[8 5 3 2] 9 [swap] [% not] [cons] app2 popdd')
 199 ```
 200
 201     [8 5 3 2] [9 swap] [9 % not]
 202
 203
 204 -------------------
 205
 206             [a b c d] uncons
 207             a [b c d] tuck
 208     [b c d] a [b c d] [not] [popop 1] [Q] ifte
 209
 210     [b c d] a [] popop 1
 211     [b c d] 1
 212
 213     [b c d] a [b c d] Q
 214
 215
 216        a [...] Q
 217     ---------------
 218        result 0
 219
 220        a [...] Q
 221     ---------------
 222            1
 223
 224
 225     w/ Q == [first % not] [first / 0] [rest [not] [popop 1]] [ifte]
 226
 227
 228
 229     a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]
 230     a [b c d]  first % not
 231     a b % not
 232     a%b not
 233     bool(a%b)
 234
 235     a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]
 236     a [b c d]                first / 0
 237     a b / 0
 238     a/b 0
 239
 240     a [b c d] [first % not] [first / 0] [rest [not] [popop 1]]   [ifte]
 241     a [b c d]                            rest [not] [popop 1] [Q] ifte
 242     a [c d]                                   [not] [popop 1] [Q] ifte
 243     a [c d]                                   [not] [popop 1] [Q] ifte
 244
 245     a [c d] [not] [popop 1] [Q] ifte
 246     a [c d]  not
 247
 248     a [] popop 1
 249     1
 250
 251     a [c d] Q
 252
 253
 254     uncons tuck [first % not] [first / 0] [rest [not] [popop 1]] [ifte]
 255
 256
 257
 258
 259 ### I finally sat down with a piece of paper and blocked it out.
 260
 261 First, I made a function `G` that expects a number and a sequence of candidates and return the result or zero:
 262
 263        n [...] G
 264     ---------------
 265         result
 266
 267        n [...] G
 268     ---------------
 269            0
 270
 271 It's a recursive function that conditionally executes the recursive part of its recursive branch
 272
 273     [Pg] [E] [R1 [Pi] [T]] [ifte] genrec
 274
 275 The recursive branch is the else-part of the inner `ifte`:
 276
 277     G == [Pg] [E] [R1 [Pi] [T]]   [ifte] genrec
 278       == [Pg] [E] [R1 [Pi] [T] [G] ifte] ifte
 279
 280 But this is in hindsight.  Going forward I derived:
 281
 282     G == [first % not]
 283          [first /]
 284          [rest [not] [popop 0]]
 285          [ifte] genrec
 286
 287 The predicate detects if the `n` can be evenly divided by the `first` item in the list.  If so, the then-part returns the result.  Otherwise, we have:
 288
 289     n [m ...] rest [not] [popop 0] [G] ifte
 290     n [...]        [not] [popop 0] [G] ifte
 291
 292 This `ifte` guards against empty sequences and returns zero in that case, otherwise it executes `G`.
 293
 294
 295 ```python
 296 define('G [first % not] [first /] [rest [not] [popop 0]] [ifte] genrec')
 297 ```
 298
 299 Now we need a word that uses `G` on each (head, tail) pair of a sequence until it finds a (non-zero) result.  It's going to be designed to work on a stack that has some candidate `n`, a sequence of possible divisors, and a result that is zero to signal to continue (a non-zero value implies that it is the discovered result):
 300
 301        n [...] p find-result
 302     ---------------------------
 303               result
 304
 305 It applies `G` using `nullary` because if it fails with one candidate it needs the list to get the next one (the list is otherwise consumed by `G`.)
 306
 307     find-result == [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec
 308
 309     n [...] p [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec
 310
 311 The base-case is trivial, return the (non-zero) result.  The recursive branch...
 312
 313     n [...] p roll< popop uncons [G] nullary find-result
 314     [...] p n       popop uncons [G] nullary find-result
 315     [...]                 uncons [G] nullary find-result
 316     m [..]                       [G] nullary find-result
 317     m [..] p                                 find-result
 318
 319 The puzzle states that the input is well-formed, meaning that we can expect a result before the row sequence empties and so do not need to guard the `uncons`.
 320
 321
 322 ```python
 323 define('find-result [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec')
 324 ```
 325
 326
 327 ```python
 328 J('[11 9 8 7 3 2] 0 tuck find-result')
 329 ```
 330
 331     3.0
 332
 333
 334 In order to get the thing started, we need to `sort` the list in descending order, then prime the `find-result` function with a dummy candidate value and zero ("continue") flag.
 335
 336
 337 ```python
 338 define('prep-row sort reverse 0 tuck')
 339 ```
 340
 341 Now we can define our program.
 342
 343
 344 ```python
 345 define('AoC20017.2.extra [prep-row find-result +] step_zero')
 346 ```
 347
 348
 349 ```python
 350 J('''
 351
 352 [[5 9 2 8]
 353  [9 4 7 3]
 354  [3 8 6 5]] AoC20017.2.extra
 355
 356 ''')
 357 ```
 358
 359     9.0
 360