module td_2a.dice

Inheritance diagram of ensae_teaching_cs.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