text:
from random import choice
from typing import cast, Optional

from algorithms.base_algorithm import Algorithm

from base.grid import Grid
from base.cell import Cell

class HuntAndKill(Algorithm):
    """
    Hunt-and-Kill algorithm picks a random starting cell and randomly walks. It cannot walk on an already visited cell,
    and if finds at a dead-end (no more unvisited cells around current one), "hunts" from the northwest corner the
    first cell that is unvisted and has at least one visited neighbor; then starts walking again.
    """

    def on(self, grid: Grid) -> None:
        current_cell: Optional[Cell] = grid.random_cell()

        while current_cell is not None:
            unvisited_neighbors = [neighbor for neighbor in current_cell.neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) > 0:
                # as long as there are unvisited paths, walk them
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                current_cell = neighbor
            else:
                # enter hunt mode, find first unvisited cell near any visited cell
                current_cell = None

                for cell in grid.each_cell():
                    visited_neighbors = [neighbor for neighbor in cell.neighbors if len(neighbor.links) > 0]
                    if len(cell.links) == 0 and len(visited_neighbors) > 0:
                        current_cell = cast(Cell, cell)  # outside of Mypy it's a mere assignment
                        neighbor = choice(visited_neighbors)
                        current_cell += neighbor
                        break


text:
from random import choice
from typing import Optional

from base.cell import Cell, is_cell
from base.grid import Grid
from algorithms.base_algorithm import Algorithm

class RecursiveBacktracker(Algorithm):
    """
    Recursive Backtracker algorithm picks a random starting cell and randomly walks.
    It cannot walk on an already visited cell, and if finds at a dead-end (no more unvisited cells around current one),
    goes back in its steps until has a cell at least one visited neighbor; then starts walking again.
    """

    def __init__(self, starting_cell: Optional[Cell] = None) -> None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) -> None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError("Starting point of the algorithm must be a valid cell in the grid")

        # We'll use the list as a stack to do very easily any backtracking
        walked_path = []
        walked_path.append(self.starting_cell)

        while walked_path:
            current_cell = walked_path[-1]

            unvisited_neighbors = [neighbor for neighbor in current_cell.neighbors if not neighbor.links]
            if not unvisited_neighbors:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

repo_language: Python

mime_type: text/plain


text:
from abc import ABCMeta, abstractmethod

from base.grid import Grid

class Algorithm(metaclass=ABCMeta):

    @abstractmethod
    def on(self, grid: Grid) -> None:
        raise NotImplementedError

    @property
    def name(self) -> str:
        return self.__class__.__name__


text:
from random import choice

from algorithms.base_algorithm import Algorithm
from base.grid import Grid

class BinaryTree(Algorithm):
    """
    A binary tree visits each cell in the grid and chooses to carve a passage either north or east with a simple random.
    Causes topmost row and rightmost column to always be straight lines.
    """

    def on(self, grid: Grid) -> None:
        for cell in grid.each_cell():
            neighbors = []
            if cell.north:
                neighbors.append(cell.north)
            if cell.east:
                neighbors.append(cell.east)
            if len(neighbors) > 0:
                neighbor = choice(neighbors)
                cell += neighbor


text:
from algorithms.base_algorithm import Algorithm
from base.grid import Grid

class AldousBroder(Algorithm):
    """
    Aldous-Broder algorithm works by always choosing a random neighbor of a randomly-selected also cell, and linking
    them if not yet visited ("random walking"), repeating until all cells are visited once.
    Can take long to compute on big grids (slow-to-finish).
    """

    def on(self, grid: Grid) -> None:
        current_cell = grid.random_cell()
        unvisited_count = grid.size - 1

        while unvisited_count > 0:
            neighbor = current_cell.random_neighbour()
            if neighbor is None:
                raise ValueError("Aldous-Broder algorithm needs all cells to have at least one neighbor")
            if len(neighbor.links) == 0:
                current_cell += neighbor
                unvisited_count -= 1
            current_cell = neighbor


text:
from random import choice

from algorithms.base_algorithm import Algorithm

from base.grid import Grid

class Wilson(Algorithm):
    """
    Wilson algorithm works by choosing a random cell as origin, another as destination, and performs as loop-erased
    random walk towards it using the neighbors. Stores the path until comes to either destination or a "walked" path
    cell, former causing the algorithm to delete the loop until there and keep going.
    Takes a long to compute on big grids (slow-to-start).
    """

    def on(self, grid: Grid) -> None:
        unvisited = []
        for cell in grid.each_cell():
            unvisited.append(cell)

        first_cell = choice(unvisited)
        unvisited.remove(first_cell)

        while len(unvisited) > 0:
            # start a walk
            cell = choice(unvisited)
            path = [cell]

            while cell in unvisited:
                cell = cell.random_neighbour()
                try:
                    position = path.index(cell)
                    # already walked, perform loop-erase. e.g. A -> B -> C -> D -> B   becomes A -> B
                    path = path[:position + 1]
                except ValueError:
                    path.append(cell)

            # Passage carving once has found a valid path
            for index in range(len(path) - 1):
                path[index] += path[index + 1]
                unvisited.remove(path[index])


text:
from abc import ABCMeta, abstractmethod
from typing import Any

from base.grid import Grid

class Exporter(metaclass=ABCMeta):

    @abstractmethod
    def render(self, grid: Grid, ** kwargs: Any) -> None:
        """Base """

    @property
    def name(self) -> str:
        return self.__class__.__name__


text:
from time import gmtime, strftime

from typing import Any, cast, List, Optional, Union

from base.cell import Cell
from base.grid import Grid
from base.colored_grid import ColoredGrid
from exporters.base_exporter import Exporter
import pathfinders.dijkstra as Dijkstra
import pathfinders.longest_path as LongestPath

class Wolf3DExporter(Exporter):
    """
    Drawing logic adapted from ASCIIRenderer: Draws topmost row (northen wall), then proceeds drawing south-east.
    """

    HEX_FILL = 0x00

    # always add a 0x00 byte afterwards to all wall and objects
    WALL_STONE = 0x01
    WALL_EMPTY_CELL = 0x6c
    WALL_ELEVATOR_EXIT_EW = 0x15

    OBJECT_EMPTY = 0x00
    OBJECT_STARTING_POSITION_FACING_N = 0x13
    OBJECT_STARTING_POSITION_FACING_E = 0x14
    OBJECT_STARTING_POSITION_FACING_S = 0x15
    OBJECT_STARTING_POSITION_FACING_W = 0x16
    OBJECT_GUARD_FACING_E = 0x6c
    OBJECT_GUARD_FACING_N = 0x6d
    OBJECT_GUARD_FACING_W = 0x6e
    OBJECT_GUARD_FACING_S = 0x6f

    # As our cells are bigger than 1 wolf3D cell (ours being 2x2), maps are smaller
    MAP_MAX_ROWS = 31
    MAP_MAX_COLUMNS = 31

    MAX_ENEMIES = 149  # limits per level: 149 enemies, 399 objects, and 64 doors

    # because LEV map columns don't align perfectly with our cells,
    # we'll fill the rightmost remaining columns of each row
    WALL_FILL = [WALL_STONE, HEX_FILL]
    OBJECT_FILL = [OBJECT_EMPTY, HEX_FILL]

    @property
    def enemies_count(self) -> int:
        return self._enemies_count

    def __init__(self) -> None:
        self._enemies_count: int = 0

    def render(self, grid: Union[Grid, ColoredGrid], **kwargs: Any) -> None:
        assert isinstance(grid, ColoredGrid)

        filename = strftime("%d%H%M%S", gmtime())

        for key in kwargs:
            if key == "filename":
                filename = kwargs[key]

        if grid.rows < self.MAP_MAX_ROWS or grid.columns < self.MAP_MAX_COLUMNS:
            grid = self._expand(grid, self.MAP_MAX_ROWS, self.MAP_MAX_COLUMNS)

        if grid.rows > self.MAP_MAX_ROWS:
            raise ValueError("Wolfenstein3D NMap only allows maps with {} rows maximum".format(self.MAP_MAX_ROWS))
        if grid.columns > self.MAP_MAX_COLUMNS:
            raise ValueError("Wolfenstein3D NMap only allows maps with {} columns maximum".format(self.MAP_MAX_COLUMNS))

        grid = self._store_solution(grid)

        # first row is easy as it's all wall
        walls = self.WALL_FILL + self.WALL_FILL * grid.columns * 2 + self.WALL_FILL
        objects = self.OBJECT_FILL + self.OBJECT_FILL * grid.columns * 2 + self.OBJECT_FILL

        for row in grid.each_row():
            walls_top = [self.WALL_STONE, self.HEX_FILL]
            objects_top = [self.OBJECT_EMPTY, self.HEX_FILL]

            walls_bottom = [self.WALL_STONE, self.HEX_FILL]
            objects_bottom = [self.OBJECT_EMPTY, self.HEX_FILL]

            for cell in row:
                wall_body = self._wall_for(cell, grid)
                object_body = self._object_for(cell, grid)
                if cell.linked_to(cell.east):
                    wall_east_boundary = [self.WALL_EMPTY_CELL, self.HEX_FILL]
                else:
                    wall_east_boundary = [self.WALL_STONE, self.HEX_FILL]
                walls_top += wall_body + wall_east_boundary
                objects_top += object_body + [self.OBJECT_EMPTY, self.HEX_FILL]

                if cell.linked_to(cell.south):
                    wall_south_boundary = [self.WALL_EMPTY_CELL, self.HEX_FILL]
                else:
                    wall_south_boundary = [self.WALL_STONE, self.HEX_FILL]
                walls_bottom += wall_south_boundary + [self.WALL_STONE, self.HEX_FILL]
                objects_bottom += [self.OBJECT_EMPTY, self.HEX_FILL] * 2

            walls += walls_top + self.WALL_FILL
            objects += objects_top + self.OBJECT_FILL

            walls += walls_bottom + self.WALL_FILL
            objects += objects_bottom + self.OBJECT_FILL

        self._write_data(filename, walls, objects)

    @staticmethod
    def is_valid(grid: ColoredGrid) -> bool:
        """
        Wolf3D exit wall cell is a switch that only gets rendered east and west
        """
        _, end = LongestPath.calculate(grid)
        cell = grid[end[0], end[1]]
        if cell is None:
            raise ValueError("Ending row not found at row {} column {}".format(*end))
        linked_neighbor = cell.links[0]     # assume exactly one path to the exit
        return (cell.east is not None and cell.east == linked_neighbor) or \
               (cell.west is not None and cell.west == linked_neighbor)

    @staticmethod
    def _expand(grid: ColoredGrid, rows: int, columns: int) -> ColoredGrid:
        new_grid = ColoredGrid(rows, columns)
        for cell in grid.each_cell():
            new_grid.set_cell_at(cell.row, cell.column, cell)
        return new_grid

    @staticmethod
    def _store_solution(grid: ColoredGrid) -> ColoredGrid:
        start, end = LongestPath.calculate(grid)
        Dijkstra.calculate_distances(grid, start, end)
        return grid

    @staticmethod
    def _write_data(filename: str, walls: List[int], objects: List[int]) -> None:
        with open(filename, "wb") as file:
            # write walls
            file.write(bytes(walls))
            # padding with walls until exactly 8192 bytes
            padding = [Wolf3DExporter.WALL_EMPTY_CELL, Wolf3DExporter.HEX_FILL] * round((8192 - len(walls)) / 2)
            file.write(bytes(padding))

            # then write objects
            file.write(bytes(objects))
            # and again padding (which should be exactly the same)
            padding = [Wolf3DExporter.OBJECT_EMPTY, Wolf3DExporter.HEX_FILL] * round((8192 - len(objects)) / 2)
            file.write(bytes(padding))

        print("Filename: {}".format(filename))

    @staticmethod
    def _cell_distance(cell: Cell, grid: ColoredGrid) -> Optional[int]:
        if grid.distances is not None and grid.maximum > 0 and grid.distances[cell] is not None:
            return cast(int, grid.distances[cell])
        else:
            return None

    def _wall_for(self, cell: Cell, grid: ColoredGrid) -> List[int]:
        wall = [self.WALL_EMPTY_CELL, self.HEX_FILL] if len(cell.links) > 0 else [self.WALL_STONE, self.HEX_FILL]
        distance = self._cell_distance(cell, grid)
        if distance is not None and distance == grid.maximum:
            return [self.WALL_ELEVATOR_EXIT_EW, self.HEX_FILL]
        return wall

    def _object_for(self, cell: Cell, grid: ColoredGrid) -> List[int]:
        distance = self._cell_distance(cell, grid)
        if distance is not None:
            if 0 < distance < grid.maximum:
                # main path never reaches deadends, so no need to check for cell contents
                return [self.OBJECT_EMPTY, self.HEX_FILL]
            elif distance == grid.maximum:
                # finish cell: Nothing as wall will be overriden with exit cell
                return [self.OBJECT_EMPTY, self.HEX_FILL]
            else:
                # starting cell
                linked_neighbor = cell.links[0]     # assume exactly one path to the exit
                if cell.east and cell.east == linked_neighbor:
                    return [self.OBJECT_STARTING_POSITION_FACING_E, self.HEX_FILL]
                elif cell.north and cell.north == linked_neighbor:
                    return [self.OBJECT_STARTING_POSITION_FACING_N, self.HEX_FILL]
                elif cell.west and cell.west == linked_neighbor:
                    return [self.OBJECT_STARTING_POSITION_FACING_W, self.HEX_FILL]
                else:
                    return [self.OBJECT_STARTING_POSITION_FACING_S, self.HEX_FILL]
        else:
            return self._cell_contents(cell)

    def _cell_contents(self, cell: Cell) -> List[int]:
        if len(cell.links) == 1 and self.enemies_count < self.MAX_ENEMIES:
            # dead-end
            self._enemies_count += 1
            linked_neighbor = cell.links[0]
            if cell.east and cell.east == linked_neighbor:
                return [self.OBJECT_GUARD_FACING_E, self.HEX_FILL]
            elif cell.north and cell.north == linked_neighbor:
                return [self.OBJECT_GUARD_FACING_N, self.HEX_FILL]
            elif cell.west and cell.west == linked_neighbor:
                return [self.OBJECT_GUARD_FACING_W, self.HEX_FILL]
            else:
                return [self.OBJECT_GUARD_FACING_S, self.HEX_FILL]
        else:
            return [self.OBJECT_EMPTY, self.HEX_FILL]


text:
from typing import Any

from exporters.base_exporter import Exporter
from base.grid import Grid

class ASCIIExporter(Exporter):
    """
    Renders to stdout an ASCII representation of the maze.
    Rendering starts with top walls and nortwest corner setup, so it only needs to care of each cell's east and
    south walls.
    """

    def render(self, grid: Grid, **kwargs: Any) -> None:
        output = "+" + "---+" * grid.columns + "\n"

        for row in grid.each_row():
            top = "|"
            bottom = "+"
            for cell in row:
                # NOTE: Book here creates dummy (-1,-1) cell. Not doing it until needed
                body = grid.contents_of(cell)
                east_boundary = " " if cell.linked_to(cell.east) else "|"
                top += body + east_boundary
                south_boundary = "   " if cell.linked_to(cell.south) else "---"
                corner = "+"
                bottom += south_boundary + corner
            output += top + "\n"
            output += bottom + "\n"

        print(output)


text:
from typing import Any, cast

from exporters.base_exporter import Exporter
from base.cell import Cell
from base.grid import Grid

class UnicodeExporter(Exporter):
    """
    Renders to stdout a UNICODE representation of the maze.
    Not present in the book but suggested as exercise. And looks better than ASCII mazes :)
    """

    #  if not linked/closed, add that side's value to find position at array:
    #    N        1
    #  W   E    2   4
    #    S        8
    JUNCTIONS = [" ", " ", " ", "\u251b", " ", "\u2517", "\u2501", "\u253b", " ", "\u2503", "\u2513", "\u252b",
                 "\u250f", "\u2523", "\u2533", "\u254b"]
    NORTH = 1
    WEST = 2
    EAST = 4
    SOUTH = 8

    def render(self, grid: Grid, **kwargs: Any) -> None:
        horizontal_wall = "\u2501"
        vertical_wall = "\u2503"

        output = self.JUNCTIONS[12]
        for x in range(grid.columns - 1):
            output += (horizontal_wall * 3 + self.get_topmost_junction(cast(Cell, grid.cell_at(row=0, column=x))))
        output += horizontal_wall * 3 + self.JUNCTIONS[10] + "\n"

        for row in grid.each_row():
            top = vertical_wall
            bottom = self.get_leftmost_junction(row[0])
            for cell in row:
                body = grid.contents_of(cell)
                east_boundary = " " if cell.linked_to(cell.east) else vertical_wall
                top += body + east_boundary
                south_boundary = "   " if cell.linked_to(cell.south) else horizontal_wall * 3
                bottom += south_boundary + self.get_south_east_junction(cell)
            output += top + "\n"
            output += bottom + "\n"

        print(output)

    @staticmethod
    def get_leftmost_junction(cell: Cell) -> str:
        #
        #    [ X ]
        #
        #  [ X-south]
        #
        junction = UnicodeExporter.NORTH

        if cell.south:
            junction += UnicodeExporter.SOUTH
            if not cell.linked_to(cell.south):
                junction += UnicodeExporter.EAST
        else:
            junction += UnicodeExporter.EAST

        return UnicodeExporter.JUNCTIONS[junction]

    @staticmethod
    def get_topmost_junction(cell: Cell) -> str:
        # special case for 1st row's junctions
        #
        #    [ X ]      [X-east]
        #
        junction = UnicodeExporter.EAST + UnicodeExporter.WEST

        if not cell.linked_to(cast(Cell, cell.east)):
            junction += UnicodeExporter.SOUTH

        return UnicodeExporter.JUNCTIONS[junction]

    @staticmethod
    def get_south_east_junction(cell: Cell) -> str:
        # Taking advantage that we always go forward east and south, just need to calculate available posibilities
        #
        #    [ X ]      [X-east]
        #
        #  [ X-south] [X-southeast]
        #
        junction = 0

        if cell.east:
            if not cell.linked_to(cell.east):
                junction += UnicodeExporter.NORTH
            if not cell.east.south:
                junction += UnicodeExporter.EAST
        else:
            junction += UnicodeExporter.NORTH

        if cell.south:
            if not cell.linked_to(cell.south):
                junction += UnicodeExporter.WEST
            if not cell.south.east:
                junction += UnicodeExporter.SOUTH
        else:
            junction += UnicodeExporter.WEST

        if cell.east and cell.south:
            south_east_cell = cast(Cell, cell.south.east)
            if not cell.east.linked_to(south_east_cell):
                junction += UnicodeExporter.EAST
            if not cell.south.linked_to(south_east_cell):
                junction += UnicodeExporter.SOUTH
        try:
            return UnicodeExporter.JUNCTIONS[junction]
        except IndexError as ie:
            print("junction:{} error:{}".format(junction, ie))
            return " "


text:
from time import gmtime, strftime
from typing import Any, cast, Tuple

from PIL import Image, ImageDraw

from exporters.base_exporter import Exporter
from base.colored_grid import ColoredGrid
from base.grid import Grid

STEP_BACKGROUND = 0

class PNGExporter(Exporter):

    def render(self, grid: Grid, **kwargs: Any) -> None:
        has_color = isinstance(grid, ColoredGrid)

        filename, cell_size, coloring = self._process_kwargs(**kwargs)
        image = self._render(grid, cell_size, coloring and has_color)
        image.save("{}.png".format(filename), "PNG", optimize=True)

    @staticmethod
    def _render(grid: Grid, cell_size: int = 4, coloring: bool = False) -> Image:
        wall_color = (0, 0, 0)
        image_width = cell_size * grid.columns
        image_height = cell_size * grid.rows

        image = Image.new("RGBA", (image_width + 1, image_height + 1), (255, 255, 255))
        draw = ImageDraw.Draw(image)

        for draw_pass in range(2):
            for cell in grid.each_cell():
                x1 = cell.column * cell_size
                y1 = cell.row * cell_size
                x2 = (cell.column + 1) * cell_size
                y2 = (cell.row + 1) * cell_size

                if draw_pass == STEP_BACKGROUND and coloring:
                    if coloring:
                        color = cast(ColoredGrid, grid).background_color_for(cell)
                    else:
                        color = (255, 255, 255)
                    draw.rectangle((x1, y1, x2, y2), fill=color)
                else:
                    if not cell.north:
                        draw.line((x1, y1, x2, y1), fill=wall_color, width=1)
                    if not cell.west:
                        draw.line((x1, y1, x1, y2), fill=wall_color, width=1)
                    if not cell.linked_to(cell.east):
                        draw.line((x2, y1, x2, y2), fill=wall_color, width=1)
                    if not cell.linked_to(cell.south):
                        draw.line((x1, y2, x2, y2), fill=wall_color, width=1)

        return image

    @staticmethod
    def _process_kwargs(**kwargs: Any) -> Tuple[str, int, bool]:
        filename = strftime("%Y%m%d%H%M%S", gmtime())
        cell_size = 10
        coloring = False
        for key in kwargs:
            if key == "filename":
                filename = kwargs[key]
            elif key == "cell_size":
                cell_size = kwargs[key]
            elif key == "coloring":
                coloring = kwargs[key]
        return filename, cell_size, coloring

# ----


text:
from typing import Dict, List, Optional, Tuple, TYPE_CHECKING

# Avoid cyclic import, as Cell uses Distances
if TYPE_CHECKING:
    from base.cell import Cell
else:
    Cell = "Cell"

Cells = Dict[Cell, int]

class Distances:

    def __init__(self, root: Cell) -> None:
        if not is_cell(root):
            raise ValueError("Root must be a cell")

        self.root: Cell = root
        self._cells: Cells = dict()
        self._cells[root] = 0

    def __getitem__(self, cell: Cell) -> Optional[int]:
        if not is_cell(cell):
            raise IndexError("Distances must be indexed with a cell")

        if cell in self._cells.keys():
            return self._cells[cell]
        return None

    def __setitem__(self, cell: Cell, distance: int) -> None:
        if not is_cell(cell):
            raise IndexError("Distances must be indexed with a cell")

        self._cells[cell] = distance

    @property
    def cells(self) -> List[Cell]:
        return list(self._cells.keys())

    @property
    def max(self) -> Tuple[Cell, int]:
        max_distance = 0
        max_cell = self.root

        for cell in self._cells:
            if self._cells[cell] > max_distance:
                max_cell = cell
                max_distance = self._cells[cell]

        return max_cell, max_distance

    def path_to(self, destination: Cell) -> "Distances":
        """
        Traverses backwards, from destination to root/origin
        """
        if not is_cell(destination):
            raise ValueError("Destination must be a cell")

        current_cell = destination

        breadcrumbs = Distances(self.root)
        breadcrumbs[current_cell] = self._cells[current_cell]

        while current_cell != self.root:
            for neighbor in current_cell.links:
                if self._cells[neighbor] < self._cells[current_cell]:
                    breadcrumbs[neighbor] = self._cells[neighbor]
                    current_cell = neighbor
                    break

        return breadcrumbs

def is_cell(cell: Cell) -> bool:
    return type(cell).__name__ == Cell


text:
from typing import cast, Optional, Tuple

from base.distance_grid import DistanceGrid
from base.cell import Cell

MAX_DARK = 210                          # Dark meaning farther than or more distant than
MAX_BRIGHT = round(MAX_DARK / 2)        # And thus, bright means closer than or less distant than
MAX_BRIGHT_INTENSITY = MAX_BRIGHT - 1

class ColoredGrid(DistanceGrid):

    def background_color_for(self, cell: Cell) -> Optional[Tuple[int, int, int]]:
        if self.distances is not None and self.maximum > 0 and self.distances[cell] is not None:
            distance = cast(int, self.distances[cell])
            if distance > 0 and distance < self.maximum:
                intensity = float((self.maximum - distance)) / self.maximum
                dark = round(MAX_DARK * intensity)
                bright = MAX_BRIGHT + round(MAX_BRIGHT_INTENSITY * intensity)
                return dark, bright, dark
            elif distance == self.maximum:
                return 128, 0, 0
            else:
                # starting cell in blue
                return 0, 148, 255
        else:
            return None


text:
from random import randrange
from typing import cast, Generator, List, Optional, Tuple

from base.cell import Cell, is_cell

Key = Tuple[int, int]
CellList = List[Cell]

class Grid:

    @property
    def rows(self) -> int:
        return self._rows

    @property
    def columns(self) -> int:
        return self._columns

    @property
    def size(self) -> int:
        return self.rows * self.columns

    @property
    def dimensions(self) -> Key:
        return self.rows, self.columns

    @property
    def deadends(self) -> List[Cell]:
        return [cell for cell in self.each_cell() if len(cell.links) == 1]

    def __init__(self, rows: int, columns: int) -> None:
        if rows is None or rows < 2:
            raise ValueError("Rows must be an integer greater than 1")
        if columns is None or columns < 2:
            raise ValueError("Columns must an integer greater than 1")

        self._rows: int = rows
        self._columns: int = columns
        self._grid: List[List[Cell]] = self.prepare_grid()
        self.configure_cells()

    def cell_at(self, row: int, column: int) -> Optional[Cell]:
        if not (0 <= row < self.rows):
            return None
        if not (0 <= column < self.columns):
            return None
        return self._grid[row][column]

    def set_cell_at(self, row: int, column: int, value: Cell) -> None:
        self._grid[row][column] = value

    def prepare_grid(self) -> List[List[Cell]]:
        return [[Cell(row, column) for column in range(self.columns)] for row in range(self.rows)]

    def configure_cells(self) -> None:
        """
        Create all the north/sout/east/west dependencies of the cells
        """
        for cell in self.each_cell():
            row = cell.row
            column = cell.column

            cell.north = self[row - 1, column]
            cell.south = self[row + 1, column]
            cell.east = self[row, column + 1]
            cell.west = self[row, column - 1]

    def random_cell(self) -> Cell:
        row = randrange(0, self.rows)
        column = randrange(0, self.columns)
        return cast(Cell, self[row, column])

    def each_row(self) -> Generator[CellList, None, None]:
        for row in range(self.rows):
            yield self._grid[row]

    def each_cell(self) -> Generator:
        for row in self.each_row():
            for cell in row:
                yield cell

    def contents_of(self, cell: Cell) -> str:
        return "   "

    def __getitem__(self, key: Key) -> Optional[Cell]:
        if not is_key(key):
            raise IndexError('Only grid[row,col] __getitem__ calls are supported')
        return self.cell_at(*key)

        if is_key(key):
            row, column = key
            if row < 0 or row > self.rows - 1:
                return None
            if column < 0 or column > self.columns - 1:
                return None
            return self._grid[row][column]

    def __setitem__(self, key: Key, value: Cell) -> None:
        if not (is_key(key) and is_cell(value)):
            raise IndexError('Only grid[row,col] __setitem__ calls are supported')
        self.set_cell_at(*key, value)

    def __contains__(self, other: Cell) -> bool:
        if is_cell(other):
            for cell in self.each_cell():
                if cell == other:
                    return True
        return False

def is_key(key: Key) -> bool:
    """
    Runtime check for key correctness
    """
    return isinstance(key, tuple) and len(key) == 2 and not any(not isinstance(value, int) for value in key)


text:
from typing import TYPE_CHECKING, Tuple, Union

from base.grid import Grid
from base.cell import Cell

if TYPE_CHECKING:
    from base.distance_grid import DistanceGrid     # noqa: F401
    from base.colored_grid import ColoredGrid       # noqa: F401

class Rotator:
    """
    Each rotation is always 90 degrees clockwise.
    Not present in the book but suggested as exercise. Good for mitigating weak algorithm straight paths.
    """

    @staticmethod
    def on(grid: Union[Grid, "DistanceGrid", "ColoredGrid"]) -> Union[Grid, "DistanceGrid", "ColoredGrid"]:
        grid_type = type(grid)

        # row i becomes col n-i when rotating 90 degrees clockwise
        rotated_grid = grid_type(rows=grid.columns, columns=grid.rows)

        for old_cell in grid.each_cell():
            row, column = Rotator._rotated_coordinates(old_cell, rotated_grid)
            new_cell = rotated_grid.cell_at(row, column)
            if new_cell is None:
                raise IndexError("Cell not found at row {} column {}".format(row, column))
            Rotator._rotate_cell_neighbors(new_cell, old_cell, rotated_grid)

        return rotated_grid

    @staticmethod
    def _rotated_coordinates(cell: Cell, grid: Grid) -> Tuple[int, int]:
        row = cell.column
        column = (grid.columns - cell.row - 1)
        return row, column

    @staticmethod
    def _rotate_cell_neighbors(new_cell: Cell, old_cell: Cell, grid: Grid) -> None:
        for link in old_cell.links:
            row, column = Rotator._rotated_coordinates(link, grid)
            neighbor = grid.cell_at(row, column)
            if neighbor is None:
                raise IndexError("Cell not found at row {} column {}".format(row, column))
            new_cell.link(neighbor)


text:
from random import choice
from typing import Any, cast, Dict, Hashable, List, Optional
import warnings

from base.distances import Distances

Links = Dict["Cell", bool]
CellList = List["Cell"]

class Cell:

    @property
    def row(self) -> int:
        return self._row

    @property
    def column(self) -> int:
        return self._column

    @property
    def links(self) -> CellList:
        return list(self._links.keys())

    @property
    def neighbors(self) -> CellList:
        neighbors_list: CellList = []
        if self.north:
            neighbors_list.append(self.north)
        if self.south:
            neighbors_list.append(self.south)
        if self.east:
            neighbors_list.append(self.east)
        if self.west:
            neighbors_list.append(self.west)
        return neighbors_list

    @property
    def distances(self) -> Distances:
        distances = Distances(self)
        frontier = [self]

        while len(frontier) > 0:
            new_frontier = []
            for cell in frontier:
                for linked_cell in cell.links:
                    if distances[linked_cell] is None and distances[cell] is not None:
                        distances[linked_cell] = cast(int, distances[cell]) + 1
                        new_frontier.append(linked_cell)
            frontier = new_frontier

        return distances

    @property
    def data(self) -> Dict:
        return self._data

    def __init__(self, row: int, column: int) -> None:
        if row is None or row < 0:
            raise ValueError("Row must be a positive integer")
        if column is None or column < 0:
            raise ValueError("Column must be a positive integer")

        self._row: int = row
        self._column: int = column
        self._links: Dict[Cell, bool] = {}
        self._data: Dict = {}
        self.north: Optional[Cell] = None
        self.south: Optional[Cell] = None
        self.east: Optional[Cell] = None
        self.west: Optional[Cell] = None

    def link(self, cell: "Cell", bidirectional: bool = True) -> "Cell":
        """
        Links current cell to specified one
        """
        if not is_cell(cell):
            raise ValueError("Link can only be made between two cells")

        self._links[cell] = True
        if bidirectional:
            cell.link(cell=self, bidirectional=False)
        return self

    def unlink(self, cell: "Cell", bidirectional: bool = True) -> "Cell":
        """
        Unlinks current cell from specified one
        """
        if cell is None:
            warnings.warn("Attempted to remove non-existant link", UserWarning)
        elif not is_cell(cell):
            raise ValueError("Link can only be removed between two cells")

        if self.linked_to(cell):
            del self._links[cell]
            if bidirectional:
                cell.unlink(cell=self, bidirectional=False)
        return self

    def linked_to(self, cell: Optional["Cell"]) -> bool:
        if is_cell(cell):
            return cell in self._links
        elif cell is None:
            return False
        else:
            raise ValueError("Attempted to check link with non-cell")

    def random_neighbour(self) -> Optional["Cell"]:
        if len(self.neighbors) == 0:
            return None
        else:
            return choice(self.neighbors)

    def has_data(self, key: Hashable) -> bool:
        return key in self.data.keys()

    def __iadd__(self, cell: "Cell") -> "Cell":
        """
        Overload for the += operator with the link method
        """
        self.link(cell)
        return self

    def __isub__(self, cell: "Cell") -> "Cell":
        """
        Overload for the -= operator with the link method
        """
        self.unlink(cell)
        return self

    def __and__(self, other_cell: Optional["Cell"]) -> bool:
        """
        Overload for the & operator with the linked? method
        """
        return self.linked_to(other_cell)

    def __hash__(self) -> int:
        return hash((self.column, self.row))

    def __repr__(self) -> str:
        return "({},{}) = {}".format(self.column, self.row, str(hex(id(self))))

    # Note: The following methods actually don't take into account neighbors/linked-cells, but for now is enough

    def __eq__(self, other_cell: Optional["Cell"]) -> bool:       # type: ignore
        if not is_cell(other_cell) or other_cell is None:
            return False
        return self.row == other_cell.row and self.column == other_cell.column

    def __ne__(self, other_cell: "Cell") -> bool:       # type: ignore
        return not self == other_cell

def is_cell(cell: Any) -> bool:
    return isinstance(cell, Cell)


text:
from typing import Optional     # noqa: F401

from base.grid import Grid
from base.cell import Cell
from base.distances import Distances    # noqa: F401

"""
Distance is represented as hexadecimal
"""

class DistanceGrid(Grid):

    def __init__(self, rows: int, columns: int) -> None:
        super().__init__(rows, columns)
        self._distances: Optional[Distances] = None
        self.maximum: int = 0

    @property
    def distances(self) -> Optional[Distances]:
        return self._distances

    @distances.setter
    def distances(self, value: Optional[Distances]) -> None:
        self._distances = value
        if self._distances:
            _, self.maximum = self._distances.max

    def contents_of(self, cell: Cell) -> str:
        if self.distances is not None and self.distances[cell] is not None:
            return format(self.distances[cell], "02X").center(3)
        else:
            return super().contents_of(cell)


text:
version: "2"
services:
  mazes-for-programmers-base:
    build:
      args:
        uid: ${UID}
        gid: ${GID}
      context: ../..
      dockerfile: build/base/Dockerfile
    image: mazes-for-programmers:base
    working_dir: /code
    command: "/bin/true"


text:
FROM python:3.11-slim

LABEL title "Mazes-for-programmers-Python-src"
LABEL maintainer "Diego / Kartones"
LABEL contrib1 "https://github.com/Kartones"
LABEL url "https://kartones.net"

# Define environment vars to expose to container here
# ENV <key> <value>

# Env vars sent from docker-compose or docker build
ARG uid=1000
ARG gid=1000

RUN getent group $gid || groupadd --gid $gid mazes-for-programmers
RUN getent passwd $uid || useradd -m -u $uid -g $gid mazes-for-programmers

RUN chown -R $uid:$gid /usr/local

RUN apt-get update -y \
  && rm -rf /var/lib/apt/lists/*

USER $uid

RUN pip install --upgrade pip
COPY requirements.txt /code/requirements.txt
RUN pip install -r /code/requirements.txt


text:
version: "2"
services:
  mazes-for-programmers:
    build:
      args:
        uid: ${UID}
        gid: ${GID}
      context: ../..
      dockerfile: build/dev/Dockerfile
    image: mazes-for-programmers:dev
    volumes:
      - ../..:/code
      - ../..:/opt/mazes-for-programmers
      - ~/.bash_history.mazes-for-programmers:/home/mazes-for-programmers/.bash_history
    environment:
      - PYTHONPATH=/code
    command: "/bin/true"


text:
FROM mazes-for-programmers:base

ARG uid=1000
ARG gid=1000

USER $uid

VOLUME /code
WORKDIR /code


text:
from typing import Tuple

from base.distance_grid import DistanceGrid

Point = Tuple[int, int]

def calculate_distances(grid: DistanceGrid, start: Point, end: Point) -> None:
    """
    Calculate the distances in the grid using Dijkstra's algorithm
    """
    if grid[start] is None:
        raise IndexError("Invalid start cell {} column {}".format(*start))
    if grid[end] is None:
        raise IndexError("Invalid destination cell row {} column {}".format(*end))

    grid.distances = grid[start].distances.path_to(grid[end])  # type: ignore


text:
from typing import Tuple

from base.distance_grid import DistanceGrid

Point = Tuple[int, int]

def calculate(grid: DistanceGrid) -> Tuple[Point, Point]:
    """
    Calculates a longest path inside a maze, by calculating the longest past from nortwest corner,
    then using that point as the actual start and calculating its most distant cell.
    """
    start_cell = grid[0, 0]
    if start_cell is None:
        raise IndexError("Invalid start cell row {} column {}".format(0, 0))

    new_start_cell, distance = start_cell.distances.max
    goal_cell, distance = new_start_cell.distances.max

    return (new_start_cell.row, new_start_cell.column), (goal_cell.row, goal_cell.column)


text:
import argparse
import time

from typing import cast, Dict, Type, Union

from algorithms.base_algorithm import Algorithm
from base.grid import Grid
from base.distance_grid import DistanceGrid

import pathfinders.dijkstra as Dijkstra
import pathfinders.longest_path as LongestPath

from demos.demo_utils import ALGORITHMS, str2bool

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Run statistics for all algorithms")
    parser.add_argument("rows", type=int, help="number of rows")
    parser.add_argument("columns", type=int, help="number of columns")
    parser.add_argument("-t", "--tries", type=int, default=10, help="number of tries")
    parser.add_argument("-p", "--pathfinding", type=str2bool, default=False, help="whether solve the maze")
    args = parser.parse_args()

    rows = args.rows
    columns = args.columns
    size = rows * columns
    tries = args.tries
    pathfinding = args.pathfinding

    algorithm_averages = {}
    algorithm_benchmarks: Dict[Type[Algorithm], Dict[str, float]] = {}
    pathfinding_benchmarks: Dict[Type[Algorithm], Dict[str, float]] = {}

    print("Rows: {}\ncolumns: {}\nTotal cells: {}\nRuns per algorithm: {}".format(rows, columns, size, tries))
    print("Pathfinding: {}".format(pathfinding))
    for algorithm in ALGORITHMS:
        print("> running {}".format(algorithm.__name__))

        pathfinding_timings = []
        timings = []
        deadend_counts = []
        for _ in range(tries):
            if pathfinding:
                grid: Union[Grid, DistanceGrid] = DistanceGrid(rows, columns)
            else:
                grid = Grid(rows, columns)

            time_start = time.perf_counter()
            algorithm().on(grid)
            time_end = time.perf_counter()

            deadend_counts.append(len(grid.deadends))
            timings.append(time_end - time_start)

            if pathfinding:
                time_start = time.perf_counter()
                start, end = LongestPath.calculate(cast(DistanceGrid, grid))
                Dijkstra.calculate_distances(cast(DistanceGrid, grid), start, end)
                time_end = time.perf_counter()
                pathfinding_timings.append(time_end - time_start)

        total_deadends = sum(deadend_counts)
        algorithm_averages[algorithm] = total_deadends / len(deadend_counts)
        timings = sorted(timings)
        algorithm_benchmarks[algorithm] = {
            "min": timings[0],
            "max": timings[-1],
            "average": sum(timings) / tries
        }
        if pathfinding:
            pathfinding_timings = sorted(pathfinding_timings)
            pathfinding_benchmarks[algorithm] = {
                "min": pathfinding_timings[0],
                "max": pathfinding_timings[-1],
                "average": sum(pathfinding_timings) / tries
            }

    sorted_averages = sorted(algorithm_averages.items(), key=lambda x: -x[1])
    print("\nAverage dead-ends (deadends/total-cells, sorted by % desc):")
    for algorithm, average in sorted_averages:
        percentage = average * 100.0 / size
        print(" {:>22}: {:03.0f}/{:03d} ({:.2f}%)".format(algorithm.__name__, average, size, percentage))

    sorted_benchmarks = sorted(algorithm_benchmarks.items(), key=lambda x: -x[1]["average"])
    print("\nGeneration speed benchmark (seconds, sorted by average desc):")
    for algorithm, benchmark in sorted_benchmarks:
        print(" {:>22}: avg: {:03.6f} min: {:03.6f} max: {:03.6f}".format(algorithm.__name__, benchmark["average"],
              benchmark["min"], benchmark["max"]))

    if pathfinding:
        sorted_pathfinding_benchmarks = sorted(pathfinding_benchmarks.items(), key=lambda x: -x[1]["average"])
        print("\nPathfinding speed benchmark (seconds, sorted by average desc):")
        for algorithm, benchmark in sorted_pathfinding_benchmarks:
            print(" {:>22}: avg: {:03.6f} min: {:03.6f} max: {:03.6f}".format(algorithm.__name__, benchmark["average"],
                  benchmark["min"], benchmark["max"]))


text:
import argparse
from time import gmtime, strftime
from typing import cast

from base.colored_grid import ColoredGrid
from base.rotator import Rotator

import pathfinders.dijkstra as Dijkstra
import pathfinders.longest_path as LongestPath

from demos.demo_utils import ALGORITHM_NAMES, str2bool, get_algorithm, get_exporter

DEFAULT_EXPORTER = "PNGExporter"
AVAILABLE_EXPORTERS = ["PNGExporter"]
AVAILABLE_ALGORITHMS = ALGORITHM_NAMES

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Render a maze")
    parser.add_argument("rows", type=int, help="number of rows")
    parser.add_argument("columns", type=int, help="number of columns")
    parser.add_argument("algorithm", type=str, help="algorithm to use")
    parser.add_argument("-e", "--exporter", type=str, default=DEFAULT_EXPORTER, help="maze exporter to use")
    parser.add_argument("-f", "--filename", type=str, default=None, help="file name to use")
    parser.add_argument("-r", "--rotations", type=int, default=0,
                        help="number of 90 degree clockwise rotations to perform")
    parser.add_argument("-p", "--pathfinding", type=str2bool, default=False, help="whether solve the maze")
    parser.add_argument("-c", "--coloring", type=str2bool, help="whether to color the maze solution")
    args = parser.parse_args()

    rows = args.rows
    columns = args.columns
    algorithm = get_algorithm(args.algorithm, AVAILABLE_ALGORITHMS)
    exporter = get_exporter(args.exporter, AVAILABLE_EXPORTERS)
    filename = args.filename if args.filename else strftime("%Y%m%d%H%M%S", gmtime())
    rotations = args.rotations
    pathfinding = args.pathfinding
    coloring = args.coloring
    print("Algorithm: {}\nRows: {}\ncolumns: {}\nExporter: {}".format(args.algorithm, rows, columns, args.exporter))
    print("90deg Rotations: {}\nPathfinding: {}\nColoring: {}".format(rotations, pathfinding, coloring))

    # Always use Colored Grid. Just don"t color the output if colored == False
    grid = ColoredGrid(rows, columns)

    algorithm.on(grid)

    for num in range(rotations):
        grid = cast(ColoredGrid, Rotator().on(grid))

    # here pathfinding first, so if also colored we"ll see the route colored, else if colored will see all maze painted
    if pathfinding:
        start, end = LongestPath.calculate(grid)
        print("Solving maze from row {} column {} to row {} column {}".format(*start, *end))
        Dijkstra.calculate_distances(grid, start, end)
    elif coloring:
        starting_position = (round(grid.rows / 2), round(grid.columns / 2))
        print("Drawing colored maze with start row {} column {}".format(*starting_position))
        if grid[starting_position] is None:
            raise IndexError("Invalid start cell row {} column {}".format(*starting_position))
        grid.distances = grid[starting_position].distances  # type: ignore

    exporter.render(grid, coloring=coloring, filename=filename)

    print("Maze has {} dead-ends".format(len(grid.deadends)))


text:
from argparse import ArgumentTypeError
from typing import List, Type

from algorithms.base_algorithm import Algorithm
from algorithms.aldous_broder import AldousBroder
from algorithms.binary_tree import BinaryTree
from algorithms.hunt_and_kill import HuntAndKill
from algorithms.recursive_backtracker import RecursiveBacktracker
from algorithms.sidewinder import Sidewinder
from algorithms.wilson import Wilson
from exporters.base_exporter import Exporter
from exporters.ascii_exporter import ASCIIExporter
from exporters.png_exporter import PNGExporter
from exporters.unicode_exporter import UnicodeExporter
from exporters.wolf3d_exporter import Wolf3DExporter

ALGORITHMS: List[Type[Algorithm]] = [AldousBroder, BinaryTree, HuntAndKill, RecursiveBacktracker, Sidewinder, Wilson]
ALGORITHM_NAMES: List[str] = [x.__name__ for x in ALGORITHMS]
# TODO: Add PixelExporter
EXPORTERS: List[Type[Exporter]] = [Wolf3DExporter, PNGExporter, UnicodeExporter, ASCIIExporter]
EXPORTER_NAMES: List[str] = [x.__name__ for x in EXPORTERS]

def _instantiate_algorithm(desired_algorithm: str) -> Algorithm:
    for algorithm in ALGORITHMS:
        if algorithm.__name__ == desired_algorithm:
            return algorithm()

    raise ValueError("Invalid algorithm. Valid algorithms: {}".format("|".join(
        [algorithm.__name__ for algorithm in ALGORITHMS])))

def get_algorithm(algorithm: str, available_algorithms: List[str]) -> Algorithm:
    if algorithm in available_algorithms:
        return _instantiate_algorithm(algorithm)

    raise ValueError("Invalid algorithm. Available algorithms: {}".format("|".join(available_algorithms)))

def _instantiate_exporter(desired_exporter: str) -> Exporter:
    for exporter in EXPORTERS:
        if exporter.__name__ == desired_exporter:
            return exporter()

    raise ValueError("Invalid exporter. Valid exporters: {}".format("|".join(
        [exporter.__name__ for exporter in EXPORTERS])))

def get_exporter(exporter: str, available_exporters: List[str]) -> Exporter:
    if exporter in available_exporters:
        return _instantiate_exporter(exporter)

    raise ValueError("Invalid exporter. Available exporters: {}".format("|".join(available_exporters)))

def str2bool(source_string: str) -> bool:
    # https://stackoverflow.com/a/43357954/2531987
    if source_string.lower() in ("yes", "true", "t", "y", "1"):
        return True
    elif source_string.lower() in ("no", "false", "f", "n", "0"):
        return False
    else:
        raise ArgumentTypeError("Stringified boolean value expected")


text:
import argparse
from time import gmtime, strftime
from typing import cast

from base.colored_grid import ColoredGrid
from exporters.png_exporter import PNGExporter
from exporters.wolf3d_exporter import Wolf3DExporter
import pathfinders.dijkstra as Dijkstra
import pathfinders.longest_path as LongestPath

from demos.demo_utils import ALGORITHM_NAMES, get_algorithm, get_exporter

DEFAULT_EXPORTER = "Wolf3DExporter"
AVAILABLE_EXPORTERS = ["Wolf3DExporter"]
AVAILABLE_ALGORITHMS = ALGORITHM_NAMES

def store_solution(grid: ColoredGrid) -> ColoredGrid:
    start, end = LongestPath.calculate(grid)
    Dijkstra.calculate_distances(grid, start, end)
    return grid

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Render a maze")
    parser.add_argument("rows", type=int, help="number of rows")
    parser.add_argument("columns", type=int, help="number of columns")
    parser.add_argument("algorithm", type=str, help="algorithm to use")
    parser.add_argument("-e", "--exporter", type=str, default=DEFAULT_EXPORTER, help="maze exporter to use")
    parser.add_argument("-f", "--filename", type=str, default=None, help="file name to use")
    args = parser.parse_args()

    rows = args.rows
    columns = args.columns
    algorithm = get_algorithm(args.algorithm, AVAILABLE_ALGORITHMS)
    exporter = cast(Wolf3DExporter, get_exporter(args.exporter, AVAILABLE_EXPORTERS))
    filename = strftime("%d%H%M%S", gmtime())

    print("Algorithm: {}\nRows: {}\ncolumns: {}\nExporter: {}".format(args.algorithm, rows, columns, args.exporter))

    valid_map = False
    while not valid_map:
        grid = ColoredGrid(rows, columns)
        algorithm.on(grid)
        valid_map = exporter.is_valid(grid)
        if not valid_map:
            print("Generated maze has no east/west linked ending cell. Recreating...")

    exporter.render(grid, filename=filename)

    print("Generated maze map has {} enemies".format(exporter.enemies_count))

    grid = store_solution(grid)
    PNGExporter().render(grid, coloring=True, filename=filename)


text:
import argparse
from typing import cast

from base.distance_grid import DistanceGrid
from base.rotator import Rotator

import pathfinders.dijkstra as Dijkstra
import pathfinders.longest_path as LongestPath

from demos.demo_utils import ALGORITHM_NAMES, str2bool, get_algorithm, get_exporter

DEFAULT_EXPORTER = "UnicodeExporter"
AVAILABLE_EXPORTERS = ["ASCIIExporter", "UnicodeExporter"]
AVAILABLE_ALGORITHMS = ALGORITHM_NAMES

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Render a maze")
    parser.add_argument("rows", type=int, help="number of rows")
    parser.add_argument("columns", type=int, help="number of columns")
    parser.add_argument("algorithm", type=str, help="algorithm to use")
    parser.add_argument("-e", "--exporter", type=str, default=DEFAULT_EXPORTER, help="maze exporter to use")
    parser.add_argument("-r", "--rotations", type=int, default=0,
                        help="number of 90 degree clockwise rotations to perform")
    parser.add_argument("-p", "--pathfinding", type=str2bool, default=False, help="whether solve the maze")
    args = parser.parse_args()

    rows = args.rows
    columns = args.columns
    algorithm = get_algorithm(args.algorithm, AVAILABLE_ALGORITHMS)
    exporter = get_exporter(args.exporter, AVAILABLE_EXPORTERS)
    rotations = args.rotations
    pathfinding = args.pathfinding
    print("Algorithm: {}\nRows: {}\ncolumns: {}\nExporter: {}".format(args.algorithm, rows, columns, args.exporter))
    print("90deg Rotations: {}\nPathfinding: {}".format(rotations, pathfinding))

    grid = DistanceGrid(rows, columns)
    algorithm.on(grid)

    for num in range(rotations):
        grid = cast(DistanceGrid, Rotator().on(grid))

    if pathfinding:
        start, end = LongestPath.calculate(grid)
        print("Solving maze from row {} column {} to row {} column {}".format(*start, *end))
        Dijkstra.calculate_distances(grid, start, end)

    exporter.render(grid)

    print("Maze has {} dead-ends".format(len(grid.deadends)))


text:
from base.cell import Cell

def test_equality() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 1)
    assert a_cell == another_cell

def test_linking() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)

    assert a_cell.linked_to(another_cell) is False
    assert another_cell.linked_to(a_cell) is False
    assert a_cell.linked_to(yet_another_cell) is False
    assert another_cell.linked_to(yet_another_cell) is False

    a_cell.link(another_cell)

    assert a_cell.linked_to(another_cell) is True
    assert another_cell.linked_to(a_cell) is True
    assert a_cell.linked_to(yet_another_cell) is False
    assert another_cell.linked_to(yet_another_cell) is False

def test_linking_using_operator_overloads() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)

    assert not a_cell & another_cell
    assert not another_cell & a_cell
    assert not a_cell & yet_another_cell
    assert not another_cell & yet_another_cell

    a_cell += another_cell
    assert a_cell & another_cell
    assert another_cell & a_cell
    assert not a_cell & yet_another_cell
    assert not another_cell & yet_another_cell

def test_unlinking() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)

    a_cell.link(another_cell)
    a_cell.link(yet_another_cell)

    assert a_cell.linked_to(another_cell) is True
    assert another_cell.linked_to(a_cell) is True
    assert a_cell.linked_to(yet_another_cell) is True

    a_cell.unlink(another_cell)

    assert a_cell.linked_to(another_cell) is False
    assert another_cell.linked_to(a_cell) is False
    assert a_cell.linked_to(yet_another_cell) is True
    assert yet_another_cell.linked_to(a_cell) is True

def test_unlinking_using_operator_overloads() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)
    a_cell += another_cell
    a_cell += yet_another_cell

    assert a_cell & another_cell
    assert another_cell & a_cell
    assert a_cell & yet_another_cell

    a_cell -= another_cell

    assert not a_cell & another_cell
    assert not another_cell & a_cell
    assert a_cell & yet_another_cell
    assert yet_another_cell & a_cell

def test_links_listing() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)

    a_cell += another_cell
    a_cell += yet_another_cell

    assert set(a_cell.links).intersection([another_cell, yet_another_cell]) == set(a_cell.links)
    assert another_cell.links == [a_cell]
    assert yet_another_cell.links == [a_cell]

def test_has_no_neighbors() -> None:
    assert Cell(1, 1).neighbors == []

def test_has_neighbors() -> None:
    a_cell = Cell(1, 1)
    another_cell = Cell(1, 2)
    yet_another_cell = Cell(2, 1)

    a_cell.north = another_cell
    another_cell.south = yet_another_cell
    yet_another_cell.east = another_cell
    yet_another_cell.west = a_cell

    assert another_cell in a_cell.neighbors
    assert yet_another_cell not in a_cell.neighbors
    assert len(a_cell.neighbors) == 1
    assert a_cell not in another_cell.neighbors
    assert yet_another_cell in another_cell.neighbors
    assert len(another_cell.neighbors) == 1
    assert a_cell in yet_another_cell.neighbors
    assert another_cell in yet_another_cell.neighbors
    assert len(yet_another_cell.neighbors) == 2

def test_distances() -> None:
    a_cell = Cell(0, 0)
    another_cell = Cell(0, 1)
    yet_another_cell = Cell(0, 2)

    a_cell.east = another_cell
    a_cell += another_cell
    another_cell.east = yet_another_cell
    another_cell += yet_another_cell
    distances = a_cell.distances
    assert set(distances.cells) == {yet_another_cell, another_cell, a_cell}
    assert distances[a_cell] == 0
    assert distances[another_cell] == 1
    assert distances[yet_another_cell] == 2


text:
from base.distances import Distances
from base.cell import Cell

def test_index_access() -> None:
    a_cell = Cell(0, 0)
    distances = Distances(a_cell)

    assert distances[a_cell] == 0

    another_cell = Cell(0, 1)
    distance = 13
    distances[another_cell] = distance
    assert distances[another_cell] == distance

    assert distances[Cell(2, 2)] is None

def test_max_distance() -> None:
    cell_1 = Cell(0, 0)
    distances = Distances(cell_1)

    cell_2 = Cell(0, 1)
    distance_from_2_to_1 = 4
    distances[cell_2] = distance_from_2_to_1

    cell_3 = Cell(1, 0)
    distance_from_3_to_1 = 5
    distances[cell_3] = distance_from_3_to_1

    cell_4 = Cell(2, 0)
    distance_from_4_to_1 = 8
    distances[cell_4] = distance_from_4_to_1

    assert distances.max == (cell_4, distance_from_4_to_1,)


text:
from base.grid import Grid
from base.cell import Cell

def test_constructor() -> None:
    grid = Grid(2, 2)
    assert grid.columns == 2
    assert grid.rows == 2

    grid = Grid(3, 3)
    assert grid.columns == 3
    assert grid.rows == 3

def test_cell_access() -> None:
    grid = Grid(2, 2)

    assert grid.cell_at(0, 0) == Cell(0, 0)
    assert grid.cell_at(0, 1) == Cell(0, 1)
    assert grid.cell_at(1, 0) == Cell(1, 0)
    assert grid.cell_at(1, 1) == Cell(1, 1)

    assert grid.cell_at(-1, 0) is None
    assert grid.cell_at(0, -1) is None
    assert grid.cell_at(4, 0) is None
    assert grid.cell_at(0, 4) is None

def test_cell_access_using_operator_overloads() -> None:
    grid = Grid(2, 2)

    assert grid[0, 0] == Cell(0, 0)
    assert grid[0, 1] == Cell(0, 1)
    assert grid[1, 0] == Cell(1, 0)
    assert grid[1, 1] == Cell(1, 1)

    assert grid[-1, 0] is None
    assert grid[0, -1] is None
    assert grid[4, 0] is None
    assert grid[0, 4] is None

def test_neighbors_setup_when_grid_is_created() -> None:
    grid = Grid(2, 2)

    assert grid[0, 0].north is None        # type: ignore
    assert grid[0, 0].south == Cell(1, 0)  # type: ignore
    assert grid[0, 0].east == Cell(0, 1)   # type: ignore
    assert grid[0, 0].west is None         # type: ignore

    assert grid[0, 1].north is None        # type: ignore
    assert grid[0, 1].south == Cell(1, 1)  # type: ignore
    assert grid[0, 1].east is None         # type: ignore
    assert grid[0, 1].west == Cell(0, 0)   # type: ignore

    assert grid[1, 0].north == Cell(0, 0)  # type: ignore
    assert grid[1, 0].south is None        # type: ignore
    assert grid[1, 0].east == Cell(1, 1)   # type: ignore
    assert grid[1, 0].west is None         # type: ignore

    assert grid[1, 1].north == Cell(0, 1)  # type: ignore
    assert grid[1, 1].south is None        # type: ignore
    assert grid[1, 1].east is None         # type: ignore
    assert grid[1, 1].west == Cell(1, 0)   # type: ignore

def test_random_cell() -> None:
    grid = Grid(2, 2)

    for _ in range(100):
        assert grid.random_cell() in [Cell(0, 0), Cell(0, 1), Cell(1, 0), Cell(1, 1)]

def test_size() -> None:
    assert Grid(2, 2).size == 4
    assert Grid(3, 3).size == 9
    assert Grid(4, 4).size == 16


text:
import subprocess
import sys

SOURCE_FOLDER = "."

def test_flake8_compliance() -> None:
    flake8_binary = subprocess.check_output("which flake8",
                                            shell=True,
                                            stderr=sys.stderr).decode("ascii").replace("\n", "")

    result = subprocess.call("{} {}".format(flake8_binary, SOURCE_FOLDER),
                             shell=True,
                             stdout=sys.stdout,
                             stderr=sys.stderr)
    assert result == 0

def test_mypy_compliance() -> None:
    mypy_binary = subprocess.check_output("which mypy",
                                          shell=True,
                                          stderr=sys.stderr).decode("ascii").replace("\n", "")

    result = subprocess.call("{} --ignore-missing-imports --disallow-untyped-defs --check-untyped-defs"
                             " --warn-redundant-casts --warn-return-any --warn-unused-ignores --strict-optional"
                             " {}".format(mypy_binary, SOURCE_FOLDER),
                             shell=True,
                             stdout=sys.stdout,
                             stderr=sys.stderr)
    assert result == 0


text:
List of Data Science/Big Data Resources
======================
This list contains free learning resources for data science and big data related concepts, techniques, and applications. Inspired by [Free Programming Books](https://github.com/vhf/free-programming-books).

Each entry provides the expected audience for the certain book (beginner, intermediate, or veteran). It may be subjective, but it provides some clue of how difficult the book is.

### How To Contribute
- Fork
- Edit, and add your recommendations (for beginner, intermediate, or veteran)
- Send a Pull Request

### Index
* [Data Science Introduction](#data-science-introduction)
* [Data Processing](#big-data-processing)
* [Data Analysis](#big-data-analysis)
	* [Fundamentals](#fundamentals)
	* [Network Analysis](#network-analysis)
	* [Statistics](#statistics)
	* [Data Mining](#data-mining)
	* [Machine Learning](#machine-learning)
* [Data Science Application](#big-data-application)
	* [Data Visualization](#data-visualization)
* [Uncategorized](#uncategorized)
* [MOOCs about Data Science](#moocs)

### Data Science Introduction
* [Data Science: An Introduction](http://en.wikibooks.org/wiki/Data_Science:_An_Introduction) - Wikibook - `Beginner`
* [Disruptive Possibilities: How Big Data Changes Everything](http://www.amazon.com/Disruptive-Possibilities-Data-Changes-Everything-ebook/dp/B00CLH387W) - Jeffrey Needham - `Beginner`
* [Introduction to Data Science](http://jsresearch.net/) - Jeffery Stanton - `Beginner`
* [Real-Time Big Data Analytics: Emerging Architecture](http://www.amazon.com/Real-Time-Big-Data-Analytics-Architecture-ebook/dp/B00DO33RSW) - Mike Barlow - `Beginner`
* [The Evolution of Data Products](http://www.amazon.com/The-Evolution-Data-Products-ebook/dp/B005QEKQUY/ref=sr_1_63?s=digital-text&ie=UTF8&qid=1351898530&sr=1-63) - Mike Loukides - `Beginner`
* [The Promise and Peril of Big Data](http://www.aspeninstitute.org/sites/default/files/content/docs/pubs/The_Promise_and_Peril_of_Big_Data.pdf) - David Bollier - `Beginner`

### Data Processing
* [Data-Intensive Text Processing with MapReduce](http://lintool.github.io/MapReduceAlgorithms/MapReduce-book-final.pdf) - Jimmy Lin and Chris Dyer - `Intermediate`

### Data Analysis
#### Fundamentals
* [Fundamental Numerical Methods and Data Analysis](http://ads.harvard.edu/books/1990fnmd.book/) - George W. Collins - `Beginner`
* [Introduction to Metadata](http://www.getty.edu/research/publications/electronic_publications/intrometadata/index.html) - Murtha Baca - `Beginner`
* [Introduction to R - Notes on R: A Programming Environment for Data Analysis and Graphics](http://cran.r-project.org/doc/manuals/R-intro.pdf) - W. N. Venables, D. M. Smith, and the R Core Team - `Beginner`
* [Modeling with Data: Tools and Techniques for Scientific Computing](http://modelingwithdata.org/about_the_book.html) - Ben Klemens - `Beginner`
* [R for Data Science: Import, Tidy, Transform, Visualize, and Model Data](http://r4ds.had.co.nz/) - Hadley Wickham & Garrett Grolemund - `Beginner`
- [Advanced R](http://adv-r.had.co.nz/) - Hadley Wickham - `Intermediate`

#### Network Analysis
* [Introduction to Social Network Methods](http://faculty.ucr.edu/~hanneman/nettext/) - Robert A. Hanneman and Mark Riddle - `Intermediate`
* [Networks, Crowds, and Markets: Reasoning About a Highly Connected World](http://www.cs.cornell.edu/home/kleinber/networks-book/) - David Easley and Jon Kleinberg - `Intermediate`
* [Network Science](http://barabasilab.neu.edu/networksciencebook/downlPDF.html) - Sarah Morrison - `Beginner`
* [The Wealth of Networks](http://www.benkler.org/Benkler_Wealth_Of_Networks.pdf) - Yochai Benkler - `Beginner`

#### Statistics
* [Advanced Data Analysis from an Elementary Point of View](http://www.stat.cmu.edu/~cshalizi/ADAfaEPoV/ADAfaEPoV.pdf) - Cosma Rohilla Shalizi - `Veteran`
* [An Introduction to R](http://cran.r-project.org/doc/manuals/R-intro.pdf) - W. N. Venables, D. M. Smith, and the R Core Team - `Beginner`
* [Analyzing Linguistic Data: a practical introduction to statistics](http://www.ualberta.ca/~baayen/publications/baayenCUPstats.pdf) - R. H. Baayan - `Beginner`
* [Applied Data Science](http://columbia-applied-data-science.github.io/appdatasci.pdf) - Ian Langmore and Daniel Krasner - `Intermediate`
* [Concepts and Applications of Inferential Statistics](http://vassarstats.net/textbook/) - Richard Lowry - `Beginner`
* [Forecasting: Principles and Practice](https://www.otexts.org/fpp/) - Rob J. Hyndman and George Athanasopoulos - `Intermediate`
* [Introduction to Probability](http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/pdf.html) - Charles M. Grinstead and J. Laurie Snell - `Beginner`
* [Introduction to Statistical Thought](http://www.math.umass.edu/~lavine/Book/book.pdf) - Michael Lavine - `Beginner`
* [OpenIntro Statistics - Second Edition](http://www.openintro.org/stat/textbook.php) - David M. Diez, Christopher D. Barr, and Mine Cetinkaya-Rundel - `Beginner`
* [simpleR - Using R for Introductory Statistics](http://cran.r-project.org/doc/contrib/Verzani-SimpleR.pdf) - John Verzani - `Beginner`
* [Statistics](http://upload.wikimedia.org/wikipedia/commons/8/82/Statistics.pdf) - `Beginner`
* [Think Stats: Probability and Statistics for Programmers v2.0](http://greenteapress.com/thinkstats2/thinkstats2.pdf) - Allen B. Downey - `Beginner`
* [Computer Age Statistical Inference: Algorithms, Evidence and Data Science](https://web.stanford.edu/~hastie/CASI/) - Bradley Efron and Trevor Hastie - `Intermediate`

#### Data Mining
* [Data Mining and Analysis: Fundamental Concepts and Algorithms](https://repo.palkeo.com/algo/information-retrieval/Data%20mining%20and%20analysis.pdf) - Mohammed J. Zaki and Wagner Meira Jr. - `Intermediate`
* [Data Mining and Knowledge Discovery in Real Life Applications](http://www.intechopen.com/books/data_mining_and_knowledge_discovery_in_real_life_applications) - Julio Ponce and Adem Karahoca - `Beginner`
* [Data Mining for Social Network Data](http://link.springer.com/book/10.1007%2F978-1-4419-6287-4) - Springer - `Veteran`
* [Mining of Massive Datasets](http://infolab.stanford.edu/~ullman/mmds/book.pdf) - Anand Rajaraman, Jure Leskovec, and Jeffrey D. Ullman - `Intermediate`
* [Knowledge-Oriented Applications in Data Mining](http://www.intechopen.com/books/knowledge-oriented-applications-in-data-mining) - Kimito Funatsu - `Intermediate`
* [New Fundamental Technologies in Data Mining](http://www.intechopen.com/books/new-fundamental-technologies-in-data-mining) - Kimito Funatsu - `Intermediate`
* [R and Data Mining: Examples and Case Studies](http://cran.r-project.org/doc/contrib/Zhao_R_and_data_mining.pdf) - Yanchang Zhao - `Beginner`
* [The Elements of Statistical Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/) - Trevor Hastie, Robert Tibshirani, and Jerome Friedman - `Intermediate`
* [Theory and Applications for Advanced Text Mining](http://www.intechopen.com/books/theory-and-applications-for-advanced-text-mining) - Shigeaki Sakurai - `Intermediate`

#### Machine Learning
* [A Course in Machine Learning](http://ciml.info/) - Hal Daume - `Beginner`
* [A First Encounter with Machine Learning](https://www.ics.uci.edu/~welling/teaching/273ASpring10/IntroMLBook.pdf) - Max Welling - `Beginner`
* [Bayesian Reasoning and Machine Learning](http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/031013.pdf) - David Barber - `Veteran`
* [Gaussian Processes for Machine Learning](http://www.gaussianprocess.org/gpml/chapters/) - Carl Edward Rasmussen and Christopher K. I. Williams - `Veteran`
* [Introduction to Machine Learning](http://alex.smola.org/drafts/thebook.pdf) - Alex Smola and S.V.N. Vishwanathan - `Intermediate`
* [Probabilistic Programming & Bayesian Methods for Hackers](http://camdavidsonpilon.github.io/Probabilistic-Programming-and-Bayesian-Methods-for-Hackers/) - Cam Davidson-Pilon (main author) - `Intermediate`
* [The LION Way: Machine Learning plus Intelligent Optimization](http://www.lionsolver.com/LIONbook/) - Robert Battiti and Mauro Brunato - `Intermediate`
* [Thinking Bayes](http://www.greenteapress.com/thinkbayes/) - Allen B. Downey - `Beginner`
* [Sklearn Basics](http://nbviewer.ipython.org/github/jakevdp/sklearn_scipy2013/tree/master/notebooks/) - `Beginner`
* [Deep Learning](http://www.deeplearningbook.org) - Ian Goodfellow, Yoshua Bengio and Aaron Courville - `Intermediate`

### Data Science Application
#### Information Retrieval
* [Introduction to Information Retrival](http://nlp.stanford.edu/IR-book/) - Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schutze - `Intermediate`

#### Data Visualization
* [Interactive Data Visualization for the Web](http://chimera.labs.oreilly.com/books/1230000000345/index.html) - Scott Murray - `Beginner`
* [Plotting and Visualization in Python](http://nbviewer.ipython.org/urls/gist.github.com/fonnesbeck/5850463/raw/a29d9ffb863bfab09ff6c1fc853e1d5bf69fe3e4/3.+Plotting+and+Visualization.ipynb) - `Beginner`
* [ggplot2: Elegant Graphics for Data Analysis](https://github.com/hadley/ggplot2-book) - Hadley Wickham - `Beginner`

### Uncategorized
* [Data Journalism Handbook](http://datajournalismhandbook.org/1.0/en/) - Jonathan Gray, Liliana Bounegru, and Lucy Chambers - `Beginner`
* [Building Data Science Teams](http://assets.en.oreilly.com/1/eventseries/23/Building-Data-Science-Teams.pdf) - DJ Patil - `Beginner`
* [Information Theory, Inference, and Learning Algorithms](http://www.inference.phy.cam.ac.uk/itprnn/book.html) - David MacKay - `Intermediate`
* [Mathematics for Computer Science](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf) - Eric Lehman, Thomas Leighton, and Albert R. Meyer - `Beginner`
* [The Field Guide to Data Science](http://www.boozallen.com/media/file/The-Field-Guide-to-Data-Science.pdf) - `Beginner`

### MOOCs about Data Science
* [Data Mining with Weka](http://www.cs.waikato.ac.nz/ml/weka/mooc/dataminingwithweka/) - Ian H. Witten - `Intermediate`
* [Mining Massive Datasets](https://class.coursera.org/mmds-002) - Jeff Ullman, Jure Leskovec, Anand Rajaraman (Coursera) - `Beginner`
* [Introduction to Data Science](https://class.coursera.org/datasci-001/class) - Bill Howe (Coursera) - `Beginner`
* [Introduction to Hadoop and MapReduce](https://www.udacity.com/course/ud617) - Udacity - `Beginner`
* [Machine Learning](https://class.coursera.org/ml-003/class) - Andrew Ng (Coursera) - `Beginner`
* [Machine Learning Video Library](http://work.caltech.edu/library/#!?goback=.gde_35222_member_5810981726511443971) - Yaser Abu-Mostafa - `Intermediate`
* [Natural Language Processing](https://class.coursera.org/nlp/lecture/preview) - Dan Jurafsky and Christopher Manning (Coursera) - `Intermediate`
* [Social and Economic Networks: Models and Analysis](https://class.coursera.org/networksonline-001/class) - Matthew O. Jackson (Coursera) - `Intermediate`
* [Social Network Analysis](https://class.coursera.org/sna-003/class) - Lada Adamic (Coursera) - `Intermediate`
* [Deep Learning](https://www.coursera.org/specializations/deep-learning) - Andrew Ng (Coursera) - `Intermediate`

## License

[![CC0](http://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg)](https://creativecommons.org/publicdomain/zero/1.0/)

repo_name: chaconnewu/free-data-science-books


text:
# Implementation notes

## Persistence providers -- state-based

### GIDC

1. Verify object unpacks correctly (therefore, correct file hash)
2. Add to known authors and object store if successful

### GEOC

1. Verify object unpacks correctly
2. Verify object author is known to persister
3. Verify object signature
4. Verify a binding for object already exists
5. Add to object store if successful

### GOBS

1. Verify object unpacks correctly
2. Verify object author is known to persister
3. Verify object signature
4. Verify no pre-existing debinding for GOBS address exists (NOT the target)
5. Add to object store if successful

### GOBD

1. Verify object unpacks correctly
2. Verify object author is known to persister
3. Verify object signature
4. Verify no pre-existing debinding for the GOBD dynamic address exists (NOT the target)
5. State verification:
    + If persistence provider has no existing GOBD at that dynamic address:
        1. Verify GOBD has no history
        2. Verify dynamic address is correctly constructed
    + If persistence provider has an existing GOBD at that dynamic address:
        1. Verify author of new frame matches existing author
        2. Verify history of new frame contains (at least) most recent existing frame
6. Add to object store if successful

### GDXX

1. Verify object unpacks correctly
2. Verify object author is known to persister
3. Verify object signature
4. Verify no pre-existing debinding for GDXX address exists (NOT the target)
5. Verify author/recipient is same as referenced object
6. Add to object store if successful

### GARQ

1. Verify object unpacks correctly
2. Verify object recipient is known to persister
3. Verify no pre-existing debinding for GARQ address exists (NOT the target)
4. Add to object store if successful

repo_name: Muterra/doc-golix


text:
**Warning:** this repo is considered public pre-release information and is in varying levels of completeness. If you have questions or comments, please [contact us](mailto:badg@muterra.io).

# Introduction

## Almost plain English

**Golix is a cryptographic protocol:**

+ It's a set of rules
+ that computer programs can agree on in advance,
+ which mathematically prove (with a few assumptions)
+ that a piece of data comes from a specific person,
+ and that the data cannot be seen by any third-parties.

**It is trustless and self-authenticating:**

+ Unlike Google or Facebook, large companies built on Golix cannot see your data
+ Unlike Google or Facebook, you "log in" to Golix once locally (on *your* computer, not over the web), and that proves to everyone else that you are who you say you are
+ You don't need to contact a third party to log in, so it works (for example) within your home wireless network, even if your internet connection goes out

**It is fully social:**

+ You can share and re-share data, at any time, with anyone
+ Unless and until you explicitly share something, it is provably private

**It is especially well-suited to the "Internet of Things" (IoT):**

+ Golix works regardless of your internet connection
+ It is substantially simpler to develop on than existing IoT frameworks
+ It is designed to work with many, many more total devices than exist on the internet today
+ It doesn't expose your IoT devices to the "outside world"

## More specifically

If I'm ```Alice```, the point of Golix is that:

1. I, ```Alice```, am always ```Alice```, and ```Alice``` is always me.
    1. If ```someone``` shares something with me, they are guaranteed to be sharing with ```Alice```.
    2. If I share something with ```someone```, they are guaranteed it comes from ```Alice```.
2. When I, ```Alice```, create some piece of data, I am guaranteed that ```no one``` else can see it. This also includes the servers where the data is stored.
3. I *may* choose to share that data with ```anyone```, at any time. I may also choose *not* to share it.
    1. Once I share it with ```someone```, they may share it with ```anyone``` else, at any time, without any restriction.
    2. Those recipients may, in turn, re-share it with ```anyone``` else, and so on.
    3. There will be no public record of who has shared with whom.
4. The data that I, ```Alice```, create, cannot be altered by ```anyone``` at any time, including by myself.
5. That data will always be available at the same place.
    1. It will always be accessible from a singular, exclusive, consistent address.
    2. Any new servers that host it will preserve and reuse that address.
6. I may also create a unique, consistent address for dynamic content.
    1. This dynamic content will be composed of the unalterable pieces of data from (5).
    2. The referent of this dynamic address (which piece of data it points to) can only be changed by me, ```Alice```.
    3. ```Anyone``` can see and use this dynamic address.
7. I may at any time declare a piece of data "in use".
    1. This is a matter of public record. ```Anyone``` can see that I, ```Alice```, am using that data.
    2. ```Anyone``` else may also declare the data "in use", regardless of who created it.
8. Servers must retain data if, and only if, it is declared "in use".

These constraints are enforced by:

1. Cryptography (```Alice``` is identified only by her public key fingerprint).
2. Cryptography (```Alice``` encrypts all data client-side immediately upon creation).
3. Cryptography (Sharing is defined as the transfer of the secret key for the data, and the key is shared asymmetrically, **separately** from the data itself).
4. Cryptography (Data is statically addressed by its hash digest).
5. Cryptography (Data is statically addressed by its hash digest, as per above).
6. Cryptography (```Alice``` must sign all dynamic addresses she creates, and monotonicity is enforced through a hash chain).
7. Cryptography (```Alice``` must sign all data "bindings" she creates).
8. Auditing the servers (in the long term, this could be enforced via blockchain).

Note: here, ```Alice```, ```anyone```, ```no one```, and ```someone``` are *digital* entities. They may or may not have any relationship to *physical* entities: they could be a Nest thermostat, a person, a business, purely digital, etc.

# Technical discussion

**Abstract:** Golix provides end-to-end encryption for distributed agent-based networks, especially internet-connected physical devices (IoT), while substantially simplifying their development. This document begins with a brief overview of the Golix protocol, followed by a more detailed discussion of its most important aspects.

Other documents:

+ [See it in action](https://github.com/Muterra/py_hypergolix_demos)
+ [Python protocol implementation](https://github.com/Muterra/py_golix)
+ [System whitepaper](whitepaper.md)
+ [Full technical specification](spec.md)
+ [Security whitepaper](security-whitepaper.md)
+ [Changelog](changelog.md)

-----

The Golix protocol is the result of several observations:

1. Third-party servers are more economically scalable than personal servers, and will therefore always be attractive to certain consumers
2. Trusting third-party servers with information access control and retention lifetime may be inappropriate for some (or all) kinds of information
3. Certificate issuance does not map well to massively distributed systems like social networks or smart devices
4. Using IP addresses, URLs, and authentication tokens to communicate between nodes on such distributed systems profoundly complicates their development

As a result, Golix:

1. Embraces third-party centralized servers, but also supports federation
2. Uses cryptography to enforce data access control, and a consensus process to enforce data lifetimes, minimizing necessary server trust
3. Establishes trust-on-first-use consistent entity "identities" from a combination of public keys (addressed by their hash fingerprints)
4. Addresses information and identities by the cryptographic hash digest of its content

Golix is a relatively low-level protocol and is not intended for *direct* use in a human-readable network. Conceptually, it is very similar to a virtual private network, except instead of connecting physical devices (eg an individual computer), it connects abstract entities (eg a particular user) -- as represented by a particular set of public/private keypairs.

Golix is the core technology powering [Hypergolix](https://www.hypergolix.com), a local background service that drastically simplifies IoT development. If you'd like to stay updated, please join the [Hypergolix mailing list](https://www.hypergolix.com/#page-top). **Note that the Golix Protocol used to be called "the Muse protocol".** It was re-branded as Golix in February 2016.

# Contributing

Help is welcome and needed. Unfortunately we're so under-staffed that we haven't even had time to make a thorough contribution guide. In the meantime:

## Guide

+ Issues are great! Open them for anything: feature requests, bug reports, etc.
+ Fork, then PR.
+ Open an issue for every PR.
  + Use the issue for all discussion.
  + Reference the PR somewhere in the issue discussion.
+ Please be patient. We'll definitely give feedback on anything we bounce back to you, but especially since we lack a contribution guide, style guide, etc, this may be a back-and-forth process.
+ Please be courteous in all discussion.

## Project priorities

Note: these needs are specific to external contributors. Internal development priorities differ substantially.

+ Contribution guide
+ Code of conduct
+ Protocol security audits
+ Slack channel (or similar)

See also:

+ [Hypergolix contributions](https://github.com/Muterra/py_hypergolix#contributing)
+ [Hypergolix demo contributions](https://github.com/Muterra/py_hypergolix_demos#contributing)

## Sponsors and backers

If you like what we're doing, please consider [sponsoring the project](https://opencollective.com/golix#sponsor) or [becoming a backer](https://opencollective.com/golix).

**Sponsors**

-----

**Backers**

# Entity-agents and their identities

In the physical world, every deliberate change of state is the result of autonomous action by a physical entity. Golix uses cryptographic "identities" -- basically, a collection of public/private keypairs -- as a direct digital analogue to such physical entities. In exactly the same way as a person is required to build a house, on a Golix network, an identity is required to create data.

As the basic unit of agency on a Golix network, these entities have three capabilities:

1. They may always create new information
2. They may always retain existing information
3. They may always share existing information

However, the borders of agency on a Golix network are relatively strict. Golix information, once shared, cannot be explicitly controlled: every party with knowledge of that information will always ultimately retain the power to re-share that information, in exactly the same way that a conversation can always be repeated to a third party. Influence over others' actions on a Golix network remains explicitly social; as in the physical world, there is no algorithmic limit to second-party agency. Similarly, the creator of information is afforded no special privileges on a Golix network.

It is important to note that these identities have no inherent relation to the physical world. At a protocol level, Golix entities are identified **exclusively** by the fingerprint of their public keys. Golix provides no inherent verification mechanism; these must be constructed on top of the protocol. As such, in terms of physical identities, a Golix ```identity``` may be anonymous, pseudonymous, or eponymous, entirely depending on the content the identity creates and the services it interacts with.

# Content

All information on a Golix network is private by default; entities use client-side encryption prior to upload to enforce this confidentiality without trusting third-party servers. Because these third-party "persistence providers" (basically, Golix-compliant servers) retain content until it is explicitly removed, Golix is best described as an at-rest encryption scheme. However, unlike existing at-rest protocols (for example, PGP), Golix data is infinitely and dynamically sharable. In other words, any privileged entity (*ie* any ```identity``` with the information's symmetric key) may share anything with anyone at any time. This is only possible through complete separation of data encapsulation from key encapsulation.

The lifetime of this content, once uploaded, is determined by consensus agreement. Data containers themselves are fully volatile; analogously to reference-counting memory-managed programming languages, data only persists so long as it has been referenced by a Golix binding. There are no restrictions on binding: any entity may bind to any content at any time. Only the binding entity may remove the binding; however, their ```identity``` address (again, the public key fingerprint) is retained as public metadata in the binding, meaning:

1. The data's binder, and not its author, can be held accountable for (*ie* billed for) its persistence
2. Anyone requesting takedown of the data (copyright claims, right to be forgotten, etc) may pursue social, legal, or economic action against the binder directly, without involving persistence providers

Furthermore, a specific kind of binding (appropriately but unoriginally termed a "dynamic binding") supports dynamic content. Dynamic bindings may only be modified (updated or removed) by their binder, and are crucial for applying the static Golix address system to mutable content.

# Addresses

All Golix addresses are cryptographic hash digests, which makes server path information irrelevant to client requests. Because all Golix data is encrypted, we can also safely remove authorization restrictions on downstream physical information delivery. Together, these have the effect of wholly decoupling the network infrastructure from communications between entities. Communication state is entirely separate from connection state; "session" management and authentication is handled entirely client-side, purely based on the availability of private keys in memory, while the underlying client manages all connection information ephemerally and automatically.

This is incredibly powerful; not only does it allow applications to completely ignore IP addresses, it allows them to self-authenticate. In contrast to those *network-oriented* addresses necessary for physical data delivery, hash addressing allows for an *agent-oriented* architecture: network topology becomes irrelevant to applications, which focus directly on "who" said "what" to "whom".

To explicitly reiterate, note that hash addressing is also applied to the Golix entities themselves. This is especially important for portable devices; by assigning an autonomous device its own dedicated Golix ```identity```, it becomes trivially reachable and discoverable by any other ```identity``` **regardless of the underlying connection infrastructure**.