# module `td_2a.dice`¶

## Short summary¶

module `ensae_teaching_cs.td_2a.dice`

Quelques problèmes de Google Jam.

source on GitHub

## Classes¶

class

truncated documentation

`DiceStraight`

Inspired by Problem A. Dice Straight. On dispose de n

## Static Methods¶

staticmethod

truncated documentation

`parse`

Reads the content of a problem Returns a list of `DiceStraight`.

## Methods¶

method

truncated documentation

`__init__`

Dices = list of 6-uples

`__len__`

Retourne le nombre de dés.

`__str__`

Usual.

`compute_edges`

Computes all possible edges.

`compute_paths`

Computes the paths accross every node if the position is included in the node description as triplet. The …

`find_intervals`

We need to find the longest sequence of consecutive face values. We are then looking to order the face values …

`longest_path_length_flow`

We use an algorithm of maximum flow to solve the graph. We use the graph where each node is a triplet *(position, …

`longest_path_length_graph`

This solution is fast as long as the problem does not include too similar dices. In that case, the created …

## Documentation¶

Quelques problèmes de Google Jam.

source on GitHub

class `ensae_teaching_cs.td_2a.dice.``DiceStraight`(dices)[source]

Bases : `object`

Inspired by Problem A. Dice Straight. On dispose de n dés à six faces, chaque face contient un nombre entier. On dispose les dès en ligne en choisissant chaque face de telle sorte que le nombre entier d’un dé précède celui de son voisin de droite, plus exactement, on veut construire une suite d’entiers consécutifs. Le problème consiste à déterminer, pour un jeu de dès donné la séquence la plus longue.

source on GitHub

Dices = list of 6-uples

source on GitHub

`__init__`(dices)[source]

Dices = list of 6-uples

source on GitHub

`__len__`()[source]

Retourne le nombre de dés.

source on GitHub

`__str__`()[source]

Usual.

source on GitHub

`compute_edges`(add_position=True)[source]

Computes all possible edges.

Paramètres

add_position – add position into the node definition

Renvoie

`list of tuple (n1, n2)`

Each node is a triplet: (position, dice, face value) if app_position, a couple (dice, face value) otherwise.

source on GitHub

`compute_paths`(edges)[source]

Computes the paths accross every node if the position is included in the node description as triplet. The function checks that the same dice does not appear twice along the path. The function returns a list of paths described by a list of tuple (dice, face).

source on GitHub

`find_intervals`()[source]

We need to find the longest sequence of consecutive face values. We are then looking to order the face values and to determine intervals of consecutives values. Wwe check that every pair of consecutive numbers can be linked with two different dices.

Renvoie

list of intervals.

source on GitHub

`longest_path_length_flow`(fLOG=<function noLOG>, verbose=False)[source]

We use an algorithm of maximum flow to solve the graph. We use the graph where each node is a triplet (position, dice, face value). Each node is connected to (-1, -1, -1). We add another node (-2, -2, -2) which begins every path. We write N as the number of dices + 1. We add edges to nodes (position, N, N) from every node. We finally add final edges from nodes (position, N, N) to (N, N, N) whose weight is `1/N`. Let’s denote the maximum flow as M. MN determines the longest length.

source on GitHub

`longest_path_length_graph`(fLOG=<function noLOG>)[source]

This solution is fast as long as the problem does not include too similar dices. In that case, the created graph is too big.

source on GitHub

static `parse`(str_or_file)[source]

Reads the content of a problem Returns a list of `DiceStraight`.

Paramètres

str_or_file – string or filename

Renvoie

list of `DiceStraight`

source on GitHub