/r/dailyprogrammer #188 hard

arrows_and_arrows.py

# -*- coding: utf-8 -*-
# /r/dailyprogrammer #188 hard
# http://www.reddit.com/r/dailyprogrammer/comments/2m82yz/
# Title: [2014-11-14] Challenge #188 [Hard] Arrows and Arrows, part 1
""" Arrows and arrows

 -- (2014) Dave J (https://github.com/DaveAtGit)
"""

# Imports
from argparse import ArgumentParser

# Classes


class Node:
    def __init__(self, x, y, d):
        self.x = x      # x-coordinate
        self.y = y      # y-coordinate
        self.d = d      # directory
        self.b = None   # back
        self.m = None   # mark

    def mark(self, mark):
        if self.m is None:
            self.m = mark
        return self.m

    def next(self, matrix):
        x, y = self.x, self.y
        if self.d in '<>':
            x += (1, -1)[self.d == '<']
            x %= matrix.width
        else:
            y += (1, -1)[self.d == '^']
            y %= matrix.height
        p = matrix[x, y]
        old_mark = p.m
        if p.mark(self.m) == self.m:
            p.b = self
        return p, p.m == self.m, old_mark == self.m

    def __str__(self):
        return "({x}, {y}, {d}, {m})".format(**vars(self))


class Matrix:
    def __init__(self, height, width, raw_data):
        self.height = height
        self.width = width
        self.data = [[Node(x, y, c) for x, c in enumerate(line.strip())]
                     for y, line in enumerate(raw_data.strip().split('\n'))]
                     # list comprehension ftw!
        self.cycle = None

    def __getitem__(self, tpl):
        x, y = tpl
        return self.data[y][x]

    def __iter__(self):
        yield from (n for line in self.data
                      for n in line)
                    # generator

    def run(self):
        mark = 0
        l = []
        for node in self:   # using the generator to iterate over each node
            if node.m is not None:
                continue    # we don't need to look at it, if it is already marked
            c = self.__cycle(node, mark)
            l = max(l, c, key=len)
            mark += 1
        self.cycle = l
        return l

    def __cycle(self, node, mark):
        path = []
        node.mark(mark)
        while True:
            p, successor, cycle = node.next(self)
            if not successor:
                return []
            if cycle:
                break
            node = p

        p = node.b
        while p and p != node:
            path.append(p)
            p = p.b
        path.append(node)

        return path

    def printable_cycle(self):
        pm = [[(' ', n.d)[n in self.cycle] for n in line] for line in self.data]
        return '\n'.join(''.join(l) for l in pm)

    def __str__(self):
        return '\n'.join(''.join(n.d for n in l) for l in self.data)

# Functions


def handle(matrix: Matrix):
    """ does something :P """
    matrix.run()
    print("Longest cycle: {}".format(len(matrix.cycle)))
    print(matrix.printable_cycle())


def main():
    """ reads arguments """
    ap = ArgumentParser()
    ap.add_argument("file", nargs="+", type=str,
                    help="Files to read from.")

    args = ap.parse_args()

    for fpath in args.file:
        with open(fpath) as f:
            w, h = map(int, f.readline().strip().split())
            matrix = Matrix(h, w, f.read())
        handle(matrix)

if __name__ == '__main__':
    main()