3
\$\begingroup\$

In an effort to stretch my programming muscles, I'm doing the Advent of Code 2018 in a language new to me: Python. Coming from a C# background, I'm probably making all kinds of mistakes or are unaware of some usefull things in Python. This is my solution to day 3, and I would like to get a review on my code. I'm interested in both better ways to solve the problem using Python's tools, but also anything that has to do with style (I tried applying PEP8 rules), readability, etc. Thanks!

The full challenge is here and a bit involved, I'll try to keep it a bit shorter here.

The challenge

The Elves managed to locate the chimney-squeeze prototype fabric for Santa's suit. Unfortunately, nobody can even agree on how to cut the fabric. The whole piece of fabric they're working on is a very large square - at least 1000 inches on each side.

Each Elf has made a claim about which area of fabric would be ideal for Santa's suit. All claims have an ID and consist of a single rectangle with edges parallel to the edges of the fabric. Each claim's rectangle is defined as follows:

  • The number of inches between the left edge of the fabric and the left edge of the rectangle.
  • The number of inches between the top edge of the fabric and the top edge of the rectangle.
  • The width of the rectangle in inches.
  • The height of the rectangle in inches.

A claim like #123 @ 3,2: 5x4 means that claim ID 123 specifies a rectangle 3 inches from the left edge, 2 inches from the top edge, 5 inches wide, and 4 inches tall. The problem is that many of the claims overlap, causing two or more claims to cover part of the same areas. For example, consider the following claims:

- #1 @ 1,3: 4x4
- #2 @ 3,1: 4x4
- #3 @ 5,5: 2x2

Visually, these claim the following areas:

........
...2222.
...2222.
.11XX22.
.11XX22.
.111133.
.111133.
........

The four square inches marked with X are claimed by both 1 and 2. (Claim 3, while adjacent to the others, does not overlap either of them.) If the Elves all proceed with their own plans, none of them will have enough fabric. How many square inches of fabric are within two or more claims?

This puzzle also comes with custom puzzle input. I can provide mine, but it's 1350 lines long. The example above provides the way the input is formatted.

Day3.py

class Claim(object):
    id = None
    x = None
    y = None
    width = None
    height = None

    def __init__(self, claim_id, x, y, width, height):
        self.id = claim_id
        self.x = x
        self.y = y
        self.width = width
        self.height = height

    def __repr__(self):
        return "<Claim #%s - %s, %s - %sx%s>" % (self.id, self.x, self.y, self.width, self.height)


def read_file_lines(file_path, strip_lines=True):
    """ Reads the specified file and returns it's lines an array
        file_path: the path to the file
        strip_lines (default: true): boolean to indicate whether or not to strip leading and trailing whitespace from each line

        Returns: An array of the lines in the file as string
    """
    with open(file_path, "r") as f:
        if strip_lines:
            return [l.strip() for l in f.readlines()]

        return [l for l in f.readlines()]


def parse_input(lines):
    claims = []
    for line in lines:
        parts = line.split(" ")

        id = int(parts[0][1:])
        x = int(parts[2].split(",")[0])
        y = int(parts[2].split(",")[1][:-1])
        width = int(parts[3].split("x")[0])
        height = int(parts[3].split("x")[1])

        claims.append(Claim(id, x, y, width, height))

    return claims


def generate_matrix(size):
    return [[0]*size for _ in range(size)]


def print_matrix(matrix):
    line = ""
    for y in range(0, len(matrix[0])):
        line = line + str(y) + ": "
        for x in range(0, len(matrix[0])):
            line = line + str(matrix[x][y])
        print(line)
        line = ""


if __name__ == '__main__':
    content = read_file_lines("input.txt")
    claims = parse_input(content)

    matrix = generate_matrix(1000)
    print_matrix(matrix)

    for claim in claims:
        x_indexes = range(claim.x, claim.x + claim.width)
        y_indexes = range(claim.y, claim.y + claim.height)

        for x in x_indexes:
            for y in y_indexes:
                matrix[x][y] = matrix[x][y] + 1

    print_matrix(matrix)

    inches_double_claimed = 0
    for x in range(0, len(matrix[0])):
        for y in range(0, len(matrix[0])):
            if matrix[x][y] >= 2:
                inches_double_claimed += 1

    print("Inches claimed by two or more claims:", inches_double_claimed)
\$\endgroup\$
4
\$\begingroup\$

This is rather good Python, pleasant to read and using good practices already. I'll just focus on making it more Pythonic.


    def __repr__(self):
        return "<Claim #%s - %s, %s - %sx%s>" % (self.id, self.x, self.y, self.width, self.height)

This should be __str__, as it is meant for "fancy" formatting like this. Ideally, __repr__ should be build such as eval(repr(x)) will reconstruct x.

class Claim(object):
    id = None
    x = None
    y = None
    width = None
    height = None

    def __init__(self, claim_id, x, y, width, height):
        self.id = claim_id
        self.x = x
        self.y = y
        self.width = width
        self.height = height

    def __repr__(self):
        return "<Claim #%s - %s, %s - %sx%s>" % (self.id, self.x, self.y, self.width, self.height)

This whole class could be replaced by a namedtuple. Considering the previous remark, I’d write:

from collections import namedtuple


class Claim(namedtuple('Claim', 'id x y width height')):
    def __str__(self):
        return "<Claim #{} - {}, {} - {}x{}>".format(self.id, self.x, self.y, self.width, self.height)

Note that I replaced old-school % formating with the prefered str.format method. Note that there is also f-strings available if you are using Python 3.6+.

Also note that in your original class you defined class variables that were overriden in the constructor. Don't. There is no gain in doing so as these class variables will never be used anyway.


def read_file_lines(file_path, strip_lines=True):
    """ Reads the specified file and returns it's lines an array
        file_path: the path to the file
        strip_lines (default: true): boolean to indicate whether or not to strip leading and trailing whitespace from each line

        Returns: An array of the lines in the file as string
    """
    with open(file_path, "r") as f:
        if strip_lines:
            return [l.strip() for l in f.readlines()]

        return [l for l in f.readlines()]

You don't need to read the whole file in memory at once and then create an array of the same content again. Instead, I’d suggest using a generator since you are transforming the output of this function anyway, so rather keep it nice with the memory:

def read_file_lines(file_path, strip_lines=True):
    """ Reads the specified file and returns it's lines
        file_path: the path to the file
        strip_lines (default: true): boolean to indicate whether or not to strip leading and trailing whitespace from each line

        Generates the lines in the file as string
    """
    with open(file_path, "r") as f:
        for line in f:
            if strip_lines:
                yield line.strip()
            else:
                yield line

def parse_input(lines):
    claims = []
    for line in lines:
        parts = line.split(" ")

        id = int(parts[0][1:])
        x = int(parts[2].split(",")[0])
        y = int(parts[2].split(",")[1][:-1])
        width = int(parts[3].split("x")[0])
        height = int(parts[3].split("x")[1])

        claims.append(Claim(id, x, y, width, height))

    return claims

You used list-comprehensions in other places so you know how to use them. You should try to extract the parsing logic out of the loop so you can use them here too. I’d write this function as:

def parse_input(lines):
    return [Claim.from_input(line) for line in lines]

and rework the Claim class into:

class Claim(namedtuple('Claim', 'id x y width height')):
    def __str__(self):
        return "<Claim #{} - {}, {} - {}x{}>".format(self.id, self.x, self.y, self.width, self.height)

    @classmethod
    def from_input(cls, line):
        parts = line.split(" ")

        id = int(parts[0][1:])
        x = int(parts[2].split(",")[0])
        y = int(parts[2].split(",")[1][:-1])
        width = int(parts[3].split("x")[0])
        height = int(parts[3].split("x")[1])

        return cls(id, x, y, width, height)

In fact, I'd probably merge the two previous functions into a single one, but there is no harm in keeping both:

def parse_input(filename):
    with open(filename) as f:
        return [Claim.from_input(line.strip()) for line in f]

def generate_matrix(size):
    return [[0]*size for _ in range(size)]

Nothing to say here, you didn't fall in the trap of writting [[0] * size] * size.


def print_matrix(matrix):
    line = ""
    for y in range(0, len(matrix[0])):
        line = line + str(y) + ": "
        for x in range(0, len(matrix[0])):
            line = line + str(matrix[x][y])
        print(line)
        line = ""

Time to learn to use str.join:

def print_matrix(matrix):
    string = '\n'.join(
            'line {}: {}'.format(i, ''.join(map(str, line)))
            for i, line in enumerate(matrix))
    print(string)

if __name__ == '__main__':
    content = read_file_lines("input.txt")
    claims = parse_input(content)

    matrix = generate_matrix(1000)
    print_matrix(matrix)

    for claim in claims:
        x_indexes = range(claim.x, claim.x + claim.width)
        y_indexes = range(claim.y, claim.y + claim.height)

        for x in x_indexes:
            for y in y_indexes:
                matrix[x][y] = matrix[x][y] + 1

    print_matrix(matrix)

    inches_double_claimed = 0
    for x in range(0, len(matrix[0])):
        for y in range(0, len(matrix[0])):
            if matrix[x][y] >= 2:
                inches_double_claimed += 1

    print("Inches claimed by two or more claims:", inches_double_claimed)

As you made in the print_matrix function, you are iterating over indices to access content of the matrix. Instead, you should iterate over the content directly if you need it:

for line in matrix:
    for claims in line:
        if claims > 1:
            inches_double_claimed += 1

And, in fact, these loops could be written in a single generator expression fed to sum:

inches_double_claimed = sum(claims > 1 for line in matrix for claims in line)

I would also advice you to wrap this code in a main function parametrized by the file name to read.


There is still room for improvement: maybe defining a Matrix class to abstract your functions manipulating it, using re to simplify input parsing, using a defaultdict(defaultdict(int)) to support arbitrary sizes of fabric (and avoid wasting memory on small problems); but it is still fine as it is.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks so much! Very comprehensable and a lot of things to absorb! \$\endgroup\$ – Céryl Wiltink Dec 31 '18 at 8:01
2
\$\begingroup\$

I wrote about Pythonic constructs in an other answer, so I'll focus in introducing helpful modules in this one. All in all, I'd say that converting the input to Claim objects is wasting resources and you should focus on your intermediate matrix representation instead. Or maybe as intermediate representation for documentation purposes, but you don't need to store them all at once in memory.

As such, I would only use the re module to parse a line and immediately store it into the matrix.

Such matrix should not be pre-allocated and allowed to be arbitrarily large if need be. For such cases, the collections module features two helpful classes: defaultdict and Counter.

Lastly, the fileinput module make it easy to use a/several file names on the command line or standard input.

My take on this would be:

import re
import fileinput
from collections import namedtuple, defaultdict, Counter


INPUT_PATTERN = re.compile(r'#\d+ @ (\d+),(\d+): (\d+)x(\d+)')


class Claim(namedtuple('Claim', ['x', 'y', 'width', 'height'])):
    @property
    def horizontal(self):
        return range(self.x, self.x + self.width)

    @property
    def vertical(self):
        return range(self.y, self.y + self.height)


def parse_input(stream):
    for line in stream:
        match = INPUT_PATTERN.match(line)
        if match:
            yield Claim(*map(int, match.groups()))


def claim_fabric(claims):
    fabric = defaultdict(Counter)
    for claim in claims:
        for line in claim.horizontal:
            fabric[line].update(claim.vertical)
    return fabric


def count_overlaping_claims(fabric):
    return sum(
            claims > 1
            for line in fabric.values()
            for claims in line.values())


if __name__ == '__main__':
    fabric = claim_fabric(parse_input(fileinput.input()))
    print(count_overlaping_claims(fabric))
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks! I'm used to C# so Objects are my knee-jerk reaction to anything. I see a lot of cool new stuff in here for me to research. I'll approve the other answer because of the completeness, but at the very least: Have an upvote! \$\endgroup\$ – Céryl Wiltink Dec 31 '18 at 8:00
0
\$\begingroup\$

Another python feature crying to be used is scatter/gather assignments. You can replace:

    parts = line.split(" ")

    id = int(parts[0][1:])
    x = int(parts[2].split(",")[0])
    y = int(parts[2].split(",")[1][:-1])
    width = int(parts[3].split("x")[0])
    height = int(parts[3].split("x")[1])

with the at least slightly more readable:

    line = line[1:].replace(':','') # nuke extra punctuation
    id, _, xy, size = line.split(" ")
    id = int(id)
    x, y = [int(i) for i in xy.split(',')]
    width, height = [int(i) for i in size.split('x')]

The first and second lines can of course be combined if you're going for more brevity, but I thought breaking the cleanup away from the breakup clarified it a little.

| improve this answer | |
\$\endgroup\$

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.