Треугольные решетки: просто соединенные полиамины

9

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

Сетки

Мы будем использовать раскладку треугольной сетки Мартина для ввода:

треугольная сетка

Обратите внимание на тот факт, что центры треугольников образуют примерно прямоугольную сетку и что верхний левый треугольник "указывает" вверх. Затем мы можем описать подмножество этой сетки, дав прямоугольную «звездную карту», ​​указывающую, какие треугольники включены, а какие нет. Например, эта карта:

** **
*****

соответствует наименьшему polyiamond, который содержит отверстие:

9-луночное с отверстием

Отверстия

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

Соревнование

Напишите функцию или программу, которые принимают в качестве входных данных «звездную карту», ​​как описано выше, и выводят истинные значения в том и только в том случае, если указанное подмножество треугольной сетки является односвязным многоугольником .

Больше примеров

*** ***
*******

соответствует polyiamond

13-луночное без отверстия

который просто связан.


*   *
** **
 ***

соответствует polyiamond

9-луночный без отверстия

который просто связан.


**  **
*** **
 ****

соответствует non- polyiamond

13 треугольников, которые ничего интересного

который не был бы просто связан, даже если бы это был polyiamond.

Входные характеристики

  • Ввод будет состоять только из звездочек, пробелов и перевода строки.
  • Первым символом ввода всегда будет пробел или звездочка (соответствует направленному вверх треугольнику в левом верхнем углу сетки).
  • В первой и последней строках всегда будет хотя бы одна звездочка.
  • НЕТ гарантии, что строки после первой строки не будут пустыми. Два перевода строки в строке могут появиться в допустимом вводе.
  • Длина линий не обязательно должна быть одинаковой.

Условие победы

Это , так что кратчайший ответ в байтах выигрывает.

Тестовые случаи

Правдивые карты:

1) *

2) *
   *

3) **

4) *** ***
   *******

5) *   *
   ** **
    ***

6) *
   **
    *

7)    **
     ***
   ****

8) ****
   **   *
    *****

9) ***********
   **    **  **
    ****  **  **
              **
   ************

Ложные карты:

1) *
   *
   *

2) * *

3) *
    *

4)  **
   **

5) ***

   ***

6) ** **
   *****

7) **  **
   *** **
    ****

8)  *
    *

9) *****
   **   *
    *****
quintopia
источник
1
хороший вопрос Если треугольные сетки станут чем-то единым, позвольте мне предложить их представить, например, AV VA\nVAVAVвместо того, ** **\n*****чтобы облегчить визуализацию для человека. Я уже внес изменение в одну из диаграмм Мартина ASCII.
Уровень Река Сент
Я не был особенно обеспокоен читаемостью человека, нет. Я хотел сделать все, что было бы проще для программы, оставаясь маленькой.
Quintopia
Так в принципе ложно, если есть раздел, только «связанный» углами?
Майкл Кляйн
1
Или если есть части, которые вообще не связаны. Мартин сформулировал это так: «Истинно, если фигура и земля соединены вдоль краев, так что 2 заливки достаточно, чтобы перекрасить плоскость».
Quintopia

Ответы:

4

Улитки , 95 байт

F&
lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}\*}+l\ ,~a~|{\ (lr|=((ul.)2 ,l~a~)d|!((ul.)2 ,l~a~)u}+~

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

F&                         ,, option F: pad lines with spaces to the length of the longest
                           ,, option &: print 1 iff match succeeds from every cell
lr                         ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, direction down, if we are an even number of orthogonal moves from the top left
      | !((ul.)2 ,l~a~) u  ,, or, direction up if we are odd number of moves from the top left
    }  \*                  ,, literal '*'
}+                         ,, 1 or more times
l\ ,~a~                    ,, check that we are on the leftmost * in the top line

|                          ,, the part before this is for starting on '*'; part after for starting on ' '

{ \                        ,, literal ' '
    (   lr                 ,, direction left or right, or
      | =((ul.)2 ,l~a~) d  ,, same drill as before...
      | !((ul.)2 ,l~a~) u 
}+                         ,, 1 or more times
~                          ,, end on an out of bounds cell
feersum
источник
Я не понимаю, как это работает, но это полностью работает.
Quintopia
3

CJam, 101 98 байт

qN/_z,f{' e]}{S2*f+W%z}4*:eeee::f+:~{_(aL{+_{_2,.+1$2,.-@_:+1&!2*(a.+}%2${a1$&},\;@1$-@@}h;\;-}2*!

Попробуйте онлайн.

Я наконец преодолел свой страх перед выполнением заливки в CJam. Это примерно так же безобразно, как я ожидал, и вполне определенно можно играть в гольф.

Общая идея состоит в том, чтобы выполнить две заливки (которые фактически выполняются как удаления из списка не посещенных ячеек). Первый проход удалит все пробелы, которые достижимы от края. Затем второй проход выберет первый *в порядке чтения и удалит все треугольники, доступные для этого. Если и только если результирующий список пуст, полиамонт был просто связан:

  • Если у полиамона была дыра, первая заливка не может достать и удалить эту дыру.
  • Если входные данные состоят из нескольких отсоединенных полиалмазов, вторая заливка потока не сможет достать и удалить все из них.
Мартин Эндер
источник