Le Tangram est un puzzle de dissection composé de sept formes: cinq triangles de tailles différentes, un parallélogramme et un carré. Étant donné une forme, l'objectif est de recréer la forme en utilisant toutes les pièces et sans se chevaucher. Il existe évidemment une infinité de façons d'organiser cet ensemble de pièces dans l'avion. Un sous-ensemble intéressant est le

Grille Tangrams

Nous pouvons dessiner le carré Tangram "standard" en un carré plus grand qui est divisé par une grille en 16 carrés plus petits. Les tangrams de la grille ne sont que des formes constituées des pièces du tangram, de sorte que tous les sommets des pièces se trouvent sur les points de la grille.

Ce sont les types de puzzles Tangram que nous voulons considérer dans ce défi, car ils sont probablement plus faciles à gérer que les plus généraux.

En remarque: Les mathématiciens chinois Chuan-Chin Hsiung et Fu Traing Wang ont prouvé en 1942 qu'il n'y avait que 13 tangrams convexes. Ils ont d'abord montré que le problème peut être réduit à des tangrammes de grille, puis ont utilisé des arguments combinatoires et géométriques. Ce sont tous ces 13:

Défi

Étant donné un tangram de grille résoluble, produire une dissection du tangram de grille dans les sept morceaux de tangram.

IO

Un tangram est donné comme une image en noir et blanc (la forme est en noir, le fond en blanc), avec des multiples des deux côtés de 50px. La grille a une largeur d'exactement 50px. Les lignes de la grille sont parallèles aux côtés de l'image.

MODIFIER: L'image peut être acceptée en entrée et renvoyée en sortie dans n'importe quel format d'image raster pratique comme PNG, TIFF, PBM, etc., mais une représentation sous forme de tableau binaire 2D, de chaîne ou de matrice est acceptable.

La sortie devrait à nouveau avoir la même taille et devrait avoir à nouveau la même forme, mais avec chaque pièce une couleur différente, ou alternativement avec des lignes blanches séparant toutes les pièces. Il convient de noter que le quadrilatère non rectangulaire peut être inversé.

Les pixels sur la bordure des pièces ne doivent pas exactement correspondre à ceux de la forme, même s'il y a des effets de repliement ou d'autres flous, c'est toujours correct.

Exemple d'entrée et de sortie:

Exemples:

Solutions possibles:

BBC BASIC, 570 514 490 octets ASCII

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

435 octets tokenisés

Le programme complet affiche une entrée de L.bmpsur l'écran, puis la modifie pour trouver une solution.

*DISPLAY L
t=PI/8q=FNa(1)
DEFFNa(n)IFn=7END
LOCALz,j,p,i,c,s,x,y,m,u,v
F.z=0TO99u=z MOD10*100v=z DIV10*100ORIGINu,v
F.j=0TO12S.4p=0F.i=j+3TOj+9S.2c=9*COS(i*t)s=9*SIN(i*t)p=p*4-(POINT(c,s)<>0)*2-(POINT(9*c,9*s)<>0)N.
m=n:IFn=5A.(43A.p)=0p=0m=7
IF(ASCM."??O|(C",n)-64A.p)=0THEN
F.i=-1TO0GCOL0,-i*n:c=99*COS(j*t)s=99*SIN(j*t)y=402/3^m MOD3-1MOVE-c-s*y,c*y-s:x=n<3MOVEc*x-s*x,s*x+c*x:x=2778/3^m MOD3-1y=5775/3^m MOD3-1PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y:IFi q=FNa(n+1)ORIGINu,v
N.
ENDIF
N.N.=0

Explication

Notez que dans BBC basic, une distance de 1 pixel = 2 unités, de sorte que la grille de 50 x 50 pixels devient une grille de 100 x 100.

Nous utilisons une fonction récursive pour placer les 2 grands triangles, triangle moyen, carré et parallélogramme dans la forme. La forme antérieure de la liste est dessinée avant le prochain appel récursif. si un appel récursif revient sans trouver de solution, la forme précédente est sur-dessinée en noir et une nouvelle position de la forme précédente est essayée.

Une fois ces cinq formes dessinées, placer les deux petits triangles n'est qu'une formalité. Il est cependant nécessaire d'en dessiner un, afin de les distinguer s'ils partagent un bord commun. Nous colorons uniquement l'un des deux petits triangles. L'autre est laissé en noir naturel.

Le placement de chaque forme est tenté à différentes coordonnées x, y et en 4 rotations différentes. Pour tester s'il y a de l'espace libre pour dessiner une forme, nous utilisons le modèle ci-dessous, avec des angles de 45 degrés. Les rotations sont faites autour du *et les 8 pixels testés sont en 2 demi-cercles de rayon 9 et 81 unités et tombent sur des lignes rayonnantes à des multiples impairs de 22,5 degrés sur les axes x et y.

Pour un grand triangle, les 8 espaces doivent être vides. Pour les autres formes, seules certaines cellules doivent être claires, un masque est donc appliqué.

+----+----   Shape             Mask HGFEDCBA Mask decimal 
|\ E/|\G /  
| \/F|H\/    1,2. Large triangle    11111111    -1
|C/\ | /     3. Med triangle        00001111    15
|/ D\|/      4. Square              00111100    60
+----*       5. Parallelogram       11101000   -24
|\ B/        6. Small triangle      00000011     3
|A\/         7. Parallogr reversed  00101011    43
| /          Note: reversed parallelogram is checked/drawn at recursion depth n=5
|/           with a special check, but the coordinates are encoded as m=7.  

Une fois qu'il est établi qu'une forme conviendra, elle doit être dessinée. S'il s'agit d'un triangle avec PLOT 85lequel il est tracé , s'il s'agit d'un parallélogramme, le nombre est 32 plus élevé (notez que, pour les PLOTbesoins, nous considérons un carré comme un parallélogramme spécial). Dans les deux cas, 3 sommets consécutifs doivent être donnés. Le deuxième sommet est à l'origine de la forme (marqué *dans le tableau ci-dessus) sauf dans le cas du grand triangle, où (avant la rotation) il est -1,-1.Les 2 autres sommets peuvent avoir des coordonnées x et y -1,0 or 1qui sont extraites de la base 3 nombres codés, puis mis à l'échelle par 99 et pivotés si nécessaire par transformation avec cet s.

Code non golfé

  *DISPLAY L
  t=PI/8                                          :REM Constant 22.5 degrees.
  q=FNa(1)                                        :REM Call function, return dummy value to q
  END                                             :REM End the program gracefully if no solution. Absent in golfed version.

  DEFFNa(n)                                       :REM Recursive function to place shapes.
  IFn=7END                                        :REM If n=7 solution found, end program.
  LOCALk,z,j,p,i,c,s,x,y,m,u,v                    :REM declare local variables for function.
  k=ASCMID$("??O|(C",n)-64                        :REM Bitmasks for big tri, big tri, med tri, sq, normal paralellogram, small tri.
  FORz=0TO99                                      :REM For each point on the grid
    u=z MOD10*100:v=z DIV10*100                   :REM calculate its x and y coordinates relative to bottom left of screen
    ORIGINu,v                                     :REM and set the origin to this point.
    FORj=0TO12STEP4                               :REM For each rotation 0,90,180,270deg
      p=0                                         :REM assume no non-black pixels found
      FORi=j+3TOj+9STEP2                          :REM test angles of 3,5,7,9 times 22.5 deg anticlockwise from right x axis.
        c=9*COS(i*t)                             :REM Coords of test points at radius ll
        s=9*SIN(i*t)
        p*=4                                      :REM Leftshift any existing data in p
        p-=(POINT(c,s)<>0)*2+(POINT(9*c,9*s)<>0)  :REM and check pixels at radius 11 and 99.
      NEXT
      m=n                                         :REM The index of the shape to plot normally corresponds with recursion depth n.
      IF n=5 AND (43ANDp)=0 p=0:m=7               :REM If n=5 check if a reverse parallelogram is possible (mask 43). If so, clear p and change m to 7.
      REM                                         :REM Check p against mask k, if the shape fits then...
      IF (k ANDp)=0 THEN
        FOR i=-1 TO 0                               :REM draw the shape in colour, and if deeper recursions prove unsuccesful, redraw it in black.
          GCOL0,-i*n                                :REM Colour is equal to n.
          c=99*COS(j*t)                             :REM Set parameters c and s for scaling by 99
          s=99*SIN(j*t)                             :REM and rotation by 0,90,180 or 270 as appropriate.
          x=-1                                      :REM For vertex 1, x=-1 always.
          y=402/3^m MOD3-1                          :REM Lookup y value for vertex 1.
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=n<3                                     :REM For vertex 2, coords are 0,0 except for large triangle where they are -1,-1
          y=x                                       :REM in BBC BASIC, TRUE=-1
          MOVEc*x-s*y,s*x+c*y                       :REM Use c and s to transform the vertex and move to it.
          x=2778/3^m MOD3-1                         :REM Lookup x and y value for vertex 3.
          y=5775/3^m MOD3-1                         :REM PLOT85 uses last 2 points + specified point to make triangle, PLOT85+32 makes paralelogram (or square.)
          PLOT85-32*(n MOD6>3),c*x-s*y,s*x+c*y      :REM Use c and s to transform the vertex and draw shape.
          IFi q=FNa(n+1):ORIGINu,v                  :REM If i=-1 recurse to next level. If it fails, reset the origin before replotting this level's shape in black.
        NEXT
      ENDIF
    NEXT
  NEXT
  =0                                                :REM Dummy value to return from function

Sortie

Ceci est un montage des solutions trouvées par le programme pour les cas de test. L'utilisation de 99 au lieu de 100 pour des raisons de golf laisse quelques petits trous noirs. Comme les formes sont redessinées pendant les recherches, l'exécution de certains cas peut prendre quelques secondes et est assez fascinante à regarder.