docs/Advent_of_Code_2017_December_1st.md

   1 # Advent of Code 2017
   2
   3 ## December 1st
   4
   5 \[Given\] a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.
   6
   7 For example:
   8
   9 * 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.
  10 * 1111 produces 4 because each digit (all 1) matches the next.
  11 * 1234 produces 0 because no digit matches the next.
  12 * 91212129 produces 9 because the only digit that matches the next one is the last digit, 9.
  13
  14
  15 ```python
  16 from notebook_preamble import J, V, define
  17 ```
  18
  19 I'll assume the input is a Joy sequence of integers (as opposed to a string or something else.)
  20
  21 We might proceed by creating a word that makes a copy of the sequence with the first item moved to the last, and zips it with the original to make a list of pairs, and a another word that adds (one of) each pair to a total if the pair matches.
  22
  23     AoC2017.1 == pair_up total_matches
  24
  25 Let's derive `pair_up`:
  26
  27          [a b c] pair_up
  28     -------------------------
  29        [[a b] [b c] [c a]]
  30
  31
  32 Straightforward (although the order of each pair is reversed, due to the way `zip` works, but it doesn't matter for this program):
  33
  34     [a b c] dup
  35     [a b c] [a b c] uncons swap
  36     [a b c] [b c] a unit concat
  37     [a b c] [b c a] zip
  38     [[b a] [c b] [a c]]
  39
  40
  41 ```python
  42 define('pair_up dup uncons swap unit concat zip')
  43 ```
  44
  45
  46 ```python
  47 J('[1 2 3] pair_up')
  48 ```
  49
  50     [[2 1] [3 2] [1 3]]
  51
  52
  53
  54 ```python
  55 J('[1 2 2 3] pair_up')
  56 ```
  57
  58     [[2 1] [2 2] [3 2] [1 3]]
  59
  60
  61 Now we need to derive `total_matches`.  It will be a `step` function:
  62
  63     total_matches == 0 swap [F] step
  64
  65 Where `F` will have the pair to work with, and it will basically be a `branch` or `ifte`.
  66
  67     total [n m] F
  68
  69 It will probably be easier to write if we dequote the pair:
  70
  71        total [n m] i F′
  72     ----------------------
  73          total n m F′
  74
  75 Now `F′` becomes just:
  76
  77     total n m [=] [pop +] [popop] ifte
  78
  79 So:
  80
  81     F == i [=] [pop +] [popop] ifte
  82
  83 And thus:
  84
  85     total_matches == 0 swap [i [=] [pop +] [popop] ifte] step
  86
  87
  88 ```python
  89 define('total_matches 0 swap [i [=] [pop +] [popop] ifte] step')
  90 ```
  91
  92
  93 ```python
  94 J('[1 2 3] pair_up total_matches')
  95 ```
  96
  97     0
  98
  99
 100
 101 ```python
 102 J('[1 2 2 3] pair_up total_matches')
 103 ```
 104
 105     2
 106
 107
 108 Now we can define our main program and evaluate it on the examples.
 109
 110
 111 ```python
 112 define('AoC2017.1 pair_up total_matches')
 113 ```
 114
 115
 116 ```python
 117 J('[1 1 2 2] AoC2017.1')
 118 ```
 119
 120     3
 121
 122
 123
 124 ```python
 125 J('[1 1 1 1] AoC2017.1')
 126 ```
 127
 128     4
 129
 130
 131
 132 ```python
 133 J('[1 2 3 4] AoC2017.1')
 134 ```
 135
 136     0
 137
 138
 139
 140 ```python
 141 J('[9 1 2 1 2 1 2 9] AoC2017.1')
 142 ```
 143
 144     9
 145
 146
 147
 148 ```python
 149 J('[9 1 2 1 2 1 2 9] AoC2017.1')
 150 ```
 151
 152     9
 153
 154
 155           pair_up == dup uncons swap unit concat zip
 156     total_matches == 0 swap [i [=] [pop +] [popop] ifte] step
 157
 158         AoC2017.1 == pair_up total_matches
 159
 160
 161 ```python
 162
 163 ```
 164
 165 Now the paired digit is "halfway" round.
 166
 167     [a b c d] dup size 2 / [drop] [take reverse] cleave concat zip
 168
 169
 170 ```python
 171 J('[1 2 3 4] dup size 2 / [drop] [take reverse] cleave concat zip')
 172 ```
 173
 174     [[3 1] [4 2] [1 3] [2 4]]
 175
 176
 177 I realized that each pair is repeated...
 178
 179
 180 ```python
 181 J('[1 2 3 4] dup size 2 / [drop] [take reverse] cleave  zip')
 182 ```
 183
 184     [1 2 3 4] [[1 3] [2 4]]
 185
 186
 187
 188 ```python
 189 define('AoC2017.1.extra dup size 2 / [drop] [take reverse] cleave  zip swap pop total_matches 2 *')
 190 ```
 191
 192
 193 ```python
 194 J('[1 2 1 2] AoC2017.1.extra')
 195 ```
 196
 197     6
 198
 199
 200
 201 ```python
 202 J('[1 2 2 1] AoC2017.1.extra')
 203 ```
 204
 205     0
 206
 207
 208
 209 ```python
 210 J('[1 2 3 4 2 5] AoC2017.1.extra')
 211 ```
 212
 213     4
 214
 215
 216 # Refactor FTW
 217
 218 With Joy a great deal of the heuristics from Forth programming carry over nicely.  For example, refactoring into small, well-scoped commands with mnemonic names...
 219
 220              rotate_seq == uncons swap unit concat
 221                 pair_up == dup rotate_seq zip
 222            add_if_match == [=] [pop +] [popop] ifte
 223           total_matches == [i add_if_match] step_zero
 224
 225               AoC2017.1 == pair_up total_matches
 226
 227            half_of_size == dup size 2 /
 228                split_at == [drop] [take reverse] cleave
 229           pair_up.extra == half_of_size split_at zip swap pop
 230
 231         AoC2017.1.extra == pair_up.extra total_matches 2 *
 232