Jon Bristow

Posted on Dec 9, 2019

Advent of Code 2019 Solution Megathread - Day 9: Sensor Boost

#adventofcode #challenge #adventofcode2019 #spoilers

Oh no, IntCodes! (I'm starting to see a pattern here...)

Day 9 - The Problem

After an easy decryption of an image file, we're back in our module and speeding through the solar system. Unfortunately, we seem to have picked up a distress beacon! What is it saying? We must update our IntCode interpreter to find out!

Part 1 seems simple enough: Add big number support and a new relative parameter addressing system.

And after whacking our heads against the wall on why relative mode wasn't working the way we thought it should for too long, Part 2 is "merely" the same as part 1, but potentially very slow. If you weren't careful, your solution might be running for a long time.

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?

Languages Seen On Day 08

javascript x 4
kotlin x 2
python x 2
PHP
clojure
perl
swift

Completion Stats

By applying a best-fit descending power trend-line to the 1 and 2 star columns on the stats page, my estimates predict:

1 star on day. 25: 6358 people

2 stars on day 25: 420 people. _Nice

If you're still going, take heart in that you are in a rapidly dwindling pool of people.

Doing other questionable statistics gives me: 415/6248

Top comments (23)

Massimo Artizzu • Dec 9 '19 • Edited

So, we're going to work with Intcodes every other day? 😩

The worst part is that, since we're reserving two digit for the opcodes, I expect we're going to work with them again in the future (even though it says "You now have a complete Intcode computer.")

Moreover, the problem forgot to mention that when we write back to the memory, it could be done in relative mode too and not just position mode. Thanks 🤦‍♂️

But anyway... JavaScript with generators blah blah. I lost quite some time trying to understand why my solution didn't work... Until I realized I was passing the input values incorrectly 😵 I have none but myself to blame there...

Only new thing: the use of JavaScript's BigInt. Hooray for ES2020!

Solution for both parts:

const parameterCount = { 1: 3, 2: 3, 3: 1, 4: 1, 5: 2, 6: 2, 7: 3, 8: 3, 9: 1, 99: 0 };
const codes = input.split(',').map(BigInt);

function* createProgramInstance(localCodes, ...stack) {
  let instructionPointer = 0;
  let relativeBase = 0;
  function* getInstructions() {
    while (instructionPointer < localCodes.length) {
      const instruction = Number(localCodes[instructionPointer]);
      const opcode = instruction % 100;
      const modes = Array.from({ length: 3 }, (_, index) => Math.floor(instruction / 10 ** (index + 2) % 10));
      const paramCount = parameterCount[opcode];
      const params = localCodes.slice(instructionPointer + 1, instructionPointer + paramCount + 1);
      instructionPointer += paramCount + 1;
      yield { opcode, modes, params };
    }
  }

  function execute({ opcode, modes, params }) {
    function getAddress(index) {
      return (modes[index] === 2 ? relativeBase : 0) + Number(params[index]);
    }
    function getValue(index) {
      const value = modes[index] === 1 ? params[index] : localCodes[getAddress(index)];
      return typeof value === 'bigint' ? value : 0n;
    }

    switch (opcode) {
      case 1:
        localCodes[getAddress(2)] = getValue(0) + getValue(1);
        break;
      case 2:
        localCodes[getAddress(2)] = getValue(0) * getValue(1);
        break;
      case 3:
        localCodes[getAddress(0)] = stack.shift();
        break;
      case 4:
        return getValue(0);
      case 5:
        if (getValue(0)) {
          instructionPointer = Number(getValue(1));
        }
        break;
      case 6:
        if (getValue(0) === 0n) {
          instructionPointer = Number(getValue(1));
        }
        break;
      case 7:
        localCodes[getAddress(2)] = BigInt(getValue(0) < getValue(1));
        break;
      case 8:
        localCodes[getAddress(2)] = BigInt(getValue(0) === getValue(1));
        break;
      case 9:
        relativeBase += Number(getValue(0));
        break;
    }
  }

  for (const instruction of getInstructions()) {
    if (instruction.opcode === 99) {
      return;
    }
    const output = execute(instruction);
    if (typeof output === 'bigint') {
      yield output;
    }
  }
}

for (const part of [1n, 2n]) {
  const program = createProgramInstance(codes, part);
  console.log(`# Part ${part}`);
  for (const value of program) {
    console.log(String(value));
  }
}

Running times:

~2.5 ms
~370 ms

Hardware: MacBook Pro mid-2015

As usual, my text and input can be found on my repo.

BTW, I'm dead last in the leaderboards among those who completed all 9 days 😂 Jon, you're ahead of me without today!

Mustafa Haddara • Dec 9 '19

the problem forgot to mention that when we write back to the memory, it could be done in relative mode too and not just position mode.

this burned me, i sat there for 30 minutes trying to figure out what i was doing wrong

Johnny • Dec 9 '19

I believe the two digits are just there because of opcode 99 :)

Massimo Artizzu • Dec 9 '19

And that would make ten opcodes so far, right.

Well, let's hope we won't have to implement more! 😄

After all we already have basic arithmetic, I/O, conditional jumps, comparisons and pointer manipulation... What else do we need for a basic processor?

Jon Bristow • Dec 10 '19 • Edited

We're in uncharted waters! I think this is first year we've had so much refactoring/reuse work to do. (Definitely the earliest)

It's been pretty frustrating going, but getting things to work has been satisfying as heck.

Chad S • Dec 9 '19

Hi, a (very wordy) Python solution using a generator function.

def compute_str(program_str, verbose=False):
    program_str = program_str + ',0' * 1000  # Add additional memory
    program = program_str.split(',')
    program = [int(opcode) for opcode in program]
    return compute(program, verbose=verbose)

# Returns opcode_str; paramter modes; and number to increment instruction_pointer by
def parse_first(int_value):
    map_opcode_to_param_num = {'99': 0, '01': 3, '02': 3, '03': 1, '04': 1, '05': 2, '06': 2, '07': 3, '08': 3, '09': 1}
    max_value_str_len = max(map_opcode_to_param_num.values()) + 2  # Two len opcode

    value_str = str(int_value)
    value_str = value_str.zfill(max_value_str_len)  # Pad with leading zeros

    opcode_str = value_str[-2:]

    parameter_modes = value_str[:-2]

    if opcode_str not in map_opcode_to_param_num.keys():
        print(f'ERROR - invalid opcode: {opcode_str}')

    parameter_mode_map = {'0': 'position', '1': 'immediate', '2': 'relative'}
    parameter_modes = [parameter_mode_map[parameter_mode] for parameter_mode in parameter_modes]
    parameter_modes = [] if opcode_str == '99' else parameter_modes[-map_opcode_to_param_num[opcode_str]:]  # Reduce to correct num of param modes for opcode
    parameter_modes = parameter_modes[::-1]  # Reverse mode order

    instruction_pointer_increment = map_opcode_to_param_num[opcode_str] + 1

    return opcode_str, parameter_modes, instruction_pointer_increment


def compute(program, verbose=False):
    program = list(program)

    instruction_pointer = 0
    relative_base = 0

    while instruction_pointer < len(program):
        int_value = program[instruction_pointer]
        opcode_str, parameter_modes, instruction_pointer_increment = parse_first(int_value)
        if verbose:
            print(f'Processing: {opcode_str}')

        if opcode_str == '99':
            print('Exiting (99 code)...')
            return program

        elif opcode_str == '01':
            # Add
            param_mode_1, param_mode_2, param_mode_3 = parameter_modes

            parameter_1 = program[instruction_pointer + 1]
            if param_mode_1 == 'position':
                operand_1 = program[parameter_1] 
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1] 
            else:
                print(f'ERROR - invalid parameter mode: {parameter_1}')

            parameter_2 = program[instruction_pointer + 2]
            if param_mode_2 == 'position':
                operand_2 = program[parameter_2] 
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2] 
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            parameter_3 = program[instruction_pointer + 3]
            if param_mode_3 == 'position':  # Note: since writing to memory, cannot be immediate
                output_address = parameter_3
            elif param_mode_3 == 'relative':
                output_address = relative_base + parameter_3
            else:
                print('ERROR - immediate mode for writing to memory')

            # Perform op
            result = operand_1 + operand_2
            program[output_address] = result
            instruction_pointer += instruction_pointer_increment


        elif opcode_str == '02':
            # Multiply
            param_mode_1, param_mode_2, param_mode_3 = parameter_modes

            parameter_1 = program[instruction_pointer + 1]
            if param_mode_1 == 'position':
                operand_1 = program[parameter_1] 
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1] 
            else:
                print(f'ERROR - invalid parameter mode: {parameter_1}')

            parameter_2 = program[instruction_pointer + 2]
            if param_mode_2 == 'position':
                operand_2 = program[parameter_2] 
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2] 
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            parameter_3 = program[instruction_pointer + 3]
            if param_mode_3 == 'position':  # Note: since writing to memory, cannot be immediate
                output_address = parameter_3
            elif param_mode_3 == 'relative':
                output_address = relative_base + parameter_3
            else:
                print('ERROR - immediate mode while writing to memory')

            # Perform op
            result = operand_1 * operand_2
            program[output_address] = result
            instruction_pointer += instruction_pointer_increment

        elif opcode_str == '03':   
            # Input
            param_mode_1 = parameter_modes[0]

            parameter_1 = program[instruction_pointer + 1]
            if param_mode_1 == 'position':
                output_address = parameter_1
            elif param_mode_1 == 'relative':
                output_address = relative_base + parameter_1
            else:
                print('ERROR - immediate mode while writing to memory')

            user_input = None
            # Keep looping while user_input is None
            while user_input is None:
                user_input = (yield 'input')
            if verbose:
                print(f'Input Received: {user_input}')

            program[output_address] = user_input
            instruction_pointer += instruction_pointer_increment

        elif opcode_str == '04':
            # Output
            param_mode_1 = parameter_modes[0]
            parameter_1 = program[instruction_pointer + 1]
            read_address = parameter_1

            if param_mode_1 == 'position':
                output = program[read_address]
            elif param_mode_1 == 'immediate':
                output = read_address
            elif param_mode_1 == 'relative':
                output = program[relative_base + read_address]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            if verbose:
                print(f'Output: {output}')
            yield output
            instruction_pointer += instruction_pointer_increment

        elif opcode_str == '05':
            # Jump if True
            param_mode_1, param_mode_2 = parameter_modes
            parameter_1 = program[instruction_pointer + 1]
            parameter_2 = program[instruction_pointer + 2]

            if param_mode_1 == 'position':
                operand_1 = program[parameter_1]
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            if param_mode_2 == 'position':
                operand_2 = program[parameter_2]
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            if operand_1 != 0:
                instruction_pointer = operand_2
            else:
                instruction_pointer += instruction_pointer_increment

        elif opcode_str == '06':
            # Jump if False
            param_mode_1, param_mode_2 = parameter_modes
            parameter_1 = program[instruction_pointer + 1]
            parameter_2 = program[instruction_pointer + 2]

            if param_mode_1 == 'position':
                operand_1 = program[parameter_1]
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            if param_mode_2 == 'position':
                operand_2 = program[parameter_2]
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            if operand_1 == 0:
                instruction_pointer = operand_2
            else:
                instruction_pointer += instruction_pointer_increment

        elif opcode_str == '07':
            # Less than
            param_mode_1, param_mode_2, param_mode_3 = parameter_modes
            parameter_1 = program[instruction_pointer + 1]
            parameter_2 = program[instruction_pointer + 2]

            if param_mode_1 == 'position':
                operand_1 = program[parameter_1]
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            if param_mode_2 == 'position':
                operand_2 = program[parameter_2]
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            parameter_3 = program[instruction_pointer + 3]
            output_address = parameter_3
            if param_mode_3 == 'position':
                program[output_address] = 1 if operand_1 < operand_2 else 0
            elif param_mode_3 == 'relative':
                program[relative_base + output_address] = 1 if operand_1 < operand_2 else 0
            else:
                print('ERROR - immediate mode while writing to memory')

            instruction_pointer += instruction_pointer_increment

        elif opcode_str == '08':
            # Equals
            param_mode_1, param_mode_2, param_mode_3 = parameter_modes
            parameter_1 = program[instruction_pointer + 1]
            parameter_2 = program[instruction_pointer + 2]

            if param_mode_1 == 'position':
                operand_1 = program[parameter_1]
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            if param_mode_2 == 'position':
                operand_2 = program[parameter_2]
            elif param_mode_2 == 'immediate':
                operand_2 = parameter_2
            elif param_mode_2 == 'relative':
                operand_2 = program[relative_base + parameter_2]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_2}')

            parameter_3 = program[instruction_pointer + 3]
            output_address = parameter_3

            if param_mode_3 == 'position':
                program[output_address] = 1 if operand_1 == operand_2 else 0
            elif param_mode_3 == 'relative':
                program[relative_base + output_address] = 1 if operand_1 == operand_2 else 0
            else:
                print('ERROR - immediate mode while writing to memory')

            instruction_pointer += instruction_pointer_increment

        elif opcode_str == '09':
            # Relative base offset instruction
            param_mode_1 = parameter_modes[0]

            parameter_1 = program[instruction_pointer + 1]
            if param_mode_1 == 'position':
                operand_1 = program[parameter_1]
            elif param_mode_1 == 'immediate':
                operand_1 = parameter_1
            elif param_mode_1 == 'relative':
                operand_1 = program[relative_base + parameter_1]
            else:
                print(f'ERROR - invalid parameter mode: {param_mode_1}')

            relative_base = relative_base + operand_1
            instruction_pointer += instruction_pointer_increment

        else:
            print('ERROR - invalid opcode')
            return

    print('End of program without 99 code')
    return

Chad S • Dec 9 '19 • Edited

Getting output is done by running:

run = compute_str(puzzle_input)
next(run)

then...

Part 1

print(run.send(1))

or Part 2:

print(run.send(2))

jyothi9999 • Dec 13 '19

"""
Hi,
now i am learning python
i also wrote a program in very basic
but i did not get the answer
can u give me any hint
"""

import numpy as np

f = open("input9","r") # file opening
code = f.read() + ',0' * 1000 # for reading files with commas(,) as list
nList = code.split(',')
f.close() # file closing

print(nList)

for i in range(0, len(nList)): # converting elements of List(strings) into integers
nList[i] = int(nList[i])

print(len(nList))

def get_digit(number, n):
return number // 10**n % 10

def intcode(nList,in1):
List = nList.copy()
for i,each in enumerate(nList):
List[i] = int(each)
i = 0
rb = 0

while i < len(nList):
    n = List[i]
    op = 10 * get_digit(n, 1) + get_digit(n, 0)
    p1_mode = get_digit(n, 2)
    p2_mode = get_digit(n, 3)
    p3_mode = get_digit(n, 1)

    if op == 1 or op == 2 or op == 7 or op == 8:
        int1 = int2 = position = p1 = p2 = 0
        int1 = List[i + 1]
        int2 = List[i + 2]
        int3 = List[i + 3]

        if p1_mode == 1:
            p1 = int1
        elif p1_mode == 0 and int1 >= 0 :
            p1 = List[int1]
        elif p1_mode == 2 and int1 + rb >= 0:
            p1 = List[int1 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p1_mode}')

        if p2_mode == 1:
            p2 = int2
        elif p2_mode == 0 and int1 >= 0:
            p2 = List[int2]
        elif p2_mode == 2 and int2 + rb >= 0:
            p2 = List[int2 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p2_mode}')

        if p3_mode == 0 and int1 >= 0:           # p3_mode noi in immediate mode (!= 1)
            position = List[int3]
        elif p3_mode == 2 and int3 + rb >= 0:
            position = List[int3 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p3_mode}')

        if op == 1:
            add = p1 + p2
            List[position] = add
        elif op == 2:
            multi = p1 * p2
            List[position] = multi
        elif op == 7:
            if p1 < p2:
                List[position] = 1
            else:
                List[position] = 0
        elif op == 8:
            if p1 == p2:
                List[position] = 1
            else:
                List[position] = 0

        i = i + 4
        continue

    elif op == 3 or op == 4 or op == 9:

        int1 = p1 = 0
        int1 = List[i + 1]

        if p1_mode == 1:
            print('ERROR - immediate mode while writing to memory')
        elif p1_mode == 0 and int1 >= 0:
            print(int1)
            p1 = List[int1]
        elif p1_mode == 2 and int1 + rb >= 0:
            print(int1 + rb)
            p1 = List[int1 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p1_mode}')

        if op == 3:
            if p1_mode == 1:
                List[i+1] = in1
            elif p1_mode == 0 and List[i+1] >= 0:
                List[List[i+1]] = in1
            elif p1_mode == 2 and List[i+1] + rb >= 0:
                List[List[i+1] + rb] = in1
            else:
                print(f'ERROR - invalid parameter mode: {p1_mode}')

        elif op == 4:
            output = p1
            print('output ----------------------------------> ', output)

        elif op == 9:
            rb = rb + p1
            print("rb........................", rb)

        i = i + 2
        continue

    elif op == 5 or op == 6:

        int1 = int2 = p1 = p2 = 0
        int1 = List[i + 1]
        int2 = List[i + 2]

        if p1_mode == 1:
            p1 = int1
        elif p1_mode == 0 and int1 >= 0:
            p1 = List[int1]
        elif p1_mode == 2 and int1 + rb >= 0:
            p1 = List[int1 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p1_mode}')

        if p2_mode == 1:
            p2 = int2
        elif p2_mode == 0 and int1 >= 0:
            p2 = List[int2]
        elif p2_mode == 2 and int2 + rb >= 0:
            p2 = List[int2 + rb]
        else:
            print(f'ERROR - invalid parameter mode: {p2_mode}')

        if (op == 5 and p1 != 0) or (op == 6 and p1 == 0):
            i = p2
            continue
        i = i + 3
        continue

    elif op == 99:
        print("********* PROGRAM HALTED *********")
        break

    else:
        print(f'ERROR - invalid opcode {op}')
        break

return List

boost_program = intcode(nList,1)
print(boost_program)

print(intcode(boost_program,1))[1]

Chad S • Dec 9 '19

I'll be posting my other attempts to: github.com/devChad/advent_of_code

Einar Norðfjörð • Dec 9 '19

JS Solution w/ generators again

I like being able to "plug in" the IO implementation at runtime with the yields, it's almost like algebraic effects in JS

const { createInterface } = require('readline')

const rl = createInterface({
  input: process.stdin,
  output: process.stdout
})

const question = str =>
  new Promise(res => {
    rl.question(str, res)
  })

const INSTRUCTIONS = {
  ADD: 1,
  MULT: 2,
  INPUT: 3,
  OUTPUT: 4,
  JUMP_IF_TRUE: 5,
  JUMP_IF_FALSE: 6,
  LESS_THAN: 7,
  EQUALS: 8,
  ADJUST_RELATIVE_BASE: 9,
  HALT: 99
}

function runProgram(instructions) {
  instructions = instructions.slice()

  return function* amplifier() {
    let lastOutput = null
    let relativeBase = 0
    for (let i = 0; i < instructions.length; ++i) {
      const instruction = instructions[i]
      const parsed = String(instruction)
        .padStart(5, '0')
        .split('')
      const getValue = (value, mode = '0') => {
        if (mode === '0') {
          return instructions[value] || 0
        } else if (mode === '1') {
          return value
        } else if (mode === '2') {
          return instructions[relativeBase + value] || 0
        }
      }
      const setValue = (index, value, mode = '0') => {
        if (mode === '0') {
          instructions[index] = value
        } else if (mode === '2') {
          instructions[relativeBase + index] = value
        }
      }
      const opCode = Number(parsed.slice(3).join(''))
      const modes = parsed.slice(0, 3)
      switch (opCode) {
        case INSTRUCTIONS.ADD: {
          const x = getValue(instructions[++i], modes[2])
          const y = getValue(instructions[++i], modes[1])
          setValue(instructions[++i], x + y, modes[0])
          break
        }
        case INSTRUCTIONS.MULT: {
          const x = getValue(instructions[++i], modes[2])
          const y = getValue(instructions[++i], modes[1])
          setValue(instructions[++i], x * y, modes[0])
          break
        }
        case INSTRUCTIONS.INPUT: {
          setValue(instructions[++i], yield { type: 'INPUT' }, modes[2])
          break
        }
        case INSTRUCTIONS.OUTPUT: {
          lastOutput = getValue(instructions[++i], modes[2])
          yield { type: 'OUTPUT', value: lastOutput }
          break
        }
        case INSTRUCTIONS.JUMP_IF_TRUE: {
          const compare = getValue(instructions[++i], modes[2])
          const jumpTo = getValue(instructions[++i], modes[1]) - 1
          if (compare != 0) {
            i = jumpTo
          }
          break
        }
        case INSTRUCTIONS.JUMP_IF_FALSE: {
          const compare = getValue(instructions[++i], modes[2])
          const jumpTo = getValue(instructions[++i], modes[1]) - 1
          if (compare == 0) {
            i = jumpTo
          }
          break
        }
        case INSTRUCTIONS.LESS_THAN: {
          const x = getValue(instructions[++i], modes[2])
          const y = getValue(instructions[++i], modes[1])
          setValue(instructions[++i], x < y ? 1 : 0, modes[0])
          break
        }
        case INSTRUCTIONS.EQUALS: {
          const x = getValue(instructions[++i], modes[2])
          const y = getValue(instructions[++i], modes[1])
          setValue(instructions[++i], x === y ? 1 : 0, modes[0])
          break
        }
        case INSTRUCTIONS.ADJUST_RELATIVE_BASE: {
          const adjustBy = getValue(instructions[++i], modes[2])
          relativeBase += adjustBy
          break
        }
        case INSTRUCTIONS.HALT:
          return lastOutput
      }
    }
  }
}

const runProgramWithIO = async program => {
  let input = undefined
  while (true) {
    const { value, done } = program.next(input)

    if (done) {
      return value
    }

    if (value.type === 'INPUT') {
      input = Number(await question('input : '))
      continue
    } else if (value.type === 'OUTPUT') {
      console.log('output:', value.value)
    }
  }
}

const input = require('fs')
  .readFileSync(require('path').resolve(__dirname, './input.txt'))
  .toString()

const instructions = input.split(',').map(Number)

runProgramWithIO(runProgram(instructions)())
  .then(final => console.log('final :', final))
  .then(() => process.exit())

Leon Fedotov • Dec 9 '19

Dope! Ive started doing this but it was taking me too long, checkout my solutions at github.com/LeonFedotov/advent-of-code

Ali Spittel • Dec 9 '19

def get_modes(modes):
    return [int(mode) for mode in [modes[2], modes[1], modes[0], modes[3:]]]


class Computer:
    def __init__(self, data):
        self.idx = 0
        self.data = data[:] + [0] * 3000
        self.done = False
        self.output = None
        self.inputs = []
        self.relative_base = 0

    def get_params(self, mode1, mode2, mode3):
        return self.get_param(mode1, 1), self.get_param(mode2, 2), self.get_param(mode3, 3)

    def get_param(self, mode, increment):
        if mode == 0:
            return self.data[self.idx + increment]
        elif mode == 1:
            return self.idx + increment
        else:
            return self.relative_base + self.data[self.idx + increment]

    def add(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.data[param3] = self.data[param1] + self.data[param2]
        self.idx += 4

    def multiply(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.data[param3] = self.data[param1] * self.data[param2]
        self.idx += 4

    def take_input(self, mode1):
        param1 = self.get_param(mode1, 1)
        self.data[param1] = self.inputs.pop(0)
        self.idx += 2

    def create_output(self, mode1):
        param1 = self.get_param(mode1, 1)
        self.output = self.data[param1]
        self.idx += 2
        return self.output

    def less_than(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.data[param3] = 1 if self.data[param1] < self.data[param2] else 0
        self.idx += 4

    def equals(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.data[param3] = 1 if self.data[param1] == self.data[param2] else 0
        self.idx += 4

    def jump_if_true(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.idx = self.data[param2] if self.data[param1] != 0 else self.idx + 3

    def jump_if_false(self, mode1, mode2, mode3):
        param1, param2, param3 = self.get_params(mode1, mode2, mode3)
        self.idx = self.data[param2] if self.data[param1] == 0 else self.idx + 3

    def relative_offset(self, mode1):
        param1 = self.get_param(mode1, 1)
        self.relative_base += self.data[param1]
        self.idx += 2

    def calculate(self, input_val):
        self.inputs.append(input_val)
        modes = {
            1: lambda: self.add(mode1, mode2, mode3),
            2: lambda: self.multiply(mode1, mode2, mode3),
            3: lambda: self.take_input(mode1),
            5: lambda: self.jump_if_true(mode1, mode2, mode3),
            6: lambda: self.jump_if_false(mode1, mode2, mode3),
            7: lambda: self.less_than(mode1, mode2, mode3),
            8: lambda: self.equals(mode1, mode2, mode3),
            9: lambda: self.relative_offset(mode1)
        }
        while True:
            mode1, mode2, mode3, opcode = get_modes(f"{self.data[self.idx]:05}")
            if opcode in modes:
                modes[opcode]()              
            elif opcode == 4:
                return self.create_output(mode1)                
            elif opcode == 99:
                self.done = True
                return self.output


with open("input.txt") as _file:
    for line in _file:
        input_vals = [int(num) for num in line.split(",")]
        computer = Computer(input_vals)
        print(f"Part 1: {computer.calculate(1)}")

        computer = Computer(input_vals)
        print(f"Part 2: {computer.calculate(2)}")

Mustafa Haddara • Dec 9 '19

I've been sending input and read output "manually", but it worked well enough for day 7. Interestingly, I learned something about ruby today: arrays are essentially unbounded! so i didn't have worry about the memory issue, I could just read/write to where in the array I wanted and if the array was too short, I'd just read out a nil instead of getting some form of IndexOutOfBoundsError or something.

I made this comment somewhere else in the thread, but the fact that opcode 09 could also work in relative mode, (and that we could write to addresses in relative mode as well) threw me off, I spent way too long trying to track that bug down.

class IntCode
    def initialize(instructions)
        @instructions = instructions
        @ptr = 0
        @in_buff = []
        @out_buff = []
        @rel_base = 0
        @blocked = false
    end

    def send_input(thing)
        @in_buff.push(thing)
    end

    def read_output()
        return @out_buff.shift()
    end

    def inspect()
        puts @instructions.to_s
        puts @out_buff.to_s
    end

    def isBlocked()
        return @blocked
    end

    def read_mem(idx)
        if idx < 0
            puts "wat: negative index"
        end
        val = @instructions[idx]
        if val == nil
            @instructions[idx] = 0
            return 0
        else
            return val
        end
    end

    def write_mem(idx)
    end

    def run()
        @blocked = false
        while @ptr < @instructions.length do
            # puts @ptr, @instructions.to_s
            base_op = read_mem(@ptr)
            # puts base_op
            op = base_op % 100  # get last 2 digits
            flags = base_op / 100 # top n digits
            arg1 = read_value(@instructions, @ptr+1, flags%10)
            if op == 1
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                flags = flags / 10
                arg3 = read_value(@instructions, @ptr+3, flags%10)
                r = read_mem(arg1) + read_mem(arg2)
                @instructions[arg3] = r
                @ptr += 4
            elsif op == 2
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                flags = flags / 10
                arg3 = read_value(@instructions, @ptr+3, flags%10)
                r = read_mem(arg1) * read_mem(arg2)
                @instructions[arg3] = r
                @ptr += 4
            elsif op == 3
                if @in_buff.empty?
                    # puts "waiting for input"
                    @blocked = true
                    return false
                end
                input = @in_buff.shift()
                # puts "got input #{input}, putting in location #{arg1}"
                @instructions[arg1] = input.to_i
                @ptr += 2
            elsif op == 4
                output = read_mem(arg1)
                @out_buff.push(output)
                # puts "output: #{output}"
                @ptr += 2
            elsif op == 5
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                if read_mem(arg1) != 0
                    @ptr = read_mem(arg2)
                else
                    @ptr += 3
                end
            elsif op == 6
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                if read_mem(arg1) == 0
                    @ptr = read_mem(arg2)
                else
                    @ptr += 3
                end
            elsif op == 7
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                flags = flags / 10
                arg3 = read_value(@instructions, @ptr+3, flags%10)
                if read_mem(arg1) < read_mem(arg2)
                    @instructions[arg3] = 1
                else
                    @instructions[arg3] = 0
                end
                @ptr += 4
            elsif op == 8
                flags = flags / 10
                arg2 = read_value(@instructions, @ptr+2, flags%10)
                flags = flags / 10
                arg3 = read_value(@instructions, @ptr+3, flags%10)
                if read_mem(arg1) == read_mem(arg2)
                    @instructions[arg3] = 1
                else
                    @instructions[arg3] = 0
                end
                @ptr += 4
            elsif op == 9
                @rel_base += read_mem(arg1)
                # puts "updated relative base to #{@rel_base}"
                @ptr += 2
            elsif op == 99
                # puts "halting!"
                break
            else
                puts "wat"
                return @instructions
            end
        end
        return @instructions
    end

    def read_value(instructions, arg, flag)
        if flag == 1
            return arg
        elsif flag == 2
            v = read_mem(arg) + @rel_base
            return v
        else
            return read_mem(arg)
        end
    end
end


if __FILE__ == $0
    instructions = []
    File.open(ARGV[0], "r") do |file_handle|
        file_handle.each_line do |line|
            instructions = line.split(",").map { |n| n.to_i } 
            break
        end
    end

    vm = IntCode.new(instructions)
    vm.send_input(2)
    vm.run()
    puts vm.read_output()
end

Neil Gall • Dec 9 '19 • Edited

Well that was tough! The new requirements revealed a few deficiencies with my IntCode emulator. My addressing modes were a mess for writes, but somehow made it this far anyway. The need to expand the memory on demand meant a substantial refactor. I also had to use a nonstandard (but widely supported) __int128 data type to support the big numbers required.

Printing large numbers is also lacking support in the C standard library. I had to cut a couple of corners...

char *print_opcode(opcode n) {
    static char str[50];
    if (n == 0)
        return "0";
    else {
        char *s = str + sizeof(str)-1;
        int negative = 0;
        opcode x = n;
        if (x < 0) {
            negative = 1;
            x = -x; // eek, minimum negative value edge case
        }
        for (*--s = '\0'; x != 0 && s != str; x /= 10) {
            *--s = '0' + (x % 10);
        }
        if (negative) 
            *--s = '-';
        return s; // eek, not thread safe
    }
}

As part of my debugging I had it trace the execution using made-up assembly language:

Part 1
0000             1102  mul 34463338,34463338
0004             1007   lt 1187721666102244,34463338
0008             1005  jnz 0,53
0011             1101  add 0,3
0015              109 base 988
0017              209 base 3
0019                9 base 3
0021              209 base 3
0023              209 base 3
0025              203   in 1
0027             1008   eq 1,1
0031             1005  jnz 1,65
0065             1102  mul 32,1
0069             1101  add 0,500
0073             1101  add 0,636
0077             1102  mul 36,1
0081             1101  add 0,29
0085             1102  mul 864,1
0089             1102  mul 21,1

One advantage of using C is speed though. We were warned it might take time to run but the tests and both parts of my implementation run in 84 milliseconds!

Full code here. I've enjoyed my return to C programming but I'm quietly hoping for something using a high-level language tomorrow!

Johnny • Dec 9 '19

Today's addition was simple enough. For safe access to "not yet allocated" memory, I created 2 new helper functions:

; Reads a value from memory
(defn read-mem [process-state address]
  (let [mem (:memory process-state)]
    (if (>= address (count mem)) 0 (mem address))))

; Writes a value to memory and returns the new process state
(defn write-mem [process-state address value]
  (let [mem (:memory process-state)]
    (if (>= address (count mem))
      (assoc process-state :memory (conj (into mem (repeat (- address (count mem)) 0)) value))
      (assoc-in process-state [:memory address] value))))

And after changing the instruction type from int to long (which is the default number type in clojure anyway), I could just add the new stuff to my existing framework:

; new parameter mode function
(fn [process-state address]
  (+ (read-mem process-state address) (:rel-base process-state)))

; new opcode
(def rel-base-offset-opcode
  {:operator (fn [process-state offset-pointer]
               (-> process-state
                   (update :rel-base + (read-mem process-state offset-pointer))
                   (update :pointer + 2)))
   :params   1})

As always, here's the whole code: github.com/jkoenig134/AdventOfCode...

Ryan Palo • Dec 16 '19

Had a rough time hunting down some issues that caused all of the available test cases to pass but failed my puzzle input. Turns out I should have been using "x % 10" to get the one's digit, not "x % 3" like I had.

Also, I feel like the specification for how opcode 3 (read input) works with this new relative parameter mode wasn't made super clear. But it worked out in the end. Here's my rust solution:

/// Day 9: Sensor Boost
/// 
/// Boost sensors with relative Intcode parameters.

use std::fs;

use crate::intcode::IntcodeInterpreter;

/// Parses the input.  Expects a single line of integers separated by
/// commas
fn parse_input() -> Vec<isize> {
    let text: String = fs::read_to_string("data/day9.txt").unwrap();
    let cleaned = text.trim();
    cleaned.split(",").map( |c| c.parse().unwrap()).collect()
}

pub fn run() {
    let numbers = parse_input();
    let mut a = IntcodeInterpreter::new(numbers);
    a.push_input(2);
    a.run();
    println!("Result: {}", a.shift_output());
}

And my Intcode Interpreter:

use std::io;
use std::collections::HashMap;

/// An Intcode Interpreter is a simple virtual machine that uses opcodes
/// to modify its internal memory
pub struct IntcodeInterpreter {
    memory: HashMap<usize, isize>,
    in_buffer: Vec<isize>,
    out_buffer: Vec<isize>,
    ip: usize,
    relative_base: isize,
}

impl IntcodeInterpreter {
    pub fn new(numbers: Vec<isize>) -> Self {
        let mut memory: HashMap<usize, isize> = HashMap::new();
        for (ind, num) in numbers.iter().enumerate() {
            memory.insert(ind, *num);
        }
        Self {
            memory,
            in_buffer: Vec::new(),
            out_buffer: Vec::new(),
            ip: 0,
            relative_base: 0,
        }
    }

    /// Sets a memory address to a value
    pub fn set(&mut self, position: usize, value: isize) {
        self.memory.insert(position, value);
    }

    /// Reads from a memory address
    pub fn get(&mut self, position: usize) -> isize {
        *self.memory.entry(position).or_default()
    }

    /// Shows the memory for debugging
    pub fn print(&self) {
        println!("{:?}", self.memory);
    }

    /// Get the current instruction
    pub fn current_instruction(&mut self) -> isize {
        self.get(self.ip) % 100
    }

    /// Add a value to the input queue
    pub fn push_input(&mut self, value: isize) {
        self.in_buffer.push(value);
        if self.current_instruction() == 98 {
            self.memory.insert(self.ip, self.memory[&self.ip] - 95);
            // Return the instruction to
            // a 3 while maintaining
            // argtype values
        }
    }

    pub fn count_output(&self) -> usize {
        self.out_buffer.len()
    }

    /// Pop a value off the output queue
    pub fn shift_output(&mut self) -> isize {
        if self.out_buffer.is_empty() {
            panic!("Shift from empty out buffer!");
        }
        self.out_buffer.remove(0)
    }

    /// Runs the program in memory until the stopcode (99) is reached
    /// 
    /// All new ops should have their own method.
    /// They take no rust args, but read in args as needed and
    /// shift the instruction pointer when they're done.
    /// Steps should be the number of args used + 1 for the opcode
    pub fn run(&mut self) {
        loop {
            match self.current_instruction() {
                1 => self.op1(),
                2 => self.op2(),
                3 => self.op3(),
                4 => self.op4(),
                5 => self.op5(),
                6 => self.op6(),
                7 => self.op7(),
                8 => self.op8(),
                9 => self.op9(),
                98 => return,  // Halt until receiving input
                99 => return,  // End of program
                _ => panic!("Unrecognized opcode {}.", self.get(self.ip)),
            };
        }
    }

    /// Reads a number from STDIN
    fn read_stdin() -> isize {
        let mut buffer = String::new();
        io::stdin().read_line(&mut buffer).expect("STDIN read failed.");
        buffer.trim().parse::<isize>().unwrap()
    }

    /// Write a number to STDOUT
    fn write_stdout(number: isize) {
        println!("{}", number);
    }

    /// Process the parameter mode and provide the value given
    /// as a parameter
    fn arg(&mut self, offset: usize) -> isize {
        let new_index = self.ip + offset;
        let mode = (self.memory[&self.ip] / 10isize.pow(1 + offset as u32)) % 10;
        if mode == 2 {
            let addr = self.relative_base + self.memory[&new_index];
            let val = self.get(addr as usize);
            self.get(addr as usize)
        } else if mode == 1 {
            self.memory[&new_index]
        } else if mode == 0 {
            self.get(self.memory[&new_index] as usize)
        } else {
            panic!("Unknown parameter mode {}", mode);
        }
    }

    /// Returns the address to write output to
    fn output_address(&self, offset: usize) -> usize {
        let mode = (self.memory[&self.ip] / 10isize.pow(1 + offset as u32)) % 10;
        let new_index = self.ip + offset;
        if mode == 0 {
            self.memory[&new_index] as usize
        } else if mode == 2 {
            (self.relative_base + self.memory[&new_index]) as usize
        } else {
            panic!("Output address with weird mode");
        }
    }

    /// Steps the IP forward "count" steps, wrapping if needed
    fn step(&mut self, count: usize) {
        self.ip = (self.ip + count) % self.memory.len();
    }

    /// Causes the interpreter to block until receiving input
    fn halt_on_input(&mut self) {
        // Update the last two digits from 03 to 98, but maintain
        // the argtype values
        self.memory.insert(self.ip, self.memory[&self.ip] + 95); 
    }

    /// Add [1] + [2], store in [3]
    fn op1(&mut self) {
        let in1 = self.arg(1);
        let in2 = self.arg(2);
        let out = self.output_address(3);

        self.set(out, in1 + in2);

        self.step(4);
    }

    /// Mult [1] * [2], store in [3]
    fn op2(&mut self) {
        let in1 = self.arg(1);
        let in2 = self.arg(2);
        let out = self.output_address(3);

        self.set(out, in1 * in2);

        self.step(4);
    }

    /// Read one value from STDIN and store it in [1]
    fn op3(&mut self) {
        let out = self.output_address(1);

        let val: isize;
        if self.in_buffer.is_empty() {
            self.halt_on_input();
            return;
        } else {
            val = self.in_buffer.remove(0);
        }
        self.set(out, val);

        self.step(2);
    }

    /// Read [1] and send it to STDOUT
    fn op4(&mut self) {
        let arg = self.arg(1);
        self.out_buffer.push(arg);

        self.step(2);
    }

    /// If [1] != 0, set IP -> [2], else nothing
    fn op5(&mut self) {
        if self.arg(1) != 0 {
            self.ip = self.arg(2) as usize;
        } else {
            self.step(3);
        }
    }

    /// if [1] == 0, set IP -> [2], else nothing
    fn op6(&mut self) {
        if self.arg(1) == 0 {
            self.ip = self.arg(2) as usize;
        } else {
            self.step(3);
        }
    }

    /// if [1] < [2], set [3] to 1, else 0
    fn op7(&mut self) {
        let out = self.output_address(3);

        if self.arg(1) < self.arg(2) {
            self.set(out, 1);
        } else {
            self.set(out, 0);
        }

        self.step(4);
    }

    /// if [1] == [2], set [3] to 1, else 0
    fn op8(&mut self) {
        let out = self.output_address(3);

        if self.arg(1) == self.arg(2) {
            self.set(out, 1);
        } else {
            self.set(out, 0);
        }

        self.step(4);
    }

    /// Shift relative base by [1]
    fn op9(&mut self) {
        self.relative_base += self.arg(1);
        self.step(2);
    }
}

fiddlerpianist • Dec 12 '19

My big deal was making the Intcode computer fully backwards compatible with Day 5 and 7 as well as making it run for Day 9. (I haven't tried it with Day 2, though for some reason there's a part of my brain that thinks that is perhaps irreconcilable with that day).

I felt like the directions to this one were incredibly unclear. Should the program be able to write in the original instruction space or not? "Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)" What does "beyond" mean here? How do you differentiate between "beyond" memory and "any other memory," particularly if you can't "access memory at a negative space"? It was also unclear that the "beyond" memory was actually initialized with zeros. (I originally assumed that the program wouldn't attempt to access uninitialized space, but that ended up being proved wrong almost immediately.)

Still, this implementation served me pretty well:

from enum import Enum

class Operation(Enum):
    ADDITION = 1
    MULTIPLICATION = 2
    INPUT = 3
    OUTPUT = 4
    JUMP_IF_TRUE = 5
    JUMP_IF_FALSE = 6
    LESS_THAN = 7
    EQUALS = 8
    RELATIVE_BASE = 9
    TERMINATION = 99

class Mode(Enum):
    POSITION = 0
    IMMEDIATE = 1
    RELATIVE = 2

class Instruction:
    def __init__(self, opcode):
        # instruction: 1 is add, 2 is multiply, 3 is input, 4 is output, 99 is end
        self.operation = Operation(_get_nth_digit(1, opcode) * 10 + _get_nth_digit(0, opcode))
        # mode: 0 is indirect, 1 is immediate
        self.modes = list(map(Mode, [_get_nth_digit(2, opcode), _get_nth_digit(3, opcode), _get_nth_digit(4, opcode)]))       
    def __str__(self):
        return "{}, {}".format(repr(self.operation), self.modes)

class ProgramState:
    def __init__(self, ops, output = None, address = 0, memory = {}, rel_base = 0, done = False):
        self.ops = ops # the instruction set
        self.output = output # any previous output
        self.address = address # index of next instruction to execute
        self.memory = memory # the memory heap
        self.rel_base = rel_base # the relative base from which to calculate relative addresses
        self.done = done # flag to indicate whether this program has hit opcode 99
    def __repr__(self):
        return "Last Output: {}, Rel Base: {}. Op Address: {}".format(self.output, self.rel_base, self.address)

def run(state, inp):
    return _run(state.ops, inp, state.address, state.output, state.memory, state.rel_base)

def _run(ops, input, starting_addr, last_output, memory, rel_base):
    # start at the front of the inputs
    input_idx = 0
    # no output yet
    output = last_output
    # assign to i for brevity
    i = starting_addr
    while ops[i] != 99:
        instruction = Instruction(ops[i])
        if instruction.operation is Operation.ADDITION:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            destination = _get_resolved_position(instruction, ops, rel_base, i, 3)
            _write(first + second, destination, ops, memory)
            i += 4
        elif instruction.operation is Operation.MULTIPLICATION:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            destination = _get_resolved_position(instruction, ops, rel_base, i, 3)
            _write(first * second, destination, ops, memory)
            i += 4
        elif instruction.operation is Operation.INPUT:
            destination = _get_resolved_position(instruction, ops, rel_base, i, 1)
            _write(int(input[input_idx]), destination, ops, memory)
            input_idx += 1
            i += 2
        elif instruction.operation is Operation.OUTPUT:
            output = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            i += 2
            return ProgramState(ops, output, i, memory, rel_base, False)
        elif instruction.operation is Operation.JUMP_IF_TRUE:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            if first != 0:
                i = second
            else:
                i += 3
        elif instruction.operation is Operation.JUMP_IF_FALSE:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            if first == 0:
                i = second
            else:
                i += 3
        elif instruction.operation is Operation.LESS_THAN:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            destination = _get_resolved_position(instruction, ops, rel_base, i, 3)
            _write(1 if first < second else 0, destination, ops, memory)
            i += 4
        elif instruction.operation is Operation.EQUALS:
            first = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            second = _get_resolved_arg(instruction, ops, memory, rel_base, i, 2)
            destination = _get_resolved_position(instruction, ops, rel_base, i, 3)
            _write(1 if first == second else 0, destination, ops, memory)
            i += 4
        elif instruction.operation is Operation.RELATIVE_BASE:
            rel_offset = _get_resolved_arg(instruction, ops, memory, rel_base, i, 1)
            rel_base += rel_offset
            i += 2
    return ProgramState(ops, output, i, {}, rel_base, True)

# Returns the number at the given position (0 being the rightmost)
def _get_nth_digit(n, number):
    return number // 10**n % 10

def _get_resolved_arg(instruction, ops, memory, rel_base, address, arg):
    # ops[i+1] if instruction.modes[0] is Mode.IMMEDIATE else ops[ops[i+1]]
    mode = instruction.modes[arg-1]
    if mode is Mode.IMMEDIATE:
        return ops[address+arg]

    final_addr = ops[address+arg] # Here, mode is POSITION or RELATIVE
    # if RELATIVE add the relative base
    if mode is Mode.RELATIVE:
        final_addr += rel_base
    return ops[final_addr] if final_addr < len(ops) else memory.get(final_addr,0)

def _get_resolved_position(instruction, ops, rel_base, address, arg):
    # ops[i+1] if instruction.modes[0] is Mode.IMMEDIATE else ops[ops[i+1]]
    mode = instruction.modes[arg-1]
    if mode is Mode.POSITION:
        return ops[address+arg]
    elif mode is Mode.RELATIVE:
        return ops[address+arg]+rel_base
    else:
        print ("Bonkers! Unhandled case")

def _write(value, destination, ops, memory):
    if destination < len(ops):        
        ops[destination] = value
    else:
        memory[destination] = value

And the driver program for Day 9:

from intcode import ProgramState
from intcode import run


with open('day09.txt') as f:
    # split line into operation list
    opsAsStrings = f.read().split(",")
    # turn them all into integers
    ops = list(map(int, opsAsStrings))

def boost(ops, inp):
    outputs = []
    state = run(ProgramState(ops), [inp])
    while not state.done:
        print (state.output)
        outputs.append(state.output)
        state = run(state, [])
    print (state.memory)
    return outputs

# Part One
print ("Part One: %s" % boost(ops, 1))
print ("Part Two: %s" % boost(ops, 2))

Jon Bristow • Dec 9 '19 • Edited

woof, here's my new Kotlin intcode parser, as the day's specific code is now as simple as loading the file, splitting it, and running it.

Key rewrite pieces:

More monads.
Redid my janky parameter reader.
Switched from arrays to maps. (GIGANTIC SPEEDUP)
Kotlin data classes come with a copy function! Using constructors to manually do the same thing was the final and most pernicious bug. USE THE copy FUNCTION WHEN PRESERVING IMMUTABILITY!

package intcode

import arrow.core.*

sealed class Mode {
    fun assignable(first: Long, offset: Long) =
        when (this) {
            is Immediate -> throw Error("Cannot assign to immediate value")
            is Position -> first
            is Relative -> (offset + first)
        }

    fun valueOf(first: Long, code: Map<Long, Long>, relativeBase: Long) =
        when (this) {
            is Immediate -> first.some()
            is Position -> code[first].toOption()
            is Relative -> code[relativeBase + first].toOption()
        }.getOrElse { 0L }

    object Immediate : Mode()
    object Position : Mode()
    object Relative : Mode()
}

data class CurrentState(
    val pointer: Option<Long> = 0L.some(),
    val inputs: MutableList<Long> = mutableListOf(),
    val output: Option<Long> = Option.empty(),
    val relativeBase: Long = 0
)

operator fun CurrentState.plus(n: Int) = copy(pointer = pointer.map { it + n })
operator fun CurrentState.plus(n: Long) = copy(pointer = pointer.map { it + n })

fun Pair<Long, Mode>.index(state: CurrentState) = second.assignable(first, state.relativeBase)

fun Pair<Long, Mode>.value(code: Map<Long, Long>, state: CurrentState) =
    second.valueOf(first, code, state.relativeBase)

sealed class Instruction {
    abstract val opcodes: Int
    abstract fun execute(
        code: MutableMap<Long, Long>,
        params: List<Pair<Long, Mode>>,
        state: CurrentState
    ): Either<String, CurrentState>

    open fun findInputs(code: MutableMap<Long, Long>, state: CurrentState): Either<String, List<Pair<Long, Mode>>> =
        state.pointer.fold(
            { emptyList<Pair<Long, Mode>>().right() },
            { pointer ->
                (pointer + 1..pointer + 3)
                    .map { code[it] ?: 0 }
                    .zip(extractParameterType(pointer, code))
                    .fold(listOf<Pair<Long, Mode>>().right()) { a: Either<String, List<Pair<Long, Mode>>>, b ->
                        a.flatMap { acc ->
                            b.second.fold({
                                "Pointer $pointer: Problem parsing input ${b.first}: $it".left()
                            }, {
                                (acc + (b.first to it)).right()
                            })
                        }
                    }
            })

    private fun extractParameterType(pointer: Long, code: MutableMap<Long, Long>) =
        "%010d".format((code[pointer] ?: 0) / 100).takeLast(opcodes).reversed()
            .map {
                when (it) {
                    '0' -> Mode.Position.right()
                    '1' -> Mode.Immediate.right()
                    '2' -> Mode.Relative.right()
                    else -> "Bad mode $it".left()
                }
            }


    sealed class ThreeParameterInstruction : Instruction() {
        override val opcodes: Int = 3

        class Add : ThreeParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> {
                code[params[2].index(state)] = params[0].value(code, state) + params[1].value(code, state)
                return (state + 4).right()
            }
        }

        class Multiply : ThreeParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> {
                code[params[2].index(state)] = params[0].value(code, state) * params[1].value(code, state)
                return (state + 4).right()
            }
        }

        class LessThan : ThreeParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> {
                code[params[2].index(state)] = when {
                    params[0].value(code, state) < params[1].value(code, state) -> 1L
                    else -> 0L
                }
                return (state + 4).right()
            }
        }

        class Equal : ThreeParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> {
                code[params[2].index(state)] = when {
                    params[0].value(code, state) == params[1].value(code, state) -> 1
                    else -> 0L
                }
                return (state + 4).right()
            }
        }
    }

    sealed class TwoParameterInstruction : Instruction() {
        override val opcodes: Int = 2

        class JumpIfTrue : TwoParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> {
                return when (params[0].value(code, state)) {
                    0L -> state + 3
                    else -> state.copy(pointer = params[1].value(code, state).some())
                }.right()
            }
        }

        class JumpIfFalse : TwoParameterInstruction() {
            override fun execute(
                code: MutableMap<Long, Long>,
                params: List<Pair<Long, Mode>>,
                state: CurrentState
            ): Either<String, CurrentState> =
                when (params[0].value(code, state)) {
                    0L -> state.copy(pointer = params[1].value(code, state).some())
                    else -> state + 3
                }.right()
        }
    }

    class SetFromInput(private val inputOption: Option<Long>) : Instruction() {
        override val opcodes: Int = 1
        override fun execute(
            code: MutableMap<Long, Long>,
            params: List<Pair<Long, Mode>>,
            state: CurrentState
        ) = inputOption.fold(
            { state },
            { input ->
                code[params[0].index(state)] = input
                state.copy(pointer = state.pointer.map { it + 2 })
            }).right()
    }

    class Output : Instruction() {
        override val opcodes: Int = 1
        override fun execute(
            code: MutableMap<Long, Long>,
            params: List<Pair<Long, Mode>>,
            state: CurrentState
        ): Either<String, CurrentState> {
            println("OUTPUT: ${params[0].value(code, state)}")
            return state.copy(
                pointer = state.pointer.map { it + 2 },
                output = params[0].value(code, state).some()
            ).right()
        }
    }

    class ModifyRelativeBase : Instruction() {
        override val opcodes: Int = 1
        override fun execute(
            code: MutableMap<Long, Long>,
            params: List<Pair<Long, Mode>>,
            state: CurrentState
        ): Either<String, CurrentState> {
            return state.copy(
                pointer = state.pointer.map { it + 2 },
                relativeBase = state.relativeBase + params[0].value(code, state)
            ).right()
        }
    }

    object End : Instruction() {
        override val opcodes: Int = 0
        override fun execute(
            code: MutableMap<Long, Long>,
            params: List<Pair<Long, Mode>>,
            state: CurrentState
        ): Either<String, CurrentState> = state.copy(pointer = Option.empty()).right()
    }
}


fun parseInstruction(
    instruction: Long,
    input: MutableList<Long>
): Either<String, Pair<Instruction, MutableList<Long>>> =
    when (instruction % 100) {
        1L -> (Instruction.ThreeParameterInstruction.Add() to input).right()
        2L -> (Instruction.ThreeParameterInstruction.Multiply() to input).right()
        3L -> (Instruction.SetFromInput(input.firstOrNone()) to input.drop(1).toMutableList()).right()
        4L -> (Instruction.Output() to input).right()
        5L -> (Instruction.TwoParameterInstruction.JumpIfTrue() to input).right()
        6L -> (Instruction.TwoParameterInstruction.JumpIfFalse() to input).right()
        7L -> (Instruction.ThreeParameterInstruction.LessThan() to input).right()
        8L -> (Instruction.ThreeParameterInstruction.Equal() to input).right()
        9L -> (Instruction.ModifyRelativeBase() to input).right()
        99L -> (Instruction.End to input).right()
        else -> "Problem parsing instruction $instruction".left()
    }


fun handleCodePoint(
    code: MutableMap<Long, Long>,
    eitherState: Either<String, CurrentState>
): Either<String, CurrentState> =
    eitherState.flatMap { state ->
        state.pointer.fold(
            { "Program has stopped.".left() },
            { pointer ->
                code[pointer].rightIfNotNull { "Code point $pointer undefined." }.flatMap { codeValue ->
                    parseInstruction(codeValue, state.inputs).flatMap { (instr, inp) ->
                        instr.findInputs(code, state).flatMap { params ->
                            instr.execute(code, params, state.copy(pointer = pointer.some(), inputs = inp))
                        }
                    }
                }
            }
        )
    }

fun step(code: MutableMap<Long, Long>, state: CurrentState): Either<String, Long> {
    return step(code, state.right())
}

tailrec fun step(
    code: MutableMap<Long, Long>,
    state: Either<String, CurrentState>
): Either<String, Long> = when (state) {
    is Either.Left<String> -> "Error: ${state.a}".left()
    is Either.Right<CurrentState> -> {
        when (state.b.pointer) {
            is None -> state.b.output.fold({ "No output".left() }, { it.right() })
            is Some<Long> -> step(code, handleCodePoint(code, state))
        }
    }
}

View full discussion (23 comments)

DEV Community

Advent of Code 2019 Solution Megathread - Day 9: Sensor Boost

Day 9 - The Problem

Ongoing Meta

Dev.to List of Leaderboards

Neat Statistics

Languages Seen On Day 08

Completion Stats

Top comments (23)

print(nList)

print(len(nList))

print(intcode(boost_program,1))[1]

Read next

Configuring User and Group Accounts in Microsoft Entra ID (Azure AD)-AZ 104

Understanding Microsoft Entra ID (Formerly Azure Active Directory) for the Azure Administration Certification Exam-Az 104

LeetCode in Golang: Parsing A Boolean Expression

Judging the first DEV Web Game Challenge