PyCon X


2nd - 5th May 2019

Traversing Mazes the Pythonic Way and Other Algorithmic Adventures

Programming isn’t just about software architectures and object-oriented design; it is also about solving algorithmic problems efficiently, some of which are really hard [Hetland, 2010].

The way we decide to represent and to solve our problems (i.e., the data structure and the algorithm we use, respectively) has a great impact on the overall complexity of our solution.

In this scenario, graphs define a powerful mental (and mathematical) model to deal with many algorithmic problems: “if we can formulate a problem as one dealing with graphs, even if it doesn’t look like a graph problem, we are probably one step closer to solving it.” [Hetland, 2010].

Indeed, graphs constitute the building blocks for many (hard) problems. Thus, mastering graphs and graph algorithms (e.g., graph traversals) provides a jump start to deal with many other problems, such as finding the shortest path to get out from a dungeon in a D&D story [^1].

With particular considerations to the authoritative books on this subject (such as the classics by T. Cormen and S.S. Skiena) for the theoretical part (actually intended to be very limited and mostly referenced), this talk aims at providing an overview of graphs and main graph-based algorithms for Python programmers.

The general outline of the talk will cover the following topics:

  • Implementing Graphs and Trees;
  • “DRY” Algorithms
    • “Memoization” and “Dynamic Programming”
  • “Mazes” Traversals and Search
    • Graph Traversals
    • Shortest Path Algorithms

The main goal of the talk is to analyse how one of the most fundamental (data) structure of “ADS” university classes, may be handled (and implemented) in a very pythonic way, in accordance with the Zen of Python (e.g., beautiful is better than ugly, simple is better than complex, readability counts).

To this end, code examples and case studies will be presented during the talk to encourage the discussion and to stimulate the attendees to come up with different solutions.

Very basic math skills are required, together with familiarity with programming in general and with Python in particular.

Do you have some questions on this talk?

New comment