La tâche consiste à dessiner un polygone régulier de n côtés en utilisant uniquement une boussole et une règle non marquée.

L'entrée (n) est l'un des 10 nombres suivants: 3, 4, 5, 6, 8, 10, 12, 15, 16, 17.

Méthode : comme vous n'avez qu'une règle et une boussole, vous ne pouvez dessiner que des points, des lignes et des cercles.

Une ligne ne peut être tracée:

• à travers deux points existants.

Un cercle ne peut être tracé:

• avec un point comme centre et son périmètre passant par un deuxième point.

Un point ne peut être tracé:

• à l'intersection de deux lignes,

• à l'intersection (s) d'une ligne et d'un cercle,

• à l'intersection de deux cercles,

• au début, quand vous pouvez tirer 2 points pour commencer.

À travers ce processus (et uniquement à travers ce processus), vous devez tracer les n lignes du n-gon demandé, ainsi que tout travail requis pour arriver à cette étape.

EDIT: La position des intersections doit être calculée, mais les lignes et les cercles peuvent être tracés par tout moyen fourni par la langue.

La sortie est une image d'un polygone régulier à n côtés, montrant le travail.

Graphiquement, il n'y a pas de restrictions sur la taille, le format, l'épaisseur des lignes ou tout autre élément non mentionné ici. Cependant, il doit être possible de distinguer visuellement des lignes, cercles et leurs intersections distincts. Aditionellement:

• Les n lignes qui composent les côtés de votre n-gon doivent être d'une couleur différente de votre «travail» (c'est-à-dire des points, des cercles ou d'autres lignes) et une couleur différente à votre arrière-plan.
• Le travail peut laisser les bordures de la zone de dessin, à l'exception des points, qui doivent tous se trouver dans les limites visibles de l'image.
• Un cercle peut être un cercle complet ou simplement un arc (tant qu'il montre les intersections requises).
• Une ligne est infinie (c'est-à-dire quitte la zone de dessin) ou coupée aux deux points qu'elle traverse. EDIT: Une ligne peut être tracée de n'importe quelle longueur. Les points ne peuvent être créés qu'à l'intersection visuelle de la ligne tracée.
• Un point peut être tracé à votre guise, y compris ne pas le marquer.

La notation est double, une soumission obtient 1 point par entrée prise en charge, pour un maximum de 10 points. En cas d'égalité, le nombre d'octets le plus court l'emporte.

La reconnaissance sera accordée aux soumissions qui peuvent construire des n-gons en un minimum d'étapes ou qui peuvent construire des n-gons en dehors de la plage donnée, mais cela n'aidera pas votre score.

Informations de fond de Wikipedia

BBC Basic, 8 polygones: 3,4,5,6,8,10,12,15 côtés (également 60 côtés)

Téléchargez l'émulateur sur http://www.bbcbasic.co.uk/bbcwin/download.html

J'ai décidé de ne pas inclure 16 côtés, simplement parce que ma pré-construction devenait plutôt encombrée. 2 autres cercles et une ligne seraient nécessaires. BTW 17 côtés est en effet très compliqué et irait peut-être mieux en tant que programme séparé.

J'ai obtenu plus de retour pour ajouter 2 cercles à ma construction d'origine pour faire le pentagone, car cela m'a également donné accès à 10,15 et 60 côtés.

  GCOL 7                               :REM light grey
  z=999                                :REM width of display (in positive and negative direction)
  e=1                                  :REM enable automatic drawing of line through intersections of 2 circles
  DIM m(99),c(99),p(99),q(99),r(99)    :REM array dimensioning for lines and points
  REM lines have a gradient m and y-intercept c. Points have coordinates (p,q) and may be associated with a circle of radius r.

  REM PRECONSTRUCTION

  ORIGIN 500,500
  p(60)=0:q(60)=0                      :REM P60=centre of main circle
  p(15)=240:q(15)=70                   :REM P15=intersection main circle & horiz line
  t=FNr(60,15)                         :REM draw main circle, set radius, SQR(240^2+70^2)=250 units (125 pixels)
  t=FNl(1,60,15)                       :REM L1=horizontal through main circle
  t=FNc(15,45,1,60,-1)                 :REM define P45 as other intersection of main cir and horiz line. overwrite P15 with itself.

  t=FNr(15,45):t=FNr(45,15)            :REM draw 2 large circles to prepare to bisect L1
  t=FNc(61,62,2,45,15)                 :REM bisect L1, forming line L2 and two new points
  t=FNc(30,0,2,60,-1)                  :REM define points P0 and P30 on the crossings of L2 and main circle
  t=FNr(30,60):t=FNc(40,20,3,60,30)    :REM draw circles at P30, and line L3 through intersections with main circle, to define 2 more points
  t=FNr(15,60):t=FNc(25,5,4,60,15)     :REM draw circles at P15, and line L4 through intersections with main circle, to define 2 more points
  t=FNx(63,3,4):t=FNl(5,63,60)         :REM draw L5 at 45 degrees
  t=FNc(64,53,5,60,-1)                 :REM define where L5 cuts the main circle

  e=0                                  :REM disable automatic line drawing through intersections of 2 circles
  GCOL 11                              :REM change to light yellow for the 5 sided preconstruction
  t=FNx(65,1,4):t=FNr(65,0)            :REM draw a circle of radius sqrt(5) at intersection of L1 and L4
  t=FNc(66,67,1,65,-1)                 :REM find point of intersection of this circle with L1
  t=FNr(0,67)                          :REM draw a circle centred at point 0 through that intersection
  t=FNc(36,24,6,60,0)                  :REM find the intersections of this circle with the main circle


  REM USER INPUT AND POLYGON DRAWING

  INPUT d
  g=ASC(MID$("  @@XT u X @  T",d))-64  :REM sides,first point: 3,0; 4,0; 5,24; 6,20; 8,53; 10,24; 12,0; 15,20
  IF d=60 THEN g=24                    :REM bonus polygon 60, first point 24
  FORf=0TOd
    GCOL12                             :REM blue
    h=(g+60DIVd)MOD60                  :REM from array index for first point, calculate array index for second point
    t=FNr(h,g)                         :REM draw circle centred on second point through first point
    t=FNc((h+60DIVd)MOD60,99,99,60,h)  :REM calculate the position of the other intersection of circle with main circle. Assign to new point.
    GCOL9                              :REM red
    LINEp(g),q(g),p(h),q(h)            :REM draw the side
    g=h                                :REM advance through the array
  NEXT

  END

  REM FUNCTIONS

  REM line through a and b
  DEFFNl(n,a,b)
  m(n)=(q(a)-q(b))/(p(a)-p(b))
  c(n)=q(a)-m(n)*p(a)
  LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z
  =n

  REM radius of circle at point a passing through point b
  DEFFNr(a,b)
  r(a)=SQR((p(a)-p(b))^2+(q(a)-q(b))^2)
  CIRCLEp(a),q(a),r(a)
  =a

  REM intersection of 2 lines: ma*x+ca=mb*x+cb so (ma-mb)x=cb-ca
  DEFFNx(n,a,b)
  p(n)=(c(b)-c(a))/(m(a)-m(b))
  q(n)=m(a)*p(n)+c(a)
  =n

  REM intersection of 2 circles a&b (if b>-1.) The first step is calculating the line through the intersections
  REM if b < 0 the first part of the function is ignored, and the function moves directly to calculating intersection of circle and line.
  REM inspiration from http://math.stackexchange.com/a/256123/137034

  DEFFNc(i,j,n,a,b)
  IF b>-1 c(n)=((r(a)^2-r(b)^2)-(p(a)^2-p(b)^2)-(q(a)^2-q(b)^2))/2/(q(b)-q(a)):m(n)=(p(a)-p(b))/(q(b)-q(a)):IF e LINE -z,c(n)-m(n)*z,z,c(n)+m(n)*z

  REM intersection of circle and line
  REM (mx+ c-q)^2+(x-p)^2=r^2
  REM (m^2+1)x^2 + 2*(m*(c-q)-p)x + (c-q)^2+p^2-r^2=0
  REM quadratic formula for ux^2+vx+w=0 is x=-v/2u +/- SQR(v^2-4*u*w)/2u or x= v/2u +/- SQR((v/2u)^2 - w/u)

  u=m(n)^2+1
  v=-(m(n)*(c(n)-q(a))-p(a))/u               :REM here v corresponds to v/2u in the formula above
  w=SQR(v^2-((c(n)-q(a))^2+p(a)^2-r(a)^2)/u)


  s=SGN(c(n)+m(n)*v-q(a)):IF s=0 THEN s=1    :REM sign of s depends whether midpoint between 2 points to be found is above centre of circle a
  p(i)=v+s*w:q(i)=m(n)*p(i)+c(n)             :REM find point that is clockwise respect to a
  p(j)=v-s*w:q(j)=m(n)*p(j)+c(n)             :REM find point that is anticlockwise respect to a
  =n

Le programme effectue une pré-construction avant de demander une entrée utilisateur. Cela suffit pour définir au moins 2 points sur le cercle principal qui correspondent aux sommets adjacents d'une figure à 3,4,5,6,8,10,12,15 ou 60 faces. Les points sont stockés dans un ensemble de tableaux à 99 éléments, dans lesquels les éléments 0 à 59 sont réservés pour des points également espacés autour de la circonférence. Ceci est principalement pour la clarté, l'octogone ne s'intègre pas parfaitement dans 60 points, donc une certaine flexibilité est nécessaire là-bas (et aussi pour le 16-gon s'il était inclus.) L'image ressemble à l'image ci-dessous, en blanc et gris, avec seulement les deux cercles jaunes étant exclusivement dédiés aux formes à multiples de 5 côtés. Voir http://en.wikipedia.org/wiki/Pentagon#mediaviewer/File:Regular_Pentagon_Inscribed_in_a_Circle_240px.gifpour ma méthode de dessin pentagone préférée. L'angle gai est d'éviter les lignes verticales, car le programme ne peut pas gérer des gradients infinis.

L'utilisateur entre un nombre dpour le nombre de côtés requis. Le programme recherche dans le tableau l'index du premier des deux points (le suivant est à 60 / j dans le sens des aiguilles d'une montre.)

Le programme parcourt ensuite le processus de dessin d'un cercle centré sur le deuxième point qui passe par le premier, et de calcul de la nouvelle intersection afin de contourner le cercle principal. Les cercles de construction sont dessinés en bleu et le polygone requis est dessiné en rouge. Les images finales ressemblent à ceci.

Je suis assez content d'eux. BBC Basic effectue les calculs avec suffisamment de précision. Cependant, il est évident (en particulier avec 15 et 60 côtés) que BBC Basic a tendance à dessiner des cercles avec un rayon légèrement plus petit qu'il ne devrait.

Mathematica, 2 3 4 polygones, 759 octets

S=Solve;n=Norm;A=Circle;L=Line;c={#,Norm[#-#2]}&{a_,b_List}~p~{c_,d_List}:=a+l*b/.#&@@S[a+l*b==c+m*d,{l,m}]{a_,b_List}~p~{c_,r_}:=a+l*b/.S[n[c-a-l*b]==r,l]{c_,r_}~p~{d_,q_}:={l,m}/.S[n[c-{l,m}]==r&&n[d-{l,m}]==q,{l,m}]q={0,0};r={1,0};a=q~c~r;b=r~c~q;Graphics@Switch[Input[],3,{s=#&@@p[a,b];A@@@{a,b},Red,L@{q,r,s,q}},4,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;A@@@{a,b,d},L/@Accumulate/@{k,j},Red,L@{q,e,r,f,q}},6,{d={q,r};e=#&@@d~p~a;f=e~c~q;{g,h}=a~p~f;{i,j}=a~p~b;A@@@{a,b,f},L@{#-2#2,#+2#2}&@@d,Red,L@{r,i,g,e,h,j,r}},8,{k={q,r};{d,e}=a~p~b;j={d,e-d};d=k~p~j~c~q;{e,f}=j~p~d;g=e~c~q;h=q~c~e;i=r~c~e;{o,s}=g~p~h;{t,u}=g~p~i;o={o,2s-2o};s={t,2u-2t};{t,u}=o~p~d;{v,w}=s~p~d;A@@@{a,b,d,g,h,i},L/@Accumulate/@{k,j,o,s},Red,L@{q,t,e,v,r,u,f,w,q}}]

Puces aléatoires:

• L'entrée est fournie via l'invite.
• Je supporte actuellement les entrées 3 , 4 , 6 , 8 .
• Parmi vos options, j'ai choisi les styles de traçage suivants:
  • Cercles pleins.
  • Lignes d'un point d'extrémité à l'autre, sauf si une intersection pertinente se trouve à l'extérieur, auquel cas je coderai l'étendue en dur.
  • Pas de points.
  • Les travaux sont noirs, les polygones sont rouges - non pas pour des raisons esthétiques mais pour des raisons de golf.
• Il y a une sérieuse duplication de code entre les polygones. Je pense qu'à un moment donné, je ferai une seule construction pour chacun d'eux, en énumérant toutes les lignes et les points et les cercles le long du chemin, puis réduira simplement le Switchpour sélectionner les cercles et les lignes pertinents pour chaque construction. De cette façon, je pourrais réutiliser un grand nombre de primitives entre eux.
• Le code contient de nombreuses fonctions standard qui déterminent toutes les intersections pertinentes et créent des cercles à partir de deux points.
• Avec cela en place, j'ajouterai plus de polygones à l'avenir.

Voici le code non golfé:

S = Solve;
n = Norm;
A = Circle;
L = Line;
c = {#, Norm[# - #2]} &
{a_, b_List}~p~{c_, d_List} := 
 a + l*b /. # & @@ S[a + l*b == c + m*d, {l, m}]
{a_, b_List}~p~{c_, r_} := a + l*b /. S[n[c - a - l*b] == r, l]
{c_, r_}~p~{d_, q_} := {l, m} /. 
  S[n[c - {l, m}] == r && n[d - {l, m}] == q, {l, m}]
q = {0, 0};
r = {1, 0};
a = q~c~r;
b = r~c~q;
Graphics@Switch[Input[],
  3,
  {
   s = # & @@ p[a, b];
   A @@@ {a, b},
   Red,
   L@{q, r, s, q}
   },
  4,
  {
   k = {q, r};
   {d, e} = a~p~b;
   j = {d, e - d};
   d = k~p~j~c~q;
   {e, f} = j~p~d;
   A @@@ {a, b, d},
   L /@ Accumulate /@ {k, j},
   Red,
   L@{q, e, r, f, q}
   },
  6,
  {
   d = {q, r};
   e = # & @@ d~p~a;
   f = e~c~q;
   {g, h} = a~p~f;
   {i, j} = a~p~b;
   A @@@ {a, b, f},
   L@{# - 2 #2, # + 2 #2} & @@ d,
   Red,
   L@{r, i, g, e, h, j, r}
   },
  8,
  {
   k = {q, r};
   {d, e} = a~p~b;
   j = {d, e - d};
   d = k~p~j~c~q;
   {e, f} = j~p~d;
   g = e~c~q;
   h = q~c~e;
   i = r~c~e;
   {o, s} = g~p~h;
   {t, u} = g~p~i;
   o = {o, 2 s - 2 o};
   s = {t, 2 u - 2 t};
   {t, u} = o~p~d;
   {v, w} = s~p~d;
   A @@@ {a, b, d, g, h, i},
   L /@ Accumulate /@ {k, j, o, s},
   Red,
   L@{q, t, e, v, r, u, f, w, q}
   }
  ]

Et voici les sorties: