Défi pour les frimas à venir = dessiner des carrés

Bonjour les Panoramicien(ne)s, FBPanistes et autres FBCrocodilien(ne)s

(Inspiré d’un test donné à « la pîscine » de « l’école 42 »)

Soit une grille de 12 x 12 cellules carrées dans lesquelles on dispose 12 points.
Il y a donc 144 possibilités de positionner un point.
Créer un programme pour relier 4 points entre eux pour former
1) le plus grand carré
2) le plus petit carré
possibles.
Il se peut qu’il n’y ait aucun carré à tracer.
Vous avez toute la durée des frimas pour trouver une ou des solutions.

Rien ne vous interdit de créer un autre programme pour disposer aléatoirement des points
puis, dans un deuxième temps chercher à les relier.

Bon courage

NB. Bien évidemment, vous pouvez changer la dimension de la grille et le nombre de points à y disposer si ça vous dit.

Bonjour Ouf_ça_passe,

C'est un bon défi !

Première difficulté : comment tirer 12 points tous différents ?

C'est une question classique. Je vous laisse chercher Smile

Sujet: Classique, classique Ven 18 Oct 2019 - 11:12

pour toi oui, Jean.
J'espérais appâter Papydall aussi.

Papydall.
Où es-tu Question

Sujet: re Ven 18 Oct 2019 - 15:23

Ouf_ca_passe a écrit:: Soit une grille de 12 x 12 cellules carrées dans lesquelles on dispose 12 points.
Il y a donc 144 possibilités de positionner un point.

C'est pas tout à fait vrai...
...à moins de pouvoir placer plusieurs point dans la même case.
Wink

J'aime bien ce genre de défi aussi Very Happy

@yannick
La grille comporte 144 emplacements, donc 144 possibilités de placer des points. Même si tu place 2 points au même emplacement dans la grille, la grille comportera toujours 144 cases, donc 144 possibilités tongue

Pour ma part, je suis la logique de jean_debord, à savoir 1 point par case.

ma solution à : comment tirer 12 points tous différents:

Ca, c'était facile, par contre, déterminer si 4 points forme un carré, le + petit, le + grand, ça ne me saute pas aux yeux quant à la manière de procéder scratch

J'y réfléchi drunken

Sujet: Si si Ven 18 Oct 2019 - 16:26

@ Yannick

Tu peux agrandir la grille si tu veux.
Par ex. 16 x 16 font 256 possibilités de marquer un point si je ne m’abuse comme dirait le docteur du même nom. Very Happy

Sujet: re Ven 18 Oct 2019 - 17:31

Si vous avez 144 cases vous avez au premier point 144 possibilités
au deuxième point, à moins de pouvoir remettre un point sur la case ou se trouve le premier,
vous n' avez plus que 143 possibilités et ainsi de suite...
Twisted Evil

Voici une solution en FBPano pour le tirage au sort :

Code:: const NG = 12 ' Taille de la grille
const NP = 12 ' Nb de points a tirer

dim x%(NP), y%(NP) ' Coordonnees des points
dim t%(NG, NG) ' Tableau memorisant les points trouves
dim xi%, yi% ' Valeurs tirees
dim i% ' Variable de boucle

randomize timer

for i = 1 to NP
  repeat
   xi = int(rnd * NG) + 1
   yi = int(rnd * NG) + 1
  until t(xi, yi) = 0
  t(xi, yi) = 1
  x(i) = xi
  y(i) = yi
  ? i, x(i), y(i)
next i

N.B. Les tableaux commencent à l'indice 1 !

Pour les carrés, je proposerais l'algorithme suivant :

1. Prendre 2 points pour définir le côté du carré
2. Chercher s'il existe un troisième point
3. Si oui chercher un quatrième point

Il faut tester toutes les combinaisons possibles de 2 points. Il y en a 12 * 11 / 2 = 66

Les chance d'obtenir 2 carrés dans la grille ne sont pas bien épaisses!
Voici un test, pressez la barre d'espace pour voir un nouveau tirage:

test:

Code:: full_space 0
label debut
dim key,j
dim i,point,y,x,siz,siz_grid
siz=12 :' nb de points
' la grille commence à 0, donc une grille de 144 points commence au point n°0 et termine au point n°143 ---> donc il faut enlever 1 à siz_grid!
siz_grid=(siz*siz)-1 :' grille de siz*siz points
dim mypoint(siz-1,siz-1) :' tableau de stockage des coordonnées des points

' un picture d'affichage de la grille et des points
picture 1 : width 1,20*siz-1 : height 1,20*siz-1
2d_target_is 1
2d_fill_on
2d_fill_color 255,0,0

debut:
' RAZ du tableau de stockage des coordonnées des points
for i=0 to siz-1
   for j=0 to siz-1
   mypoint(i,j)=0
   next j
next i

' RAZ du picture d'affichage
2d_clear

' affichage d'une grille
for i=0 to height(1) step 20
   2d_line 0,(siz/2)+i,width(1),(siz/2)+i
   2d_line (siz/2)+i,0,(siz/2)+i,height(1)
next i

' tirer 'siz' points tous différents
for i=1 to siz
   point = int(siz_grid*rnd(1)) :' n° du point, de 0 à siz_grid
   y=mod(point,siz) : x=(point-y)/siz :' coordonnées du point dans la grille
   while mypoint(x,y)=1 :' le point est déjà stocké dans le tableau?
   point = int(siz_grid*rnd(1)) :' oui, alors nouveau tirage
   y=mod(point,siz) : x=(point-y)/siz :'
   end_while
   mypoint(x,y)=1 :' sinon le point est unique, l'écrire dans le tableau
next i

' affichage des points
for point=0 to siz_grid :' n° du point, de 0 à siz_grid
   y=mod(point,siz) : x=(point-y)/siz :' coordonnées du point dans la grille
   if mypoint(x,y)=1 then print point," : x=",x," y=",y
   if mypoint(x,y)=1 then tracepoint(x,y) :' traçage des points
next point

' relancer avec la barre 'espace'
repeat : key=scancode : until key=0
repeat : key=scancode : until key>0
if key=32 then goto debut

END
sub tracepoint(x,y)
   2d_circle (siz/2)+x*20,(siz/2)+y*20,4
end_sub

sub tracecarre(x_depart,y_depart,taille)
   2d_pen_color 0,0,255 : 2d_pen_width 4
   2d_line (siz/2)+x_depart*20,(siz/2)+y_depart*20,(siz/2)+(taille-0+x_depart)*20,(siz/2)+y_depart*20
   2d_line (siz/2)+(taille-0+x_depart)*20,(siz/2)+y_depart*20,(siz/2)+(taille-0+x_depart)*20,(siz/2)+(taille-0+y_depart)*20
   2d_line (siz/2)+(taille-0+x_depart)*20,(siz/2)+(taille-0+y_depart)*20,(siz/2)+x_depart*20,(siz/2)+(taille-0+y_depart)*20
   2d_line (siz/2)+x_depart*20,(siz/2)+(taille-0+y_depart)*20,(siz/2)+x_depart*20,(siz/2)+y_depart*20
   2d_pen_color 0,0,0 : 2d_pen_width 1
end_sub

Ouf_ça_passe _ou_ça_ casse a écrit:: j'espérais appâter Papydall aussi.

Merci pour avoir pensé à moi.
Voilà bientôt deux longs mois que je ne suivais pas le forum à cause de mon état de santé (je vous épargne les détails).
Il me faut, sans doute du temps pour que ma mécanique se mette à tourner !

silvermann a écrit:: … par contre, déterminer si 4 points forme un carré, le + petit, le + grand, ça ne me saute pas aux yeux quant à la manière de procéder

Soit 4 points A(xa,ya), B(xb,yb), C(xc,yc), D(xd,yd)
Pour prouver que ces 4 points forment un carré, on peut procéder comme suit :
• Commencer par démontrer que le quadrilatère est un losange en déterminant les longueurs de ses côtés AB, BD, DC et CA et en vérifiant qu’ils sont tous égaux.
• Puis prouver que ce losange est un carré en calculant la longueur des 2 diagonales AD et BC et en vérifiant qu’elles ont même longueur.

Rappel : pour calculer la distance entre 2 points A(xa,ya) et B(xb,yb)
Distance = Racine carrée de [(xb-xa)² + (yb-ya)²]

A+

EDIT : Il faut aussi prendre en considération qu’il ne s’agit pas d’un quadrilatère dégénéré : 3 (ou 4) points ne doivent pas être alignés !

Admin Nombre de messages : 2386 Date d'inscription : 28/05/2007

Je suis content de te revoir sur le forum, Papydall, et j'espère que tu vas te remettre très vite.

_________________

Défi pour les frimas à venir = dessiner des carrés Webdav

username : panoramic@jack-panoramic password : panoramic123

Nombre de messages : 7095 Localisation : 77 Date d'inscription : 29/11/2007

Content moi aussi papydall, tu commençais à nous inquiéter...
Bon courage pour la suite !

Sujet: re Dim 20 Oct 2019 - 23:09

Content de te revoir parmis nous Papydall !
cheers

Merci les amis.
Voici une fonction qui détermine si les 4 points A, B ,C, D de coordonnées xa,ya ; xb,yb ; xc,yc ; xd,yd est un carré

Code:: rem ============================================================================
rem Fonction pour déterminer si le quadrilatère ABCD de coordonnées
rem xa,ya ; xb,yb ; xc,yc ; xd,yd est un carré
rem ============================================================================
   ' carré avec côtés // aux axes __
message Carree_ABCD(100,100,300,100,300,300,100,300) : ' <--- 1 carrée |__|

   ' carré avec côtés // aux bissectrices des axes /\
message Carree_ABCD(300,100,500,300,300,500,100,300) : ' <--- 1 carrée \/

message Carree_ABCD(100,100,100,100,200,100,300,250) : ' <--- 0 ce n'est pas un carré

end
rem ============================================================================
' Déterminer la distance entre deux points de coordonnées x1,y1 et x2,y2
FNC Distance_AB(x1,y1,x2,y2)
   result sqr((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
END_FNC
rem ============================================================================
' Déterminer si le quadrilatère ABCD de coordonnées xa,ya ; xb,yb ; xc,yc ; xd,yd
' est un carré
' Retourne 1 si c'est un carré, 0 sinon
' Si les 4 côtés sont égaux, il s'agit d'un losange.
' Si en plus les 2 diagonales sont égales, il s'agit d'un carré.
FNC Carree_ABCD(xa,ya,xb,yb,xc,yc,xd,yd)
   dim_local d1,d2,d3,d4,d5,d6
   d1 = Distance_AB(xa,ya,xb,yb) : ' côté 1
   d2 = Distance_AB(xb,yb,xc,yc) : ' côté 2
   d3 = Distance_AB(xc,yc,xd,yd) : ' côté 3
   d4 = Distance_AB(xd,yd,xa,ya) : ' côté 4
   d5 = Distance_AB(xa,ya,xc,yc) : ' diagonale 1
   d6 = Distance_AB(xb,yb,xd,yd) : ' diagonale 2

   if (d1 = d2) and (d1 = d3) and (d1 = d4) and (d5 = d6)
   result 1
   else
   result 0
   end_if
END_FNC
rem ============================================================================

Sujet: Orientation Lun 21 Oct 2019 - 8:09

Je suis content d’avoir intéressé 4 seniors des PANO et j’espère que d’autres suivront.

Vous avez tou(te)s compris que les carrés pouvaient être en diagonale aussi ou autres orientations.

Je pense que certains d’entre vous pourraient aussi en faire un jeu à condition d’intégrer obligatoirement au moins 1 carré à dessiner sinon le jeu aurait peu d’intérêt. Donc hors tirage des autres points.

@ Papydall
Je te souhaite un bon retour par minous (Euh, je me suis trompé, je voulais écrire "parmi nous").
Tes précieux conseils nous ont manqué.

Votre Ouf_ca_passe_ou_ca_casse

Dernière édition par silverman le Mar 22 Oct 2019 - 9:41, édité 1 fois

Merci pour ton aide Papydall, mais j'y ai réfléchi depuis et je ne pensais pas à une méthode purement mathématique Wink

Je compte lire les points en partant du haut à gauche(ordonnée à l'origine) et faire ceci:

idée:

cela va me permettre de tester toutes les combinaisons, et m'affranchir de l'angle d'inclinaisons du carré

La réalisation... Very Happy

ma solution finale:

Code:: full_space 0

label debut

dim j,mem_pt,lx,ly,grand_carre,petit_carre,gc_xa,gc_ya,gc_xb,gc_yb,pc_xa,pc_ya,pc_xb,pc_yb,sol,nbpt
dim i,point,x,y,siz,siz_grid,x1,y1

nbpt=36 :' nb de points
siz=12 :' taille horizontale de la grille (grille carrée)

' la grille commence à 0, donc une grille de 144 points commence au point n°0 et termine au point n°143 ---> donc il faut enlever 1 à siz_grid!
siz_grid=(siz*siz)-1 :' grille de siz*siz points
dim mypoint(siz-1,siz-1) :' tableau de stockage des coordonnées des points

' un picture d'affichage de la grille et des points
picture 1 : width 1,20*siz-1 : height 1,20*siz-1
2d_target_is 1
2d_fill_on
2d_fill_color 255,0,0
left 1,200

debut:
' RAZ du tableau de stockage des coordonnées des points
for y=0 to siz-1
   for x=0 to siz-1
   mypoint(x,y)=0
   next x
next y

' RAZ form 0 et picture d'affichage
2d_target_is 0 : 2d_clear
print "Patientez..." : print
2d_target_is 1 : 2d_clear

' affichage d'une grille
for i=0 to height(1) step 20
   2d_line 0,(siz/2)+i,width(1),(siz/2)+i
   2d_line (siz/2)+i,0,(siz/2)+i,height(1)
next i

' tirer 'nbpt' points tous différents
for i=1 to nbpt
   point = int(siz_grid*rnd(1)) :' n° du point, de 0 à siz_grid
   x=mod(point,siz) : y=(point-x)/siz :' coordonnées du point dans la grille
   while mypoint(x,y)=1 :' le point est déjà stocké dans le tableau?
   point = int(siz_grid*rnd(1)) :' oui, alors nouveau tirage
   x=mod(point,siz) : y=(point-x)/siz :'
   end_while
   mypoint(x,y)=1 :' sinon le point est unique, l'écrire dans le tableau
next i

' affichage des points
for point=0 to siz_grid :' n° du point, de 0 à siz_grid
   x=mod(point,siz) : y=(point-x)/siz :' coordonnées du point dans la grille
   if mypoint(x,y)=1 then tracepoint(x,y) :' traçage des points
next point

' recherche des carrés
' principe : ex. pour 12 points:
' le point 1 va être testé avec les 11 restant car il peut former un carré qu'avec ces 11 points
' le point 2 va être testé avec les 10 restant car il peut former un carré qu'avec ces 10 points, le point précédent ayant déjà été testé...
' etc... il y aura de moins en moins de point à lire...
'
sol = 0 :' RAZ de la variable "solution trouvée"
mem_pt=0 : j=0 : grand_carre=0 : petit_carre=siz*1.5 :' initialisation
repeat :' teste l'ensemble des points...
   point=mem_pt :' rafraîchir la variable "point" pour le sub "lirepoint()"
   lirepoint() :' lire un point
   mem_pt=point
   x1=x : y1=y :' mémoriser x et y pour plus tard
   j=j+1
   for i=j to nbpt-1 :' teste le point lu avec le point suivant (il y aura de moins en moins de point à lire...)
   lirepoint() :' lire le point suivant (x et y changent)
   lx=x-x1 :'
   ly=y-y1 :'
   if point_exist(x-ly,y+lx)=1 :' on calcule les coordonnées du point qui pourrait former le 3ème coin d'un carré; Ce point existe t'il ?
   if point_exist(x-ly-lx,y+lx-ly)=1 :' on calcule les coordonnées du point qui pourrait former le 4ème coin d'un carré; Ce point existe t'il ?
   if sqr(power(x-x1,2)+power(y-y1,2))>grand_carre :' oui, alors on mémorise le carré qui a le plus grand côté
   grand_carre=sqr(power(x-x1,2)+power(y-y1,2))
   gc_xa=x1
   gc_ya=y1
   gc_xb=x
   gc_yb=y
   end_if
   if sqr(power(x-x1,2)+power(y-y1,2))<petit_carre :' oui, alors on mémorise le carré qui a le plus petit côté
   petit_carre=sqr(power(x-x1,2)+power(y-y1,2))
   pc_xa=x1
   pc_ya=y1
   pc_xb=x
   pc_yb=y
   end_if
   sol=1 :' une solution a été trouvé
' tracecarre(x1,y1,x,y,int(rnd(255)),int(rnd(255)),int(rnd(255))) :' debug : voir tous les carrés
' print x1," ",y1
' print x," ",y
' print x-ly," ",y+lx
' print x-ly-lx," ",y+lx-ly
' print
   end_if :' le point qui pourrait formerle 4ème coin n'existe pas
   end_if :' le point qui pourrait former le 3ème coin n'existe pas
   next i
until j=nbpt-1 :' ...jusqu'à tous les lire

' trace le + grand carré
if grand_carre>0
   print "En BLEU, le + grand carré"
   tracecarre(gc_xa,gc_ya,gc_xb,gc_yb,0,0,255)
end_if

' trace le + petit carré
if petit_carre<siz*1.5
   tracecarre(pc_xa,pc_ya,pc_xb,pc_yb,0,255,0)
   print "En VERT, le + petit carré"
end_if

' raffraîchit l'affichage des points
for point=0 to siz_grid :' n° du point, de 0 à siz_grid
   x=mod(point,siz) : y=(point-x)/siz :' coordonnées du point dans la grille
   if mypoint(x,y)=1 then tracepoint(x,y) :' traçage des points
next point

' nouveau tirage automatique si pas de solution
if sol=0 then goto debut

' nouveau tirage avec la barre 'espace'
print
print "Barre d'espace pour un nouveau tirage"
if wait_key()=32 then goto debut

END
' Les subs / fnc
sub tracepoint(x,y)
   2d_circle (siz/2)+x*20,(siz/2)+y*20,4
end_sub

sub lirepoint()
   repeat
   x=mod(point,siz) : y=(point-x)/siz
   point=point+1
   until mypoint(x,y)=1
end_sub

fnc point_exist(point_exist_x%,point_exist_y%)
   result 0
   if point_exist_x%>=0 and point_exist_x%<siz
   if point_exist_y%>=0 and point_exist_y%<siz
   result mypoint(point_exist_x%,point_exist_y%)
   end_if
   end_if
end_fnc

sub tracecarre(x1,y1,x2,y2,R,V,B)
dim_local lx,ly
   2d_pen_color R,V,B : 2d_pen_width 4
   2d_poly_from (siz/2)+x1*20,(siz/2)+y1*20
   lx=x2-x1
   ly=y2-y1
   2d_poly_to (siz/2)+x2*20,(siz/2)+y2*20
   2d_poly_to (siz/2)+(x2-ly)*20,(siz/2)+(y2+lx)*20
   2d_poly_to (siz/2)+(x2-ly-lx)*20,(siz/2)+(y2+lx-ly)*20
   2d_poly_to (siz/2)+x1*20,(siz/2)+y1*20
   2d_pen_color 0,0,0 : 2d_pen_width 1
end_sub

fnc wait_key()
   dim_local wait_key_key%
   repeat : wait_key_key%=scancode : until wait_key_key%=0
   repeat : wait_key_key%=scancode : until wait_key_key%>0
   result wait_key_key%
end_fnc

BRAVO l’homme d’argent ! king

Solution élégante malgré les 2 GOTO que je n’aime pas trop ! Mais ça c’est une question de goût. Wink

Tu as gagné le titre … heu Ouf_ça_passe, quel est le prix à gagner déjà ?

@Ouf_ça_passe cette fois-ci ça a passé et ça n’a pas cassé.
Merci d’avoir proposé ce défi : ça a fait réveiller le forum.
Si tu as d’autres défis …

Papydall a écrit:: ...malgré les 2 GOTO que je n’aime pas trop...

C'est fait exprès pour les anti-gotoïste lol!

Le défi c'est que chacun propose une solution. Je suis curieux de voir d'autres algorithmes, comment les autres ont fait... geek

Allez, allez, à vos claviers! Very Happy

Sujet: Bravo Sllverman Mar 22 Oct 2019 - 11:24

Ainsi il n’a pas fallu attendre la fin des frimas pour obtenir une réponse de Silverman.
Qu’il soit récompensé par l’expression de ma profonde considération (et c’est déjà beaucoup).
Cela ne doit pas décourager les autres à persévérer pour proposer d’autres solutions.
Il doit y en avoir.
Et chez les seniors des PANO, c’est comme chez les marines américains, il y a les premiers arrivés mais il ne faut jamais perdre un membre de la mission.

Bonne réflexion

» Une formule pour les dessiner tous
» Sauriez-vous compter les carrés ?
» Nouveau défi pour les spécialistes
» Carrés disséqués
» Défi2 = les moindres carrés