Obrint la caixa forta

Avís

Per a resoldre aquest exercici no es poden fer servir iteracions (ni for ni while ), només les funcions predefinides de Python i les dels mòduls itertools, functools i operator. Tampoc es poden fer servir llistes, tuples, diccionaris ni cap altra estructura de dades per a desar tots els elements dels iterables.

Un ric empresari d’avançada edat mor i deixa en herència el contingut de la seva caixa forta. El problema és que ningú no coneix la combinació de la caixa, i els hereus no poden obrir-la fàcilment. Sortosament, el besnét preferit del difunt aporta una pista:

Un dia el besavi em va dir que els seus dos nombres de la sort eren el 17 i el 13. Ara no recordo si la combinació de la caixa forta és un múltiple de 17 que conté 13 o bé un múltiple de 13 que conté 17.

El més espavilat de la família s’adona que, com que la combinació de la caixa forta està composta de cinc dígits, si en un principi hi ha milers de combinacions possibles, aquesta pista redueix tant les possibilitats que en pocs minuts la pot tenir oberta. Ara, només li manca conèixer aquestes possibles combinacions. Per això us demana ajuda a vosaltres, que sabeu programar en Python.

Deseu les funcions següents al fitxer caixa_forta.py.

1. Dissenyeu la funció següent:

   caixa_forta.combinacions(n)

   Donat un enter positiu n, retorna un iterador sobre totes les possibles combinacions que tenen n dígits, incloent les que tenen zeros a l’esquerra. Les combinacions generades per l’iterador, han de ser strings de n dígits i han d’estar en ordre creixent:

   
   >>> from caixa_forta import combinacions
   >>> it = combinacions(2)
   >>> for x in it:
   ...    print (x, end=" ")
   00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
   >>> next(it)
   Traceback (most recent call last):
    ...
   StopIteration
   >>> len(list(combinacions(4)))
   10000
   

   Hi ha diverses maneres de resoldre aquest problema. Una d’elles consisteix en utilitzar range() i map(); una altra, itertools.product() i map().

   Disposeu de jocs de prova al fitxer combinacions.txt.

2. Dissenyeu la funció booleana següent:

   caixa_forta.tretze_disset(s)

   Donat un string s que representa un nombre enter, retorna True si i només si el nombre és múltiple de disset i conté el tretze o bé és múltiple de tretze i conté el disset:

   
   >>> from caixa_forta import tretze_disset
   >>> tretze_disset('1300')
   False
   >>> tretze_disset('0170')
   False
   >>> tretze_disset('0117')
   True
   >>> tretze_disset('66130')
   True
   

   Disposeu de jocs de prova al fitxer tretze_disset.txt.

3. Tot seguit dissenyeu la funció següent:

   caixa_forta.filtra_combs(it)

   Donat un iterador que produeix una seqüència de combinacions (strings de dígits), retorna un altre iterador que produeix només les combinacions de la seqüència original que compleixen les condicions esmentades pel besnét. Utilitzeu les funcions tretze_disset() i filter()

   
   >>> from caixa_forta import filtra_combs
   >>> it1 = iter(['0000', '0136', '1139', '1360', '2117', '9999'])
   >>> it2 = filtra_combs(it1)
   >>> for x in it2:
   ...   print (x, end="/")
   0136/1139/1360/
   >>> next(it2)
   Traceback (most recent call last):
    ...
   StopIteration
   

   Disposeu de jocs de prova al fitxer filtra_combs.txt.

4. Finalment, dissenyeu la funció següent:

   caixa_forta.llista_combs(n)

   Donat un enter n, retorna la llista de totes les combinacions bones amb n dígits, en ordre creixent. Utilitzeu les funcions anteriors.

   
   >>> from caixa_forta import llista_combs
   >>> llista_combs(2)
   []
   >>> llista_combs(3)
   ['117', '136']
   >>> llista_combs(4)
   ['0117', '0136', '1139', '1170', '1309', '1326', '1343', '1360', '1377', '1394', '1417', '1513', '1703', '1716', '1729', '1742', '1755', '1768', '1781', '1794', '2171', '2717', '3172', '3213', '4017', '4131', '4173', '4913', '5134', '5174', '5317', '6137', '6175', '6613', '6617', '7176', '7917', '8177', '8313', '9178', '9217']
   >>> len(llista_combs(5))
   539
   
   

   Com veieu, hi ha 539 possibles combinacions bones de cinc dígits. Si heu resolt bé el problema sabreu quines són.

   Disposeu de jocs de prova al fitxer llista_combs.txt.

Solució

Podeu trobar una solució proposada dels exercicis al fitxer caixa_forta.py.