Coverage for src/ensae_teaching_cs/td_2a/dice.py: 97%
79 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Quelques problèmes de
5`Google Jam <https://code.google.com/codejam/>`_.
7"""
8import numpy
11class DiceStraight:
12 """
13 Inspired by `Problem A. Dice Straight
14 <https://codingcompetitions.withgoogle.com/codejam/
15 round/0000000000201909/00000000002017fc>`_.
16 On dispose de *n* dés à six faces, chaque face contient un nombre entier.
17 On dispose les dès en ligne en choisissant chaque face
18 de telle sorte que le nombre entier d'un dé
19 précède celui de son voisin de droite, plus exactement,
20 on veut construire une suite d'entiers consécutifs.
21 Le problème consiste à déterminer, pour un jeu de dès donné
22 la séquence la plus longue.
23 """
25 def __init__(self, dices):
26 """
27 Dices = list of 6-uples
28 """
29 self.dices = dices
31 @staticmethod
32 def parse(str_or_file):
33 """
34 Reads the content of a problem
35 Returns a list of @see cl DiceStraight.
37 @param str_or_file string or filename
38 @return list of @see cl DiceStraight
39 """
40 if "\n" not in str_or_file:
41 with open(str_or_file, "r") as f:
42 str_or_file = f.read()
43 parsed = []
44 lines = str_or_file.strip("\n ").split("\n")
45 nbp = int(lines[0])
46 pos = 1
47 for i in range(0, nbp):
48 nbd = int(lines[pos])
49 pos += 1
50 dices = []
51 for _ in range(0, nbd):
52 dice = [int(_) for _ in lines[pos].split()]
53 if len(dice) != 6:
54 raise ValueError(
55 f"A dice has no 6 faces '{lines[pos]}'")
56 pos += 1
57 dices.append(dice)
58 parsed.append(DiceStraight(dices))
59 return parsed
61 def __len__(self):
62 """
63 Retourne le nombre de dés.
64 """
65 return len(self.dices)
67 def __str__(self):
68 """
69 Displays dices.
70 """
71 rows = []
72 for dice in self.dices:
73 rows.append(f'{dice!r}')
74 return '\n'.join(rows)
76 @staticmethod
77 def max_number_sequences(n):
78 """
79 Returns the maximum number of sequences
80 given the number of dices.
81 """
82 res = []
83 for k in range(1, n + 1):
84 res.append(((6. * n / k) ** k, k))
85 return max(res)
87 def longest_straight_sequence(self):
88 """
89 Returns one of the longest sequence of consecutive integers.
90 It returns a list of tuple (face, dice). The implementation
91 may be improved a lot.
92 """
93 des = numpy.array(self.dices)
94 faces = []
95 nde = []
96 for i in range(des.shape[0]):
97 faces.extend(des[i, :])
98 nde.extend([i for j in range(des.shape[1])])
99 ensemble = list(zip(faces, nde))
100 ensemble.sort()
102 def sequence(ensemble, pos, seq):
103 des_choisis = set(ensemble[s][1] for s in seq)
104 face = ensemble[pos][0]
106 a = pos + 1
107 while a < len(ensemble) and ensemble[a][0] == face:
108 a += 1
109 if a >= len(ensemble) or ensemble[a][0] != face + 1:
110 # pas possible
111 return seq
113 b = a
114 while b < len(ensemble) and ensemble[b][0] == face + 1:
115 b = b + 1
117 seqs = []
118 for i in range(a, b):
119 if ensemble[i][1] not in des_choisis:
120 seq2 = seq.copy()
121 seq2.append(i)
122 seq2 = sequence(ensemble, i, seq2)
123 seqs.append(seq2)
124 if len(seqs) == 0:
125 return seq
126 seqs_len = max([(len(s), s) for s in seqs])
127 return seqs_len[1]
129 best = None
130 for i in range(len(ensemble)):
131 res = sequence(ensemble, i, [i])
132 if best is None or len(res) > len(best):
133 best = res
135 if len(best) == 1:
136 return []
137 res = [ensemble[i] for i in best]
138 return [(d, f) for (f, d) in res]