import os
import numpy as np

import constants

class Graph:
    '''State graph for level.'''
    def __init__(self, id, isWall, boxes, targets, man_row, man_col):
        self.man = (man_row, man_col)
        self.isWall = isWall
        self.targets = tuple(map(tuple, sorted(targets)))
        self.boxes = tuple(map(tuple, sorted(boxes)))
        self.diff = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Do not compute anything more than once.
        self.computed = {
            'simple_bfs': False,
            'state_bfs': False,
            'reverse_bfs': False,
            'area_bfs': False,
            'scc_bfs': False,
            'counter_intuitive': False,
            'astar': False,
            'good_tiles': False,
        }

        current_dir = os.getcwd()
        self.tmp_dir = os.path.join(current_dir, 'tmp', str(id))
        self.bin_dir = os.path.join(current_dir, 'bins', str(id))
        self.graph_dir = os.path.join(current_dir, 'graph', str(id))
        for dir in [self.tmp_dir, self.bin_dir, self.graph_dir]:
            if not os.path.exists(dir):
                os.makedirs(dir)
        self.input_file = os.path.join(self.tmp_dir, 'input.in')
        self.cpp_dir = os.path.join(current_dir, constants.CPP_DIR)
        self.graph_dot_file = os.path.join(self.graph_dir, 'graph.zip.dot')
        self.map_file = os.path.join(self.graph_dir, 'graph.zip.map')
        self.scc_graph_dot_file = os.path.join(self.graph_dir, 'scc_graph.zip.dot')

        # Create input file suitable as input for C++.
        with open(self.input_file, 'w') as out:
            out.write('%d %d\n' % (len(isWall[0]), len(isWall)))
            for row in isWall:
                out.write('%s\n' % ' '.join([str(int(x)) for x in row]))

            out.write('%d\n' % len(boxes))
            for r,c in boxes:
                out.write('%d %d\n' % (r,c))
            for r,c in targets:
                out.write('%d %d\n' % (r,c))

            out.write('%d %d\n' % (man_row, man_col))

        # Create and save state graph and graph of strongly connected components.
        self._create_graph()
        self._create_scc_graph()

    def _create_graph(self):
        '''Creates state graph and save it to a file.'''

        # If file already exists, do not create it again.
        if os.path.isfile(self.graph_dot_file):
            return

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.CREATE)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.CREATE)

        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s %s <%s' % (
            constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, self.map_file, self.input_file))

    def _create_scc_graph(self):
        '''Creates scc graph and save it to a file.'''

        # If file already exists, do not create it again.
        if os.path.isfile(self.scc_graph_dot_file):
            return

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.CREATE_SCC)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.CREATE_SCC)

        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s %s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, self.scc_graph_dot_file))

    def _simple_bfs(self):
        '''Compute number of reachable tiles.

            In the past, it also computed shortest path and reachable states count.
            Now we have faster ways to do it using Boost.
        '''
        if self.computed['simple_bfs']: return
        self.computed['simple_bfs'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.SIMPLE_BFS)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.SIMPLE_BFS)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.SIMPLE_BFS)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s <%s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.input_file, out_file))

        shortest, reachable_states_cnt, reachable_tile_cnt = None, None, None
        with open(out_file, 'r') as inp:
            try:
                shortest, reachable_states_cnt, reachable_tile_cnt = map(int, inp.readline().split())
            except:
                pass

        # self.shortest_path = shortest
        # self.reachable_states_count = reachable_states_cnt
        self.reachable_tile_count = reachable_tile_cnt

    def get_reachable_tile_count(self):
        '''Get number of reachable tiles.'''
        self._simple_bfs()
        return self.reachable_tile_count

    def _state_bfs(self):
        '''Run BFS on state graph to get the length of shortest path and number.'''
        if self.computed['state_bfs']: return
        self.computed['state_bfs'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.STATE_BFS)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.STATE_BFS)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.STATE_BFS)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, out_file))

        shortest, reachable_states_cnt = None, None
        with open(out_file, 'r') as inp:
            try:
                shortest, reachable_states_cnt = map(int, inp.readline().split())
            except:
                pass

        self.shortest_path = shortest
        self.reachable_states_count = reachable_states_cnt

    def get_reachable_states(self):
        '''Get number of reachable states.'''
        self._state_bfs()
        return self.reachable_states_count

    def get_shortest_path(self):
        '''Get the length of the shortest solution.'''
        self._state_bfs()
        return self.shortest_path

    def _reverse_state_bfs(self):
        '''Run BFS on transposed graph to get the number of viable states.'''
        if self.computed['reverse_bfs']: return
        self.computed['reverse_bfs'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.REVERSE_STATE_BFS)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.REVERSE_STATE_BFS)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.REVERSE_STATE_BFS)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, out_file))

        viable_states_count = None
        with open(out_file, 'r') as inp:
            try:
                viable_states_count, = map(int, inp.readline().split())
            except:
                pass

        self.viable_states_count = viable_states_count

    def get_viable_states_count(self):
        '''Get the number of viable states.'''
        self._reverse_state_bfs()
        return self.viable_states_count

    def _area_bfs(self):
        '''Get the minimum number of box pushes.

            Run Dijkstra's algorithm for finding the shortest path.
            Every edge has weight either 0 or 1, if the box moved during this step or not.
        '''
        if self.computed['area_bfs']: return
        self.computed['area_bfs'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.AREA_BFS)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.AREA_BFS)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.AREA_BFS)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, out_file))

        shortest = None
        with open(out_file, 'r') as inp:
            try:
                shortest, = map(int, inp.readline().split())
            except:
                pass

        self.shortest_boxes_path = shortest

    def get_shortest_boxes_path(self):
        '''Get the minimum number of pushes.'''
        self._area_bfs()
        return self.shortest_boxes_path

    def _scc_bfs(self):
        '''Run BFS on graphs of strongly connected components.'''
        if self.computed['scc_bfs']: return
        self.computed['scc_bfs'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.SCC_BFS)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.SCC_BFS)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.SCC_BFS)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.scc_graph_dot_file, out_file))

        shortest, scc_count = None, None
        with open(out_file, 'r') as inp:
            try:
                shortest, scc_count = map(int, inp.readline().split())
            except:
                pass

        self.shortest_path = shortest
        self.scc_count = scc_count

    def get_scc_count(self):
        '''Number of strongly connected components.'''
        self._scc_bfs()
        return self.scc_count

    def get_scc_shortest(self):
        '''Length of solution in graph of stronlgy connected components.'''
        self._scc_bfs()
        return self.shortest_path

    def _counter_intuitive_bfs(self):
        '''Get the minimum number of counter-intuitive steps along any shortest path.

            * run BFS to get the length of shortest path L
            * create set 'shortest_vertices' of nodes lying on any shortest path
                * initialize set with all winning states with distance L
                * traverse transposed graph to get all nodes closer and closer to the start
            * use this set to run Dijkstra's algorithm on the graph of nodes on some shortest path
                * weight of edges is either 0 or 1, depending on positiveness of min_pushes difference
        '''
        if self.computed['counter_intuitive']: return
        self.computed['counter_intuitive'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.COUNTER_INTUITIVE)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.COUNTER_INTUITIVE)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.COUNTER_INTUITIVE)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, out_file))

        shortest = None
        with open(out_file, 'r') as inp:
            try:
                shortest, = map(int, inp.readline().split())
            except:
                pass

        self.counter_intuitive_steps = shortest

    def get_counter_intuitive_steps(self):
        '''Get the minimum number of counter-intuitive steps along any shortest path.'''
        self._counter_intuitive_bfs()
        return self.counter_intuitive_steps

    def _astar(self):
        '''Run A* algorithm.'''
        if self.computed['astar']: return
        self.computed['astar'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.ASTAR)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.ASTAR)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.ASTAR)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, out_file))

        astar_states_count = None
        with open(out_file, 'r') as inp:
            try:
                astar_states_count, = map(int, inp.readline().split())
            except:
                pass

        self.astar_states_count = astar_states_count

    def get_astar_states_count(self):
        '''Get the number of states visited by A*.'''
        self._astar()
        return self.astar_states_count

    def _good_tiles(self):
        '''Traverse transposed graph to get the number of good tiles.

            Good tile means, that there exists a viable state, where the man stands on this tile.
        '''
        if self.computed['good_tiles']: return
        self.computed['good_tiles'] = True

        bin_file = os.path.join(self.bin_dir, '%s.run' % constants.GOOD_TILES)
        cpp_file = os.path.join(self.cpp_dir, '%s.cpp' % constants.GOOD_TILES)
        out_file = os.path.join(self.tmp_dir, '%s.out' % constants.GOOD_TILES)
        os.system(constants.CPP_COMPILE % (bin_file, cpp_file))
        os.system('%s %s %s %s >%s' % (constants.CPP_RUN_PREFIX, bin_file, self.graph_dot_file, self.map_file, out_file))

        good_boxes_tiles = None
        with open(out_file, 'r') as inp:
            try:
                good_boxes_tiles, = map(int, inp.readline().split())
            except:
                pass

        self.good_boxes_tiles = good_boxes_tiles

    def get_good_boxes_tiles(self):
        '''Get the number of good boxes tiles.'''
        self._good_tiles()
        return self.good_boxes_tiles
