# Welcome to tryalgo’s documentation!¶

This Python library implements various algorithms and data structures such as graph, string and computational geometry problems.

Proofs of correctness of these algorithms are available in the French language book: Programmation efficace : les 128 algorithmes qu’il faut avoir compris et codés en Python au cours de sa vie.

## Installation¶

### With PIP¶

You can install the tryalgo package using pip:

\$ pip3 install tryalgo


### From PyPI¶

Download the tar.gz file from PyPI and extract it. The library consists of a directory named tryalgo containing several Python modules.

## First steps¶

### Coin change¶

Here is an dynamic programming example, with coin change (6 lines of source code):

#!/usr/bin/env python3

from tryalgo import coin_change

print(coin_change([3, 5, 11], 29))


Which should print True because 29 can be expressed as the linear combination 6*3 + 0*5 + 1*11.

### Longest palindrome substring of a string¶

In order to find the longest palindrome substring of a string, you can use the implementation of Manacher’s algorithm (source) as follows:

from tryalgo import manacher
print(manacher("babcbabcbaccba"))


which will print (1,10). Indeed, the substring from index 1 to index 10 (excluding position 10) is the palindrome “abcbabcba”.

### Pathfinding¶

Now, suppose you want to compute the shortest paths in the following graph starting at vertex 0.

First, we need to encode this graph with a an adjacency list data structure graph, which format we call listlist, where graph[u] is the list of neighbors of vertex u. The edge weights are simply encoded in a squared matrix:

graph = [[1, 3],
[0, 2, 3],
[1, 4, 5],
[0, 1, 5, 6],
[2, 7],
[2, 3, 7, 8],
[3, 8, 9],
[4, 5, 10],
[5, 6, 10],
[6, 11],
[7, 8],
[9]]

_ = None
#           0  1  2  3  4  5  6  7  8  9 10 11
weights = [[_, 1, _, 4, _, _, _, _, _, _, _, _], # 0
[1, _, 1, 3, _, _, _, _, _, _, _, _], # 1
[_, 1, _, _, 3, 8, _, _, _, _, _, _], # 2
[4, 3, _, _, _, 2, 2, _, _, _, _, _], # 3
[_, _, 3, _, _, _, _, 1, _, _, _, _], # 4
[_, _, 8, 2, _, _, _, 2, 7, _, _, _], # 5
[_, _, _, 2, _, _, _, _, 3, 2, _, _], # 6
[_, _, _, _, 1, 2, _, _, _, _, 3, _], # 7
[_, _, _, _, _, 7, 3, _, _, _, 2, _], # 8
[_, _, _, _, _, _, 2, _, _, _, _, 1], # 9
[_, _, _, _, _, _, _, 3, 2, _, _, _], #10
[_, _, _, _, _, _, _, _, _, 1, _, _]] #11


The shortest path can be computed using Dijkstra’s algorithm, also known as lowest-cost search. Our implementation returns the table of distances from the source and a predecessor table describing the shortest path tree:

from tryalgo import dijkstra

dist, prec = dijkstra(graph, weights, source=0)

node = 10
print(dist[10])  # Will print 9, the distance from node 0 to node 10
path = [node]
while prec[node] is not None:
node = prec[node]
path.append(node)
print(path[::-1])  # Will print [0, 1, 2, 4, 7, 10], a shortest path from 0 to 10


If your graph is sparse (contains few arcs), then you might want to represent it using dictionaries. Formally, the sparse graph representation is a list of dictionaries sparse such that v belongs to sparse[u] if there is an arc (u,v) of weight sparse[u][v]. We call this graph format listdict. For example, the above graph would be represented as:

[{1: 1, 3: 4},
{0: 1, 2: 1, 3: 3},
{1: 1, 4: 3, 5: 8},
{0: 4, 1: 3, 5: 2, 6: 2},
{2: 3, 7: 1},
{2: 8, 3: 2, 7: 2, 8: 7},
{3: 2, 8: 3, 9: 2},
{4: 1, 5: 2, 10: 3},
{5: 7, 6: 3, 10: 2},
{6: 2, 11: 1},
{7: 3, 8: 2},
{9: 1}]


This data structure encodes both the graph and the arc weights, hence it is possible to invoke the function the following way:

dist, prec = dijkstra(sparse, sparse, source=0)