Doodlebugs

hw12.py

#!/usr/bin/env python3
import itertools
import sys
from typing import NamedTuple, List, Optional, Callable, Iterable, Collection
from random import Random
from argparse import ArgumentParser

_DOODLEBUG_GESTATION = 8
_ANT_GESTATION = 3


class RandGen(object):

    def randrange(self, min_inclusive: int, max_exclusive: int) -> int:
        raise NotImplementedError()

    def choice(self, items: Collection):
        if not isinstance(items, list):
            items = list(items)
        idx = self.randrange(0, len(items))
        return items[idx]



class RandomRandGen(RandGen):

    def __init__(self, rng: Random):
        self.rng = rng

    def randrange(self, min_inclusive: int, max_exclusive: int) -> int:
        return self.rng.randrange(min_inclusive, max_exclusive)


class Size(NamedTuple):

    nrows: int
    ncols: int

    def ncells(self):
        return self.nrows * self.ncols


class Delta(NamedTuple):

    rows: int
    cols: int


class Position(object):

    def __init__(self, row, col):
        self.row = row
        self.col = col

    def translate(self, delta: Delta):
        self.row += delta.rows
        self.col += delta.cols
        return self

    def copy(self) -> 'Position':
        return Position(self.row, self.col)

    def update(self, other: 'Position'):
        self.row = other.row
        self.col = other.col

    def __str__(self):
        return str(self.to_tuple())

    def __eq__(self, other):
        return isinstance(other, Position) and other.row == self.row and other.col == self.col

    def to_tuple(self):
        return self.row, self.col


DIRECTIONS = (
                             Delta(-1, 0),
             Delta(0, -1),                  Delta(0, 1),
                             Delta( 1, 0)
            )


class Organism(object):

    def __init__(self, gestation: int, position: Position):
        self.position = position
        assert position
        self.ticks_since_bred = 0
        self.gestation = gestation
        assert gestation

    def is_doodlebug(self):
        raise NotImplementedError("subclass must implement")

    def is_ant(self):
        raise NotImplementedError("subclass must implement")

    def is_starved(self, nticks: int):
        raise NotImplementedError("subclass must implement")

    def move(self, world: 'World', randgen: RandGen):
        delta = randgen.choice(DIRECTIONS)
        pos = self.position.copy()
        pos.translate(delta)
        if world.contains(pos) and not world.occupied(pos):
            self.position.update(pos)

    def birth(self, position: Position):
        raise NotImplementedError("subclass must implement")

    def breed(self, world: 'World', randgen: RandGen):
        self.ticks_since_bred += 1
        if self.ticks_since_bred >= self.gestation:
            unoccupied = []
            for delta in DIRECTIONS:
                position = self.position.copy().translate(delta)
                if world.contains(position) and not world.occupied(position):
                    unoccupied.append(position)
            if unoccupied:
                position = randgen.choice(unoccupied)
                world.spawn(self.birth(position))
                self.ticks_since_bred = 0
                return

    def __str__(self):
        return f"{type(self)}<position={self.position}>"

    def tick(self, world: 'World', randgen: RandGen):
        self.move(world, randgen)
        self.breed(world, randgen)


class Ant(Organism):

    def __init__(self, position: Position):
        super().__init__(_ANT_GESTATION, position)

    def is_doodlebug(self):
        return False

    def is_ant(self):
        return True

    def birth(self, position: Position):
        return Ant(position)

    def is_starved(self, nticks: int):
        return False


class Doodlebug(Organism):

    def __init__(self, position: Position):
        super().__init__(_DOODLEBUG_GESTATION, position)
        self.ticks_since_fed = 0

    def is_doodlebug(self):
        return True

    def is_ant(self):
        return False

    def birth(self, position: Position):
        return Doodlebug(position)

    def feed(self, world: 'World', randgen: RandGen) -> bool:
        adjacent_positions = [self.position.copy().translate(delta) for delta in DIRECTIONS]
        ant_positions = []
        for position in adjacent_positions:
            if world.is_ant(position):
                ant_positions.append(position)
        if ant_positions:
            position = randgen.choice(ant_positions)
            world.kill(position)
            self.position.update(position)
            self.ticks_since_fed = 0
            return True
        self.ticks_since_fed += 1
        return False

    def move(self, world: 'World', randgen: RandGen):
        fed = self.feed(world, randgen)
        if not fed:
            super().move(world, randgen)

    def is_starved(self, nticks: int):
        return self.ticks_since_fed >= 3


class World(object):

    def __init__(self, size: Size, organisms: List[Organism]):
        self.size = size
        self.organisms = organisms
        self.nticks = 0
        self._check()

    @staticmethod
    def create(size: Size, ndoodlebugs: int, nants: int, randgen: RandGen) -> 'World':
        positions = [Position(row, col) for row, col in itertools.product(range(size.nrows), range(size.ncols))]
        assert (ndoodlebugs + nants) < len(positions)
        organisms = []
        def place(n: int, factory: Callable[[Position], Organism]):
            for i in range(n):
                positions_index = randgen.randrange(0, len(positions))
                position = positions[positions_index]
                organisms.append(factory(position))
                del positions[positions_index]
        place(ndoodlebugs, Doodlebug)
        place(nants, Ant)
        return World(size, organisms)

    def at(self, pos: Position) -> Optional[Organism]:
        for organism in self.organisms:
            if organism.position == pos:
                return organism

    def occupied(self, pos: Position) -> bool:
        return self.at(pos) is not None

    def spawn(self, organism: Organism):
        assert not self.occupied(organism.position)
        assert self.contains(organism.position), f"not in world: {organism.position}"
        self.organisms.append(organism)

    def kill(self, pos: Position):
        assert self.contains(pos), f"not in world: {pos}"
        index = None
        for i, organism in enumerate(self.organisms):
            if pos == organism.position:
                index = i
                break
        assert index is not None
        del self.organisms[index]

    def is_doodlebug(self, pos: Position):
        o = self.at(pos)
        return o and o.is_doodlebug()

    def is_ant(self, pos: Position):
        o = self.at(pos)
        return o and o.is_ant()

    def contains(self, pos: Position) -> bool:
        return 0 <= pos.row < self.size.nrows and 0 <= pos.col < self.size.ncols

    def count_ants(self) -> int:
        return sum([organism.is_ant() for organism in self.organisms])

    def all_ants(self) -> bool:
        return self.size.ncells() == self.count_ants()

    def count_doodlebugs(self) -> int:
        return sum([organism.is_doodlebug() for organism in self.organisms])

    def count(self) -> int:
        return len(self.organisms)

    def _check(self):
        positions = [o.position for o in self.organisms]
        position_tuples = set([p.to_tuple() for p in positions])
        assert len(position_tuples) == len(self.organisms), "expect unique positions"
        for p in positions:
            assert self.contains(p), f"expect position {p} in world"

    def tick(self, randgen: RandGen):
        self.nticks += 1
        # be sure to copy list before each set of iterations
        for organism in list(filter(lambda o: o.is_doodlebug(), self.organisms)):
            organism.tick(self, randgen)
        for organism in list(filter(lambda o: o.is_ant(), self.organisms)):
            organism.tick(self, randgen)
        starver_indexes = []
        for i in range(len(self.organisms)):
            if self.organisms[i].is_starved(self.nticks):
                starver_indexes.append(i)
        starver_indexes.reverse()
        for idx in starver_indexes:
            del self.organisms[idx]
        self._check()

    @staticmethod
    def render_cell(cell: Optional[Organism]):
        if cell is None: return '-'
        if cell.is_doodlebug(): return 'X'
        if cell.is_ant(): return 'o'
        raise ValueError("not a doodlebug or ant?: " + str(cell))

    def render(self) -> str:
        rows: List[List[Optional[Organism]]] = [[self.at(Position(row, col)) for col in range(self.size.ncols)] for row in range(self.size.nrows)]
        return "\n".join([''.join([World.render_cell(c) for c in row]) for row in rows])

    def __str__(self) -> str:
        return f"World<size={self.size},population={len(self.organisms)}>"


def main():
    parser = ArgumentParser(description="Run Doodlebugs simulation.")
    parser.add_argument("-r", "--num-rows", type=int, default=20, metavar="N", help="world height")
    parser.add_argument("-c", "--num-cols", type=int, default=20, metavar="N", help="world width")
    parser.add_argument("-d", "--num-doodlebugs", type=int, metavar="N", help="number of doodlebugs at start")
    parser.add_argument("-a", "--num-ants", type=int, metavar="N", help="number of ants at start")
    parser.add_argument("-p", "--pause", type=int, metavar="N", help="pause every N boards; use 0 to never pause")
    parser.add_argument("-s", "--seed", type=int, metavar="N", help="seed for random number generator")
    parser.add_argument("-m", "--max-ticks", type=int, metavar="N", help="stop after N ticks")
    args = parser.parse_args()
    size = Size(args.num_rows, args.num_cols)
    ndoodlebugs = args.num_doodlebugs
    if ndoodlebugs is None:
        ndoodlebugs = max(1, size.ncells() // 80)
    nants = args.num_ants
    if nants is None:
        nants = max(1, size.ncells() // 4)
    randgen = RandomRandGen(Random(args.seed))
    world = World.create(size, ndoodlebugs, nants, randgen)
    while args.max_ticks is None or world.nticks >= args.max_ticks:
        if args.pause and (world.nticks % args.pause == 0):
            print()
            print(world.nticks)
            print(world.render())
            input("Press enter to continue...")
        world.tick(randgen)
        if world.count() == 0:
            print("Apocalypse", file=sys.stderr)
            break
        if world.all_ants():
            print("I for one welcome our new ant overlords", file=sys.stderr)
            break
    print()
    print(world.nticks)
    print(world.render())
    return 0


if __name__ == '__main__':
    exit(main())

test_hw12.py

#!/usr/bin/env python3
from random import Random
from typing import Iterable
from unittest import TestCase

from hw12 import World, Size, Position, Doodlebug, Ant, RandGen, RandomRandGen

SEED = 12345

class KnownRandGen(RandGen):

    def __init__(self, numbers: Iterable[int]=None):
        self.iterator = (numbers or range(2 ** 64)).__iter__()

    def randrange(self, min_inclusive: int, max_exclusive: int) -> int:
        value = self.iterator.__next__()
        width = max_exclusive - min_inclusive
        offset = value % width
        return min_inclusive + offset


class WorldTest(TestCase):

    def test_init(self):
        world = World.create(Size(5, 5), 2, 10, RandomRandGen(Random(SEED)))
        self.assertEqual(2, world.count_doodlebugs())
        self.assertEqual(10, world.count_ants())

    def test_at(self):
        world = World.create(Size(5, 5), 0, 0, RandomRandGen(Random(SEED)))
        self.assertListEqual([], world.organisms)
        world.organisms.append(Doodlebug(Position(1, 1)))
        world.organisms.append(Ant(Position(2, 2)))
        o = world.at(Position(1, 1))
        self.assertIsNotNone(o)
        self.assertTrue(o.is_doodlebug())
        o = world.at(Position(2, 2))
        self.assertIsNotNone(o)
        self.assertTrue(o.is_ant())
        self.assertIsNone(world.at(Position(0, 0)))
        self.assertIsNone(world.at(Position(4, 4)))


    def test_render(self):
        world = World.create(Size(3, 3), 1, 2, RandomRandGen(Random(SEED)))
        rendering = world.render()
        self.assertNotEqual("---\n---\n---", rendering)
        x_count = sum([1 if 'X' == ch else 0 for ch in rendering])
        o_count = sum([1 if 'o' == ch else 0 for ch in rendering])
        self.assertEqual(1, x_count)
        self.assertEqual(2, o_count)


class AntTest(TestCase):

    def test_breed(self):
        r = RandomRandGen(Random(1))
        world = World.create(Size(10, 10), 0, 1, r)
        for i in range(0, 3):
            print(f"\n{world.render()}")
            self.assertEqual(1, world.count_ants())
            world.tick(r)
        for i in range(0, 3):
            print(f"\n{world.render()}")
            self.assertEqual(2, world.count_ants(), f"expect 2 ants at nticks={world.nticks}")
            world.tick(r)
        print(f"\n{world.render()}")
        self.assertEqual(4, world.count_ants(), f"expect 4 ants at nticks={world.nticks}")

    def test_move(self):
        rng = KnownRandGen()  # first move is UP
        world = World(Size(3, 3), [])
        world.spawn(Ant(Position(2, 2)))
        world.tick(rng)
        expect_ant = world.at(Position(1, 2))
        self.assertIsNotNone(expect_ant)
        self.assertTrue(world.is_ant(Position(1, 2)))
        expect_none = world.at(Position(2, 2))
        self.assertIsNone(expect_none)


class DoodlebugTest(TestCase):

    def test_starve_basic(self):
        r = KnownRandGen()
        world = World.create(Size(2, 2), 1, 0, r)
        for i in range(0, 3):
            self.assertEqual(1, world.count_doodlebugs())
            world.tick(r)
        self.assertEqual(0, world.count_doodlebugs(), f"expect starve at nticks={world.nticks}")

    def test_starve_make_space_available(self):
        self.fail("not yet implemented")

    def test_feed(self):
        r = RandomRandGen(Random(1))
        world = World.create(Size(3, 3), 1, 2, r)
        print(world.render())
        world.tick(r)
        print(world.render())
        self.assertEqual(1, world.count_ants(), "expect doodlebug to eat adjacent ant")