#!/usr/bin/env python3
import re
import sys
import itertools
import numpy as np
import networkx as nx
from matplotlib import pyplot
from pprint import pprint
INPUTS = [ 'd15-input.txt',
        'd15-input-example1.txt', 'd15-input-example2.txt', 'd15-input-example3.txt',
        'd15-input-example4.txt', 'd15-input-example5.txt', 'd15-input-example6.txt',
        'd15-input-test1.txt', 'd15-input-test2.txt', 'd15-input-test3.txt',
        'd15-input-test4.txt', 'd15-input-test5.txt', 'd15-input-test6.txt',
        'd15-input-test7.txt', ]

DEBUG = False
DEBUG_STEP = False
INPUT = INPUTS[13] if DEBUG else INPUTS[0]

# ------------------------------------------------
# constants and global state
# ------------------------------------------------
units_max = 1000
units_re = r'([GE])'
units_hp = {'G': 200, 'E': 200}
units_ap = {'G': 3, 'E': 3}

# ------------------------------------------------
# helpers
# ------------------------------------------------
hr = lambda s: ('--- %s ' % s).ljust(70, '-')

class Unit:
    def __init__(self, upos, utype, board):
        self.board = board
        self.i, self.j = upos
        self.type = utype
        self.hp = units_hp[self.type]
        self.ap = units_ap[self.type]
        self.id = next(self.board.units_id[self.type])

    def __str__(self):
        return '%s[%s, hp=%03d, ap=%d]' % (
                self.uid, self.pos, self.hp, self.ap)

    def __repr__(self):
        return self.__str__()

    def __lt__(self, other):
        return (self.i, self.j) < (other.i, other.j)

    @property
    def uid(self):
        return '%s%d' % (self.type, self.id)

    @property
    def pos(self):
        return (self.i, self.j)

    @property
    def posxy(self):
        return (self.j, self.i)

    @property
    def neighbors(self):
        ''' Returns neighbouring tiles coordinates in reading order.
            Neighbours returned are guaranteed to be available for movement.
        '''
        n = [ (self.i-1, self.j), (self.i, self.j-1), (self.i, self.j+1), (self.i+1, self.j), ]
        return list(filter(self.board.is_open, n))

    @property
    def enemies(self):
        return filter(lambda u: u.type != self.type, self.board.units)

    def add_to_graph(self):
        ''' Add the position of the unit to the graph as open tile.
        '''
        self.board.graph.add_node(self.pos) # needed in case unit is surrounded
        for n in self.neighbors:
            if self.board.typeof(n) != '#':
                self.board.graph.add_edge(self.pos, n, weight=1)

    def remove_from_graph(self):
        ''' Remove the position of the unit from the graph.
        '''
        self.board.graph.remove_node(self.pos)

    def get_targets(self):
        ''' Returns the movement and attack targets for this unit.
            Movement targets are tiles that have an enemy in attack range.
            Attack targets are enemy units currently in range.
        '''
        move_targets = set()
        attack_targets = []

        # temporarily remove us from board
        # this allows our current tile to be listed as neighbor of enemies
        self.board.board[self.i, self.j] = '.'

        for e in self.enemies:
            en = list(e.neighbors)
            move_targets.update(en)
            if self.pos in en:
                attack_targets.append(e)

        self.board.board[self.i, self.j] = self.type
        return (move_targets, attack_targets)

    def move(self, move_to):
        print('%s moved to %s' % (self, move_to), file=sys.stderr)

        # make sure node is in the graph
        if self.pos not in self.board.graph.nodes:
            self.add_to_graph()

        # mark position as open on the board
        self.board.board[self.i, self.j] = '.'

        # move to new position and update graph/board
        self.i, self.j = move_to
        self.remove_from_graph()
        self.board.board[self.i, self.j] = self.type

    def attack(self, other):
        other.hp -= self.ap
        if other.hp <= 0:
            print('%s killed %s' % (self, other), file=sys.stderr)

            # add unit to graph as open tile
            assert(other.pos not in self.board.graph.nodes)
            other.add_to_graph()

            # remove unit from board and units list
            self.board.board[other.i, other.j] = '.'
            self.board.units.remove(other)
        else:
            print('%s attacked %s' % (self, other), file=sys.stderr)

    def action(self):
        # add to board and compute all distances to open tiles
        self.add_to_graph()
        dists = nx.single_source_shortest_path_length(self.board.graph, self.pos)

        # get move/attack targets
        move_targets, attack_targets = self.get_targets()
        if attack_targets:
            hpmin = min([e.hp for e in attack_targets])
            tgt_a = min([e for e in attack_targets if e.hp == hpmin])
            self.attack(tgt_a)
            self.remove_from_graph()
            return

        # keep only target tiles in distances dict
        dists = { p: d for p, d in dists.items() if p in move_targets }

        # blocked
        if not dists:
            print('%s skipped turn' % self, file=sys.stderr)
            self.remove_from_graph()
            return

        # find the minimum distance
        mindist = min(dists.values())

        # keep only target tiles with the minimum distance
        dists = { p: d for p, d in dists.items() if d == mindist }

        # get the first target tile in reading order
        tgt_m = min(dists)

        # there may be different paths to the target tile!
        tgt_path = None
        for n in self.neighbors:
            p = nx.shortest_path(self.board.graph, n, tgt_m)
            if len(p) == mindist:
                tgt_path = p
                break
        assert(tgt_path is not None)

        # move - no need to remove from board
        self.move(tgt_path[0])

        # if mindist was 1, we are now in range
        if mindist == 1:
            move_targets, attack_targets = self.get_targets()
            hpmin = min([e.hp for e in attack_targets])
            tgt_a = min([e for e in attack_targets if e.hp == hpmin])
            self.attack(tgt_a)
            return

class Board:
    def __init__(self, inputf):
        # read dimensions
        ldims = []
        with open(inputf) as f:
            for ln, line in enumerate(f):
                ldims.append( (ln, len(line.rstrip())) )
        self.dims = (max([d[0] for d in ldims])+1, max([d[1] for d in ldims]))

        # reset unit ids
        self.units_id = {utype: iter(range(units_max)) for utype in units_hp}

        # read data
        self.board = np.empty(self.dims, dtype=np.unicode)
        self.units = []
        with open(inputf) as f:
            for ln, line in enumerate(f):
                line = line.rstrip()
                if not line.lstrip(): continue
                elif line.lstrip().startswith('//'): continue
                self.board[ln] = list(line.ljust(self.dims[1]))
                for um in re.finditer(units_re, line):
                    upos, utype = (ln, um.span()[0]), um.group(0)
                    u = Unit(upos, utype, self)
                    self.board[u.i, u.j] = u.type
                    self.units.append(u)
        self.units.sort()

        # initialize graph
        # Note: SciPy also has support for shortest path algorithms.
        #       However, it requires explicit mapping of nodes to arithmetic
        #       labels, and representing the graph as a NxN csr matrix.
        #       Updating the matrix is also a pain because of the explicit
        #       mapping to arithmetic labels.
        #       Networkx makes it much simpler to maintain a consistent
        #       state of the simulation.
        self.init_graph()

        # initialize other state
        self.round = 0

    def typeof(self, p):
        ''' Returns type of tile in coords p.
        '''
        return self.board[p[0], p[1]]

    def in_bounds(self, p):
        ''' Returns if coords p are in bounds.
        '''
        return (0 <= p[0] < self.dims[0]) and (0 <= p[1] < self.dims[1])

    def is_open(self, p):
        ''' Returns if coords p are in bounds and open.
        '''
        return self.in_bounds(p) and self.typeof(p) == '.'

    def init_graph(self):
        self.graph = nx.Graph()
        neighbors = ((-1, 0), (0, -1), (0, 1), (1, 0))

        for i, j in itertools.product(range(self.dims[0]), range(self.dims[1])):
            p = (i, j)
            if self.board[i, j] != '.':
                continue
            for di, dj in neighbors:
                n = (i + di, j + dj)
                if self.in_bounds(n) and self.typeof(n) == '.':
                    self.graph.add_edge(p, n, weight=1)

    def __repr__(self):
        return '%s<%dx%d, %d units: %s>' % (self.__class__.__name__,
                self.dims[1], self.dims[0], len(self.units), self.units)

    def __str__(self):
        return '\n'.join(np.apply_along_axis(lambda s: ''.join(s), axis=1, arr=self.board))

    def count(self, utype=None):
        if utype == None:
            return len(self.units)
        else:
            return len([u for u in self.units if u.type == utype])

    def plot(self):
        # https://matplotlib.org/examples/color/colormaps_reference.html
        wcolor = 255    # wall
        scolor = 0      # space
        Ecolor = 66     # elf
        Gcolor = 110    # gnome
        rcolor = 220    # in range

        imdata = np.full(self.board.shape, wcolor, dtype=np.uint8)
        #----------------------
        coords = np.where(self.board == '.')
        imdata[coords] = scolor
        #----------------------
        inrange = set()
        for u in self.units:
            inrange.update(u.neighbors)
        coords = tuple(zip(*inrange))
        imdata[coords] = rcolor
        #----------------------
        coords = np.where(self.board == 'G')
        imdata[coords] = Gcolor
        #----------------------
        coords = np.where(self.board == 'E')
        imdata[coords] = Ecolor
        #----------------------
        img = pyplot.imshow(imdata, cmap='Paired')
        img.get_figure().suptitle(self.score, fontfamily='monospace')
        pyplot.show()

    @property
    def finished(self):
        return len(set([u.type for u in self.units])) < 2

    @property
    def score(self):
        s = {}
        for u in self.units:
            if u.type not in s:
                s[u.type] = 0
            s[u.type] += u.hp
        return '\n'.join([ '%s(%03d)(%02d):[%3d x %4d = %6d]' %
            (k, units_hp[k], units_ap[k], self.round, v, v*self.round)
            for k, v in sorted(s.items())])

    def tick(self, quiet=False):
        print(hr('round %04d' % self.round), file=sys.stderr)

        # sort units
        self.units.sort()

        # activate units - use a copy as units may die while looping
        for u in self.units.copy():
            if (u.hp <= 0):
                continue
            if self.finished:
                print(self.score)
                print('')
                self.plot()
                return
            if DEBUG_STEP:
                self.plot()
            u.action()

        # update after tick
        if not quiet:
            self.plot()
        self.round += 1

# ------------------------------------------------
# part 1
# ------------------------------------------------
b = Board(INPUT)
b.plot()
while not b.finished:
    b.tick(quiet=True)

# ------------------------------------------------
# part 2
# ------------------------------------------------
units_ap_bak = units_ap.copy()
while True:
    units_ap['E'] += 1
    b = Board(INPUT)
    b.plot()
    ne = b.count('E')
    while not b.finished:
        b.tick(quiet=True)
        if b.count('E') < ne:
            print('Elf killed. Aborting simulation at round %d.' % (b.round), file=sys.stderr)
            b.plot()
            break
    if b.finished:
        break
units_ap = units_ap_bak

# vim:sts=4:sw=4:et:

#!/usr/bin/env python3
import re
import sys
import itertools
import numpy as np
import networkx as nx
from matplotlib import pyplot
from pprint import pprint
INPUTS = [ 'd15-input.txt',
        'd15-input-example1.txt', 'd15-input-example2.txt', 'd15-input-example3.txt',
        'd15-input-example4.txt', 'd15-input-example5.txt', 'd15-input-example6.txt',
        'd15-input-test1.txt', 'd15-input-test2.txt', 'd15-input-test3.txt',
        'd15-input-test4.txt', 'd15-input-test5.txt', 'd15-input-test6.txt',
        'd15-input-test7.txt', ]

DEBUG = False
DEBUG_STEP = False
INPUT = INPUTS[13] if DEBUG else INPUTS[0]

# ------------------------------------------------
# constants and global state
# ------------------------------------------------
units_max = 1000
units_re = r'([GE])'
units_hp = {'G': 200, 'E': 200}
units_ap = {'G': 3, 'E': 3}

# ------------------------------------------------
# helpers
# ------------------------------------------------
hr = lambda s: ('--- %s ' % s).ljust(70, '-')

class Unit:
    def __init__(self, upos, utype, board):
        self.board = board
        self.i, self.j = upos
        self.type = utype
        self.hp = units_hp[self.type]
        self.ap = units_ap[self.type]
        self.id = next(self.board.units_id[self.type])

    def __str__(self):
        return '%s[%s, hp=%03d, ap=%d]' % (
                self.uid, self.pos, self.hp, self.ap)

    def __repr__(self):
        return self.__str__()

    def __lt__(self, other):
        return (self.i, self.j) < (other.i, other.j)

    @property
    def uid(self):
        return '%s%d' % (self.type, self.id)

    @property
    def pos(self):
        return (self.i, self.j)

    @property
    def posxy(self):
        return (self.j, self.i)

    @property
    def neighbors(self):
        ''' Returns neighbouring tiles coordinates in reading order.
            Neighbours returned are guaranteed to be available for movement.
        '''
        n = [ (self.i-1, self.j), (self.i, self.j-1), (self.i, self.j+1), (self.i+1, self.j), ]
        return list(filter(self.board.is_open, n))

    @property
    def enemies(self):
        return filter(lambda u: u.type != self.type, self.board.units)

    def add_to_graph(self):
        ''' Add the position of the unit to the graph as open tile.
        '''
        self.board.graph.add_node(self.pos) # needed in case unit is surrounded
        for n in self.neighbors:
            if self.board.typeof(n) != '#':
                self.board.graph.add_edge(self.pos, n, weight=1)

    def remove_from_graph(self):
        ''' Remove the position of the unit from the graph.
        '''
        self.board.graph.remove_node(self.pos)

    def get_targets(self):
        ''' Returns the movement and attack targets for this unit.
            Movement targets are tiles that have an enemy in attack range.
            Attack targets are enemy units currently in range.
        '''
        move_targets = set()
        attack_targets = []

        # temporarily remove us from board
        # this allows our current tile to be listed as neighbor of enemies
        self.board.board[self.i, self.j] = '.'

        for e in self.enemies:
            en = list(e.neighbors)
            move_targets.update(en)
            if self.pos in en:
                attack_targets.append(e)

        self.board.board[self.i, self.j] = self.type
        return (move_targets, attack_targets)

    def move(self, move_to):
        print('%s moved to %s' % (self, move_to), file=sys.stderr)

        # make sure node is in the graph
        if self.pos not in self.board.graph.nodes:
            self.add_to_graph()

        # mark position as open on the board
        self.board.board[self.i, self.j] = '.'

        # move to new position and update graph/board
        self.i, self.j = move_to
        self.remove_from_graph()
        self.board.board[self.i, self.j] = self.type

    def attack(self, other):
        other.hp -= self.ap
        if other.hp <= 0:
            print('%s killed %s' % (self, other), file=sys.stderr)

            # add unit to graph as open tile
            assert(other.pos not in self.board.graph.nodes)
            other.add_to_graph()

            # remove unit from board and units list
            self.board.board[other.i, other.j] = '.'
            self.board.units.remove(other)
        else:
            print('%s attacked %s' % (self, other), file=sys.stderr)

    def action(self):
        # add to board and compute all distances to open tiles
        self.add_to_graph()
        dists = nx.single_source_shortest_path_length(self.board.graph, self.pos)

        # get move/attack targets
        move_targets, attack_targets = self.get_targets()
        if attack_targets:
            hpmin = min([e.hp for e in attack_targets])
            tgt_a = min([e for e in attack_targets if e.hp == hpmin])
            self.attack(tgt_a)
            self.remove_from_graph()
            return

        # keep only target tiles in distances dict
        dists = { p: d for p, d in dists.items() if p in move_targets }

        # blocked
        if not dists:
            print('%s skipped turn' % self, file=sys.stderr)
            self.remove_from_graph()
            return

        # find the minimum distance
        mindist = min(dists.values())

        # keep only target tiles with the minimum distance
        dists = { p: d for p, d in dists.items() if d == mindist }

        # get the first target tile in reading order
        tgt_m = min(dists)

        # there may be different paths to the target tile!
        tgt_path = None
        for n in self.neighbors:
            p = nx.shortest_path(self.board.graph, n, tgt_m)
            if len(p) == mindist:
                tgt_path = p
                break
        assert(tgt_path is not None)

        # move - no need to remove from board
        self.move(tgt_path[0])

        # if mindist was 1, we are now in range
        if mindist == 1:
            move_targets, attack_targets = self.get_targets()
            hpmin = min([e.hp for e in attack_targets])
            tgt_a = min([e for e in attack_targets if e.hp == hpmin])
            self.attack(tgt_a)
            return

class Board:
    def __init__(self, inputf):
        # read dimensions
        ldims = []
        with open(inputf) as f:
            for ln, line in enumerate(f):
                ldims.append( (ln, len(line.rstrip())) )
        self.dims = (max([d[0] for d in ldims])+1, max([d[1] for d in ldims]))

        # reset unit ids
        self.units_id = {utype: iter(range(units_max)) for utype in units_hp}

        # read data
        self.board = np.empty(self.dims, dtype=np.unicode)
        self.units = []
        with open(inputf) as f:
            for ln, line in enumerate(f):
                line = line.rstrip()
                if not line.lstrip(): continue
                elif line.lstrip().startswith('//'): continue
                self.board[ln] = list(line.ljust(self.dims[1]))
                for um in re.finditer(units_re, line):
                    upos, utype = (ln, um.span()[0]), um.group(0)
                    u = Unit(upos, utype, self)
                    self.board[u.i, u.j] = u.type
                    self.units.append(u)
        self.units.sort()

        # initialize graph
        # Note: SciPy also has support for shortest path algorithms.
        #       However, it requires explicit mapping of nodes to arithmetic
        #       labels, and representing the graph as a NxN csr matrix.
        #       Updating the matrix is also a pain because of the explicit
        #       mapping to arithmetic labels.
        #       Networkx makes it much simpler to maintain a consistent
        #       state of the simulation.
        self.init_graph()

        # initialize other state
        self.round = 0

    def typeof(self, p):
        ''' Returns type of tile in coords p.
        '''
        return self.board[p[0], p[1]]

    def in_bounds(self, p):
        ''' Returns if coords p are in bounds.
        '''
        return (0 <= p[0] < self.dims[0]) and (0 <= p[1] < self.dims[1])

    def is_open(self, p):
        ''' Returns if coords p are in bounds and open.
        '''
        return self.in_bounds(p) and self.typeof(p) == '.'

    def init_graph(self):
        self.graph = nx.Graph()
        neighbors = ((-1, 0), (0, -1), (0, 1), (1, 0))

        for i, j in itertools.product(range(self.dims[0]), range(self.dims[1])):
            p = (i, j)
            if self.board[i, j] != '.':
                continue
            for di, dj in neighbors:
                n = (i + di, j + dj)
                if self.in_bounds(n) and self.typeof(n) == '.':
                    self.graph.add_edge(p, n, weight=1)

    def __repr__(self):
        return '%s<%dx%d, %d units: %s>' % (self.__class__.__name__,
                self.dims[1], self.dims[0], len(self.units), self.units)

    def __str__(self):
        return '\n'.join(np.apply_along_axis(lambda s: ''.join(s), axis=1, arr=self.board))

    def count(self, utype=None):
        if utype == None:
            return len(self.units)
        else:
            return len([u for u in self.units if u.type == utype])

    def plot(self):
        # https://matplotlib.org/examples/color/colormaps_reference.html
        wcolor = 255    # wall
        scolor = 0      # space
        Ecolor = 66     # elf
        Gcolor = 110    # gnome
        rcolor = 220    # in range

        imdata = np.full(self.board.shape, wcolor, dtype=np.uint8)
        #----------------------
        coords = np.where(self.board == '.')
        imdata[coords] = scolor
        #----------------------
        inrange = set()
        for u in self.units:
            inrange.update(u.neighbors)
        coords = tuple(zip(*inrange))
        imdata[coords] = rcolor
        #----------------------
        coords = np.where(self.board == 'G')
        imdata[coords] = Gcolor
        #----------------------
        coords = np.where(self.board == 'E')
        imdata[coords] = Ecolor
        #----------------------
        img = pyplot.imshow(imdata, cmap='Paired')
        img.get_figure().suptitle(self.score, fontfamily='monospace')
        pyplot.show()

    @property
    def finished(self):
        return len(set([u.type for u in self.units])) < 2

    @property
    def score(self):
        s = {}
        for u in self.units:
            if u.type not in s:
                s[u.type] = 0
            s[u.type] += u.hp
        return '\n'.join([ '%s(%03d)(%02d):[%3d x %4d = %6d]' %
            (k, units_hp[k], units_ap[k], self.round, v, v*self.round)
            for k, v in sorted(s.items())])

    def tick(self, quiet=False):
        print(hr('round %04d' % self.round), file=sys.stderr)

        # sort units
        self.units.sort()

        # activate units - use a copy as units may die while looping
        for u in self.units.copy():
            if (u.hp <= 0):
                continue
            if self.finished:
                print(self.score)
                print('')
                self.plot()
                return
            if DEBUG_STEP:
                self.plot()
            u.action()

        # update after tick
        if not quiet:
            self.plot()
        self.round += 1

# ------------------------------------------------
# part 1
# ------------------------------------------------
b = Board(INPUT)
b.plot()
while not b.finished:
    b.tick(quiet=True)

# ------------------------------------------------
# part 2
# ------------------------------------------------
units_ap_bak = units_ap.copy()
while True:
    units_ap['E'] += 1
    b = Board(INPUT)
    b.plot()
    ne = b.count('E')
    while not b.finished:
        b.tick(quiet=True)
        if b.count('E') < ne:
            print('Elf killed. Aborting simulation at round %d.' % (b.round), file=sys.stderr)
            b.plot()
            break
    if b.finished:
        break
units_ap = units_ap_bak

# vim:sts=4:sw=4:et:

#!/usr/bin/env python3 # ------------------------------------------------ # constants and global state # ------------------------------------------------ # ------------------------------------------------ # helpers # ------------------------------------------------ Returns neighbouring tiles coordinates in reading order.             Neighbours returned are guaranteed to be available for movement. Add the position of the unit to the graph as open tile. # needed in case unit is surrounded Remove the position of the unit from the graph. Returns the movement and attack targets for this unit.             Movement targets are tiles that have an enemy in attack range.             Attack targets are enemy units currently in range. # temporarily remove us from board # this allows our current tile to be listed as neighbor of enemies # make sure node is in the graph # mark position as open on the board # move to new position and update graph/board # add unit to graph as open tile # remove unit from board and units list # add to board and compute all distances to open tiles # get move/attack targets # keep only target tiles in distances dict # blocked # find the minimum distance # keep only target tiles with the minimum distance # get the first target tile in reading order # there may be different paths to the target tile! # move - no need to remove from board # if mindist was 1, we are now in range # read dimensions # reset unit ids # read data # initialize graph # Note: SciPy also has support for shortest path algorithms. #       However, it requires explicit mapping of nodes to arithmetic #       labels, and representing the graph as a NxN csr matrix. #       Updating the matrix is also a pain because of the explicit #       mapping to arithmetic labels. #       Networkx makes it much simpler to maintain a consistent #       state of the simulation. # initialize other state Returns type of tile in coords p. Returns if coords p are in bounds. Returns if coords p are in bounds and open. # https://matplotlib.org/examples/color/colormaps_reference.html # wall # space # elf # gnome # in range #---------------------- #---------------------- #---------------------- #---------------------- #---------------------- # sort units # activate units - use a copy as units may die while looping # update after tick # ------------------------------------------------ # part 1 # ------------------------------------------------ # ------------------------------------------------ # part 2 # ------------------------------------------------ # vim:sts=4:sw=4:et: