task.txt (10074B)
1 --- Day 10: Cathode-Ray Tube --- 2 3 You avoid the ropes, plunge into the river, and swim to shore. 4 5 The Elves yell something about meeting back up with them upriver, but the river is too loud to tell exactly what they're saying. They finish crossing the bridge and disappear from view. 6 7 Situations like this must be why the Elves prioritized getting the communication system on your handheld device working. You pull it out of your pack, but the amount of water slowly draining from a big crack in its screen tells you it probably won't be of much immediate use. 8 9 Unless, that is, you can design a replacement for the device's video system! It seems to be some kind of cathode-ray tube screen and simple CPU that are both driven by a precise clock circuit. The clock circuit ticks at a constant rate; each tick is called a cycle. 10 11 Start by figuring out the signal being sent by the CPU. The CPU has a single register, X, which starts with the value 1. It supports only two instructions: 12 13 addx V takes two cycles to complete. After two cycles, the X register is increased by the value V. (V can be negative.) 14 noop takes one cycle to complete. It has no other effect. 15 16 The CPU uses these instructions in a program (your puzzle input) to, somehow, tell the screen what to draw. 17 18 Consider the following small program: 19 20 noop 21 addx 3 22 addx -5 23 24 Execution of this program proceeds as follows: 25 26 At the start of the first cycle, the noop instruction begins execution. During the first cycle, X is 1. After the first cycle, the noop instruction finishes execution, doing nothing. 27 At the start of the second cycle, the addx 3 instruction begins execution. During the second cycle, X is still 1. 28 During the third cycle, X is still 1. After the third cycle, the addx 3 instruction finishes execution, setting X to 4. 29 At the start of the fourth cycle, the addx -5 instruction begins execution. During the fourth cycle, X is still 4. 30 During the fifth cycle, X is still 4. After the fifth cycle, the addx -5 instruction finishes execution, setting X to -1. 31 32 Maybe you can learn something by looking at the value of the X register throughout execution. For now, consider the signal strength (the cycle number multiplied by the value of the X register) during the 20th cycle and every 40 cycles after that (that is, during the 20th, 60th, 100th, 140th, 180th, and 220th cycles). 33 34 For example, consider this larger program: 35 36 addx 15 37 addx -11 38 addx 6 39 addx -3 40 addx 5 41 addx -1 42 addx -8 43 addx 13 44 addx 4 45 noop 46 addx -1 47 addx 5 48 addx -1 49 addx 5 50 addx -1 51 addx 5 52 addx -1 53 addx 5 54 addx -1 55 addx -35 56 addx 1 57 addx 24 58 addx -19 59 addx 1 60 addx 16 61 addx -11 62 noop 63 noop 64 addx 21 65 addx -15 66 noop 67 noop 68 addx -3 69 addx 9 70 addx 1 71 addx -3 72 addx 8 73 addx 1 74 addx 5 75 noop 76 noop 77 noop 78 noop 79 noop 80 addx -36 81 noop 82 addx 1 83 addx 7 84 noop 85 noop 86 noop 87 addx 2 88 addx 6 89 noop 90 noop 91 noop 92 noop 93 noop 94 addx 1 95 noop 96 noop 97 addx 7 98 addx 1 99 noop 100 addx -13 101 addx 13 102 addx 7 103 noop 104 addx 1 105 addx -33 106 noop 107 noop 108 noop 109 addx 2 110 noop 111 noop 112 noop 113 addx 8 114 noop 115 addx -1 116 addx 2 117 addx 1 118 noop 119 addx 17 120 addx -9 121 addx 1 122 addx 1 123 addx -3 124 addx 11 125 noop 126 noop 127 addx 1 128 noop 129 addx 1 130 noop 131 noop 132 addx -13 133 addx -19 134 addx 1 135 addx 3 136 addx 26 137 addx -30 138 addx 12 139 addx -1 140 addx 3 141 addx 1 142 noop 143 noop 144 noop 145 addx -9 146 addx 18 147 addx 1 148 addx 2 149 noop 150 noop 151 addx 9 152 noop 153 noop 154 noop 155 addx -1 156 addx 2 157 addx -37 158 addx 1 159 addx 3 160 noop 161 addx 15 162 addx -21 163 addx 22 164 addx -6 165 addx 1 166 noop 167 addx 2 168 addx 1 169 noop 170 addx -10 171 noop 172 noop 173 addx 20 174 addx 1 175 addx 2 176 addx 2 177 addx -6 178 addx -11 179 noop 180 noop 181 noop 182 183 The interesting signal strengths can be determined as follows: 184 185 During the 20th cycle, register X has the value 21, so the signal strength is 20 * 21 = 420. (The 20th cycle occurs in the middle of the second addx -1, so the value of register X is the starting value, 1, plus all of the other addx values up to that point: 1 + 15 - 11 + 6 - 3 + 5 - 1 - 8 + 13 + 4 = 21.) 186 During the 60th cycle, register X has the value 19, so the signal strength is 60 * 19 = 1140. 187 During the 100th cycle, register X has the value 18, so the signal strength is 100 * 18 = 1800. 188 During the 140th cycle, register X has the value 21, so the signal strength is 140 * 21 = 2940. 189 During the 180th cycle, register X has the value 16, so the signal strength is 180 * 16 = 2880. 190 During the 220th cycle, register X has the value 18, so the signal strength is 220 * 18 = 3960. 191 192 The sum of these signal strengths is 13140. 193 194 Find the signal strength during the 20th, 60th, 100th, 140th, 180th, and 220th cycles. What is the sum of these six signal strengths? 195 196 Your puzzle answer was 15880. 197 --- Part Two --- 198 199 It seems like the X register controls the horizontal position of a sprite. Specifically, the sprite is 3 pixels wide, and the X register sets the horizontal position of the middle of that sprite. (In this system, there is no such thing as "vertical position": if the sprite's horizontal position puts its pixels where the CRT is currently drawing, then those pixels will be drawn.) 200 201 You count the pixels on the CRT: 40 wide and 6 high. This CRT screen draws the top row of pixels left-to-right, then the row below that, and so on. The left-most pixel in each row is in position 0, and the right-most pixel in each row is in position 39. 202 203 Like the CPU, the CRT is tied closely to the clock circuit: the CRT draws a single pixel during each cycle. Representing each pixel of the screen as a #, here are the cycles during which the first and last pixel in each row are drawn: 204 205 Cycle 1 -> ######################################## <- Cycle 40 206 Cycle 41 -> ######################################## <- Cycle 80 207 Cycle 81 -> ######################################## <- Cycle 120 208 Cycle 121 -> ######################################## <- Cycle 160 209 Cycle 161 -> ######################################## <- Cycle 200 210 Cycle 201 -> ######################################## <- Cycle 240 211 212 So, by carefully timing the CPU instructions and the CRT drawing operations, you should be able to determine whether the sprite is visible the instant each pixel is drawn. If the sprite is positioned such that one of its three pixels is the pixel currently being drawn, the screen produces a lit pixel (#); otherwise, the screen leaves the pixel dark (.). 213 214 The first few pixels from the larger example above are drawn as follows: 215 216 Sprite position: ###..................................... 217 218 Start cycle 1: begin executing addx 15 219 During cycle 1: CRT draws pixel in position 0 220 Current CRT row: # 221 222 During cycle 2: CRT draws pixel in position 1 223 Current CRT row: ## 224 End of cycle 2: finish executing addx 15 (Register X is now 16) 225 Sprite position: ...............###...................... 226 227 Start cycle 3: begin executing addx -11 228 During cycle 3: CRT draws pixel in position 2 229 Current CRT row: ##. 230 231 During cycle 4: CRT draws pixel in position 3 232 Current CRT row: ##.. 233 End of cycle 4: finish executing addx -11 (Register X is now 5) 234 Sprite position: ....###................................. 235 236 Start cycle 5: begin executing addx 6 237 During cycle 5: CRT draws pixel in position 4 238 Current CRT row: ##..# 239 240 During cycle 6: CRT draws pixel in position 5 241 Current CRT row: ##..## 242 End of cycle 6: finish executing addx 6 (Register X is now 11) 243 Sprite position: ..........###........................... 244 245 Start cycle 7: begin executing addx -3 246 During cycle 7: CRT draws pixel in position 6 247 Current CRT row: ##..##. 248 249 During cycle 8: CRT draws pixel in position 7 250 Current CRT row: ##..##.. 251 End of cycle 8: finish executing addx -3 (Register X is now 8) 252 Sprite position: .......###.............................. 253 254 Start cycle 9: begin executing addx 5 255 During cycle 9: CRT draws pixel in position 8 256 Current CRT row: ##..##..# 257 258 During cycle 10: CRT draws pixel in position 9 259 Current CRT row: ##..##..## 260 End of cycle 10: finish executing addx 5 (Register X is now 13) 261 Sprite position: ............###......................... 262 263 Start cycle 11: begin executing addx -1 264 During cycle 11: CRT draws pixel in position 10 265 Current CRT row: ##..##..##. 266 267 During cycle 12: CRT draws pixel in position 11 268 Current CRT row: ##..##..##.. 269 End of cycle 12: finish executing addx -1 (Register X is now 12) 270 Sprite position: ...........###.......................... 271 272 Start cycle 13: begin executing addx -8 273 During cycle 13: CRT draws pixel in position 12 274 Current CRT row: ##..##..##..# 275 276 During cycle 14: CRT draws pixel in position 13 277 Current CRT row: ##..##..##..## 278 End of cycle 14: finish executing addx -8 (Register X is now 4) 279 Sprite position: ...###.................................. 280 281 Start cycle 15: begin executing addx 13 282 During cycle 15: CRT draws pixel in position 14 283 Current CRT row: ##..##..##..##. 284 285 During cycle 16: CRT draws pixel in position 15 286 Current CRT row: ##..##..##..##.. 287 End of cycle 16: finish executing addx 13 (Register X is now 17) 288 Sprite position: ................###..................... 289 290 Start cycle 17: begin executing addx 4 291 During cycle 17: CRT draws pixel in position 16 292 Current CRT row: ##..##..##..##..# 293 294 During cycle 18: CRT draws pixel in position 17 295 Current CRT row: ##..##..##..##..## 296 End of cycle 18: finish executing addx 4 (Register X is now 21) 297 Sprite position: ....................###................. 298 299 Start cycle 19: begin executing noop 300 During cycle 19: CRT draws pixel in position 18 301 Current CRT row: ##..##..##..##..##. 302 End of cycle 19: finish executing noop 303 304 Start cycle 20: begin executing addx -1 305 During cycle 20: CRT draws pixel in position 19 306 Current CRT row: ##..##..##..##..##.. 307 308 During cycle 21: CRT draws pixel in position 20 309 Current CRT row: ##..##..##..##..##..# 310 End of cycle 21: finish executing addx -1 (Register X is now 20) 311 Sprite position: ...................###.................. 312 313 Allowing the program to run to completion causes the CRT to produce the following image: 314 315 ##..##..##..##..##..##..##..##..##..##.. 316 ###...###...###...###...###...###...###. 317 ####....####....####....####....####.... 318 #####.....#####.....#####.....#####..... 319 ######......######......######......#### 320 #######.......#######.......#######..... 321 322 Render the image given by your program. What eight capital letters appear on your CRT? 323 324 Your puzzle answer was PLGFKAZG.