# -*- coding: utf-8 -*-
"""
Quelques problèmes de
`Google Jam <https://code.google.com/codejam/>`_.
:githublink:`%|py|8`
"""
import numpy
[docs]class DiceStraight:
"""
Inspired by `Problem A. Dice Straight
<https://codingcompetitions.withgoogle.com/codejam/
round/0000000000201909/00000000002017fc>`_.
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.
:githublink:`%|py|23`
"""
[docs] def __init__(self, dices):
"""
Dices = list of 6-uples
:githublink:`%|py|28`
"""
self.dices = dices
[docs] @staticmethod
def parse(str_or_file):
"""
Reads the content of a problem
Returns a list of :class:`DiceStraight <ensae_teaching_cs.td_2a.dice.DiceStraight>`.
:param str_or_file: string or filename
:return: list of :class:`DiceStraight <ensae_teaching_cs.td_2a.dice.DiceStraight>`
:githublink:`%|py|39`
"""
if "\n" not in str_or_file:
with open(str_or_file, "r") as f:
str_or_file = f.read()
parsed = []
lines = str_or_file.strip("\n ").split("\n")
nbp = int(lines[0])
pos = 1
for i in range(0, nbp):
nbd = int(lines[pos])
pos += 1
dices = []
for _ in range(0, nbd):
dice = [int(_) for _ in lines[pos].split()]
if len(dice) != 6:
raise ValueError(
"A dice has no 6 faces '{0}'".format(lines[pos]))
pos += 1
dices.append(dice)
parsed.append(DiceStraight(dices))
return parsed
[docs] def __len__(self):
"""
Retourne le nombre de dés.
:githublink:`%|py|64`
"""
return len(self.dices)
[docs] def __str__(self):
"""
Displays dices.
:githublink:`%|py|70`
"""
rows = []
for dice in self.dices:
rows.append('%r' % dice)
return '\n'.join(rows)
[docs] @staticmethod
def max_number_sequences(n):
"""
Returns the maximum number of sequences
given the number of dices.
:githublink:`%|py|81`
"""
res = []
for k in range(1, n + 1):
res.append(((6. * n / k) ** k, k))
return max(res)
[docs] def longest_straight_sequence(self):
"""
Returns one of the longest sequence of consecutive integers.
It returns a list of tuple (face, dice). The implementation
may be improved a lot.
:githublink:`%|py|92`
"""
des = numpy.array(self.dices)
faces = []
nde = []
for i in range(des.shape[0]):
faces.extend(des[i, :])
nde.extend([i for j in range(des.shape[1])])
ensemble = list(zip(faces, nde))
ensemble.sort()
def sequence(ensemble, pos, seq):
des_choisis = set(ensemble[s][1] for s in seq)
face = ensemble[pos][0]
a = pos + 1
while a < len(ensemble) and ensemble[a][0] == face:
a += 1
if a >= len(ensemble) or ensemble[a][0] != face + 1:
# pas possible
return seq
b = a
while b < len(ensemble) and ensemble[b][0] == face + 1:
b = b + 1
seqs = []
for i in range(a, b):
if ensemble[i][1] not in des_choisis:
seq2 = seq.copy()
seq2.append(i)
seq2 = sequence(ensemble, i, seq2)
seqs.append(seq2)
if len(seqs) == 0:
return seq
seqs_len = max([(len(s), s) for s in seqs])
return seqs_len[1]
best = None
for i in range(len(ensemble)):
res = sequence(ensemble, i, [i])
if best is None or len(res) > len(best):
best = res
if len(best) == 1:
return []
res = [ensemble[i] for i in best]
return [(d, f) for (f, d) in res]