11
\$\begingroup\$

I'm currently using the Advent of Code programming challenges as an opportunity to learn some python. The following code is my solution for the Day 8 challenge, where the task is to write a programm that reads a set of instructions which are then performed on registers. Registers start with a value of 0. Each instruction may increase or decrease the value of a register. The programm should return the maximum value in any register at the end of execution as well as the maximum that any register had during the whole process.

An instructions looks as follows: <register> <operation> <integer> if <register> <boolop> <integer>. Where register is a name of a register, operation is either inc to increase the value of a register, or dec to decrease its value. boolop is a comparison operator. The instruction should only be executed if the condition is true, e.g. a inc 10 if b < 0 will increase the value of the register a by 10 if the current value for register b is less than 0.

I read the input from a file called in. An example input can be found here. The expected output for this input would be (2971, 4254).

import re

def is_int(str):
    if str == '':
        return False
    if str[0] in ('+', '-'):
        return str[1:].isdecimal()
    return str.isdecimal()

def value(registers, val):
    if is_int(val):
        return int(val)
    if not val in registers:
        registers[val] = 0
    return registers[val]

def max_register(registers):
    return max([x for _, x in registers.items()])


class Operation:
    def __init__(self, line):
        res = re.search('([^ ]*) ([^ ]*) ([^ ]*)', line)
        self.left = res.group(1)
        self.operator = res.group(2)
        self.right = res.group(3)

    def __repr__(self):
        return self.left + ' ' + self.operator + ' ' + self.right       

    def perform(self, registers):
        l, r = value(registers, self.left), value(registers, self.right)
        if self.operator == 'inc':
            registers[self.left] = l + r
        elif self.operator == 'dec':
            registers[self.left] = l - r
        else:
            print('Unsupported operation', self.operator)


class Condition:
    def __init__(self, line):
        res = re.search('if ([^ ]*) ([^ ]*) ([^ ]*)', line)
        self.left = res.group(1)
        self.operator = res.group(2)
        self.right = res.group(3)

    def __repr__(self):
        return self.left + ' ' + self.operator + ' ' + self.right

    def test(self, registers):
        l, r = (value(registers, self.left), value(registers, self.right))

        if self.operator == '==':
            return l == r
        elif self.operator == '!=':
            return l != r
        if self.operator == '>':
            return l > r
        elif self.operator == '>=':
            return l >= r           
        elif self.operator == '<':
            return l < r
        elif self.operator == '<=':
            return l <= r
        else:
            print('Unsupported condition operator', self.operator)
            return False

class Instruction:

    def __init__(self, line):
        res = re.search('(.*) (if .*)', line)
        self.operation = Operation(res.group(1))
        self.condition = Condition(res.group(2))

    def __repr__(self):
        return str(self.operation) + ' ' + str(self.condition)

    def perform(self, registers):
        if self.condition.test((registers)):
            self.operation.perform(registers)

class Programm:

    def __init__(self, instr):
        self.instructions = instr
        self.position = 0

    def __repr__(self):
        return '@' + self.position + '\n' + str(self.instructions)

    def run_next(self, registers):
        if self.position >= len(self.instructions):
            return False
        self.instructions[self.position].perform(registers)
        self.position = self.position + 1
        return True

    def run(self, registers):
        for _ in range(len(self.instructions)):
            self.run_next(registers)


def parse_programm(file):
    lines = file.read().splitlines()
    return Programm([Instruction(i) for i in lines])

def run(input):
    with open(input) as infile:
        programm = parse_programm(infile)

    registers = {}
    curmax = 0
    while programm.run_next(registers):
        curmax = max(curmax, max_register(registers))
    return (max_register(registers), curmax)

if __name__ == '__main__':
    print(run("in"))

I am especially interested in whether the code is pythonic and how it could be improved. E.g. the use of regexes to parse the instructions feels kinda hacky.

\$\endgroup\$
  • \$\begingroup\$ You might want to add some explanation about your error-handling strategy. Are you trying to have robust (meaningful) behavior for ill-formed input? or just assume that the input will always match the stated grammar? If the latter, your is_int function is pointless (just cast to int); and it doesn't make sense to use re.search over re.match; and probably a bunch of other stuff. \$\endgroup\$ – Quuxplusone Dec 13 '17 at 18:40
  • \$\begingroup\$ @Quuxplusone Yes, I assume every input is correct. But I also planned for a change where the operations not only can take integers but also the name of a register. So the point of my is_int function was so simplify the usage of value(). I wanted a function where I can input a string or and int and getting back the value of the register matching the string or the intvalue itself. \$\endgroup\$ – Sebastian Stern Dec 14 '17 at 8:43
  • \$\begingroup\$ Ah, planning for future expansion. Makes sense. But were you really planning a future expansion where the function is_int(x) would return True for values of x that were not ints, but rather, register names? That sounds like your current code is redundant but your future code is actively confusing! \$\endgroup\$ – Quuxplusone Dec 14 '17 at 19:11
  • 1
    \$\begingroup\$ @Quuxplusone No, the code would stay the same, it already allows the use of register names for operands. value(int) will return the value, but value(string) will return the current value of the register with this name. The is_int function is just a helper to distinguish between those too cases in value() and will of course only return True, wenn the x is an int. \$\endgroup\$ – Sebastian Stern Dec 15 '17 at 8:40
5
\$\begingroup\$

I echo both of the previous reviewer's sentiments, but I'd also like to add that regex is overkill for the parsing here - str.split will work just fine. Implementing this and some of the other suggestions might produce code like:

class Computer:
    COMPARISONS = {
        '==': operator.eq, '<=': operator.le, '<': operator.lt, 
        '!=': operator.ne, '>=': operator.ge, '>': operator.gt,
    }

    OPERATIONS = {
        'inc': operator.add,
        'dec': operator.sub,
    }

    def __init__(self):
        self.registers = defaultdict(int)
        self.current_max = self.total_max = -float('inf')

    def parse_instruction(self, instruction):
        target, op, val, _, comp_reg, comp, comp_val = instruction.split()
        val, comp_val = int(val), int(comp_val)

        # compare the value in `comp_reg` to `comp_val` using `comp`
        if self.COMPARISONS[comp](self.registers[comp_reg], comp_val):
            old_val = self.registers[target]
            self.registers[target] = self.OPERATIONS[op](old_val, val)

            self.current_max = max(self.registers.values())
            self.total_max = max(self.total_max, self.current_max)

Here, the "inc" and "dec" operations were abstracted into a dictionary of OPERATIONS. This is slightly more complicated than it needs to be (one could simply invert val in the "dec" case and add the result to the register), but allows for other operations to be easily added.

The end usage would look like:

if __name__ == '__main__':
    instructions_file = 'instructions.txt' # path on my PC
    with open(instructions_file) as f:
        instructions = f.readlines()

    computer = Computer()
    for instruction in instructions:
        computer.parse_instruction(instruction)

    print(computer.current_max)
    print(computer.total_max)
\$\endgroup\$
  • \$\begingroup\$ Since I can only accept one answer, I'll accept this one, because it captures the suggestions from all three answer into a nice succint example. I learned a lot, thanks guys. :-) \$\endgroup\$ – Sebastian Stern Dec 14 '17 at 8:55
13
\$\begingroup\$

Few nitpicks, possible improvements and random ideas:

  • if not val in registers: is a bit less natural as if val not in registers:
  • you can replace if str == '': with if not str:
  • str, though, is not a good variable name since it shadows a built-in str type
  • is_int though can probably use the EAFP approach - try converting it to int and handle possible errors:

    def is_int(value):
        try:
            int(value)
            return True
        except (ValueError, TypeError):
            return False
    
  • max_register can be simplified to:

     return max(registers.values())
    
  • it is a good practice to define regular expression strings as raw strings
  • I think you can unpack the captured group values into variables:

    res = re.search(r'([^ ]*) ([^ ]*) ([^ ]*)', line)
    self.left, self.operator, self.right = res.groups()
    
  • the Condition class may benefit from the operator module. Instead of having multiple if/elifs, you may define a mapping of operator strings to operator functions:

    import operator
    
    OPERATIONS = {
        '==': operator.eq,
        '!=': operator.ne,
        '>': operator.gt,
        '>=': operator.gte,
        '<': operator.lt,
        '<=': operator.le
    }
    
    l, r = value(registers, self.left), value(registers, self.right)
    return OPERATIONS[self.operator](l, r)
    

    Note that I would check for validness of the operator when you extract it via the regular expression in the __init__. Also, OPERATIONS can probably a module or class-level constant.

  • think of pre-compiling regular expressions with re.compile() and re-using
\$\endgroup\$
10
\$\begingroup\$

My impression is that you have written too much code.

I'd like to encourage you to have another look at your design. Your registers are named by multi-letter strings, and have a default integer value of zero. There's a built-in data structure for this: the collections.defaultdict will handle this automatically for you if you use int as the factory function:

>>> import collections
>>> registers = collections.defaultdict(int)
>>> registers['abc'] += 100
>>> registers['def'] -= 10
>>> print(registers)
>>> defaultdict(<class 'int'>, {'abc': 100, 'def': -10})

With that in mind, what happens if you think of your program as operating against a single object - the register file - instead of operating with a collection of Condition and Statement objects?

def run(input):
    """Evaluate a series of statements of the form:

       register_name [inc|dec] integer if register_name relop integer

    where values for register_name default to zero. Return a tuple, 
    (max_reg, max_ever) containing the maximum value left in any
    register at the end of execution, and the maximum value ever 
    computed during the program.

    """
    curmax = -float('inf')
    registers = collections.defaultdict(int)

    with open(input) as infile:
        for line in infile:
            result = eval_line(line, registers)

            if result is not None:
                curmax = max(result, curmax)

    return (max(registers.values()), curmax)

I would then suggest that eval_line could be a single function, using a more detailed regular expression:

instr_re = re.compile(r'(\w+) (inc|dec) (\d+) if (\w+) ([=!><]=|[=!><]) (\d+)')

m = instr_re.match(line)
if m is None:
    return None

target, incop, opnd1, condreg, relop, opnd2 = m.groups()

If your regex is right, there shouldn't be a problem with evaluating your components:

opnd1 = int(opnd1)
opnd2 = int(opnd2)

relfn = {'==': operator.eq, ...}[relop]
incop = {'inc': operator.iadd, 'dec': operator.isub}[incop]

if relfn(registers[condreg], opnd2):
    return incop(registers[target], opnd1)

return None
\$\endgroup\$
  • \$\begingroup\$ I might suggest using more verbose variable names, I find it hard to discern what things like opnd1, relfn, and incop mean at a glance. \$\endgroup\$ – Jared Goguen Dec 13 '17 at 21:21
  • \$\begingroup\$ note that your line parsing can be easier. target, incop, opnd1, _, condreg, relop, opnd2 = line.split() \$\endgroup\$ – Adam Smith Dec 14 '17 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.