Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Rechercher
- » De miq
Pages : 1
#1 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Jeu abstrait : Tapaoumec » 07-02-2014 09:37:36
si n=6, (cas pair) on a les n-list de pièces symétriques suivantes, avec leur distance associée et le nombre de cases possibles en face de cette distance :
(1,5) - 1 - 2
(2,4) - 2 - 2
(3) - 3 - 1
si n=7, (cas impair) on a les n-list de pièces symétriques suivantes, avec leur distance associée et le nombre de cases possibles en face de cette distance :
(1,6) - 1 - 2
(2,5) - 2 - 2
(3,4) - 3 - 2
On voit que pour chaque pièce possible, il existe 2 positions valides. La seule exception vient de la pièce n/2 des cas pairs. Celle-ci n'a qu'une position possible, quel que soit le moment ou elle est jouée, alors que toutes les autres pièces ont en général 2 choix, 1 seul jouées juste après leur co-listaire.
Il faudrait refaire le calcul précédent en prenant en compte ces symétries de pièces pour réduire drastiquement les solutions de l'arbre et se rapprocher d'un comparatif équilibré des parties gagnantes possibles.
#2 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Jeu abstrait : Tapaoumec » 07-02-2014 08:32:29
Le dernier coup donné étant le coup gagnant, une victoire en un nombre pair de coups c'est du second joueur qui gagne, en un nombre impair c'est le premier.
#3 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Jeu abstrait : Tapaoumec » 06-02-2014 03:36:13
voilà un code non optimisé pour générer les parties sur les petits niveaux.
from itertools import permutations
#pour une position donnée (lettre à partir de A), un décalage donné (chiffre à partir de 1)
#et un sens donné (+1 ou -1) renvoie la nouvelle position de manière cyclique.
#les paramètres et la valeur de retour sont des catactères (sauf signe qui est ±1).
def case(cur,dec,signe):
return chr((ord(cur)-65+signe*int(dec))%n+65)
n=5
#liste des permutations possibles de l'ordre des coups
l=[[str(c) for c in p] for p in permutations(range(1,n))]
#description de chaque premier coup possible
#-élimination de la symétrie par complémentarité des pièces p et n-p au départ
#-placement de la position A devant
l=[['A']+e for e in l if int(e[0])<=n/2]
#description du coup 2
#-ajout de l'orientation du coup (pour l'instant seulement + par symétrie du plateau % A)
#-toutes les cases qu'on peut atteindre sont encore libres
l=[e[:2]+['+',chr(65+int(e[1]))]+e[2:] for e in l]
c=3
wins=[]
while c<n:
#description du coup c
#-ajout de l'orientation du coup (+ ou -)
i=(c-2)*3
nl=[]
for e in l:
nl.append([])
nl[-1].append(e[:i+2]+['+', case(e[i],e[i+1],1)]+e[i+2:])
if int(e[i+1])!=n/2: #filtrage de la symétrie +=- de n/2
nl[-1].append(e[:i+2]+['-', case(e[i],e[i+1],-1)]+e[i+2:])
#-vérification de la liberté de la case
# l=[e for e in nl if e[i+3] not in e[:i+1:3]]
l=[]
for ge in nl:
again=[] #liste des coups possibles de degré n succédants à un coup de degré n-1 donné
for e in ge:
if e[i+3] not in e[:i+1:3]:
again.append(e)
if again==[]: #cas d'un coup n-1 gagnant, on exfiltre ce coup
wins.append(e[:i+2])
else: #sinon on conserve ces coups
l.extend(again)
c+=1
[''.join(e) for e in l]
[''.join(e) for e in wins]
Ce code n'est pas optimisé. idéalement, il faudrait le transformer avec des générateurs, c'est à dire qu'il ne calculerais qu'une partie à la fois, sans mémoriser les autres. C'est faisable mais complexe. Ça permettrait de calculer les premiers cas de partie dès le début de la recherche. Dans sa version actuelle rien que la génération des combinaisons de niveau 16 est explosive en temps et en mémoire.
Au niveau 4 il me génère exactement mes calculs précédents à la main.
Au niveau 5 il trouve 4 parties victorieuses au 3ème coup : ['A1+B2+D3', 'A1+B3-D2', 'A2+C1-B4', 'A2+C4+B1'] (c'est à dire que le coup n'a pas de successeurs possibles valides.)
Les coups commençant pas A3 ne sont pas générés car ils sont symétriques de A1. En fait, en allant plus loin, les deux premiers coups sont symétriques l'un de l'autre également (par permutation des chiffres et rotation des cases) mais ça commence à devenir complexe à filtrer.
voilà les victoires au niveau 6:
['A1+B2+D3', 'A1+B2+D3', 'A1+B4-D3', 'A1+B4-D3', 'A2+C1+D3', 'A2+C1+D3', 'A2+C1-B5', 'A2+C1-B5', 'A2+C5+B1', 'A2+C5+B1', 'A2+C5-D3', 'A2+C5-D3', 'A1+B2-F4+D3', 'A1+B2+D5-E3', 'A1+B2-F5+E3', 'A1+B3+E2-C4', 'A1+B3+E4+C2', 'A1+B4+F2-D3', 'A1+B4+F5+E3', 'A1+B4-D5-E3', 'A1+B5-C2+E3', 'A1+B5-C2+E4', 'A1+B5-C4-E2', 'A1+B5-C4-E3', 'A2+C1-B3+E4', 'A2+C1+D4-F3', 'A2+C1-B4+F3', 'A2+C1-B4-D3', 'A2+C1+D4+B5', 'A2+C1+D5-E4', 'A2+C3+F1-E4', 'A2+C3+F4-B1', 'A2+C3+F4-B5', 'A2+C3+F5+E4', 'A2+C4-E1+F3', 'A2+C4-E1-D3', 'A2+C4-E1+F5', 'A2+C4-E1-D5', 'A2+C4-E3+B1', 'A2+C4-E3+B5', 'A2+C4-E5+D1', 'A2+C4-E5-F1', 'A2+C4-E5+D3', 'A2+C4-E5-F3', 'A2+C5-D1+E4', 'A2+C5+B3+E4', 'A2+C5-D4+B1', 'A2+C5+B4+F3', 'A2+C5+B4-D3', 'A2+C5-D4-F3', 'A3+D1+E2-C4', 'A3+D1-C2+E4', 'A3+D1+E4+C2', 'A3+D1-C4-E2', 'A3+D2+F1-E5', 'A3+D2-B1+C5', 'A3+D2+F5+E1', 'A3+D2-B5-C1', 'A3+D4+B1+C5', 'A3+D4-F1-E5', 'A3+D4+B5-C1', 'A3+D4-F5+E1', 'A3+D5+C2+E4', 'A3+D5-E2-C4', 'A3+D5+C4-E2', 'A3+D5-E4+C2']
et au niveau 7:['A1+B3+E4', 'A1+B3+E4', 'A1+B3+E4', 'A1+B3+E4', 'A1+B3+E4', 'A1+B3+E4', 'A1+B4-E3', 'A1+B4-E3', 'A1+B4-E3', 'A1+B4-E3', 'A1+B4-E3', 'A1+B4-E3', 'A2+C1-B6', 'A2+C1-B6', 'A2+C1-B6', 'A2+C1-B6', 'A2+C1-B6', 'A2+C1-
B6', 'A2+C6+B1', 'A2+C6+B1', 'A2+C6+B1', 'A2+C6+B1', 'A2+C6+B1', 'A2+C6+B1', 'A3+D2+F5', 'A3+D2+F5', 'A3+D2+F5', 'A3+D2+F5', 'A3+D2+F5', 'A3+D2+F5', 'A3+D5-F2', 'A3+D5-F2', 'A3+D5-F2', 'A3+D5-F2', 'A3+D5-F2', 'A3
+D5-F2', 'A1+B2-G3-D4', 'A1+B2-G3-D4', 'A1+B2-G4+D3', 'A1+B2-G4+D3', 'A1+B2-G5+E3', 'A1+B2-G5+E3', 'A1+B2-G5+E4', 'A1+B2-G5+E4', 'A1+B2+D6-E3', 'A1+B2+D6-E3', 'A1+B2+D6-E4', 'A1+B2+D6-E4', 'A1+B3+E2+G5', 'A1+B3+E
2-C5', 'A1+B3-F2-D5', 'A1+B3+E2+G5', 'A1+B3+E2-C5', 'A1+B3-F2-D5', 'A1+B3+E5+C2', 'A1+B3+E5-G2', 'A1+B3-F5+D2', 'A1+B3+E5+C2', 'A1+B3+E5-G2', 'A1+B3-F5+D2', 'A1+B3-F6+E4', 'A1+B3-F6+E4', 'A1+B4+F2-D5', 'A1+B4-E2+
G5', 'A1+B4-E2-C5', 'A1+B4+F2-D5', 'A1+B4-E2+G5', 'A1+B4-E2-C5', 'A1+B4+F5+D2', 'A1+B4-E5+C2', 'A1+B4-E5-G2', 'A1+B4+F5+D2', 'A1+B4-E5+C2', 'A1+B4-E5-G2', 'A1+B4+F6+E3', 'A1+B4+F6+E3', 'A1+B5+G2-E3', 'A1+B5+G2-E3
', 'A1+B5+G2-E4', 'A1+B5+G2-E4', 'A1+B5+G3-D4', 'A1+B5+G3-D4', 'A1+B5+G4+D3', 'A1+B5+G4+D3', 'A1+B5-D6-E3', 'A1+B5-D6-E3', 'A1+B5-D6-E4', 'A1+B5-D6-E4', 'A1+B6-C2+E3', 'A1+B6-C2+E3', 'A1+B6-C2+E4', 'A1+B6-C2+E4',
'A1+B6-C3+F4', 'A1+B6-C3+F4', 'A1+B6-C4-F3', 'A1+B6-C4-F3', 'A1+B6-C5-E3', 'A1+B6-C5-E3', 'A1+B6-C5-E4', 'A1+B6-C5-E4', 'A2+C1+D3+G4', 'A2+C1-B3+E4', 'A2+C1-B3-F4', 'A2+C1+D3+G4', 'A2+C1-B3+E4', 'A2+C1-B3-F4', '
A2+C1+D4-G3', 'A2+C1-B4+F3', 'A2+C1-B4-E3', 'A2+C1+D4-G3', 'A2+C1-B4+F3', 'A2+C1-B4-E3', 'A2+C1+D5+B6', 'A2+C1+D5+B6', 'A2+C3+F1+G6', 'A2+C3+F1+G6', 'A2+C3+F4-B1', 'A2+C3+F4-B1', 'A2+C3+F4-B6', 'A2+C3+F4-B6', 'A2
+C3-G5-B1', 'A2+C3-G5-B1', 'A2+C3-G5-B6', 'A2+C3-G5-B6', 'A2+C3+F6-G1', 'A2+C3+F6-G1', 'A2+C4-F1+G6', 'A2+C4-F1+G6', 'A2+C4-F3+B1', 'A2+C4-F3+B1', 'A2+C4-F3+B6', 'A2+C4-F3+B6', 'A2+C4+G5-B1', 'A2+C4+G5-B1', 'A2+C
4+G5-B6', 'A2+C4+G5-B6', 'A2+C4-F6-G1', 'A2+C4-F6-G1', 'A2+C5-E1-D6', 'A2+C5-E1-D6', 'A2+C5-E3-B1', 'A2+C5-E3-B1', 'A2+C5-E3-B6', 'A2+C5-E3-B6', 'A2+C5-E4+B1', 'A2+C5-E4+B1', 'A2+C5-E4+B6', 'A2+C5-E4+B6', 'A2+C5-
E6+D1', 'A2+C5-E6+D1', 'A2+C6+B3+E4', 'A2+C6+B3-F4', 'A2+C6-D3+G4', 'A2+C6+B3+E4', 'A2+C6+B3-F4', 'A2+C6-D3+G4', 'A2+C6+B4+F3', 'A2+C6+B4-E3', 'A2+C6-D4-G3', 'A2+C6+B4+F3', 'A2+C6+B4-E3', 'A2+C6-D4-G3', 'A2+C6-D5
+B1', 'A2+C6-D5+B1', 'A3+D1+E2-C5', 'A3+D1+E2-C5', 'A3+D1-C4-F2', 'A3+D1-C4-F2', 'A3+D1-C4-F5', 'A3+D1-C4-F5', 'A3+D1+E5+C2', 'A3+D1+E5+C2', 'A3+D1+E6-F2', 'A3+D1+E6-F2', 'A3+D1+E6-F5', 'A3+D1+E6-F5', 'A3+D2+F1+G
6', 'A3+D2+F1-E6', 'A3+D2-B1+C6', 'A3+D2+F1+G6', 'A3+D2+F1-E6', 'A3+D2-B1+C6', 'A3+D2-B4+F5', 'A3+D2-B4+F5', 'A3+D2+F6+E1', 'A3+D2+F6-G1', 'A3+D2-B6-C1', 'A3+D2+F6+E1', 'A3+D2+F6-G1', 'A3+D2-B6-C1', 'A3+D4-G1-F2'
, 'A3+D4-G1-F2', 'A3+D4-G1-F5', 'A3+D4-G1-F5', 'A3+D4-G2+B5', 'A3+D4-G2+B5', 'A3+D4-G5-B2', 'A3+D4-G5-B2', 'A3+D4-G6+F2', 'A3+D4-G6+F2', 'A3+D4-G6+F5', 'A3+D4-G6+F5', 'A3+D5+B1+C6', 'A3+D5-F1+G6', 'A3+D5-F1-E6',
'A3+D5+B1+C6', 'A3+D5-F1+G6', 'A3+D5-F1-E6', 'A3+D5+B4+F2', 'A3+D5+B4+F2', 'A3+D5+B6-C1', 'A3+D5-F6+E1', 'A3+D5-F6-G1', 'A3+D5+B6-C1', 'A3+D5-F6+E1', 'A3+D5-F6-G1', 'A3+D6-E1+F2', 'A3+D6-E1+F2', 'A3+D6-E1+F5', 'A
3+D6-E1+F5', 'A3+D6-E2-C5', 'A3+D6-E2-C5', 'A3+D6+C4-F2', 'A3+D6+C4-F2', 'A3+D6+C4-F5', 'A3+D6+C4-F5', 'A3+D6-E5+C2', 'A3+D6-E5+C2', 'A1+B2+D3+G4-C6', 'A1+B2+D3+G5+E4', 'A1+B2-G3+C5-E4', 'A1+B2-G3+C6-D4', 'A1+B2-
G3-D6-E4', 'A1+B2+D3+G6+F5', 'A1+B2+D4-G3+C6', 'A1+B2+D4-G5+E3', 'A1+B2-G4-C5-E3', 'A1+B2-G4+D6-E3', 'A1+B2-G4-C6-D3', 'A1+B2+D4-G6+F5', 'A1+B2+D5-F3-C6', 'A1+B2+D5-F4+C6', 'A1+B2+D5-F6+E3', 'A1+B2-G5+E6+D3', 'A1
+B2+D5-F6+E4', 'A1+B2-G5+E6+D4', 'A1+B2+D6+C3+F4', 'A1+B2+D6+C3-G4', 'A1+B2-G6+F3-C4', 'A1+B2+D6+C3+F5', 'A1+B2+D6+C4+G3', 'A1+B2+D6+C4-F3', 'A1+B2-G6+F4+C3', 'A1+B2+D6+C4-F5', 'A1+B2+D6+C5-E3', 'A1+B2-G6+F5+D3',
'A1+B2+D6+C5-E4', 'A1+B2-G6+F5+D4', 'A1+B3+E2+G4-C5', 'A1+B3+E2-C4+G5', 'A1+B3-F2-D4-G6', 'A1+B3-F2-D6-E4', 'A1+B3-F4+C6-D2', 'A1+B3-F4+C6-D5', 'A1+B3+E5+C4+G2', 'A1+B3+E5-G4-C2', 'A1+B3-F5+D4-G6', 'A1+B3-F5+D6-
E4', 'A1+B3-F6-G2-E4', 'A1+B3+E6+D2+F5', 'A1+B3+E6-F2-D5', 'A1+B3-F6+E2+G5', 'A1+B3-F6+E2-C5', 'A1+B3+E6+D4-G2', 'A1+B3+E6-F4+C2', 'A1+B3-F6-G4+D2', 'A1+B3+E6+D4-G5', 'A1+B3+E6-F4+C5', 'A1+B3-F6-G4+D5', 'A1+B3+E6
+D5-F2', 'A1+B3+E6-F5+D2', 'A1+B3-F6+E5+C2', 'A1+B3-F6+E5-G2', 'A1+B3-F6-G5+E4', 'A1+B4-E2+G3+C5', 'A1+B4-E2-C3-G5', 'A1+B4+F2-D3+G6', 'A1+B4+F2-D6-E3', 'A1+B4+F3-C6-D2', 'A1+B4+F3-C6-D5', 'A1+B4-E5+C3-G2', 'A1+B
4-E5-G3+C2', 'A1+B4+F5+D3+G6', 'A1+B4+F5+D6-E3', 'A1+B4+F6-G2-E3', 'A1+B4+F6+E2+G5', 'A1+B4+F6+E2-C5', 'A1+B4-E6+D2+F5', 'A1+B4-E6-F2-D5', 'A1+B4+F6-G3-D2', 'A1+B4-E6+D3+G2', 'A1+B4-E6-F3-C2', 'A1+B4+F6-G3-D5', '
A1+B4-E6+D3+G5', 'A1+B4-E6-F3-C5', 'A1+B4+F6+E5+C2', 'A1+B4+F6+E5-G2', 'A1+B4-E6+D5-F2', 'A1+B4-E6-F5+D2', 'A1+B4+F6-G5+E3', 'A1+B5-D2+F3-C6', 'A1+B5-D2+F4+C6', 'A1+B5+G2-E6+D3', 'A1+B5-D2+F6+E3', 'A1+B5+G2-E6+D4
', 'A1+B5-D2+F6+E4', 'A1+B5+G3+C2+E4', 'A1+B5-D3+G2-E4', 'A1+B5-D3+G4-C6', 'A1+B5-D3+G6+F2', 'A1+B5+G3+C6-D4', 'A1+B5+G3-D6-E4', 'A1+B5+G4-C2+E3', 'A1+B5-D4-G2-E3', 'A1+B5-D4-G3+C6', 'A1+B5-D4-G6+F2', 'A1+B5+G4+D
6-E3', 'A1+B5+G4-C6-D3', 'A1+B5+G6+F2-D3', 'A1+B5-D6+C2+E3', 'A1+B5+G6+F2-D4', 'A1+B5-D6+C2+E4', 'A1+B5-D6+C3+F2', 'A1+B5+G6+F3-C4', 'A1+B5-D6+C3+F4', 'A1+B5-D6+C3-G4', 'A1+B5-D6+C4-F2', 'A1+B5+G6+F4+C3', 'A1+B5-
D6+C4+G3', 'A1+B5-D6+C4-F3', 'A1+B6-C3-G2-E4', 'A1+B6-C3+F2-D5', 'A1+B6-C3-G2-E5', 'A1+B6-C3+F5+D2', 'A1+B6-C3-G5+E2', 'A1+B6-C3-G5+E4', 'A1+B6-C4+G2-E3', 'A1+B6-C4+G2-E5', 'A1+B6-C4-F2-D5', 'A1+B6-C4+G5+E2', 'A1
+B6-C4-F5+D2', 'A1+B6-C4+G5+E3', 'A2+C1+D3+G5-B6', 'A2+C1-B3+E6-F4', 'A2+C1-B3-F6+E4', 'A2+C1+D3+G6+F5', 'A2+C1+D4-G5-B6', 'A2+C1-B4+F6+E3', 'A2+C1-B4-E6-F3', 'A2+C1+D4-G6+F5', 'A2+C1+D5+B3+E4', 'A2+C1+D5+B3-F4',
'A2+C1-B5+G3-D4', 'A2+C1-B5-D3+G4', 'A2+C1+D5-F3+B6', 'A2+C1+D5+B4+F3', 'A2+C1+D5+B4-E3', 'A2+C1-B5+G4+D3', 'A2+C1-B5-D4-G3', 'A2+C1+D5-F4-B6', 'A2+C1+D5-F6-G3', 'A2+C1-B5+G6+F3', 'A2+C1-B5-D6-E3', 'A2+C1+D5-F6-
G4', 'A2+C1-B5+G6+F4', 'A2+C1-B5-D6-E4', 'A2+C1+D6-E5-G3', 'A2+C1+D6-E5-G4', 'A2+C3+F1-E4+B6', 'A2+C3-G1-F4-B6', 'A2+C3-G1-F5+D4', 'A2+C3+F1+G5-B6', 'A2+C3+F1-E5-G6', 'A2+C3-G1-F6+E5', 'A2+C3-G4+D1+E5', 'A2+C3+F4
-B5+G1', 'A2+C3-G4+D5+B1', 'A2+C3+F4-B5+G6', 'A2+C3-G4+D5+B6', 'A2+C3-G4+D6-E5', 'A2+C3-G5+E1-D4', 'A2+C3+F5+D1+E6', 'A2+C3-G5+E1+F6', 'A2+C3-G5+E1-D6', 'A2+C3+F5+D4-G1', 'A2+C3-G5+E4+B1', 'A2+C3+F5+D4-G6', 'A2+C
3-G5+E4+B6', 'A2+C3+F5+D6-E1', 'A2+C3-G5+E6+D1', 'A2+C3-G5+E6-F1', 'A2+C3-G5+E6+D4', 'A2+C3-G6+F1-E5', 'A2+C3+F6+E4+B1', 'A2+C3-G6+F4-B1', 'A2+C3+F6+E5-G1', 'A2+C3+F6-G5-B1', 'A2+C3-G6+F5+D4', 'A2+C4+G1-F3+B6', '
A2+C4-F1-E3-B6', 'A2+C4+G1-F5+D3', 'A2+C4-F1+G5-B6', 'A2+C4-F1-E5-G6', 'A2+C4+G1-F6+E5', 'A2+C4+G3-D1+E5', 'A2+C4+G3-D5+B1', 'A2+C4-F3+B5+G1', 'A2+C4+G3-D5+B6', 'A2+C4-F3+B5+G6', 'A2+C4+G3-D6-E5', 'A2+C4+G5+E1-D3
', 'A2+C4+G5+E1+F6', 'A2+C4+G5+E1-D6', 'A2+C4-F5+D1+E6', 'A2+C4+G5+E3-B1', 'A2+C4-F5+D3+G1', 'A2+C4+G5+E3-B6', 'A2+C4-F5+D3+G6', 'A2+C4+G5+E6+D1', 'A2+C4+G5+E6-F1', 'A2+C4-F5+D6-E1', 'A2+C4+G5+E6+D3', 'A2+C4+G6+F
1-E5', 'A2+C4+G6+F3+B1', 'A2+C4-F6+E3-B1', 'A2+C4-F6+E5-G1', 'A2+C4-F6-G5-B1', 'A2+C4+G6+F5+D3', 'A2+C5-E1+F3+B4', 'A2+C5-E1-D3+G4', 'A2+C5-E1+F3+B6', 'A2+C5-E1+F4-B3', 'A2+C5-E1-D4-G3', 'A2+C5-E1+F4-B6', 'A2+C5-
E6-F3+B1', 'A2+C5-E6+D3+G4', 'A2+C5-E6-F3+B4', 'A2+C5-E6-F4-B1', 'A2+C5-E6+D4-G3', 'A2+C5-E6-F4-B3', 'A2+C6-D1+E5-G3', 'A2+C6-D1+E5-G4', 'A2+C6+B3+E1+F4', 'A2+C6+B3-F1-E4', 'A2+C6-D3+G1-F5', 'A2+C6-D3+G5-B1', 'A2
+C6+B4+F1-E3', 'A2+C6+B4-E1+F3', 'A2+C6-D4-G1-F5', 'A2+C6-D4-G5-B1', 'A2+C6+B5+G1-F3', 'A2+C6+B5-D1+E3', 'A2+C6-D5-F1+G3', 'A2+C6+B5+G1-F4', 'A2+C6+B5-D1+E4', 'A2+C6-D5-F1+G4', 'A2+C6-D5-F3+B1', 'A2+C6+B5+G3-D4',
'A2+C6+B5-D3+G4', 'A2+C6-D5+B3+E4', 'A2+C6-D5+B3-F4', 'A2+C6-D5-F4-B1', 'A2+C6+B5+G4+D3', 'A2+C6+B5-D4-G3', 'A2+C6-D5+B4+F3', 'A2+C6-D5+B4-E3', 'A3+D1+E2+G4-C5', 'A3+D1+E2-C4-F5', 'A3+D1-C2+E4+B6', 'A3+D1-C2+E5-
G4', 'A3+D1+E2+G6+F5', 'A3+D1-C2+E6-F5', 'A3+D1+E4+B2-G5', 'A3+D1-C4+G2+B5', 'A3+D1-C4+G2-E5', 'A3+D1-C4+G2+B6', 'A3+D1+E4+B5+G2', 'A3+D1-C4+G5+E2', 'A3+D1-C4+G5-B2', 'A3+D1-C4+G5-B6', 'A3+D1+E4+B6-C2', 'A3+D1-C4
+G6+F2', 'A3+D1+E4+B6-C5', 'A3+D1-C4+G6+F5', 'A3+D1-C5-E2+G4', 'A3+D1+E5+C4-F2', 'A3+D1+E5-G4-C2', 'A3+D1-C5-E4+B6', 'A3+D1+E5-G6+F2', 'A3+D1-C5-E6-F2', 'A3+D1-C6+B2-G4', 'A3+D1+E6-F4+C2', 'A3+D1-C6+B4+F2', 'A3+D
1+E6-F4+C5', 'A3+D1-C6+B4+F5', 'A3+D1-C6+B5+G4', 'A3+D2-B1+C4-F5', 'A3+D2-B1+C5-E4', 'A3+D2+F1+G5+E6', 'A3+D2+F1-E5-G6', 'A3+D2-B4-E1+F5', 'A3+D2+F4+C1-B6', 'A3+D2+F4-B1+C6', 'A3+D2-B4+F1+G6', 'A3+D2-B4+F1-E6', '
A3+D2+F4+C5-E1', 'A3+D2+F4-B5+G1', 'A3+D2-B4-E5+C1', 'A3+D2+F4+C5-E6', 'A3+D2+F4-B5+G6', 'A3+D2-B4-E5+C6', 'A3+D2+F4+C6+B1', 'A3+D2+F4-B6-C1', 'A3+D2-B4+F6+E1', 'A3+D2-B4+F6-G1', 'A3+D2-B4-E6-F5', 'A3+D2-B5+G4-C1
', 'A3+D2-B5+G4-C6', 'A3+D2-B6-C4-F5', 'A3+D2+F6+E5-G1', 'A3+D2+F6-G5+E1', 'A3+D2-B6-C5-E4', 'A3+D4-G2-E1+F5', 'A3+D4-G2+B1+C6', 'A3+D4-G2-E1+F6', 'A3+D4-G2+B6-C1', 'A3+D4-G2-E6-F1', 'A3+D4-G2-E6-F5', 'A3+D4-G5+E
1+F2', 'A3+D4-G5+E1+F6', 'A3+D4-G5-B1+C6', 'A3+D4-G5+E6-F1', 'A3+D4-G5-B6-C1', 'A3+D4-G5+E6-F2', 'A3+D5+B1+C2+E4', 'A3+D5-F1+G2-E6', 'A3+D5-F1-E2+G6', 'A3+D5+B1+C4-F2', 'A3+D5+B2-G4-C1', 'A3+D5+B2-G4-C6', 'A3+D5+
B4-E1+F2', 'A3+D5+B4+F1+G6', 'A3+D5+B4+F1-E6', 'A3+D5-F4+C1-B6', 'A3+D5-F4-B1+C6', 'A3+D5+B4-E2-C1', 'A3+D5-F4+C2+E1', 'A3+D5-F4-B2-G1', 'A3+D5+B4-E2-C6', 'A3+D5-F4+C2+E6', 'A3+D5-F4-B2-G6', 'A3+D5+B4+F6+E1', 'A3
+D5+B4+F6-G1', 'A3+D5-F4+C6+B1', 'A3+D5-F4-B6-C1', 'A3+D5+B4-E6-F2', 'A3+D5-F6+E2+G1', 'A3+D5-F6-G2-E1', 'A3+D5+B6-C2+E4', 'A3+D5+B6-C4-F2', 'A3+D6+C1-B2-G4', 'A3+D6+C1-B4+F2', 'A3+D6-E1+F4+C2', 'A3+D6+C1-B4+F5',
'A3+D6-E1+F4+C5', 'A3+D6+C1-B5+G4', 'A3+D6+C2+E1+F5', 'A3+D6-E2+G1-F5', 'A3+D6+C2+E4+B1', 'A3+D6-E2+G4-C5', 'A3+D6-E2-C4-F5', 'A3+D6+C2+E5-G4', 'A3+D6+C4+G1-F2', 'A3+D6-E4+B1+C2', 'A3+D6+C4+G1-F5', 'A3+D6-E4+B1+
C5', 'A3+D6+C4+G2+B1', 'A3+D6+C4+G2+B5', 'A3+D6+C4+G2-E5', 'A3+D6-E4+B2-G5', 'A3+D6+C4+G5-B1', 'A3+D6+C4+G5+E2', 'A3+D6+C4+G5-B2', 'A3+D6-E4+B5+G2', 'A3+D6+C5-E1+F2', 'A3+D6-E5-G1-F2', 'A3+D6+C5-E2+G4', 'A3+D6+C5
-E4+B1', 'A3+D6-E5+C4-F2', 'A3+D6-E5-G4-C2']
si quelqu'un veut se plonger dedans pour étudier un jeu parfait.
#4 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Jeu abstrait : Tapaoumec » 04-02-2014 02:15:19
bon allez, je craque mes points de sommeil...
Alors 16 cases, 15 nombre, posé à distance du précédent nombre.
nombre de parties possibles = permutations de l'ordre des pièces combiné par les positions à chaque placement...
victoires évidentes ? ben, celui qui pose le 8 restreint la solution suivante possible à 1 seule case en face, donc il ne faut jamais laisser le 8 de libre et donner une solution qui mène sur une case en face d'une case occupée ?
simplifions le jeu:
si n=2 (n est le nombre de cases, n-1 le nombre de pièces) : 1 pièce, 2 cases, parties possibles (1A, 1B(qu'on élimine, c'est une permutation par rapport à la première case jouée)) 1 partie, nulles.
si n=3: 2 pièces, parties possibles (1A-2B, 1A-2C(symétrie par rapport à la précédente, on élimine), 1B-*(permutations), 2A-1C, 2A-1B(symétrie de 2A-1C), 2B-*(permutations)) --> 2 parties nulles.
si n=4: (on ne traitera plus les permutations de cases du premier coup, ni les symétries du placement du seconde coup par rapport au premier)
ordres des coups possibles (123,132,213,231,312,321), positions possibles (A(premier coup),B,C,D), chaque coup dans les 2 sens (+ ou -)
on cherche donc tous les
A(nombre)+[(autre lettre)(autre nombre)(+ ou -)]*(n-1)
avec la contrainte que la lettre suivante doit correspondre à la précédente + ou - la valeur du coup.
/ = on coupe cette branche (calculs inutiles ou impossibles)
* = restriction de mouvement imposé par les coups précédents.
A1+B2+D3 nul
A1+B2-D */
A1+B3+A */
A1+B3-C2 nul
A1- /
A2+C1+D3 nul
A2+C1-B3 nul
A2+C3+B1 nul
A2+C3-D1 nul
A2- /
A3 sym A1 par le décalage impliqué par les pièces /
autres départs que A /
6 parties en éliminant quelques symétries, toutes nulles.
On voit que la première case n'a pas d'importance, de même que le dernier chiffre.
On remarque 2 restrictions dans le panel des solutions du joueur suivant :
-la pièce n/2 ne renvoie que vers 1 seule possibilité de case
-la pièce n-a jouée immédiatement après la pièce a ne renvoie que vers 1 seule possibilité de case, l'autre étant déjà occupée.
Reste à étudier aux niveaux suivants. Mais moi je vais dodo !
#5 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Jeu abstrait : Tapaoumec » 04-02-2014 00:50:15
non, non, ça m'intéresse, comme tous les jeux, mais là j'ai vraiment pas de temps... Je note et garde sous le coude pour plus tard :)
#6 Re : Café mathématique » Combinaisons a placer dans un tableau » 31-01-2014 08:31:17
En fait ton tableau est un carré bilatin auquel on veut ajouter une troisième variable. C'est la même chose que j'ai détaillé mais en construisant au fur et à mesure le niveau 3 au lieu de le faire après avoir fini le niveau 2.
Ta méthode part d'une sous solution possible, un des carrés bilatin 10 existant. Si elle ne fonctionne pas il faudrait tester les autres bilatins 10 possibles.
#7 Re : Café mathématique » Combinaisons a placer dans un tableau » 31-01-2014 01:12:16
oui, et on a ajouté une autre contrainte aussi avec cette méthode, c'est que les solutions n'ont pas nécessairement besoin d'être partitionnées en sous-segments de 2. Rien ne dit que cette contrainte supplémentaire ne réduit pas les possibilités de solutions.
#8 Re : Café mathématique » Combinaisons a placer dans un tableau » 31-01-2014 00:54:08
la première colonne est évidente.
la seconde colonne est un décalage de la première, d'un cran pour la première lettre pour l'unicité de ligne, de 2 crans pour la seconde pour l'unicité de BL et de 3 crans pour la troisième pour les unicités de BV et MW
la troisième colonne est un décalage de la première, de 2 crans pour la première lettre (unicité dans la ligne), de 1 cran pour la seconde ligne, et pour la troisième, ni U(col1), ni V(LV), ni W(CW), ni X(col2), ni Y(CY), Z
voilà le principe, mais j'ai peur qu'il n'y ait pas de solutions à cause de l'unicité des couples associés à la troisième variable (la cinquième avec une contrainte de 2 identiques max)
Après j'ai pris le partit de décaler les lignes entières, peut-être que la solution nécessite un mélange plus irrégulier dans les colonnes.
AKU BMX CLZ DPV ERd FNW G
BLV CNY DMa EQW FSU GOX H
CMW DOZ ENb FRX GTV HPY I
DNX EPa FOc GSY HKW IQZ J
EOY FQb GPd HTZ ILX JRa A
FPZ GRc HQU IKa JMY ASb B
GQa HSd IRV JLb ANZ BTc C
HRb ITU JSW AMc BOa CKd D
ISc JKV ATX BNd CPb DLU E
JTd ALW BKY COU DQc EMV F
au stade calculé, aucune lettre ne convient pour aller avec un G en première ligne.
Après, j'ai pris la première solution de décalage que j'ai trouvée pour chaque lettre de chaque colonne. Il faudrait parcourir l'arbre de toutes les solutions et de leurs conséquences pour être sûr.
#9 Re : Café mathématique » Combinaisons a placer dans un tableau » 31-01-2014 00:26:11
j'ai relu ce que tu fait et voilà comment tu devrait le noter :
A=1 2
B=3 4
C=5 6
D=7 8
E=9 10
etc jusqu'à delta pour 50.
Le problème est donc de placer 3 lettres dans 10*10 cases sans que celle-ci ne se recoupent deux à deux dans une case, et que chacune soit une fois et une seule dans chaque ligne et colonne.
en taille 3 c'est impossible: on peut placer les deux séries de nombre, une horizontalement et l'autre verticalement puis les décaler sur les lignes suivantes, mais la troisième ne peut plus être placée.
AD BE CF
BF CD AE
CE AF BD
si ADG en 1.1, alors G en seconde ligne ne peut pas être en colonne 1, ni en colonne 2 (D) ni en colonne 3 (A) et le problème est symétrique avec les autres valeurs.
reste à généraliser à la taille 10 ou à trouver une solution de taille 10...
#10 Re : Café mathématique » Combinaisons a placer dans un tableau » 31-01-2014 00:10:04
Bon, ma méthode ne trouve pas de solution, ou alors je me suis planté dans mon algo, mais elle a du mal à dépasser le placement de 25 nombres. Adieu méthode des pas.
Ta solution est erronée, 47 se retrouve en dernière colonne première et seconde case. 50 n'est pas représenté dans cette dernière colonne, 47 est représenté deux fois dans l'avant dernière colonne, première et dernière case, et 45 y est représenté deux fois aussi, seconde et troisième case. De même pour 50, en cases 4 et 7...
#11 Re : Café mathématique » Combinaisons a placer dans un tableau » 30-01-2014 17:33:12
je ne comprends pas trop ce que tu tentes de faire dans les derniers posts. Je suis en train d'essayer de coder un générateur linéaire de l'arbre.
Un truc qui me construise directement (en passant par tranches de 5 avec chacune un des pas que j'ai listé tantôt):
[1,2,3,4,5,6,9,12,15,18,7,14,21,28,35,8,17,26,...]
puis ici il détecterait que le suivant, 35 existe déjà et donc enchaînerait sur:
[1,2,3,4,5,6,9,12,15,18,7,14,21,28,35,9
et s'il arrive à invalider 50 comme premier élément de bloc, qu'il défasse le bloc précédent pour le remplacer par le même +1
Mais je doit bientôt y aller, je ne sais pas si je pourrais le finir ce soir.
#12 Re : Café mathématique » Combinaisons a placer dans un tableau » 30-01-2014 10:41:05
voilà deux essais qui ne fonctionnent pas pour la colonne 1:
# colonne 1
pas=[1,3,7,9,11,13,17,19,21,23]
#avec px=5
px=5
[[(px*i+pz*k)%50+1 for k in range(5)] for i,pz in zip(range(10),pas)]
#avec dernière valeur du précédent +1
dec=1
res=[]
for i,pz in zip(range(10),pas):
res.append([])
for k in range(5):
tmp=(dec-1+pz*k)%50+1
res[-1].append(tmp)
dec=tmp+1
Posons le problème comme un arbre :
+1 +3 +7
1 2 3 4 5 ___6 9 12 15 18 ____ 7 14 21 28 35 __...
\ \___ 8 15 22 29 36__...
\ \...
\__ 7 10 13 16 19 __...
\...
Il faut calculer les solutions de +3 dont le premier nombre est entre 6 et 38(=50-4*3) pour éviter le recouvrement d'un nombre de 1 à 5.
Pour +7 il faut aller de 6 (ou 7 selon le cas du +3) à 43(=50-7) ?
Il y a peut-être moyen de réduire drastiquement la taille de cet arbre en raisonnant sur les contraintes posées par le non recouvrement d'une feuille et de ses parents.
#13 Re : Café mathématique » Combinaisons a placer dans un tableau » 30-01-2014 10:17:18
En résumé, si solution avec des pas réguliers il y a, le problème se résume à trouver
-pour les 10 pas 1,3,7,9,11,13,17,19,21,23 (au delà de 50, c'est le même pas modulo 50, et entre 25 et 50 on a une symétrie.)
-une liste de 9 valeurs de départ (la première étant fixée à 1 pour éviter les solutions par translation)
-tels que dans une colonne de 10 cases on puisse mettre les 5 nombres tous modulo 50 [départ, départ+pas, départ+2pas, départ+3pas, départ+4pas] sans recouvrement de ceux-ci.
Si cette colonne existe les autres colonnes devraient se construire par +5 et respecter toutes les conditions données.
#14 Re : Café mathématique » Combinaisons a placer dans un tableau » 30-01-2014 09:41:26
Bonjour,
Effectivement je voie mal comment gérer ça autrement qu'informatiquement, mais certainement pas en fonçant tête baissée dans la force brute.
Déjà est-tu certain qu'il y ait une solution ?
T'as essayé de théoriser sur ce qui se passait par construction ?
Étude préalable:
Première ligne :
- Condition 1 horizontale impose un départ de 1 par pas de +1
[ 1 2 3 4 5] [ 6 7 8 9 10] [11 12 13 14 15] [16 17 18 19 20] ...
Seconde ligne :
- Condition 1 verticale impose un départ à 6
- Condition 3 impose un pas minimum de +3 (parce que +2 donnerait [6 8 10 ...] déjà contenus en ligne 1)
[ 6 9 12 15 18] [21 24 27 30 33] [36 39 42 45 48] [1 4 7 10 13] ...
mais est-ce que ce pas fonctionne partout sur cette ligne sans télescopage à cause des cycles ? (tests nécessaires)
On peut peut-être éviter ce (peut-être) problème de cycles en utilisant plutôt une solution verticalement initialisée comme:
[ 6 9 12 15 18] [ 11 14 17 20 23] [16 19 22 25 28] ...
Mais cette seconde solution se répartit-elle bien (notamment dans les passages de 50 à 1)? (tests nécessaires)
Ligne 3 :
Si on a un pas de +3 en ligne 2 un pas de +4 en ligne 3 devrait fonctionner sans recouvrement ni avec la ligne 1 ni avec la ligne 2.
[19 23 27 31 35] [39 43 47 1 5] ...
où encore
[19 23 27 31 35] [24 28 32 36 40] ...
Peut-on théoriser sur la taille des pas des lignes suivantes ?
une augmentation de +1 à chaque nouvelle ligne semble fonctionner sans recouvrement (tests)
si on commence avec un pas de 2 à la première ligne et qu'on augmente par pas de 1, trouves-t'on une solution systématique ?
Non. On a un problème avec 2, c'est qu'on va répéter 2 fois les pairs et oublier les impairs en allant de 2 à 50.
On a ce problème pour tous produits de sous ensembles de la décomposition en facteurs premiers de 50, soit [2, 5, 10, 25] mais aussi pour tous leurs multiples, (notamment tous les pairs)
Ok, alors si on prends comme pas successifs pour chaque ligne 1,3,7,9,11,13,17,19,21,23 ? (c'est presque un crible d'ératosthène.)
Reste le problème de la condition 1 verticale, rien ne garantis cette condition pour l'instant.
en colonne 1 on à [1 2 3 4 5] [6 9 12 15 18] [19 26 33 40 47] [48 7 16 25 34]...
On trouve peut-être une solution à cette colonne avec la suite de pas donnés, ou avec certains de ces pas et leurs successeurs. Si on en trouve une, alors on devrait avoir la grille complète en utilisant la deuxième option pour la seconde ligne, car la colonne 2 sera alors la colonne 1 dont chaque nombre sera additionné de +5.
Si on ne trouve pas de solution pour la colonne, il faudra essayer en décalant les premiers nombres de chaque élément de la colonne (par exemple [1 2 3 4 5][7 10 13 16 19]...). Cette solution nous donnerait aussi une grille complète.
Enfin, si ça ne fonctionne toujours pas, il faudra trouver un filtre moins sévère pour le pas de la seconde ligne, voire tester sans pas (avec des successions de permutations non recouvrantes de 5 parmi 50). Mais là on ne conserve pas la propriété de la ligne 2 solution 2 qui nous permettait de générer les autres colonnes par addition.
voilà les premiers tests en python:
#p pas
#x tableau horizontal
#y tableau vertical
#z profondeur des listes du tableau
# première ligne
px=5
pz=1
l1=[[1+(px*i+pz*k)%50 for k in range(5)] for i in range(10)]
# seconde ligne méthode 1
dec=6
px=15
pz=3
l2=[[(dec-1+px*i+pz*k)%50+1 for k in range(5)] for i in range(10)]
# seconde ligne méthode 2
dec=6
px=5
pz=3
l2b=[[(dec-1+px*i+pz*k)%50+1 for k in range(5)] for i in range(10)]
# test de la répartition horizontale des 50 nombres
def test1h(l):
v=[k for i in l for k in i]
v.sort()
return v==[i for i in range(1,51)]
"""
>>> l1
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 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]]
>>> l2
[[6, 9, 12, 15, 18], [21, 24, 27, 30, 33], [36, 39, 42, 45, 48], [1, 4, 7, 10, 13], [16, 19, 22, 25, 28], [31, 34, 37, 40, 43], [46, 49, 2, 5, 8], [11, 14, 17, 20, 23], [26, 29, 32, 35, 38], [41, 44, 47, 50, 3]]
>>> l2b
[[6, 9, 12, 15, 18], [11, 14, 17, 20, 23], [16, 19, 22, 25, 28], [21, 24, 27, 30, 33], [26, 29, 32, 35, 38], [31, 34, 37, 40, 43], [36, 39, 42, 45, 48], [41, 44, 47, 50, 3], [46, 49, 2, 5, 8], [1, 4, 7, 10, 13]]
>>> test1h(l2)
True
>>> test1h(l2b)
True
"""
donc les 2 lignes 2 répondent à la condition 1, ce qui semble valider cette construction linéaire pour la suite.
Est-ce qu'on réponds à toutes les conditions ? Non, il faudrait encore vérifier que certains nombres ne tombent pas dans la même colonne quand les pas ne sont pas premiers entre eux.... (Cela dit un test dans la colonne 1 pourrait suffire si on la construit par la méthode des pas. cf propriété du passage par addition de +5 d'une colonne à l'autre.)
#15 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Arithmétique espagnole » 14-01-2014 16:10:04
En supposant que ces chiffres soient différents, on peut déjà déduire: (% est le modulo et \ la division entière)
[tex]C=0[/tex] n'apparaîtrait pas en premier chiffre du nombre et [tex]C>=2[/tex] donnerait une retenue et un chiffre supplémentaire à la somme donc [tex]\bf{C=1}[/tex]
[tex]E=(5⋅U)\%10+(5⋅A)\backslash 10[/tex] (colonne UE) et [tex]E=(5⋅O)\%10[/tex] (colonne OE) soit [tex](5⋅U)\%10+(5⋅A)\backslash 10=(5⋅O)\%10[/tex]
or dans cette équation les termes modulo donnent comme composante +0 ou +5 et le terme division entière donne une composante comprise entre +0 et +4 inclus. Du non chevauchement de ces deux composantes, on peut déduire que [tex](5⋅A)\backslash 10=0[/tex].
Puis que [tex]A\in [0, 1][/tex] et comme on a déjà le 1 que [tex]\bf{A=0}[/tex].
Il reste que [tex]E=(5⋅O)\%10[/tex] donc [tex]E\in[0,5][/tex] et comme on a déjà le 0 que [tex]\bf{E=5}[/tex].
Pour essayer d'automatiser ces derniers calculs, observons [tex]A, I\text{ et }E[/tex]. On déduit assez vite que :
-[tex]A\text{ est pair ssi }I<5[/tex]
-[tex]E=x\text{ ssi }A\in[2x,2x+1][/tex]
on peut utiliser ces deux relations de proche en proche sur chaque colonne pour déterminer les dénombrements successifs.
On récapitule ce qu'on sait déjà ! [tex][C=1, A=0, E=5][/tex]
[tex]E=5[/tex] donc [tex]O\text{ est impair}[/tex] et on a déjà 1 et 5 donc [tex]\bf{O\in[3,7,9]}[/tex].
[tex]O=3[/tex] donne [tex]T\in[1,6][/tex], [tex]O=7[/tex] donne [tex]T\in[3,8][/tex] et [tex]O=9[/tex] donne [tex]T\in[4,9][/tex].
On a déjà 1 et 9(par O) il reste donc [tex]T\in[3,4,6,8][/tex]
D'autre part, [tex]A=0[/tex] donc [tex]I<5[/tex] et on a déjà 0 et 1 donc [tex]\bf{I\in[2,3,4]}[/tex].
[tex]I=2[/tex] donne [tex]T\in[4,5][/tex], [tex]I=3[/tex] donne [tex]T\in[6,7][/tex] et [tex]I=4[/tex] donne [tex]T\in[8,9][/tex].
On a déjà 5 il reste donc [tex]T\in[4,6,7,8,9][/tex].
Le mix de ces 2 listes montre que [tex]\bf{T\in[4,8]}[/tex] (et les secondes lignes des 2 blocs précédents en donnent les [tex]I\text{ et }O[/tex] respectifs.)
On a donc plus que 2 cas de [tex]T[/tex] à tester pour 4 variables restantes [tex][U,R,V,N][/tex].
Si [tex]T=4[/tex], en récapitulant: [tex]C=1, A=0, E=5, T=4, O=9, I=2[/tex] et il nous manque [tex][3,6,7,8][/tex]
[tex]T\text{ est pair}[/tex] donc [tex]N<5[/tex], d'où [tex]N=3[/tex], donc [tex]R\in[6,7][/tex], mais [tex]R=7[/tex] ne colle pas avec [tex]T=4[/tex] donc il nous reste une seule solution [tex]N=3\text{ et }R=6[/tex].
[tex]C=1[/tex] donc [tex]V(>5)\in[7,8][/tex], mais [tex]V=7[/tex] implique [tex]U\in[4,5][/tex] qu'on a déjà et [tex]V=8[/tex] implique [tex]U\in[6,7][/tex]. On a déjà 6 donc seul [tex]U=7[/tex] est encode possible.
On a donc une solution : [tex]\bf{N=3, R=6, V=8, U=7}[/tex]
Si [tex]T=8[/tex], en récapitulant: [tex]C=1, A=0, E=5, T=8, O=7, I=4[/tex] et il nous manque [tex][2,3,6,9][/tex]
[tex]T\text{ est pair}[/tex] donc [tex]N<5[/tex], d'où [tex]N\in[2,3][/tex]. Si [tex]N=2[/tex] alors [tex]R\in[4,5][/tex]qu'on a déjà. Sinon si [tex]N=3[/tex] alors [tex]R\in[6,7][/tex] avec 7 qu'on a déjà, donc il nous reste à nouveau une seule solution [tex]N=3\text{ et }R=6[/tex].
[tex]C=1[/tex] donc [tex]V(>5)=9[/tex] donc [tex]U\in[4,5][/tex] qu'on a déjà.
Donc l'hypothèse [tex]T=8[/tex] est fausse.
En résumé, la réponse est [tex]170469*5=852345[/tex], et elle est unique.
Je n'ai fait que 6 dénombrements de profondeur max 2 et de largeur max 5. Même si la force brute résous le calcul rapidement, je préfère l'élégance de quelques remarques judicieuses. ;)
#16 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Neuf cases et 4 opérations » 14-01-2014 09:51:01
ben, en fait ça se fait très vite en remarquant qu'on a une division et une multiplication.
de 1 à 9, on élimine tous les premiers et les carrés parfaits, qui ne peuvent pas être représentés dans ces 2 calculs (car chaque chiffre n'apparaît qu'une fois).
Il reste 6 et 8, tout deux multiples de 2, donc le 2 est au croisement de ces 2 opérations.
Le 6 et 8 sont soit en résultat du produit, soit en numérateur, et le 3 et 4 sont dans les deux autres postes de ces 2 opérations.
il reste 4 chiffres a placer : 1,5,7,9 et on ne peut pas obtenir le 3 par leurs soustractions. donc c'est nécessairement 4 qui est à la croisée de la soustraction et de la multiplication. Le reste n'est que du remplissage.
#17 Re : Programmation » [Python]Plus longue sous-suite croissante » 13-01-2014 15:42:57
Bonjour,
@yoshi: apparemment les éléments des sous-suites ne sont pas nécessairement consécutifs.
Voilà comment j'ai codé la seconde question du problème :
tlm=tabLongueurMax(u)
iCur=iPrev=longueurMax(u)
r=[]
while iPrev>=0:
r.insert(0,u[iCur])
iPrev=iCur-1
while iPrev>=0 and tlm[iPrev]!=tlm[iCur]-1:
iPrev-=1
iCur=iPrev
avec u=[2, 0, 1, 5, 4, 6, 7, 3]
on obtient tlm=[1, 1, 2, 3, 3, 4, 5, 3]
puis iCur=6
et enfin r=[0, 1, 4, 6, 7]
L'idée est de partir de l'indice de la fin de la sous-liste et de remonter chercher quel est l'indice du précédent le plus proche.
#18 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 11-01-2014 00:05:35
oui leg, l'idée est de faire une roue toute petite, puis de l'appliquer et d'en déduire les pas de la suivante. mais là j'ai voulu aller trop vite, j'ai mangé des pas en comptant les multiples des entiers dans la taille de la roue, alors qu'il ne faut prendre que le premier d'entre eux. (Ça marchait bien jusqu'à la roue de taille 30.) Mais du coup je pense que les précalculs pour les produits d'autres premiers compris dans la taille de la roue vont exploser.
#19 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 11-01-2014 00:01:37
bon, ma roue ne marche pas, elle élimine au delà de ce qu'elle devrait.
il faut progresser par roues qui ne filtrent que leurs bases et pas les autres premiers de la liste, et filtrer les autres à côté. Pour ça il faut lister séparément les premiers et les crans de la roue. du coup, ça perds fortement en rentabilité...
À voir si je continue....
#20 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 10-01-2014 21:25:18
oui je peut te dire quels sont les crans. je les calcule en appliquant avec la roue précédente et jusqu'à la taille prévue pour la roue courante, c'est le principe que j'essaie de mettre en place. Ceux de la roue de taille 210 sont : [4,2,4,6,2,6,4,2,4,4,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,10,2,10,2,6,6,4,6,6,2,10,2,4,2,12,10] et elle commence en 11.
Mais on commence à avoir des non premiers genre 13*19 qui sont des calculs à ajouter en parallèle à l'application de la roue nécessaires à l'établissement de la roue suivante. Je pense que si je résous le problème que j'ai en faisant glisser les produits des ces autres premiers qui s'incrustent j'ai la méthode pour calculer toutes les roues de tailles successives.
Reste à connaître la complexité-temps de ce calcul et s'il fini par devenir plus rentable que les méthodes habituelles. À priori je pense que c'est le cas, mais ça demande finalisation et tests.
#21 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 10-01-2014 18:11:04
la roue de taille 2 et cran 2 permet d'éliminer les multiples de 2, à partir de 3
la roue de taille 2x3 et crans 2,4 permet d'éliminer les multiples de 2,3, à partir de 5
la roue de taille 2x3x5 et crans 6.4.2.4.2.4.6.2 permet d'éliminer les multiples de 2,3,et 5 à partir de 7
la roue de taille 2x3x5x7 et crans ... permet d'éliminer les multiples de 2,3,5,7 à partir de 11
Si on ajoute la correction calculée en N*log(N) multiplications et autant de tri, on peut peut-être étendre cette roue pour qu'elle filtre aussi les multiples de 11 inférieurs à 2 tailles de roue au dessus, et de 13 inférieurs à 3 tailles de roue au dessus....etc.
Si on peut itérer le processus à l'infini et calculer des roues de tailles de plus en plus grande en n*log(n) opérations, penses-tu qu'une roue de taille "produit des 20 premiers nombres premiers", mettra plus de temps qu'une roue de taille fixe, comme 30 ?
C'est ça que je cherche, pourquoi se limiter à une taille donnée, si on peut calculer une taille immense de roue ?
L'idée n'est pas de dire qu'on veut tester une quantité donnée de nombres, qu'on initialise et qu'on crible, non, l'idée est de créer le crible complet au fur et à mesure qu'on détermine chaque nombres premiers. Et je cherche par pas de tailles de roues successives.
#22 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 10-01-2014 10:37:47
Est tu en train de me dire que les roues ont 2 dimensions ?
C'est la piste sur laquelle je suis pour résoudre mon problème. Appliquer la première dimension mécaniquement après sa détermination, mais filtrer mes produits sur la seconde dimension aussi. Ça à l'air de prendre sens pour ma méthode...
#23 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 10-01-2014 00:45:37
bonsoir,
merci yoshi pour ton accueil ! (ça a l'air intéressant ton lien, j'y jetterai un œil).
leg, je suis désolé, mais je ne comprends pas grand chose à tes posts, à part l'idée générale du crible par roue. Oui, il est impossible de changer la taille de la roue en utilisant un stockage ultra optimisé comme nbPremierW32. Mais en utilisant un stockage en liste, ça ne devrait pas être un pbm. (sauf propriété de la répartition des premiers ? mais dans ce cas on devrait quand même pouvoir généraliser le principe de crible de taille n.)
bon, de mon côté, je sèche. J'ai fait le programme avec une roue qui progresse en taille, au départ de la taille 2, puis 2*3, puis 2*3*5, mais à partir de la taille 2*3*5*7 les problèmes commencent : j'ai des combinaisons (13*17) qui dépassent taille de la roue et qui du coup ne sont pas filtrées par elle...
voilà comment je procède :
A) Je commence avec [2,3,5] comme premiers connus. les premiers qui sont la base de la roue sont [2], donc la roue est de longueur 2 et le point de départ de la roue est 3.
B) De ça je déduis que le pas de la roue sera [+2] (4 n'est pas premier, donc un tour de roue partant de 3 arrivera à 5 en une étape de 2)
C) Puis je prépare la liste des premiers que je devrait connaitre pour la taille de roue suivante :
C1) cette taille sera (2*3) au départ de 5, donc il me faut la liste des premiers jusqu'à 11.
C2) je précalcule les produits possibles de premiers de la roue actuelle dans cet intervalle. En l'occurrence j'ai 3*3. (inutile de chercher avec 2, ils seront flitrés par la roue en cours.
C3) j'applique la roue jusqu'à 11, en éliminant les pas précalculés non premiers, et j'obtient [(2,3,5,)7,pas 9,11]
----------------
D) et on reprends en A en augmentant la taille de la roue du premier suivant, soit base de la roue [2,3], taille 2*3=6, point de départ 5.
E) comme en B : je déduis le pas de la nouvelle roue : 7-5=2, 11-7=4, j'ai ma taille de 6 et mes pas sont [2,4]
F) comme en C : je prépare les prochains premiers connus nécessaire pour calculer les pas de la prochaine roue (de taille 2*3*5, au départ de 7)
j'ai donc besoin d'aller calculer jusqu'à 37. Je précalcule ceux qui ne seront pas premiers dans cet intervalle [5*5, 5*7] puis j'applique la roue actuelle et obtient la liste des premiers [(2,3,5,7,11,)13,17, 19,23,pas 25,29,31,pas 35,37]
----------------
G) on reprends comme en A avec la roue suivante : [2,3,5], taille 2*3*5=30, point de départ 7.
H) comme B et E : le pas de la nouvelle roue : [11-7, 13-11, 17-13, 19-17, 23-19, 29-23, 31-29, 37-31] soit [4,2,4,2,4,6,2,6]
I) comme C et F : prochaine roue ira à 2*3*5*7+11=221, les non premiers dans l'intervalle sont [7*7,7*11,...7*31], [11*13,...11*19], [13*13,13*17]. et après application de la roue filtrée avec : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211]
et là, premier problème, relativement facilement résolu : 221, mon dernier premier de la liste nouvellement générée, n'est pas premier, c'est 13*17, donc je vais devoir travailler sans borne au prochain départ de la roue... (bon, c'est une roue, on peut décaler le départ d'un pas, pbm résolu)...
mais surtout, après 3 cycles complet de calcul et d'application de nouvelle roue sans problèmes, un des premiers crans de la nouvelle roue foire : 247 = 13*19 tombe sur un cran vérifié pour 2,3,5,7 ! (normal, vu les valeurs) mais du coup c'est toute la question du calcul de la taille de la roue qui est à reprendre, pour cette roue là, 210 n'est pas suffisant pour assurer une roue valable. Comment déterminer cette taille ?
C'est là que je sèche.
ci-joint mon code jusque là :
include itertools
def getCycle(Pi, iCycle, size):
"""Calcule les crans d'une roue avec:
-la liste des premiers connus (de la taille exacte d'un tour de roue),
-son point de départ (indice),
-sa taille désirée.
Pour ce faire, mesure les crans un par un jusqu'à la taille objectif"""
cycle=[]
while size>0 and iCycle<len(Pi)-1:
cycle.append(Pi[iCycle+1]-Pi[iCycle])
iCycle+=1
size-=cycle[-1]
if size!=0: #si jamais la borne n'est pas un nombre premier
cycle.append(size) # on clos quand même la liste
return True,cycle
return False,cycle
def getExclude(Pi,limit):
"""retourne les produits possibles de successeurs de pcourant"""
return {p*p:[p*np for np in Pi if p<np and p*np<=limit] for p in Pi if p*p<=limit}
#TODO optimiser en arrêtant les test dès le premier dépassement
def testn():
size=1
Pi=[2,3,5]
iStart=1 # soit cran = Pi[iStart] = 3, et cycle = Pi[:iStart] = [2]
limit=5
while iStart<5:
# taille de la roue = ancienne taille fois dernier premier ajouté
size*=Pi[iStart-1]
# roue et caractère premier du dernier pas
shifted,cycle=getCycle(Pi, iStart, size)
current=limit # on récupère le prochain current
limit=size*Pi[iStart]+Pi[iStart+1] # cible pour calculer roue suivante
exclude=getExclude(Pi[iStart:], limit) # liste d'exclusion
if shifted: # si le dernier cran n'est pas premier on décale la roue
cycle[-1]+=cycle[0]
del cycle[0]
current+=cycle[-1]
step=itertools.cycle(cycle)
while current<limit:
current+=next(step)
if current not in exclude: # soit on a un nouveau premier
Pi.append(current)
else: # soit on met à jour la liste d'exclusion
if exclude[current]!=[]:
exclude[exclude[current][0]]=exclude[current][1:]
del exclude[current]
iStart+=1
return Pi
dommage, parce que ça avait l'air environ deux fois plus rapide que la roue fixe de taille 30 (aucune division, pas de tri lourd vu que les exclusions sont ordonnées et gérées au fur et à mesure), déjà sur ces quelques premières valeurs.
Est-ce que 30 est une taille max pour cribler à la roue à cause de la proximité entre eux des premiers premiers ?
Si non, quelle est la formule correcte pour calculer le taille des cribles ? max(produit, autre-chose) ? quel autre chose ?
#24 Re : Programmation » Question de LEG : temps mis pour divisions par pi » 08-01-2014 14:58:29
C++ est beaucoup plus rapide que python, mais aussi beaucoup moins user friendly.
Ce que tu as l'air de décrire de nbPremierWin32 indique que les nombres premiers sont stockés par leur position dans un tableau de taille fixe au moins pour sa première dimension. Ça implique une taille de roue fixe (la roue représentant une ligne). C'est effectivement une approche très économe en mémoire.
L'idée d'augmenter la taille de la roue au fur et à mesure (ce vers quoi mes essais se dirigent) me plait bien aussi, reste à savoir si elle serait compatible avec un stockage par placement, mais ça me paraît à première vue beaucoup plus difficile, voire impossible.
Ce qu'il me reste à étudier pour suivre ma version tient pour l'instant en deux points :
-Comment déterminer les crans de la roue suivante;
-Comment sélectionner le moment du glissement d'une roue à l'autre.
J'ai des bonnes pistes de réponse à ces deux questions, mais il me reste à les formaliser rigoureusement, et à adapter le code en conséquence.
Après, une transcription de mon algo en c++ sera toujours possible, mais elle sera quand même infiniment moins efficace que nbPremierWin32 pour ce qui est du stockage des réponses (à moins qu'il ne soit possible d'intégrer l'idée du stockage binaire par position) et (à priori¹) aussi moins efficace pour les calculs.
¹:À priori, parce que la taille de roue augmentant à quand même tendance à accélérer les choses, donc ça reste à confirmer sur les très grands nombres (et c'est d'ailleurs tout l'intérêt de mon approche)
Pages : 1
- Accueil
- » Rechercher
- » De miq