docs/Advent_of_Code_2017_December_5th.md

   1 # Advent of Code 2017
   2
   3 ## December 5th
   4 ...a list of the offsets for each jump. Jumps are relative: -1 moves to the previous instruction, and 2 skips the next one. Start at the first instruction in the list. The goal is to follow the jumps until one leads outside the list.
   5
   6 In addition, these instructions are a little strange; after each jump, the offset of that instruction increases by 1. So, if you come across an offset of 3, you would move three instructions forward, but change it to a 4 for the next time it is encountered.
   7
   8 For example, consider the following list of jump offsets:
   9
  10     0
  11     3
  12     0
  13     1
  14     -3
  15
  16 Positive jumps ("forward") move downward; negative jumps move upward. For legibility in this example, these offset values will be written all on one line, with the current instruction marked in parentheses. The following steps would be taken before an exit is found:
  17
  18 *    (0) 3  0  1  -3  - before we have taken any steps.
  19 *    (1) 3  0  1  -3  - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1.
  20 *     2 (3) 0  1  -3  - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
  21 *     2  4  0  1 (-3) - jump all the way to the end; leave a 4 behind.
  22 *     2 (4) 0  1  -2  - go back to where we just were; increment -3 to -2.
  23 *     2  5  0  1  -2  - jump 4 steps forward, escaping the maze.
  24
  25 In this example, the exit is reached in 5 steps.
  26
  27 How many steps does it take to reach the exit?
  28
  29 ## Breakdown
  30 For now, I'm going to assume a starting state with the size of the sequence pre-computed.  We need it to define the exit condition and it is a trivial preamble to generate it.  We then need and `index` and a `step-count`, which are both initially zero.  Then we have the sequence itself, and some recursive function `F` that does the work.
  31
  32        size index step-count [...] F
  33     -----------------------------------
  34                 step-count
  35
  36     F == [P] [T] [R1] [R2] genrec
  37
  38 Later on I was thinking about it and the Forth heuristic came to mind, to wit: four things on the stack are kind of much.  Immediately I realized that the size properly belongs in the predicate of `F`!  D'oh!
  39
  40        index step-count [...] F
  41     ------------------------------
  42              step-count
  43
  44 So, let's start by nailing down the predicate:
  45
  46     F == [P] [T] [R1]   [R2] genrec
  47       == [P] [T] [R1 [F] R2] ifte
  48
  49     0 0 [0 3 0 1 -3] popop 5 >=
  50
  51     P == popop 5 >=
  52
  53 Now we need the else-part:
  54
  55     index step-count [0 3 0 1 -3] roll< popop
  56
  57     E == roll< popop
  58
  59 Last but not least, the recursive branch
  60
  61     0 0 [0 3 0 1 -3] R1 [F] R2
  62
  63 The `R1` function has a big job:
  64
  65     R1 == get the value at index
  66           increment the value at the index
  67           add the value gotten to the index
  68           increment the step count
  69
  70 The only tricky thing there is incrementing an integer in the sequence.  Joy sequences are not particularly good for random access.  We could encode the list of jump offsets in a big integer and use math to do the processing for a good speed-up, but it still wouldn't beat the performance of e.g. a mutable array.  This is just one of those places where "plain vanilla" Joypy doesn't shine (in default performance.  The legendary *Sufficiently-Smart Compiler* would of course rewrite this function to use an array "under the hood".)
  71
  72 In the meantime, I'm going to write a primitive function that just does what we need.
  73
  74
  75 ```python
  76 from notebook_preamble import D, J, V, define
  77 from joy.library import SimpleFunctionWrapper
  78 from joy.utils.stack import list_to_stack
  79
  80
  81 @SimpleFunctionWrapper
  82 def incr_at(stack):
  83     '''Given a index and a sequence of integers, increment the integer at the index.
  84
  85     E.g.:
  86
  87        3 [0 1 2 3 4 5] incr_at
  88     -----------------------------
  89          [0 1 2 4 4 5]
  90
  91     '''
  92     sequence, (i, stack) = stack
  93     mem = []
  94     while i >= 0:
  95         term, sequence = sequence
  96         mem.append(term)
  97         i -= 1
  98     mem[-1] += 1
  99     return list_to_stack(mem, sequence), stack
 100
 101
 102 D['incr_at'] = incr_at
 103 ```
 104
 105
 106 ```python
 107 J('3 [0 1 2 3 4 5] incr_at')
 108 ```
 109
 110     [0 1 2 4 4 5]
 111
 112
 113 ### get the value at index
 114
 115     3 0 [0 1 2 3 4] [roll< at] nullary
 116     3 0 [0 1 2 n 4] n
 117
 118 ### increment the value at the index
 119
 120     3 0 [0 1 2 n 4] n [Q] dip
 121     3 0 [0 1 2 n 4] Q n
 122     3 0 [0 1 2 n 4] [popd incr_at] unary n
 123     3 0 [0 1 2 n+1 4] n
 124
 125 ### add the value gotten to the index
 126
 127     3 0 [0 1 2 n+1 4] n [+] cons dipd
 128     3 0 [0 1 2 n+1 4] [n +]      dipd
 129     3 n + 0 [0 1 2 n+1 4]
 130     3+n   0 [0 1 2 n+1 4]
 131
 132 ### increment the step count
 133
 134     3+n 0 [0 1 2 n+1 4] [++] dip
 135     3+n 1 [0 1 2 n+1 4]
 136
 137 ### All together now...
 138
 139     get_value == [roll< at] nullary
 140     incr_value == [[popd incr_at] unary] dip
 141     add_value == [+] cons dipd
 142     incr_step_count == [++] dip
 143
 144     R1 == get_value incr_value add_value incr_step_count
 145
 146     F == [P] [T] [R1] primrec
 147
 148     F == [popop !size! >=] [roll< pop] [get_value incr_value add_value incr_step_count] tailrec
 149
 150
 151 ```python
 152 from joy.library import DefinitionWrapper
 153
 154
 155 DefinitionWrapper.add_definitions('''
 156
 157       get_value [roll< at] nullary
 158      incr_value [[popd incr_at] unary] dip
 159       add_value [+] cons dipd
 160 incr_step_count [++] dip
 161
 162      AoC2017.5.0 get_value incr_value add_value incr_step_count
 163
 164 ''', D)
 165 ```
 166
 167
 168 ```python
 169 from joy.library import DefinitionWrapper
 170
 171
 172 DefinitionWrapper.add_definitions('''
 173
 174       get_value [roll< at] nullary
 175      incr_value [[popd incr_at] unary] dip
 176       add_value [+] cons dipd
 177 incr_step_count [++] dip
 178
 179      AoC2017.5.0 get_value incr_value add_value incr_step_count
 180
 181 ''', D)
 182 ```
 183
 184
 185 ```python
 186 define('F [popop 5 >=] [roll< popop] [AoC2017.5.0] tailrec')
 187 ```
 188
 189
 190 ```python
 191 J('0 0 [0 3 0 1 -3] F')
 192 ```
 193
 194     5
 195
 196
 197 ### Preamble for setting up predicate, `index`, and `step-count`
 198
 199 We want to go from this to this:
 200
 201        [...] AoC2017.5.preamble
 202     ------------------------------
 203         0 0 [...] [popop n >=]
 204
 205 Where `n` is the size of the sequence.
 206
 207 The first part is obviously `0 0 roll<`, then `dup size`:
 208
 209     [...] 0 0 roll< dup size
 210     0 0 [...] n
 211
 212 Then:
 213
 214     0 0 [...] n [>=] cons [popop] swoncat
 215
 216 So:
 217
 218     init-index-and-step-count == 0 0 roll<
 219     prepare-predicate == dup size [>=] cons [popop] swoncat
 220
 221     AoC2017.5.preamble == init-index-and-step-count prepare-predicate
 222
 223
 224 ```python
 225 DefinitionWrapper.add_definitions('''
 226
 227 init-index-and-step-count 0 0 roll<
 228 prepare-predicate dup size [>=] cons [popop] swoncat
 229
 230 AoC2017.5.preamble init-index-and-step-count prepare-predicate
 231
 232 AoC2017.5 AoC2017.5.preamble [roll< popop] [AoC2017.5.0] tailrec
 233
 234 ''', D)
 235 ```
 236
 237
 238 ```python
 239 J('[0 3 0 1 -3] AoC2017.5')
 240 ```
 241
 242     5
 243
 244
 245
 246                     AoC2017.5 == AoC2017.5.preamble [roll< popop] [AoC2017.5.0] primrec
 247
 248                   AoC2017.5.0 == get_value incr_value add_value incr_step_count
 249            AoC2017.5.preamble == init-index-and-step-count prepare-predicate
 250
 251                     get_value == [roll< at] nullary
 252                    incr_value == [[popd incr_at] unary] dip
 253                     add_value == [+] cons dipd
 254               incr_step_count == [++] dip
 255
 256     init-index-and-step-count == 0 0 roll<
 257             prepare-predicate == dup size [>=] cons [popop] swoncat
 258
 259
 260 This is by far the largest program I have yet written in Joy.  Even with the `incr_at` function it is still a bear.  There may be an arrangement of the parameters that would permit more elegant definitions, but it still wouldn't be as efficient as something written in assembly, C, or even Python.