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