# Quick start#

## 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)
```