Find the longest path, avoiding obstacles in a 2D plane

Python 3, 2619 bytes (90 LOC), ~6 seconds (20x20)

 

#!/usr/bin/env python

import networkx as nx

class input(object):
    def __init__(self,world_string):
        rows=world_string.split("\n")
        column_count=len(rows[0])
        blocked_cells=[]
        x=0
        y=-1
        for row in rows:
            if len(row)>column_count:
                column_count=len(row)
            y+=1
            for column in row:
                if column=='1':
                    blocked_cells.append((y,x))
                x+=1
            x=0
        self.matrix=world(len(rows),column_count)
        self.block_graph(blocked_cells)
        self.matrix.add_sink()

    def block_graph(self,block_list):
        for cell in block_list:
            self.matrix.block_cell(cell)


class world(object):
    SINK="END"

    def __init__(self, rows=3, columns=3):
        self.graph=nx.grid_2d_graph(rows, columns)
        for e in self.graph.edges():
            self.graph[e[0]][e[1]]["weight"]=-1.0

    def block_cell(self,node):
        neighbours=list(self.graph[node].keys())
        for linked_node in neighbours:
            self.graph.remove_edge(node,linked_node)

    def add_sink(self):
        matrix=self.graph.nodes()[:]
        self.graph.add_node(world.SINK)
        for source_cell in matrix:
            self.graph.add_edge(source_cell, world.SINK, weight=1.0)


class algorithm(object):
    SOURCE=(0,0)
    def find_path(graph):
        def _heuristic(current, target):
            if current==target:return 0.0
            cost=nx.astar_path(graph, algorithm.SOURCE,current,lambda x,y:1)
            return -1 * len(cost)
        path=nx.astar_path(graph, algorithm.SOURCE, world.SINK, _heuristic)
        return path[:-1]

class output(object):
    directions={
        ( 1,  0)  : "n",
        (-1,  0)  : "s",
        ( 0,  1)  : "w",
        ( 0, -1)  : "e"
    }

    def edge_to_direction(source_node, dest_node):
        row_delta=source_node[0]-dest_node[0]
        column_delta=source_node[1]-dest_node[1]
        return output.directions[(row_delta, column_delta)]

    def path_to_directions(path):
        result=""
        for step in range(len(path)-1):
            result+=output.edge_to_direction(path[step],path[step+1])
        return result

    def simplify_directions(directions):
        directions+="\0"
        count=0
        result=""
        last=""
        for d in directions:
            if d!=last or d is "\0":
                result+="{} {},".format(last, count)
                count=0
                last=""
            if count==0:
                last=d
                count=1
                continue
            if d==last:
                count+=1
        return result[3:-1]



if __name__=='__main__':
    contents="010\n000\n100"    #read from file?

    data=input(contents).matrix.graph
    result_path=algorithm.find_path(data)
    directions=output.path_to_directions(result_path)
    directions=output.simplify_directions(directions)
    print(directions+"\n")
    print(str(result_path)[1:-1].replace('), (',') --> (').replace(', ',','))
 

 

Performance

I ran this solution (on my old Core i3 laptop) on the 20x20 'performance' example input and it ran in around ~6 seconds (of course, YMMV). I am SURE there are ways to do this faster, probably by orders of magnitude. However, I didn't feel like re-writing my own A* algorithm in assembly and renting some time slices on a super computer!

About this Code

_{The Idea}

The idea for this approach comes from my answer over here in Code Review. You can also read a little bit more about it and the end of my answer here.

_Dependencies

As you may have notice by the (rather prominent) line import networkx as nx - this code relies upon the Python NetworkX module to function. So do >pip install networkx if you get import errors when running.

_{Breakdown of Solution Elements by Lines of Code}

I also thought it would be interesting (and it was), after Don Muesli's comment (particularly the part "a significant part of the efffort^[sic] is formatting the output"), to examine how much of the code is for various things.

      Breakdown:

• 39 lines (or 43.33%) of the lines of code in the program are concerned with parsing the input and constructing/weighting the graph data structure.

• 37 lines (approx. 41%) directly relate solely to displaying and formatting the desired output!

• 5 lines (5.5%) are 'other' stuff, which relates to running the program (shebang line, imports, the if __name__=="__main__"..., etc).

• And 9 (yes.. nine) lines of code (or just 10%) actually relates to the algorithm usage.

      Obligatory Pie Chart:

                 

---

About the Approach

As I mentioned above, most of the idea for this approach comes from my answer over on Code Review regarding this problem.

The process itself is relatively straightforward:

1. Transform the given matrix into an undirected graph data structure
2. Annotate (i.e. add weights) the edges of that graph
3. Add a "sink" node - to be used as a search target
4. Add (weighted) edges between all nodes and the sink node
5. Use a Graph Search Algorithm (in this case A*)

 

So, taking the 3x3 matrix from the question for example. The transformation into a graph would yield something like the following:

(Note: the 'blocked' nodes do not have any edges)

Step 2; imagine each green line in the above picture has a weight of -1.

Next, for step 3 and 4 together (I didn't want to have to make another picture), take a look at the following graph:

And again imagine the edges are weighted, only red lines are weighted +1.

We can then apply the A-star algorithm from the NetworkX library to this graph, using the custom heuristic function. This makes the search algorithm score paths in an inverse manner (longest path rather than shortest). And the longest path will be the one that visits the most cells of the problem matrix!