Можете ли вы посчитать количество прямоугольников?

21

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

Можете ли вы посчитать количество прямоугольников?

+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+
|     |     |     |     |
|     |     |     |     |
+-----+-----+-----+-----+

Общее количество прямоугольников для этой мини-шахматной доски 4 x 4 точно

100

Вы были правы?

Связанная математика: Сколько прямоугольников на шахматной доске 8 × 8?

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

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

Задачи, связанные с данной : Подсчитайте уникальные прямоугольники! , Найти количество прямоугольников в массиве байтов 2D .

Формат ввода

Ваша функция или программа может работать с текстовым или графическим вводом.

Ввод текста

Сетка будет представлять собой сетку ASCII размером m- by- n ( m строк, n столбцов), состоящую из следующих символов:

  • пространства,
  • - для частей горизонтального отрезка,
  • | для частей сегмента вертикальной линии, и
  • + для углов.

Вы можете представить эту сетку ASCII в качестве входных данных / аргумента для вашей программы / функции в виде

  • одна строка, разделенная переносами строк,
  • строка без перевода строки, но с одним или двумя целыми числами, кодирующими размеры сетки, или
  • массив строк.

Примечание . Текстовый ввод содержит не менее 1 строки и не менее 1 столбца.

Графический ввод

В качестве альтернативы сетки кодируются как черно-белые PNG- изображения шириной 5 * n пикселей и высотой 5 * m пикселей. Каждое изображение состоит из 5 пикселей * 5 пикселей блоков, которые соответствуют входу ASCII:

  • Пробелы преобразуются в белые блоки. Эти блоки называются пробельными блоками.
  • Сегменты и углы линий преобразуются в блоки без пробелов. Центральный пиксель таких блоков черный.
  • Редактировать: Если два угла (на входе ASCII) соединены отрезком, соответствующие центры блоков (на графическом входе) также должны быть соединены черной линией.

Это означает, что каждый блок может быть выбран только из Пожалуйста, игнорируйте синие границы. (Нажмите здесь, чтобы увеличить изображение) .

Примечание . Синие границы приведены только для иллюстрации. Графический ввод имеет ширину не менее 5 пикселей и высоту 5 пикселей. Вы можете преобразовать графический ввод в любое монохромное изображение, возможно, в другие форматы файлов изображений). Если вы решили конвертировать, пожалуйста, укажите в ответе. Там нет штрафов за конвертацию.

Выходной формат

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

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

Примеры случаев

Случай 1, Графика: Случай 1( 30 пикселей * 30 пикселей), ASCII: ( 6 строк, 6 столбцов)

+--+  
|  |  
| ++-+
+-++ |
  |  |
  +--+

Ожидаемый результат: 3

Случай 2, Графика: Дело 2( 20 пикселей * 20 пикселей), ASCII: ( 4 строки, 4 столбца)

++-+
|+++
+++|
+-++

Ожидаемый результат: 6

Случай 3, Графика: Дело 3( 55 пикселей * 40 пикселей), ASCII: ( 8 строк, 11 столбцов)

  +++--+   
+-+++  |   
|  |  ++--+
+--+--++ ++
      |  ||
      |  ||
++    +--++
++

Ожидаемый результат: 9

Случай 4, Графика: Дело 4( 120 пикселей * 65 пикселей), ASCII: ( 13 строк, 24 столбца)

+--+--+ +--+  +--+  +--+
|  |  | |  |  |  |  |  |
+--+--+ |  |  |  |  |  |
|  |  | +--+--+--+--+--+
+--+--+    |  |  |  |   
           |  |  |  | ++
+-+-+-+-+  +--+  +--+ ++
| | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+

Ожидаемый результат: 243

Случай 5, Graphic: Дело 5( 5 точек * 5 . Точек Да, это есть!), ASCII: Просто один пробел.

Ожидаемый результат: 0

Случай 6, Графика: Дело 6( 35 пикселей * 20 пикселей), ASCII: ( 4 строки, 7 столбцов)

+--+--+
|++|++|
|++|++|
+--+--+

Ожидаемый результат: 5

Предположения

Чтобы облегчить жизнь, вам гарантировано, что:

  • Будучи не тороидальной , сетка не оборачивается ни по горизонтали, ни по вертикали.
  • Там нет свободных концов, например, +--- или +- -+. Все отрезки имеют два конца.
  • Две линии, которые встречаются в, +должны пересекаться друг с другом в этой точке.
  • Вам не нужно беспокоиться о неверных вводах.

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

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

Leaderboard

Показать фрагмент кода

code-golf ascii-art image-processing Безумие ли
источник
Разрешено ли монохромное растровое изображение?
user202729
@ user202729 Да. Если вы решили работать с изображениями, отличными от PNG, укажите это в ответе.
Безумие Ли
Является ли это действительный вход? (Угол прямоугольника касается границы большего прямоугольника.) Если это так, рассмотрите возможность добавления его в качестве контрольного примера.
Згарб
@ Zgarb Это правильный ввод. Я тоже буду редактировать пост.
Безумие Ли
Есть ли причина, по которой вы помещаете ожидаемые результаты в спойлеры? Кажется, что это только делает проверку вашего кода немного более раздражающей.
FryAmTheEggman

Ответы:

4

Грязь , 31 28 байт

T=\+[+\-]*\+/[+|]/+$
n`T&To2

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

Принимает ввод в формате ASCII.

объяснение

Синтаксис Гриме очень близок к регулярным выражениям. Каждая строка определяет шаблон, который может соответствовать или не соответствовать прямоугольнику символов. Tсоответствует прямоугольнику, верхняя строка и левый столбец которого выглядят корректно.

T=\+[+\-]*\+/[+|]/+$
T=                    Define T as
  \+[+\-]*\+          a row that matches this regex
            /         and below that
             [+|]/+   a column of + or |
                   $  with anything to its right.

Второй ряд - «основная программа».

n`T&To2
n`       Print number of rectangles that match
  T      the pattern T
   &     and
    To2  T rotated 180 degrees.
Zgarb
источник
6

JavaScript (ES6), 176 171 байт

g=a=>Math.max(...b=a.map(a=>a.length))-Math.min(...b)?``:f(a);f=
a=>a.map((b,i)=>[...b].map((_,j)=>n+=a.join`
`.split(eval(`/\\+(?=[-+]{${j}}\\+[^]{${l=b.length+~j}}([|+].{${j}}[|+][^]{${l}}){${i}}\\+[-+]{${j}}\\+)/`)).length>>1),n=0)|n
<textarea rows=8 cols=8 oninput=o.textContent=g(this.value.split`\n`)></textarea><pre id=o>
Развернуть фрагмент

Принимает ввод как массив строк одинаковой длины. Объяснение: Создает серию регулярных выражений, которые соответствуют прямоугольникам всех возможных значений ширины и высоты (и некоторых невозможных значений ширины и высоты, но для вас это гольф-код) и подсчитывает, сколько совпадений они все производят. Поскольку в регулярном выражении есть группа захвата, splitвозвращается 2n+1для nсовпадений, поэтому я сдвигаю вправо на 1, чтобы получить количество совпадений, поскольку это экономит байт, делая группу без захвата.

Нил
источник
Хм, фрагмент кода не работает для меня [Firefox 54.0.1 (32-разрядная версия) или Chrome 60.0.3112.90 (64-разрядная версия) для Windows (64-разрядная версия)].
Джонатан Аллан
Фрагмент. Он также не работает в Safari [Mac (64bit)].
г-н Xcoder
2
Кажется, что мы должны вставить материал в текстовую область. Требуется одинаковое количество символов в строке.
Безумие Ли
Ах, я вижу, хорошее место @FrenzyLi!
Джонатан Аллан
4

J , 103 95 86 80 76 70 байт

[:+/@,]*/@('-|++'*/@(e.,&'+')~&>]({.,{:)&.>@;|:;{.;{:);._3"$~2+$#:i.@$

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

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

миль
источник
1
@FrenzyLi Спасибо. Функция получает входные данные в виде массива строк, но я кодировал каждый каждый массив в виде плоской строки, преобразованной в массив, прежде чем сохранить их в каждой переменной, которая будет использоваться в качестве аргумента для функции.
миль
Ааа ... Спасибо за ваше объяснение.
Безумие Ли
@ милые милые когда вы говорите, что input как массив строк, каждая строка ввода 1 является строкой?
Иона
@Jonah Строки в J - это просто массивы символов, поэтому на самом деле ввод представляет собой двумерный массив символов.
мили
3

Mathematica, 136 134 132 байта

S=Tr@*Flatten;S@Table[1-Sign@S@{d[[{i,j},k;;l]],d[[i;;j,{k,l}]]},{i,($=Length)[d=ImageData@#]},{j,i+1,$@d},{k,w=$@#&@@d},{l,k+1,w}]&

Использование: (для старой 136-байтовой версии, но новая версия в основном идентична)

_

Заметка:

  • Это выполняется за время O (m 2 n 2 max (m, n)), поэтому используйте только небольшие входы.
  • Хотя это должно работать с двоичными изображениями, очевидно, что оно может работать с недвоичными изображениями. (но черный должен быть тождественно нулевым)
  • Графика не обязательно должна быть построена с блоками 5х5, блоки могут быть меньше.
  • @*является новым в версии 10. В более старых версиях используйте Tr~Composition~Flattenвместо Tr@*Flatten.
user202729
источник
В какой версии ММА это? В 9.0 он отвечает"Tr@" cannot be followed by "*Flatten".
Frenzy Li
1
@FrenzyLi 10.0. Да, @*(сокращение от Composition) является новым в версии 10.
user202729
1
Почему бы тебе просто не использовать RectangleCount[]?
MCMastery
2
@MCMastery Mathematica славится наличием множества встроенных, но не этим.
user202729
@ user202729 LOL Да, я
JK
2

Желе ,  60 53 52 51  50 байт

ÑFQe⁹ṚẆ;W¤
Ḣ,Ṫ
=”+ÇÇ€Ạȧ1ŀ
Zç⁾+-ȧç⁾+|$
Ẇ;"/€Ẇ€Ç€€FS

Полная программа, принимающая список строк (строк равной длины) и печатающая счетчик.

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

Как?

ÑFQe⁹ṚẆ;W¤   - Link 1, sidesAreValid?: list of lists, area; list allowedSideCharacters
Ñ            - call the next link (2) as a monad (get the sides in question
             -   note: these sides do not include the corners since the area was modified
             -   to not include the other sides by the first call to link 2 inside link 3.
 F           - flatten into a single list
  Q          - de-duplicate (unique characters)
         ¤   - nilad followed by link(s) as a nilad:
    ⁹        -   right argument (either "+-"                or "+|"               )
     Ṛ       -   reverse        (either "-+"                or "|+"               )
      Ẇ      -   all sublists   (either ["-","+","-+"]      or ["|","+","|+"]     )
        W    -   wrap           (either ["+-"]              or ["+|"]             )
       ;     -   concatenate    (either ["-","+","-+","+-"] or ["|","+","|+","+|"])
   e         - exists in?

Ḣ,Ṫ          - Link 2, topAndTail helper: list
Ḣ            - head (get the first element and modify the list)
  Ṫ          - tail (get the last element and modify the list)
 ,           - pair (the elements together)

=”+ÇÇ€Ạȧ1ŀ   - Link 3, isPartlyValid?: list of lists, area; list allowedSideCharacters
=”+          - equal to '+'? (vectorises across the whole area, 1 if so, 0 otherwise)
   Ç         - call the last link (2) as a monad (gets the values for two edges)
    Ç€       - call the last link (2) as a monad for €ach (...values for the four corners)
      Ạ      - all? (all corners are '+' 1 if so, 0 if not)
        1ŀ   - call link number 1 as a dyad with sideCharacters as the right argument
             -    ...and the modified area on the left
       ȧ     - logical and (both all corners are '+' and the sides in question look right)

Zç⁾+-ȧç⁾+|$  - Link 4, isValidSquare?: list of lists, area
Z            - transpose
 ç⁾+-        - call the last link (3) as a dyad with right argument "+-"
          $  - last two links as a monad:
      ç⁾+|   -   call the last link (3) as a dyad with right argument "+|"
     ȧ       - logical and (1 if so 0 otherwise)

Ẇ;"/€Ẇ€Ç€€FS - Main Link: list of lists of characters, rows
Ẇ            - all sublists (= all non-zero length runs of rows)
   /€        - reduce €ach by:
  "          -   zip with:
 ;           -     concatenation (= all non-zero length vertical edges)
     Ẇ€      - all sublists for €ach (= all possible areas)
       Ç€€   - call the last link (4) as a monad for €ach for €ach (for each area)
          F  - flatten
           S - sum
Джонатан Аллан
источник
2

Слип , 32 29 байт

$a([+`-]*`+>[+`|]*`+>){2}$A

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

27 байт кода + 2 байта nи oфлагов. Принимает входные данные в том же формате, который указан в вопросе (т. Е. Блок строк с разделителями новой строки).

notjagan
источник
2

Haskell, 180 167 166 байт

l=length
a%b=[a..b-1]
h c a g b=all(`elem`c)$g<$>[a..b]
f s|(#)<-(!!).(s!!)=sum[1|y<-1%l s,x<-1%l(s!!0),i<-0%y,j<-0%x,h"+|"i(#x)y,h"+-"j(y#)x,h"+|"i(#j)y,h"+-"j(i#)x]

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

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

Ними
источник
1

Желе , 41 39 34 33 байта

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+
ẆḊÐfZ€µ⁺€ẎÇÐḟL

Попробуйте онлайн! или просмотреть все дела.

На основании моего ответа в J.

объяснение

,Z;.ị$⁺€ḟ€"⁾-|Fḟ”+  Helper. Input: 2d array of characters
 Z                  Transpose
,                   Pair
  ;                   Concatenate with
     $                The tail and head
   .ị                   Select at index 0.5 -> Select at index 0 and 1
                        Jelly uses 1-based modular indexing, so
                        0 means to select the tail
      ⁺€              Repeat on each - This selects the last and first rows,
                      last and first columns, and the 4 corners
           ⁾-|       The string array ['-', '|']
          "          Vectorize
        ḟ€             Filter each
              F      Flatten
                ”+   The character '+'
               ḟ

ẆḊÐfZ€µ⁺€ẎÇÐḟL  Main. Input: 2d array of characters
      µ         Combine into a monad
Ẇ                 Generate all sublists
  Ðf              Filter for the values that are truthy (non-empty)
 Ḋ                  Dequeue
    Z€            Transpose each
       ⁺€       Repeat on each
         Ẏ      Tighten, join all lists on the next depth
          ÇÐḟ   Discard the values where executing the helper returns truthy
             L  Length
миль
источник
Теперь он наконец начинает чувствовать себя конкурентно коротким в 34 байта.
мили