/r/dailyprogrammer #191 intermediate

space_probe.py

# -*- coding: utf-8 -*-
# /r/dailyprogrammer #191 intermediate
# http://www.reddit.com/r/dailyprogrammer/comments/2o5tb7/
# Title: [2014-12-3] Challenge #191 [Intermediate] Space Probe. Alright Alright Alright.
""" Space Probe

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

# Imports
from argparse import ArgumentParser
from random import randint

# Classes


class Space:
    PCT_ASTEROIDS = .3
    PCT_GRAVITY_WELLS = .1
    SYMB_A, SYMB_GW, SYMB_S, SYMB_ST,\
    SYMB_E, SYMB_F, SYMB_P, SYMB_IMP = "AG.SEFOx"
    # Asteroid, Gravity Well, Space, Start,\
    # End, Failed, Path, Impassable (around GW)
    # >> one might want to adjust those symbols for
    #    better readability.

    def __init__(self, n, start, end):
        self._m = [[Space.SYMB_S for _ in range(n)] for _ in range(n)]
        self.N = n
        self.start = start
        self.end = end

        self[start] = Space.SYMB_ST
        self[end] = Space.SYMB_E
        
        self._fill_a()
        self._fill_gw()

    def _fill_a(self):
        num = int(self.N*self.N*Space.PCT_ASTEROIDS)
        while num > 0:
            _x = randint(0, self.N-1)
            _y = randint(0, self.N-1)
            if self.set((_x, _y), Space.SYMB_A):
                num -= 1

    def _fill_gw(self):
        num = int(self.N*self.N*Space.PCT_GRAVITY_WELLS)
        while num > 0:
            _x = randint(0, self.N-1)
            _y = randint(0, self.N-1)
            if self.set((_x, _y), Space.SYMB_GW):
                # set gravity-well's impassable border
                for ox in range(-1, 2):
                    for oy in range(-1, 2):
                        self.set((_x + ox, _y + oy),
                                 Space.SYMB_IMP)
                num -= 1

    def __getitem__(self, coords):
        return self._m[coords[1]][coords[0]]

    def __setitem__(self, coords, value):
        self._m[coords[1]][coords[0]] = value

    def __contains__(self, coords):
        return not any(map(lambda c: c < 0 or c >= self.N, coords))

    def set(self, coords, value):
        if not coords in self:
            # outside the space
            return False
        if self[coords] != Space.SYMB_S:
            return False
        self[coords] = value
        return True

    def run(self):
        def add(point, offset):
            return tuple(map(int.__add__, point, offset))
        circle = [(i-1, j-1) for i in range(3) for j in range(3)
                    if not (i == 0 and j == 0)]
        # BFS
        Q, V = list(), dict()
        V[self.start] = self.start
        Q.append(self.start)

        v = self.start
        while len(Q) > 0:
            v = Q.pop(0)
            if v == self.end:
                break   # done
            for d in circle:    # adjacents
                u = add(v, d)
                if u in self and self[u] in {Space.SYMB_S, Space.SYMB_E} and u not in V:
                    V[u] = v
                    Q.append(u)
        else:
            self[v] = Space.SYMB_F

        # render path
        while True:
            v = V[v]
            if v == self.start: break
            self[v] = Space.SYMB_P

    def __str__(self):
        return '\n'.join(''.join(l).replace(Space.SYMB_IMP, Space.SYMB_S)
                         for l in self._m)

# Functions


def main():
    """ handles arguments """
    ap = ArgumentParser()
    ap.add_argument("n", type=int,
                    help="Size of the n*n-space.")
    ap.add_argument("-s", "--start", nargs="+", type=str, required=True,
                    help="Values of the start-tuple. (separated by a comma)")
    ap.add_argument("-e", "--end", nargs="+", type=str, required=True,
                    help="Values of the end-tuple. (separated by a comma)")
    ap.add_argument("-a", "--pctA", type=float, default=Space.PCT_ASTEROIDS,
                    help="Percentage of asteroids. Default: {}".format(
                        Space.PCT_ASTEROIDS))
    ap.add_argument("-g", "--pctGW", type=float, default=Space.PCT_GRAVITY_WELLS,
                    help="Percentage of gravity wells. Default: {}".format(
                        Space.PCT_GRAVITY_WELLS))

    args = ap.parse_args()

    # dirty, but works pretty fine.
    start, end = map(eval, map(''.join, (args.start, args.end)))

    Space.PCT_ASTEROIDS = args.pctA
    Space.PCT_GRAVITY_WELLS = args.pctGW

    s = Space(args.n, start, end)
    s.run()
    print(s)

if __name__ == '__main__':
    main()