Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Quelques problèmes de 

5`Google Jam <https://code.google.com/codejam/>`_. 

6 

7""" 

8import numpy 

9 

10 

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 """ 

24 

25 def __init__(self, dices): 

26 """ 

27 Dices = list of 6-uples 

28 """ 

29 self.dices = dices 

30 

31 @staticmethod 

32 def parse(str_or_file): 

33 """ 

34 Reads the content of a problem 

35 Returns a list of @see cl DiceStraight. 

36 

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 "A dice has no 6 faces '{0}'".format(lines[pos])) 

56 pos += 1 

57 dices.append(dice) 

58 parsed.append(DiceStraight(dices)) 

59 return parsed 

60 

61 def __len__(self): 

62 """ 

63 Retourne le nombre de dés. 

64 """ 

65 return len(self.dices) 

66 

67 def __str__(self): 

68 """ 

69 Displays dices. 

70 """ 

71 rows = [] 

72 for dice in self.dices: 

73 rows.append('%r' % dice) 

74 return '\n'.join(rows) 

75 

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) 

86 

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() 

101 

102 def sequence(ensemble, pos, seq): 

103 des_choisis = set(ensemble[s][1] for s in seq) 

104 face = ensemble[pos][0] 

105 

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 

112 

113 b = a 

114 while b < len(ensemble) and ensemble[b][0] == face + 1: 

115 b = b + 1 

116 

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] 

128 

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 

134 

135 if len(best) == 1: 

136 return [] 

137 res = [ensemble[i] for i in best] 

138 return [(d, f) for (f, d) in res]