docs/Advent_of_Code_2017_December_5th.md

   1
   2 # Advent of Code 2017
   3
   4 ## December 5th
   5 ...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.
   6
   7 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.
   8
   9 For example, consider the following list of jump offsets:
  10
  11     0
  12     3
  13     0
  14     1
  15     -3
  16
  17 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:
  18
  19 *    (0) 3  0  1  -3  - before we have taken any steps.
  20 *    (1) 3  0  1  -3  - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1.
  21 *     2 (3) 0  1  -3  - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
  22 *     2  4  0  1 (-3) - jump all the way to the end; leave a 4 behind.
  23 *     2 (4) 0  1  -2  - go back to where we just were; increment -3 to -2.
  24 *     2  5  0  1  -2  - jump 4 steps forward, escaping the maze.
  25
  26 In this example, the exit is reached in 5 steps.
  27
  28 How many steps does it take to reach the exit?
  29
  30 ## Breakdown
  31 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.
  32
  33        size index step-count [...] F
  34     -----------------------------------
  35                 step-count
  36
  37     F == [P] [T] [R1] [R2] genrec
  38
  39 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!
  40
  41        index step-count [...] F
  42     ------------------------------
  43              step-count
  44
  45 So, let's start by nailing down the predicate:
  46
  47     F == [P] [T] [R1]   [R2] genrec
  48       == [P] [T] [R1 [F] R2] ifte
  49
  50     0 0 [0 3 0 1 -3] popop 5 >=
  51
  52     P == popop 5 >=
  53
  54 Now we need the else-part:
  55
  56     index step-count [0 3 0 1 -3] roll< popop
  57
  58     E == roll< popop
  59
  60 Last but not least, the recursive branch
  61
  62     0 0 [0 3 0 1 -3] R1 [F] R2
  63
  64 The `R1` function has a big job:
  65
  66     R1 == get the value at index
  67           increment the value at the index
  68           add the value gotten to the index
  69           increment the step count
  70
  71 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".)
  72
  73 In the meantime, I'm going to write a primitive function that just does what we need.
  74
  75
  76 ```python
  77 from notebook_preamble import D, J, V, define
  78 from joy.library import SimpleFunctionWrapper
  79 from joy.utils.stack import list_to_stack
  80
  81
  82 @SimpleFunctionWrapper
  83 def incr_at(stack):
  84     '''Given a index and a sequence of integers, increment the integer at the index.
  85
  86     E.g.:
  87
  88        3 [0 1 2 3 4 5] incr_at
  89     -----------------------------
  90          [0 1 2 4 4 5]
  91
  92     '''
  93     sequence, (i, stack) = stack
  94     mem = []
  95     while i >= 0:
  96         term, sequence = sequence
  97         mem.append(term)
  98         i -= 1
  99     mem[-1] += 1
 100     return list_to_stack(mem, sequence), stack
 101
 102
 103 D['incr_at'] = incr_at
 104 ```
 105
 106
 107 ```python
 108 J('3 [0 1 2 3 4 5] incr_at')
 109 ```
 110
 111     [0 1 2 4 4 5]
 112
 113
 114 ### get the value at index
 115
 116     3 0 [0 1 2 3 4] [roll< at] nullary
 117     3 0 [0 1 2 n 4] n
 118
 119 ### increment the value at the index
 120
 121     3 0 [0 1 2 n 4] n [Q] dip
 122     3 0 [0 1 2 n 4] Q n
 123     3 0 [0 1 2 n 4] [popd incr_at] unary n
 124     3 0 [0 1 2 n+1 4] n
 125
 126 ### add the value gotten to the index
 127
 128     3 0 [0 1 2 n+1 4] n [+] cons dipd
 129     3 0 [0 1 2 n+1 4] [n +]      dipd
 130     3 n + 0 [0 1 2 n+1 4]
 131     3+n   0 [0 1 2 n+1 4]
 132
 133 ### increment the step count
 134
 135     3+n 0 [0 1 2 n+1 4] [++] dip
 136     3+n 1 [0 1 2 n+1 4]
 137
 138 ### All together now...
 139
 140     get_value == [roll< at] nullary
 141     incr_value == [[popd incr_at] unary] dip
 142     add_value == [+] cons dipd
 143     incr_step_count == [++] dip
 144
 145     R1 == get_value incr_value add_value incr_step_count
 146
 147     F == [P] [T] [R1] primrec
 148
 149     F == [popop !size! >=] [roll< pop] [get_value incr_value add_value incr_step_count] primrec
 150
 151
 152 ```python
 153 from joy.library import DefinitionWrapper
 154
 155
 156 DefinitionWrapper.add_definitions('''
 157
 158       get_value == [roll< at] nullary
 159      incr_value == [[popd incr_at] unary] dip
 160       add_value == [+] cons dipd
 161 incr_step_count == [++] dip
 162
 163      AoC2017.5.0 == get_value incr_value add_value incr_step_count
 164
 165 ''', D)
 166 ```
 167
 168
 169 ```python
 170 define('F == [popop 5 >=] [roll< popop] [AoC2017.5.0] primrec')
 171 ```
 172
 173
 174 ```python
 175 J('0 0 [0 3 0 1 -3] F')
 176 ```
 177
 178     5
 179
 180
 181 ### Preamble for setting up predicate, `index`, and `step-count`
 182
 183 We want to go from this to this:
 184
 185        [...] AoC2017.5.preamble
 186     ------------------------------
 187         0 0 [...] [popop n >=]
 188
 189 Where `n` is the size of the sequence.
 190
 191 The first part is obviously `0 0 roll<`, then `dup size`:
 192
 193     [...] 0 0 roll< dup size
 194     0 0 [...] n
 195
 196 Then:
 197
 198     0 0 [...] n [>=] cons [popop] swoncat
 199
 200 So:
 201
 202     init-index-and-step-count == 0 0 roll<
 203     prepare-predicate == dup size [>=] cons [popop] swoncat
 204
 205     AoC2017.5.preamble == init-index-and-step-count prepare-predicate
 206
 207
 208 ```python
 209 DefinitionWrapper.add_definitions('''
 210
 211 init-index-and-step-count == 0 0 roll<
 212         prepare-predicate == dup size [>=] cons [popop] swoncat
 213
 214        AoC2017.5.preamble == init-index-and-step-count prepare-predicate
 215
 216                 AoC2017.5 == AoC2017.5.preamble [roll< popop] [AoC2017.5.0] primrec
 217
 218 ''', D)
 219 ```
 220
 221
 222 ```python
 223 J('[0 3 0 1 -3] AoC2017.5')
 224 ```
 225
 226     5
 227
 228
 229
 230                     AoC2017.5 == AoC2017.5.preamble [roll< popop] [AoC2017.5.0] primrec
 231
 232                   AoC2017.5.0 == get_value incr_value add_value incr_step_count
 233            AoC2017.5.preamble == init-index-and-step-count prepare-predicate
 234
 235                     get_value == [roll< at] nullary
 236                    incr_value == [[popd incr_at] unary] dip
 237                     add_value == [+] cons dipd
 238               incr_step_count == [++] dip
 239
 240     init-index-and-step-count == 0 0 roll<
 241             prepare-predicate == dup size [>=] cons [popop] swoncat
 242
 243
 244 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.