docs/Advent_of_Code_2017_December_6th.rst

   1 Advent of Code 2017
   2 ===================
   3
   4 December 6th
   5 ------------
   6
   7 ::
   8
   9     [0 2 7 0] dup max
  10
  11 .. code:: ipython3
  12
  13     from notebook_preamble import D, J, V, define
  14
  15 .. code:: ipython3
  16
  17     J('[0 2 7 0] dup max')
  18
  19
  20 .. parsed-literal::
  21
  22     [0 2 7 0] 7
  23
  24
  25 .. code:: ipython3
  26
  27     from joy.library import SimpleFunctionWrapper
  28     from joy.utils.stack import list_to_stack
  29
  30
  31     @SimpleFunctionWrapper
  32     def index_of(stack):
  33         '''Given a sequence and a item, return the index of the item, or -1 if not found.
  34
  35         E.g.:
  36
  37            [a b c] a index_of
  38         ------------------------
  39                    0
  40
  41            [a b c] d index_of
  42         ------------------------
  43                 -1
  44
  45         '''
  46         item, (sequence, stack) = stack
  47         i = 0
  48         while sequence:
  49             term, sequence = sequence
  50             if term == item:
  51                 break
  52             i += 1
  53         else:
  54             i = -1
  55         return i, stack
  56
  57
  58     D['index_of'] = index_of
  59
  60 .. code:: ipython3
  61
  62     J('[0 2 7 0] 7 index_of')
  63
  64
  65 .. parsed-literal::
  66
  67     2
  68
  69
  70 .. code:: ipython3
  71
  72     J('[0 2 7 0] 23 index_of')
  73
  74
  75 .. parsed-literal::
  76
  77     -1
  78
  79
  80 Starting at ``index`` distribute ``count`` "blocks" to the "banks" in
  81 the sequence.
  82
  83 ::
  84
  85     [...] count index distribute
  86     ----------------------------
  87                [...]
  88
  89 This seems like it would be a PITA to implement in Joypy...
  90
  91 .. code:: ipython3
  92
  93     from joy.utils.stack import iter_stack, list_to_stack
  94
  95
  96     @SimpleFunctionWrapper
  97     def distribute(stack):
  98         '''Starting at index+1 distribute count "blocks" to the "banks" in the sequence.
  99
 100         [...] count index distribute
 101         ----------------------------
 102                    [...]
 103
 104         '''
 105         index, (count, (sequence, stack)) = stack
 106         assert count >= 0
 107         cheat = list(iter_stack(sequence))
 108         n = len(cheat)
 109         assert index < n
 110         cheat[index] = 0
 111         while count:
 112             index += 1
 113             index %= n
 114             cheat[index] += 1
 115             count -= 1
 116         return list_to_stack(cheat), stack
 117
 118
 119     D['distribute'] = distribute
 120
 121 .. code:: ipython3
 122
 123     J('[0 2 7 0] dup max [index_of] nullary distribute')
 124
 125
 126 .. parsed-literal::
 127
 128     [2 4 1 2]
 129
 130
 131 .. code:: ipython3
 132
 133     J('[2 4 1 2] dup max [index_of] nullary distribute')
 134
 135
 136 .. parsed-literal::
 137
 138     [3 1 2 3]
 139
 140
 141 .. code:: ipython3
 142
 143     J('[3 1 2 3] dup max [index_of] nullary distribute')
 144
 145
 146 .. parsed-literal::
 147
 148     [0 2 3 4]
 149
 150
 151 .. code:: ipython3
 152
 153     J('[0 2 3 4] dup max [index_of] nullary distribute')
 154
 155
 156 .. parsed-literal::
 157
 158     [1 3 4 1]
 159
 160
 161 .. code:: ipython3
 162
 163     J('[1 3 4 1] dup max [index_of] nullary distribute')
 164
 165
 166 .. parsed-literal::
 167
 168     [2 4 1 2]
 169
 170
 171 Recalling "Generator Programs"
 172 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 173
 174 ::
 175
 176     [a F] x
 177     [a F] a F
 178
 179     [a F] a swap [C] dip rest cons
 180     a   [a F]    [C] dip rest cons
 181     a C [a F]            rest cons
 182     a C   [F]                 cons
 183
 184     w/ C == dup G
 185
 186     a dup G [F] cons
 187     a a   G [F] cons
 188
 189     w/ G == dup max [index_of] nullary distribute
 190
 191 .. code:: ipython3
 192
 193     define('direco dip rest cons')
 194
 195 .. code:: ipython3
 196
 197     define('G [direco] cons [swap] swoncat cons')
 198
 199 .. code:: ipython3
 200
 201     define('make_distributor [dup dup max [index_of] nullary distribute] G')
 202
 203 .. code:: ipython3
 204
 205     J('[0 2 7 0] make_distributor 6 [x] times pop')
 206
 207
 208 .. parsed-literal::
 209
 210     [0 2 7 0] [2 4 1 2] [3 1 2 3] [0 2 3 4] [1 3 4 1] [2 4 1 2]
 211
 212
 213 A function to drive a generator and count how many states before a repeat.
 214 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 215
 216 First draft:
 217
 218 ::
 219
 220     [] [GEN] x [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec
 221
 222 (?)
 223
 224 ::
 225
 226     []       [GEN] x [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec
 227     [] [...] [GEN]   [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec
 228     [] [...] [GEN]    pop index_of 0 >=
 229     [] [...]              index_of 0 >=
 230                                 -1 0 >=
 231                                  False
 232
 233 Base case
 234
 235 ::
 236
 237     [] [...] [GEN] [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec
 238     [] [...] [GEN]                      pop size --
 239     [] [...]                                size --
 240     [] [...]                                size --
 241
 242 A mistake, ``popop`` and no need for ``--``
 243
 244 ::
 245
 246     [] [...] [GEN] popop size
 247     []                   size
 248     n
 249
 250 Recursive case
 251
 252 ::
 253
 254     [] [...] [GEN] [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec
 255     [] [...] [GEN]                                   [swons] dip x  F
 256     [] [...] swons [GEN]                                         x  F
 257     [[...]]        [GEN]                                         x  F
 258     [[...]] [...]  [GEN]                                            F
 259
 260     [[...]] [...] [GEN] F
 261
 262 What have we learned?
 263
 264 ::
 265
 266     F == [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec
 267
 268 .. code:: ipython3
 269
 270     define('count_states [] swap x [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec')
 271
 272 .. code:: ipython3
 273
 274     define('AoC2017.6 make_distributor count_states')
 275
 276 .. code:: ipython3
 277
 278     J('[0 2 7 0] AoC2017.6')
 279
 280
 281 .. parsed-literal::
 282
 283     5
 284
 285
 286 .. code:: ipython3
 287
 288     J('[1 1 1] AoC2017.6')
 289
 290
 291 .. parsed-literal::
 292
 293     4
 294
 295
 296 .. code:: ipython3
 297
 298     J('[8 0 0 0 0 0] AoC2017.6')
 299
 300
 301 .. parsed-literal::
 302
 303     15
 304