docs/Advent_of_Code_2017_December_6th.md

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