Tangram является рассечение головоломки из семи форм: пять разного размера треугольников, параллелограмм и квадратная. При заданной форме цель состоит в том, чтобы воссоздать форму, используя все части и без наложения. Очевидно, существует бесконечно много способов расположить этот набор элементов на плоскости. Интересным подмножеством являются

Сетка Танграммы

Мы можем нарисовать «стандартный» квадрат Tangram в больший квадрат, который разделен сеткой на 16 меньших квадратов. Танграммы сетки - это просто фигуры, составленные из частей танграма, так что все вершины фигур находятся в точках сетки.

Это те головоломки Tangram, которые мы хотим рассмотреть в этой задаче, поскольку с ними, вероятно, легче справиться, чем с более общими.

В качестве примечания: в 1942 году китайские математики Цюань-Чин Сюн и Фу Трейнг Ван доказали, что существует только 13 выпуклых танграмм. Сначала они показали, что задача может быть сведена к сетчатым танграммам, а затем использовали некоторые комбинаторные и геометрические аргументы. Это все те 13:

Вызов

Учитывая разрешимую сетчатую танграмму, выведите разделение сетчатой ​​танграммы на семь частей танграммы.

IO

Танграм дается как черно-белое изображение (форма черного цвета, фон белым), с обеих сторон, кратными 50px. Сетка имеет ширину ровно 50 пикселей. Линии сетки параллельны сторонам изображения.

РЕДАКТИРОВАТЬ: изображение может быть принято в качестве входных данных и возвращено в качестве выходных данных в любом удобном формате растровых изображений, таких как PNG, TIFF, PBM и т. Д., Но приемлемо представление в виде двоичного 2-мерного массива или строки или матрицы.

Выходные данные должны снова иметь одинаковый размер и снова иметь одинаковую форму, но с каждым элементом разного цвета или, альтернативно, с белыми линиями, разделяющими все элементы. Стоит отметить, что непрямоугольный четырехугольник можно перевернуть.

Пиксели на границе фигур не обязательно должны совпадать с пикселями на фигуре, также, если есть эффекты сглаживания или другой пух, это все еще хорошо.

Пример ввода и вывода:

Примеры:

Возможные решения:

BBC BASIC, 570 514 490 байтов ASCII

Скачать переводчик можно по адресу http://www.bbcbasic.co.uk/bbcwin/download.html.

435 байт токенизированы

Полная программа отображает входные данные L.bmpна экране, а затем изменяет его, чтобы найти решение.

*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

объяснение

Обратите внимание, что в BBC basic расстояние 1 пиксель = 2 единицы, поэтому сетка 50x50 пикселей становится сеткой 100x100.

Мы используем рекурсивную функцию, чтобы поместить 2 больших треугольника, средний треугольник, квадрат и параллелограмм в форму. Более ранняя фигура в списке рисуется до того, как будет сделан следующий рекурсивный вызов. если рекурсивный вызов возвращается без поиска решения, более ранняя фигура перерисовывается черным, и пробуется новая позиция более ранней фигуры.

После того, как эти пять фигур нарисованы, размещение двух маленьких треугольников - это просто формальность. Однако необходимо нарисовать один из них, чтобы выделить их, если они имеют общее преимущество. Мы окрашиваем только один из двух маленьких треугольников. Другой оставлен в естественном черном цвете.

Попытка размещения каждой фигуры выполняется в разных координатах x, y и в 4 различных поворотах. Чтобы проверить, есть ли свободное место для рисования фигуры, мы используем шаблон ниже, с углами 45 градусов. Повороты сделаны примерно на *8 пикселей в 2 полукругах радиуса 9 и 81 единиц и падают на излучающие линии с нечетным кратным 22,5 градуса к осям x и y.

Для большого треугольника все 8 пробелов должны быть чистыми. Для других форм только некоторые ячейки должны быть прозрачными, поэтому применяется маска.

+----+----   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.  

Как только будет установлено, что форма будет соответствовать, она должна быть нарисована. Если это треугольник, с которым он нанесен PLOT 85, если это параллелограмм, число будет на 32 больше (обратите внимание, что для PLOTцелей мы считаем квадрат специальным параллелограммом). В любом случае необходимо указать 3 последовательных вершины. Вторая вершина является источником формы (отмечена *в приведенной выше таблице), за исключением случая большого треугольника, где (до вращения) она есть -1,-1.. Другие 2 вершины могут иметь координаты x и y, -1,0 or 1которые извлекаются из базы 3 закодированные числа, затем масштабируемые на 99 и поворачиваемые по мере необходимости путем преобразования с помощью cи s.

Код без правил

  *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

Выход

Это монтаж решений, найденных программой для тестовых случаев. Использование 99 вместо 100 для игры в гольф оставляет небольшие черные пробелы. Поскольку формы перерисовываются во время поиска, в некоторых случаях может потребоваться несколько секунд, и на них довольно интересно смотреть.