1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
/* * Copyright (c) 2019, 2020 Erik Nordstrøm <erik@nordstroem.no> * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ solution_printer!(2, print_solution, input_generator, INPUT, solve_part_1, solve_part_2); pub const INPUT: &str = include_str!("../input/2019/day2.txt"); /// ### Day 2: 1202 Program Alarm /// /// [https://adventofcode.com/2019/day/2](https://adventofcode.com/2019/day/2) /// /// On the way to your [gravity assist](https://en.wikipedia.org/wiki/Gravity_assist) around the Moon, your ship computer /// beeps angrily about a "[1202 program alarm](https://www.hq.nasa.gov/alsj/a11/a11.landing.html#1023832)". On the radio, an Elf is /// already explaining how to handle the situation: "Don't worry, that's /// perfectly norma--" The ship computer [bursts into flames](https://en.wikipedia.org/wiki/Halt_and_Catch_Fire). /// /// You notify the Elves that the computer's [magic smoke](https://en.wikipedia.org/wiki/Magic_smoke) seems to have /// escaped. "That computer ran *Intcode* programs like the gravity assist /// program it was working on; surely there are enough spare parts up there /// to build a new Intcode computer!" /// /// An Intcode program is a list of [integers](https://en.wikipedia.org/wiki/Integer) separated by commas (like /// `1,0,0,3,99`). To run one, start by looking at the first integer (called /// position `0`). Here, you will find an *opcode* - either `1`, `2`, or `99`. The /// opcode indicates what to do; for example, `99` means that the program is /// finished and should immediately halt. Encountering an unknown opcode /// means something went wrong. /// /// Opcode `1` *adds* together numbers read from two positions and stores the /// result in a third position. The three integers *immediately after* the /// opcode tell you these three positions - the first two indicate the /// *positions* from which you should read the input values, and the third /// indicates the *position* at which the output should be stored. /// /// For example, if your Intcode computer encounters `1,10,20,30`, it should /// read the values at positions `10` and `20`, add those values, and then /// overwrite the value at position `30` with their sum. /// /// Opcode `2` works exactly like opcode `1`, except it *multiplies* the two inputs /// instead of adding them. Again, the three integers after the opcode /// indicate *where* the inputs and outputs are, not their values. /// /// Once you're done processing an opcode, *move to the next one* by stepping /// forward `4` positions. /// /// For example, suppose you have the following program: /// /// ```text /// 1,9,10,3,2,3,11,0,99,30,40,50 /// ``` /// /// For the purposes of illustration, here is the same program split into multiple lines: /// /// ```text /// 1,9,10,3, /// 2,3,11,0, /// 99, /// 30,40,50 /// ``` /// /// The first four integers, `1,9,10,3`, are at positions `0`, `1`, `2`, and `3`. /// Together, they represent the first opcode (`1`, addition), the positions of /// the two inputs (`9` and `10`), and the position of the output (`3`). To handle /// this opcode, you first need to get the values at the input positions: /// position `9` contains `30`, and position `10` contains `40`. *Add* these numbers /// together to get `70`. Then, store this value at the output position; here, /// the output position (`3`) is *at* position `3`, so it overwrites itself. /// Afterward, the program looks like this: /// /// ```text /// 1,9,10,70, /// 2,3,11,0, /// 99, /// 30,40,50 /// ``` /// /// Step forward `4` positions to reach the next opcode, `2`. This opcode works /// just like the previous, but it multiplies instead of adding. The inputs /// are at positions `3` and `11`; these positions contain `70` and `50` /// respectively. Multiplying these produces `3500`; this is stored at position /// `0`: /// /// ```text /// 3500,9,10,70, /// 2,3,11,0, /// 99, /// 30,40,50 /// ``` /// /// Stepping forward `4` more positions arrives at opcode `99`, halting the /// program. /// /// Here are the initial and final states of a few more small programs: /// /// - `1,0,0,0,99` becomes `2,0,0,0,99` (`1 + 1 = 2`). /// - `2,3,0,3,99` becomes `2,3,0,6,99` (`3 * 2 = 6`). /// - `2,4,4,5,99,0` becomes `2,4,4,5,99,9801` (`99 * 99 = 9801`). /// - `1,1,1,4,99,5,6,0,99` becomes `30,1,1,4,2,5,6,0,99`. /// /// Once you have a working computer, the first step is to restore the /// gravity assist program (your puzzle input) to the "1202 program alarm" /// state it had just before the last computer caught fire. To do this, /// *before running the program*, replace position `1` with the value `12` and /// replace position `2` with the value `2`. *What value is left at position `0`* /// after the program halts? /// /// ### Examples /// /// ``` /// use codetrotter_aoc_2019_solutions::day_02::{input_generator, run_intcode_program}; /// assert_eq!(run_intcode_program(&mut input_generator("1,0,0,0,99")), &[2,0,0,0,99]); /// ``` /// /// ``` /// # use codetrotter_aoc_2019_solutions::day_02::{input_generator, run_intcode_program}; /// assert_eq!(run_intcode_program(&mut input_generator("2,3,0,3,99")), &[2,3,0,6,99]); /// ``` /// /// ``` /// # use codetrotter_aoc_2019_solutions::day_02::{input_generator, run_intcode_program}; /// assert_eq!(run_intcode_program(&mut input_generator("2,4,4,5,99,0")), &[2,4,4,5,99,9801]); /// ``` /// /// ``` /// # use codetrotter_aoc_2019_solutions::day_02::{input_generator, run_intcode_program}; /// assert_eq!(run_intcode_program(&mut input_generator("1,1,1,4,99,5,6,0,99")), &[30,1,1,4,2,5,6,0,99]); /// ``` /// /// ### Solution /// /// ⚠️ SPOILER ALERT ⚠️ /// /// ``` /// use codetrotter_aoc_2019_solutions::day_02::{INPUT, input_generator, solve_part_1}; /// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 3760627); /// ``` pub fn solve_part_1 (input_program: &Vec<Intcode>) -> Intcode { let mut program = input_program.clone(); program[1] = 12; program[2] = 2; run_intcode_program(&mut program)[0] } pub type Intcode = usize; pub fn input_generator (input: &str) -> Vec<Intcode> { input.trim_end_matches('\n').split(',').map(|intcode_str| intcode_str.parse::<Intcode>().unwrap()).collect() } pub fn run_intcode_program (program: &mut Vec<Intcode>) -> &Vec<Intcode> { let mut pc = 0; loop { let opcode = program[pc]; if opcode == 1 || opcode == 2 { let target_pos = program[pc + 3]; program[target_pos] = if opcode == 1 { program[program[pc + 1]] + program[program[pc + 2]] } else { program[program[pc + 1]] * program[program[pc + 2]] }; } else if opcode == 99 { break; } else { panic!("Invalid opcode {} at position {}", opcode, pc); } pc += 4; } program } /// ### Day 2, Part Two /// /// [https://adventofcode.com/2019/day/2#part2](https://adventofcode.com/2019/day/2#part2) /// /// "Good, the new computer seems to be working correctly! *Keep it nearby* /// during this mission - you'll probably use it again. Real Intcode /// computers support many more features than your new one, but we'll let you /// know what they are as you need them." /// /// "However, your current priority should be to complete your gravity assist /// around the Moon. For this mission to succeed, we should settle on some /// terminology for the parts you've already built." /// /// Intcode programs are given as a list of integers; these values are used /// as the initial state for the computer's *memory*. When you run an Intcode /// program, make sure to start by initializing memory to the program's /// values. A position in memory is called an *address* (for example, the first /// value in memory is at "address 0"). /// /// Opcodes (like `1`, `2`, or `99`) mark the beginning of an *instruction*. The /// values used immediately after an opcode, if any, are called the /// instruction's *parameters*. For example, in the instruction `1,2,3,4`, `1` is /// the opcode; `2`, `3`, and `4` are the parameters. The instruction `99` contains /// only an opcode and has no parameters. /// /// The address of the current instruction is called the *instruction pointer*; /// it starts at `0`. After an instruction finishes, the instruction pointer /// increases by *the number of values in the instruction*; until you add more /// instructions to the computer, this is always `4` (`1` opcode + `3` parameters) /// for the add and multiply instructions. (The halt instruction would /// increase the instruction pointer by `1`, but it halts the program instead.) /// /// "With terminology out of the way, we're ready to proceed. To complete the /// gravity assist, you need to *determine what pair of inputs produces the /// output `19690720`*." /// /// The inputs should still be provided to the program by replacing the /// values at addresses `1` and `2`, just like before. In this program, the value /// placed in address `1` is called the *noun*, and the value placed in address `2` /// is called the *verb*. Each of the two input values will be between `0` and `99`, /// inclusive. /// /// Once the program has halted, its output is available at address `0`, also /// just like before. Each time you try a pair of inputs, make sure you first /// *reset the computer's memory to the values in the program* (your puzzle /// input) - in other words, don't reuse memory from a previous attempt. /// /// Find the input *noun* and *verb* that cause the program to produce the output /// `19690720`. *What is `100 * noun + verb`?* (For example, if `noun=12` and `verb=2`, /// the answer would be `1202`.) /// /// ### Solution /// /// ⚠️ SPOILER ALERT ⚠️ /// /// ``` /// use codetrotter_aoc_2019_solutions::day_02::{INPUT, input_generator, solve_part_2}; /// assert_eq!(solve_part_2(&mut input_generator(INPUT)), 7195); /// ``` pub fn solve_part_2 (input_program: &Vec<Intcode>) -> u16 { let mut noun = 0; let mut verb = 0; 'outer: while noun <= 99 { verb = 0; while verb <= 99 { let mut program = input_program.clone(); program[1] = noun; program[2] = verb; let program_output = run_intcode_program(&mut program)[0]; if program_output == 19690720 { break 'outer; } verb += 1; } noun += 1; } (100 * noun + verb) as u16 }