docs/Advent_of_Code_2017_December_6th.rst

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