<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 1A.e - Enoncé 22 octobre 2019 (1)
Correction du premier énoncé de l'examen du 22 octobre 2019. L'énoncé propose une façon de disposer des tables rondes dans une salle ronde.
Step1:  On sait d'après les dernières questions qu'il faudra tout répéter plusieurs fois. On prend le soin d'écrire chaque question dans une fonction. C'est un mariage dans une salle ronde. On veut disposer les tables de sortes qu'elles soient éloignées le plus possible les unes des autres et du bord de la salle. Les tables sont toutes rondes et toutes la même taille.
Q1 - distance_table
Ecrire une fonction qui calcule la distance entre deux tables rondes dont on connaît le centre. Et comme ce sont des tables rondes, on considère que la distance entre deux tables est la distance entre leurs centres.
Step2:  Q2 - distance_bord
Ecrire une fonction qui calcule la distance entre une table (son centre) et le bord de la salle de rayon R.
Step3:  Q3 - table_alea
Ecrire une fonction qui tire aléatoirement une table dans le cercle de rayon R.
Step4:  On peut utiliser une autre façon en utilisant les coordonnées polaires.
Step5:  Q4 - n_table_alea
Ecrire une fonction qui tire aléatoirement N tables dans le cercle de rayon R.
Step6:  Q5 - table_proches
Ecrire une fonction qui retourne la table la plus proche d'une table ou du bord. La fonction doit retourner l'indice de la table la plus proche ou -1 si c'est le bord, puis la distance associée. On ajoute un paramètre skip_i pour éviter une table dans la liste list_tables.
Step7:  Q6 - distance_n_tables_alea
Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.
Step8:  Q7 - meilleur_table_alea
Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.
Step9:  Q8 - résultat numérique
Ecrire une fonction qui retourne le résultat pour 11 tables et une salle de diamètre 1.
Step10:  Q9 - plot_tables
Ecrire une fonction qui représente la solution avec matplotlib en partant de l'exemple donnée.
Step11:  Q10 ...
Il est difficile de tomber sur une bonne répartition de tables en partant du hasard et plus il y aura de tables, plus il faudra de tirages. On peut aussi chercher à positionner les tables selon un quadrillage hexagonal en formant une spirale et de chercher le meilleur écartement. On peut aussi partir d'un tirage puis d'éloigner les deux tables les plus proches. L'éloigner de combien, c'est une autre question. C'est la première option et elle ne marche pas très bien.
Step12:  Q10 - Voronoï
On peut aussi écarter une table de ses voisins les plus proches, voisins trouvés grâce à un diagramme de Voronoï ou à une triangulation de Delaunay.
Step13:  On ajoute le bord.
Step14:  Le diagramme de Voronoï permet de construire un voisinage de points pour qu'on peut rapprocher le plus possible d'en ensemble de triangles équilatéraux ou rapprocher une table le plus possible de sa frontière la plus éloignée. Après quelques essais, je ne peux pas que ce fut là la meilleure inspiration.
Q10 - KMeans
Une autre idée consiste à recouvrir la salle de points puis à effectuer un KMeans pour créer artificiellement des zones.
Step15:  Les centres des clusters sont les emplacements des tables cherchées.
Step16:  On essaye avec un mélange de lois normales.
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Explanation: 1A.e - Enoncé 22 octobre 2019 (1)
Correction du premier énoncé de l'examen du 22 octobre 2019. L'énoncé propose une façon de disposer des tables rondes dans une salle ronde.
End of explanation
def distance_table(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
distance_table(0, 0, 2, 1)
Explanation: On sait d'après les dernières questions qu'il faudra tout répéter plusieurs fois. On prend le soin d'écrire chaque question dans une fonction. C'est un mariage dans une salle ronde. On veut disposer les tables de sortes qu'elles soient éloignées le plus possible les unes des autres et du bord de la salle. Les tables sont toutes rondes et toutes la même taille.
Q1 - distance_table
Ecrire une fonction qui calcule la distance entre deux tables rondes dont on connaît le centre. Et comme ce sont des tables rondes, on considère que la distance entre deux tables est la distance entre leurs centres.
End of explanation
def distance_bord(x1, y1, R):
    dist = distance_table(x1, y1, 0, 0)
    return R - dist
distance_bord(1, 1, 5)
distance_bord(10, 1, 5)
Explanation: Q2 - distance_bord
Ecrire une fonction qui calcule la distance entre une table (son centre) et le bord de la salle de rayon R.
End of explanation
import random
def table_alea(R):
    R2 = R ** 2
    dist = R2 * 2
    while dist > R2:
        x = random.uniform(-R, R)
        y = random.uniform(-R, R)
        dist = x ** 2 + y ** 2
    return x, y
table_alea(5)
Explanation: Q3 - table_alea
Ecrire une fonction qui tire aléatoirement une table dans le cercle de rayon R.
End of explanation
import math
def table_alea_pol(C):
    t = random.uniform(0, math.pi)
    y = random.uniform(0, C)
    x = math.cos(t) * t
    y = math.sin(t) * t
    return x, y
table_alea_pol(5)
Explanation: On peut utiliser une autre façon en utilisant les coordonnées polaires.
End of explanation
def n_table_alea(N, R):
    return [table_alea(R) for n in range(N)]
n_table_alea(3, 5)
Explanation: Q4 - n_table_alea
Ecrire une fonction qui tire aléatoirement N tables dans le cercle de rayon R.
End of explanation
def table_proches(x1, y1, list_tables, R, skip_i):
    proche = -1
    best = distance_bord(x1, y1, R)
    for i, table in enumerate(list_tables):
        if i == skip_i:
            continue
        dist = distance_table(x1, y1, table[0], table[1])
        if dist < best:
            best = dist
            proche = i
    return proche, best
R = 5
list_tables = n_table_alea(3, R)
table_proches(1, 1, list_tables, R, None)
table_proches(R * 0.9, 0, list_tables, R, None)
Explanation: Q5 - table_proches
Ecrire une fonction qui retourne la table la plus proche d'une table ou du bord. La fonction doit retourner l'indice de la table la plus proche ou -1 si c'est le bord, puis la distance associée. On ajoute un paramètre skip_i pour éviter une table dans la liste list_tables.
End of explanation
def distance_n_tables_alea(N, R):
    distrib = n_table_alea(N, R)
    best = R ** 2
    for i, table in enumerate(distrib):
        proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
        if dist < best:
            best = dist
    return best, distrib
distance_n_tables_alea(3, R)
Explanation: Q6 - distance_n_tables_alea
Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.
End of explanation
def meilleur_table_alea(k, N, R):
    dist = 0
    best = None
    for i in range(k):
        d, distrib = distance_n_tables_alea(N, R)
        if d > dist:
            best = distrib
            dist = d
    return best, dist
meilleur_table_alea(10, 3, R)
Explanation: Q7 - meilleur_table_alea
Ecrire une fonction qui tire N tables aléatoirement et qui retourne la distance minimum entre deux tables ou le mur et les tables.
End of explanation
best, dist = meilleur_table_alea(10, 11, 1)
best, dist
Explanation: Q8 - résultat numérique
Ecrire une fonction qui retourne le résultat pour 11 tables et une salle de diamètre 1.
End of explanation
%matplotlib inline
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
R = 1
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best], [b[1] for b in best], 'o');
Explanation: Q9 - plot_tables
Ecrire une fonction qui représente la solution avec matplotlib en partant de l'exemple donnée.
End of explanation
import numpy
def improve_distrib(iter, tables, R, alpha=0.2):
    
    for it in range(iter):
        
        # On cherche la pair la plus proche.
        best = R ** 2
        pair = None
        for i, table in enumerate(tables):
            proche, dist = table_proches(table[0], table[1], tables, R, skip_i=i)
            if dist < best:
                best = dist
                pair = i, proche
        
        if it % 50 == 0:
            print(it, "paire", pair, "distance", best)
        # On choisit une table.
        if pair[0] == -1:
            i = 1
        elif pair[1] == -1:
            i = 0
        else:
            i = numpy.random.randint(0, 1)
        
        pi = pair[i]
        if pair[1-i] == -1:
            pjp = (0, 0)
            sign = 1
        else:
            pjp = tables[pair[1-i]]
            sign = -1
        
        # On calcule le vecteur entre les deux tables.
        dx, dy = (pjp[0] - tables[pi][0],
                  pjp[1] - tables[pi][1])
        
        # Un peu d'aléa.
        h = numpy.random.uniform(0, alpha)
        dx *= h * sign
        dy *= h * sign
        
        # On bouge la table.
        table = tables[pi]
        tables[pi] = (table[0] + dx, table[1] + dy)
        if distance_bord(tables[pi][0], tables[pi][1], R) < 0:
            # Table hors du cercle
            tables[pi] = (table[0] - dx, table[1] - dy)
R = 1
best_sol, dist = meilleur_table_alea(10, 11, R)
improve_distrib(351, best_sol, R, alpha=0.5)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o');
Explanation: Q10 ...
Il est difficile de tomber sur une bonne répartition de tables en partant du hasard et plus il y aura de tables, plus il faudra de tirages. On peut aussi chercher à positionner les tables selon un quadrillage hexagonal en formant une spirale et de chercher le meilleur écartement. On peut aussi partir d'un tirage puis d'éloigner les deux tables les plus proches. L'éloigner de combien, c'est une autre question. C'est la première option et elle ne marche pas très bien.
End of explanation
from scipy.spatial import Voronoi, voronoi_plot_2d, Delaunay
points = numpy.array(best_sol)
vor = Voronoi(points)
dela = Delaunay(points)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o')
voronoi_plot_2d(vor, ax=ax)
ax.triplot(points[:,0], points[:,1], dela.simplices.copy(), "--", label="Delaunay")
ax.set_xlim([-R, R])
ax.set_ylim([-R, R])
ax.legend();
Explanation: Q10 - Voronoï
On peut aussi écarter une table de ses voisins les plus proches, voisins trouvés grâce à un diagramme de Voronoï ou à une triangulation de Delaunay.
End of explanation
N = 12
bords = []
for i in range(0, N + 1):
    bords.append((R * math.cos(i / N * math.pi * 2),
                  R * math.sin(i / N * math.pi * 2)))
points2 = numpy.vstack([points, bords])
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax.add_artist(c)
ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o')
vor2 = Voronoi(points2)
dela2 = Delaunay(points2)
voronoi_plot_2d(vor2, ax=ax)
ax.triplot(points2[:,0], points2[:,1], dela2.simplices.copy(), "--")
ax.set_xlim([-R, R])
ax.set_ylim([-R, R]);
Explanation: On ajoute le bord.
End of explanation
def points_in_circle(N, R):
    points = numpy.empty(((N+1)**2, 2))    
    pos = 0
    for i in range(0, N + 1):
        for j in range(0, N + 1):
            points[pos, 0] = 1.0 * i / N * R * 2 - R
            points[pos, 1] = 1.0 * j / N * R * 2 - R
            pos += 1
    dist = points[:, 0] ** 2 + points[:, 1] ** 2
    points = points[dist <= R**2, :]
    return points
R = 1
points = points_in_circle(25, R)
fig, ax = plt.subplots(1, 1, figsize=(4, 4))
c = Circle((0, 0), R, alpha=0.2)
ax.add_artist(c)
ax.plot(points[:, 0], points[:, 1], '.');
from sklearn.cluster import KMeans
km = KMeans(n_clusters=11)
km.fit(points)
pred = km.predict(points)
Explanation: Le diagramme de Voronoï permet de construire un voisinage de points pour qu'on peut rapprocher le plus possible d'en ensemble de triangles équilatéraux ou rapprocher une table le plus possible de sa frontière la plus éloignée. Après quelques essais, je ne peux pas que ce fut là la meilleure inspiration.
Q10 - KMeans
Une autre idée consiste à recouvrir la salle de points puis à effectuer un KMeans pour créer artificiellement des zones.
End of explanation
fig, ax = plt.subplots(1, 2, figsize=(10, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax[0].add_artist(c)
ax[0].set_xlim([-R, R])
ax[0].set_ylim([-R, R])
ax[0].scatter(points[:, 0], points[:, 1], c=pred)
c = Circle((0, 0), 1, alpha=0.2)
ax[1].add_artist(c)
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R])
ax[1].plot(km.cluster_centers_[:, 0], km.cluster_centers_[:, 1], 'o')
vor2 = Voronoi(km.cluster_centers_)
voronoi_plot_2d(vor2, ax=ax[1])
ax[1].set_title("Centres des clusters - KMeans")
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R]);
def distance_n_tables(distrib, R):
    best = R ** 2
    for i, table in enumerate(distrib):
        proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
        if dist < best:
            best = dist
    return best
distance_n_tables(km.cluster_centers_, 1), distance_n_tables(best_sol, 1)
Explanation: Les centres des clusters sont les emplacements des tables cherchées.
End of explanation
from sklearn.mixture import GaussianMixture
gau = GaussianMixture(11)
gau.fit(points)
pred = gau.predict(points)
fig, ax = plt.subplots(1, 2, figsize=(10, 4))
c = Circle((0, 0), 1, alpha=0.2)
ax[0].add_artist(c)
ax[0].set_xlim([-R, R])
ax[0].set_ylim([-R, R])
ax[0].scatter(points[:, 0], points[:, 1], c=pred)
c = Circle((0, 0), 1, alpha=0.2)
ax[1].add_artist(c)
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R])
ax[1].plot(gau.means_[:, 0], gau.means_[:, 1], 'o')
vor2 = Voronoi(gau.means_)
voronoi_plot_2d(vor2, ax=ax[1])
ax[1].set_title("Centres des clusters - gaussian mixture")
ax[1].set_xlim([-R, R])
ax[1].set_ylim([-R, R]);
distance_n_tables(km.cluster_centers_, 1), distance_n_tables(gau.means_, 1)
Explanation: On essaye avec un mélange de lois normales.
End of explanation
<END_TASK>