Advent of Code 2019 Solution Megathread - Day 2: 1202 Program Alarm

Day 2 is in the books! And surprisingly, we're into pseudo-interpreter territory already!

Day 2 - The Problem

We need to slingshot ourselves around the moon, but the computer that calculates our trajectory has sadly exploded. Given our current data and the specs for that machine, we need to build ourselves a new IntCode interpreter.

It's surprising to me to see a psuedo-assembly converter so early in the Advent of Code, but this one turned out to be vaguely straightforward. Most of my personal problems stemmed from input validation. (If you're a newbie, let me assure you that input validation is almost always something that will slow you down. This goes triply for anyone learning a new language!)

Part 2 luckily doesn't require a whole lot of extra logic, but it has a bit of "optimization" and "compartmentalization" to keep tabs on.

Ongoing Meta

Dev.to List of Leaderboards

• 120635-5c140b9a - provided by Linda Thompson

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Comments

[Jon Bristow]

My kotlin solution:

object Day02 {

    private const val FILENAME = "src/main/resources/day02.txt"

    fun handleOpcode(offset: Int, intList: Either<Array<Int>, Array<Int>>): Either<Array<Int>, Array<Int>> =
        intList.flatMap {
            val opcodeChunk = it.drop(offset).take(4)

            when (opcodeChunk[0]) {
                1 -> {
                    it[opcodeChunk[3]] = it[opcodeChunk[1]] + it[opcodeChunk[2]]
                    it.right()
                }
                2 -> {
                    it[opcodeChunk[3]] = it[opcodeChunk[1]] * it[opcodeChunk[2]]
                    it.right()
                }
                99 -> it.left()
                else -> throw Error("Unknown opcode: ${opcodeChunk[0]}")
            }
        }


    fun part1() = Files.readString(Paths.get(FILENAME))
        .trim()
        .prepInput().let {
            it[1] = 12
            it[2] = 2
            it
        }.operate()[0]
        .toString()

    fun part2(): String {
        val input = Files.readString(Paths.get(FILENAME))
            .trim().prepInput()

        return (0..99).fold(Unit.right() as Either<Pair<Int, Int>, Unit>) { foundSoFar, noun ->
            foundSoFar.flatMap {
                val found = (0..99).find { verb ->
                    val inputCopy = input.copyOf()
                    inputCopy[1] = noun
                    inputCopy[2] = verb
                    inputCopy.operate()[0] == 19690720
                }
                if (found == null) {
                    foundSoFar
                } else {
                    (noun to found).left()
                }
            }
        }.fold({ (noun, verb) ->
            "%02d%02d".format(noun, verb)
        }, { throw Error("No match found.") })
    }
}

fun String.prepInput() = split(",").map { it.toInt() }.toTypedArray()

fun Array<Int>.operate() =
    this.let {
        (0..this.size / 4).map { it * 4 }
            .fold(this.right() as Either<Array<Int>, Array<Int>>) { intArr, offset ->
                handleOpcode(offset, intArr)
            }.fold({ it }, { it })
    }

fun main() {
    println("Part 1: ${Day02.part1()}")
    println("Part 2: ${Day02.part2()}")
}

[Ali Spittel]

I struggled with reading comprehension tonight 🤦🏼‍♀️

def calculate(num1, num2, nums):
    nums[1] = num1
    nums[2] = num2
    idx = 0
    while nums[idx] != 99:
        num = nums[idx]
        val1 = nums[nums[idx + 1]]
        val2 = nums[nums[idx + 2]]
        idx3 = nums[idx + 3]
        if num == 1:
            nums[idx3] = val1 + val2
        elif num == 2:
            nums[idx3] = val1 * val2
        idx += 4
    return nums[0]


with open("input.txt") as _file:
    for line in _file:
        input_values = [int(num) for num in line.split(",")]
        # part 1
        print(calculate(12, 2, input_values[:]))

        # part 2
        GOAL = 19690720
        for i in range(100):
            for j in range(100):
                if calculate(i, j, input_values[:]) == GOAL:
                    print(100 * i + j) 
                    break

[Jon Bristow]

Me too! I spent a good couple minutes trying to figure out why the sum of their test opcode didn't match the answer... 😭

[Shaurya]

Yeah, the second part's wording was really confusing to me.

[Stráhl István]

Thank you! It really helps me to understand the second part.

[Christopher Kruse]

Back again with more Clojure.

My favorite part of this is how the actions get selected. the get-action function actually returns the function used for handling the inputs (where 99 returns a function that, regardless of input, returns "stop"). Then, that function is used with the apply function inside calculate to actually pass the arguments to that function.

I'm sure there should be a better way of handling the brute force handling of part 2, but for now, it's just a poor man's nested for loop implemented using atoms.

(ns aoc2019.day2
  (:require [clojure.string :as st]))

(defn get-action
  "Selects an action from the available opcodes"
  [action]
  (condp = action
    1 +
    2 *
    99 (constantly "stop")))

(defn parse-input
  "Converts input into atom holding instruction integers."
  [input]
  (map #(Integer/parseInt %) (st/split (st/trim-newline input) #",")))

(defn initial-adjustments
  [instructions noun verb]
  (-> instructions
      (assoc 1 noun)
      (assoc 2 verb)))

(defn calculate
  "Read opcodes, insert required values, and read position 0 when complete."
  [input noun verb]
  (loop [instructions (initial-adjustments (vec (parse-input input)) noun verb)
         cursor 0]
    (let [[action pos1 pos2 result-pos] (take 4 (drop cursor instructions))
          result (apply (get-action action) [(get instructions pos1) (get instructions pos2)])]
      (if (= result "stop")
        (first instructions)
        (recur (assoc instructions result-pos result) (+ 4 cursor))))))

(defn p2019-02-part1
  [input]
  (calculate input 12 2))

(defn p2019-02-part2
  "Using the calculator from part 1, determine the proper inputs for our expected value."
  [input]
  (let [expected-result 19690720
        noun (atom 0)
        verb (atom 0)]
    (while (not= expected-result (calculate input @noun @verb))
      (swap! verb inc)
      (if (= @verb 100)
        (do
          (swap! noun inc)
          (reset! verb 0))))
    (+ @verb (* 100 @noun))))

(defn run
  "Runs the Day 2 solutions."
  []
  (let [input (slurp "inputs/2019-02-input")]
    (println (str "Part 1: " (p2019-02-part1 input)))
    (println (str "Part 2: " (p2019-02-part2 input)))))

[Linda Thompson]

JavaScript checking in! I think it'll be interesting, seeing how we re-use this in future challenges. It did take me reading the end of part 2 a number of times before I understood what I was looking for! :)

I also feel like there should be a better way to process the second part...I saw folks on the subreddit talking about just changing the noun value until it's as high as can be while still below the desired output, then changing the verb, but it seems maybe there's unforeseen issues with that? I don't know, everyone I've seen so far is just nesting for loops so I'm not that worried about it. :)

// copy of initial input, so we can reset properly
let inputCopy = [...input];

// noun - input for address 1; verb - input for address 2
let noun = 12;
let verb = 2;

// for part 2 - desired output to match - output is final value at address 0 when program is done
const desiredOutput = 19690720;
// opcode 1 - get values at position 1&2 right after code, add together, store in position 3
// opcode 2 - get values at position 1&2 right after code, multiply, store in position 3
// opcode 99 - stop program
function intCode (op, a, b, c) {
  let valA = inputCopy[a];
  let valB = inputCopy[b];

  if (op === 1) {
    inputCopy[c] = valA + valB;
  } else if (op === 2) {
    inputCopy[c] = valA * valB;
  }
}

// run through memory input, following instructions until 99 is hit
function runProgram() {
  for (let i = 0; i < inputCopy.length; i += 4) {
    if (inputCopy[i] === 99) {
      break;
    }
    intCode(inputCopy[i], inputCopy[i+1], inputCopy[i+2], inputCopy[i+3]);
  }
}

// for part 1 - insert noun & verb provided
inputCopy[1] = noun;
inputCopy[2] = verb;

runProgram();
console.log(`Part 1: position 0 value is ${inputCopy[0]}`);

// part 2 - test different values for noun & verb, insert into memory, run program - when desired output is matched, log noun & verb used & end cycle

for (let n = 0; n < 100; n++) {
  noun = n;
  let found = false;
  for (let v = 0; v < 100; v++) {
    verb = v;

    // reset copy to initial input, then replace noun & verb
    inputCopy = [...input];
    inputCopy[1] = noun;
    inputCopy[2] = verb;

    runProgram();
    let currentOutput = inputCopy[0];

    if (currentOutput === desiredOutput) {
      found = true;
      break;
    }
  }
  if (found) {
    break;
  }
}

console.log(`desired noun and verb are ${noun} & ${verb}; output value is ${inputCopy[0]}`);
console.log(`Part 2 - computed value is ${100 * noun + verb}`);

[Linda Thompson]

Also super stoked that the poem I wrote for day 1 was picked as the first winner! So my comment on the megathread has a little silver medal next to it. :) For not having written any sort of fun fiction in years, I'm really excited they liked it enough to reward it!

They sent me a fun little image when they commented on it, too -

[Jon Bristow]

Congratulations! I love the secondary artifacts and self-imposed additional challenges that people do for this. People seem to get more creative every year!

[Jakub Charvat]

Here's my Python solution - nothing special or well optimised, but it works:

def puzzle_one():
    with open('inputs/day_2.txt') as file: 
        input = list(map(lambda a: int(a), file.read().split(',')))

    opcode, index = int(input[0]), 0
    while opcode != 99:
        if opcode == 1:
            sum = input[input[index + 1]] + input[input[index + 2]]
            input[input[index + 3]] = sum
        elif opcode == 2:
            product = input[input[index + 1]] * input[input[index + 2]]
            input[input[index + 3]] = product
        elif opcode != 99:
            print('Something went wrong')

        index += 4
        opcode = input[index]

    print(f'Puzzle 1 - {input[0]}')

def puzzle_two():

    goal = 19690720

    with open('inputs/day_2.txt') as file:
        input = list(map(lambda a: int(a), file.read().split(',')))

    found = False
    for noun in range(100):
        for verb in range(100):
            memory = input[:]
            memory[1] = noun
            memory[2] = verb

            opcode, index = int(input[0]), 0
            while opcode != 99:
                if opcode == 1:
                    sum = memory[memory[index + 1]] + memory[memory[index + 2]]
                    memory[memory[index + 3]] = sum
                elif opcode == 2:
                    product = memory[memory[index + 1]] * memory[memory[index + 2]]
                    memory[memory[index + 3]] = product
                elif opcode != 99:
                    print('Something went wrong')

                index += 4
                opcode = memory[index]

            output = memory[0]

            if output == goal:
                final_noun = noun
                final_verb = verb
                found = True
                break
        if found == True:
            break
    print(f'Puzzle 2 - {100 * final_noun + final_verb}')

puzzle_one()
puzzle_two()

[Neil Gall]

In past Advent of Codes I've belligerently tried to write these machine simulators in Haskell or pure functional Kotlin or something else completely inappropriate. Maybe it's a sign of maturity that this year I've done it in C.

It's been a while since I've written C. The purity and simplicity is refreshing.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef unsigned int opcode;

struct program {
    size_t size;
    opcode base[];
};

size_t program_size(size_t n) {
    return sizeof(size_t) + sizeof(opcode) * n;
}

struct program *load_program(char *filename) {
    size_t size = 100;
    struct program *program = (struct program *)malloc(program_size(size));
    size_t pos = 0;
    opcode cur = 0;
    FILE *f = fopen(filename, "rt");
    for (;;) {
        int c = fgetc(f);
        if (c == EOF || c == ',') {
            if (pos == size) {
                size *= 2;
                program = (struct program *)realloc(program, program_size(size));
            }
            program->base[pos++] = cur;
            cur = 0;
        } else if ('0' <= c && c <= '9') {
            cur = (cur * 10) + (c - '0');
        }
        if (c == EOF) break;
    }
    fclose(f);
    program->size = pos;
    return program;
}

struct program *copy_program(struct program *program) {
    size_t size = program_size(program->size);
    struct program *copy = (struct program *)malloc(size);
    memcpy(copy, program, size);
    return copy;
}

int read_program(struct program *program, size_t pos, opcode *x) {
    if (pos >= program->size) {
        return 1;
    }
    *x = program->base[pos];
    return 0;
}

int write_program(struct program *program, size_t pos, opcode value) {
    if (pos >= program->size) {
        return 1;
    }
    program->base[pos] = value;
    return 0;
}

void print_program(struct program *program) {
    printf("%u", program->base[0]);
    for (int i = 1; i < program->size; ++i) {
        printf(",%u", program->base[i]);
    }
    printf("\n");
}

int run_program(struct program *program, int debug) {
    size_t pc = 0;
    opcode i;
    while (read_program(program, pc, &i) == 0 && i != 99) {
        opcode x, y, z;
        if (read_program(program, pc+1, &x) != 0) return 1;
        if (read_program(program, x,    &x) != 0) return 1;
        if (read_program(program, pc+2, &y) != 0) return 1;
        if (read_program(program, y,    &y) != 0) return 1;
        if (read_program(program, pc+3, &z) != 0) return 1;
        if (debug) printf("pc=%u i=%u x=%u y=%u z=%u\n", pc, i, x, y, z);
        switch (i) {
            case 1: 
                if (write_program(program, z, x + y) != 0) return 1;
                break;
            case 2:
                if (write_program(program, z, x * y) != 0) return 1;
                break;
            default:
                return 1;
        }
        if (debug) print_program(program);
        pc += 4;
    }
    return 0;
}

void modify_program(struct program *program) {
    program->base[1] = 12;
    program->base[2] = 2;
}

void part1(struct program *original) {
    printf("Part 1\n");
    struct program *program = copy_program(original);
    modify_program(program);
    run_program(program, 0);
    print_program(program);
    free(program);  
}

void part2(struct program *original) {
    opcode noun = 0;
    opcode verb = 0;
    int result = 0;
    while (noun < 100 && verb < 100) {
        struct program *program = copy_program(original);
        write_program(program, 1, noun);
        write_program(program, 2, verb);
        int result = run_program(program, 0) == 0 && program->base[0] == 19690720;
        free(program);

        if (result) {
            break;
        }

        if (++noun > 99) {
            noun = 0;
            ++verb;
        }
    }
    printf("Part 2\nnoun = %u\nverb = %u\nresult = %u\n", noun, verb, 100*noun+verb);
}

static struct program test_program = {
    .size = 12,
    .base = { 1,9,10,3,2,3,11,0,99,30,40,50 }
};

int main(int argc, char **argv) {
    struct program *program = (argc < 2) ? load_program("input.txt") : &test_program;
    part1(program);
    part2(program);

    if (program != &test_program) {
        free(program);
    }
    return 0;
}

[Jon Bristow]

Funny, I think they're harder to write initially in a functional language, but easier to modify and extend in later questions.

[Neil Gall]

Extending to part 2 was easy enough. But the description today made it clear more is coming so I can't wait to find out!

[Rizwan]

It took more time than I expected but finally done with it. I actually started Day 1 today as well.

Here is my solution in swift. Incase anyone would like followup code can be found here in Github

/// --- Day 2: 1202 Program Alarm ---
func computeIntCode(_ input: [Int]) -> Int {
    var numbers = input

    func add(_ aPosition: Int, _ bPosistion: Int) -> Int {
        return numbers[aPosition] + numbers[bPosistion]
    }

    func multiply(_ aPosition: Int, _ bPosistion: Int) -> Int {
        return numbers[aPosition] * numbers[bPosistion]
    }

    func compute(integers:[Int]) {
        let opcode = integers[0]
           switch opcode {
           case 1:
               let result = add(integers[1], integers[2])
               numbers[integers[3]] = result
               //print(numbers)
               break
           case 2:
               let result = multiply(integers[1], integers[2])
               numbers[integers[3]] = result
               //print(numbers)
               break
           case 99:
               break
           default:
               break
           }
    }

    var index = 0
    while true {
        let number = numbers[index]
        if number == 1 || number == 2 {
            compute(integers: Array(numbers[index...index+4]))
            index = index + 4
        }
        else if number == 99 {
            break
        }
    }
    //print(numbers)
    return numbers[0]
}

func computeIntCode(_ input:[Int], _ noun: Int, _ verb: Int) -> Int {
    var input = input
    input[1] = noun
    input[2] = verb
    return computeIntCode(input)
}

let input = """
    1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,1,10,19,2,9,19,23,1,9,23,27,2,27,9,31,1,31,5,35,2,35,9,39,1,39,10,43,2,43,13,47,1,47,6,51,2,51,10,55,1,9,55,59,2,6,59,63,1,63,6,67,1,67,10,71,1,71,10,75,2,9,75,79,1,5,79,83,2,9,83,87,1,87,9,91,2,91,13,95,1,95,9,99,1,99,6,103,2,103,6,107,1,107,5,111,1,13,111,115,2,115,6,119,1,119,5,123,1,2,123,127,1,6,127,0,99,2,14,0,0
    """
let numbers = input.components(separatedBy: ",").compactMap{Int($0)}

func partOne() {
    dump(computeIntCode(numbers,12,2))
}

func partTwo() {
    for i in 0..<99 {
        for j in 0..<99 {
            if computeIntCode(numbers,i,j) == 19690720 {
                print("noun: \(i) \n verb: \(j)")
                dump(100 * i + j)
                return
            }
        }
    }
}

partOne()
partTwo()

[Shaurya]

My solution in Rust

fn part_a(mut input: Vec<u32>) -> u32 {
    input[1] = 12;
    input[2] = 2;

    let mut i: usize = 0;
    while i < input.len() {
        if i % 4 == 0 {
            let opcode = input[i];
            if opcode == 99 {
                break;
            }
            let index_1 = input[i + 1] as usize;
            let index_2 = input[i + 2] as usize;
            let index_3 = input[i + 3] as usize;

            if opcode == 1 {
                input[index_3] = input[index_1] + input[index_2];
            } else if opcode == 2 {
                input[index_3] = input[index_1] * input[index_2];
            }
        }
        i = i + 1;
    }

    input[0]
}

fn part_b(input: Vec<u32>) -> u32 {
    let mut i = 0;
    let mut j = 0;
    while i < 100 {
        let mut input = input.clone();

        if exec_intcode_program(input, i, j) == 19690720 {
            return 100 * i + j;
            break;
        }

        if j == 99 {
            i = i + 1;
            j = 0;
        }
        j = j + 1;
    }

    0
}
fn exec_intcode_program(input: Vec<u32>, addl_inp_1: u32, addl_inp_2: u32) -> u32 {
    let mut input = input.clone();

    input[1] = addl_inp_1;
    input[2] = addl_inp_2;

    let mut i: usize = 0;
    while i < input.len() {
        if i % 4 == 0 {
            let opcode = input[i];
            if opcode == 99 {
                break;
            }
            let index_1 = input[i + 1] as usize;
            let index_2 = input[i + 2] as usize;
            let index_3 = input[i + 3] as usize;

            if opcode == 1 {
                input[index_3] = input[index_1] + input[index_2];
            } else if opcode == 2 {
                input[index_3] = input[index_1] * input[index_2];
            }
        }
        i = i + 1;
    }

    input[0]
}

[Supriya Srivatsa]

Some Kotlin code :)

fun main() {
    val input = readDayInputAsString(2).split(",").map { it.toInt() }
    val noun = 12
    val verb = 2

    println(solvePart1(input, noun, verb))  //5434663
    println(solvePart2(input, noun, verb))  //4559
}

private fun solvePart1(programInput: List<Int>, noun: Int, verb: Int) : Int {
    val input = programInput.toMutableList()
    input[1] = noun
    input[2] = verb
    for(i in input.indices step 4) {
        when(input[i]) {
            99 -> return input[0]
            1 -> input[input[i+3]] = input[input[i+1]] + input[input[i+2]]
            2 -> input[input[i+3]] = input[input[i+1]] * input[input[i+2]]
        }
    }
    return input[0]
}

private fun solvePart2(programInput: List<Int>, noun: Int, verb: Int) : Int {
    for(i in 0..99) {
        for(j in 0..99) {
            if(solvePart1(programInput, i, j) == 19690720)
                return 100 * i + j
        }
    }
    return 100 * noun + verb
}

On github: github.com/sup95/AdventOfCode-19/b...