Skip to content

Instantly share code, notes, and snippets.

@Kmaschta
Last active April 12, 2019 19:26
Show Gist options
  • Save Kmaschta/ec6d8ff72a49f7271abb to your computer and use it in GitHub Desktop.
Save Kmaschta/ec6d8ff72a49f7271abb to your computer and use it in GitHub Desktop.
Algorithme Dobble
#!/usr/bin/python
# coding: utf-8
import sys
def plan_projectif(modulo):
"""Génération d'un plan projectif réel
Il est composé d'un plan affine (une matrice) et
des points à l'infini du plan réel.
Des symboles uniques sont définis pour chaque
points du plan affine et chaque point à l'infini.
(ici un index de 0 à l'infini)
plan_affine, pts_infini = plan_projectif(3)
plan_affine == [[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]
pts_infini == [9, 10, 11, 12]
"""
plan_affine = []
pts_infini = []
index = 0
# Génération du plan affine
for i in range(modulo):
plan_affine.append([])
for j in range(modulo):
plan_affine[i].append(index)
index += 1
# Génération des points à l'infini
for i in range(modulo + 1):
pts_infini.append(index)
index += 1
return {
'plan_affine': plan_affine,
'pts_infini': pts_infini,
}
def droite(modulo, plan, a, b, f=None):
"""Trace une droite dans le plan projectif et retourne
tous les points par laquelle elle est passée"""
coords = []
points = []
# Calcul des coordonnés de tous les points
for i in range(modulo):
if f is None:
# f(x) = ax + b
# On applique l'opérateur modulo parce que le résultat
# n'est pas un nombre entier, mais un nombre modulo
x = i % modulo
y = (a * i + b) % modulo
else:
# f(0), f(1), f(2) ... f(modulo)
x = f
y = i % modulo
coords.append({'x': x, 'y': y})
# Récupération des points dans le plan affine
for c in coords:
points.append(plan['plan_affine'][c['y']][c['x']])
# Récupération du dernier points dans les points à l'infini
if f is None:
points.append(plan['pts_infini'][a + 1])
else:
points.append(plan['pts_infini'][0])
return points
def droites(modulo, plan):
"""Récupère toutes les droites possible d'un plan projectif"""
liste = []
# Lignes verticales
for i in range(modulo):
liste.append(droite(modulo, plan, 0, 0, f=i))
# Lignes pour f(x) = ax + b
for a in range(modulo):
for b in range(modulo):
liste.append(droite(modulo, plan, a, b))
# Enfin, la ligne qui passe par tous les points à l'infini
liste.append(plan['pts_infini'])
return liste
if __name__ == '__main__':
# Asmodée a choisi de générer un jeu de carte avec
# huit symboles par carte, pour ça, il faut générer
# un plan projectif avec un nombre entier modulo de 7
# (le nombre choisi par Asmodée)
#
# C'est une constante, mais on peut calculer le modulo
# Avec le nombre total de symboles, le nombre de carte
# Et donc le nombre de symbole par carte. (non inclus)
try:
modulo = int(sys.argv[1])
except (IndexError, ValueError):
modulo = 7
plan = plan_projectif(modulo)
# Affiche une liste que l'on peut comparer à un deck
# qui contient un nombre de 8 élements par carte, tout
# comme Dobble (même si Asmodée a volontairement choisi
# de retirer deux cartes)
# Qui possède les propriétés suivantes :
# - Chaque carte est unique ;
# - Chaque carte a le même nombre de symbole que toutes
# les autres ;
# - Chaque carte possède un et un seul élément en commun
# avec toutes les cartes.
deck = droites(modulo, plan)
print('Nombre de cartes', len(deck))
print('Toutes les cartes :')
for i, carte in enumerate(deck):
print('#{}'.format(i), carte)
@Kmaschta
Copy link
Author

Kmaschta commented Nov 5, 2015

Pour plus d'informations sur les mathématiques qui ont servi à générer un tel algo, je vous laisse un cours d'un professeur de l'Université de Lyon qui explique tout ça de façon très claire : http://math.univ-lyon1.fr/~deleglis/PDF/dobble.pdf

@introlinux
Copy link

I don't know why, but it doesn't work properly, I got cards without repeated elements trying to do 7 elements per card.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment