Дана двумерная матрица из 0 и 1 с. Найдите количество островков для 1 и 0, где соседи находятся только по горизонтали и вертикали.
Given input:
1 1 1 0
1 1 1 0
output = 1 1
Number of 1s island = 1
xxx-
xxx-
Number of 0s island = 1
---x
---x
------------------------------
Given input:
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
output = 2 2
Number of 1s island = 2
----
xxxx <-- an island of 1s
----
xxxx <-- another island of 1s
Number of 0s island = 2
xxxx <-- an island
----
xxxx <-- another island
----
------------------------------
Given input:
1 0 0
0 0 0
0 0 1
output = 2 1
Number for 1's island = 2:
x-- <-- an island of 1s
---
--x <-- an island of 1s
Number of 0's island = 1:
-xx \
xxx > 1 big island of 0s
xx- /
------------------------------
Given input:
1 1 0
1 0 0
output = 1 1
Number for 1's island =1 and number of 0's island = 1
------------------------------
Given input:
1 1
1 1
output = 1 0
Number for 1's island =1 and number of 0's island = 0
code-golf
binary-matrix
Кб радость
источник
источник
[[1,0];[0,1]]
11111 / 10001 / 10101 / 10001 / 11111
→2 1
Ответы:
APL (Dyalog Unicode) ,
2928 байтов SBCS-1 благодаря @ Adám
Попробуйте онлайн!
⊂,~∘⊂
матрица и ее отрицание{
}¨
для каждого из них сделать⍸⍵
список пар координат 1с+/↑|∘.-⍨
матрица манхэттенских расстояний2>
матрица соседей∨.∧⍨⍣≡
переходное закрытие≢∪
количество уникальных строкисточник
^:_
?J , 57 байт
Попробуйте онлайн!
Это одна из тех, где идея невероятно проста (и я думаю, что это весело), но выполнение ее имело некоторую механическую длительность, которая маскирует простоту ... например, смещение исходной матрицы во всех направлениях с 0 заливкой является многословным
((,-)#:i.3) |.!.0
.Вполне вероятно, что эту механическую длину можно продолжить, и я могу попробовать завтра вечером, но сейчас я опишу суть.
Скажите, что наш вклад:
Начнем с матрицы уникальных целых чисел одинакового размера:
Затем для каждой ячейки мы находим максимум всех ее соседей и умножаем на входную маску:
Мы повторяем этот процесс, пока матрица не перестанет меняться:
А затем посчитайте количество уникальных ненулевых элементов. Это говорит нам о количестве 1 островов.
Мы применяем тот же процесс к «1 минус вход», чтобы получить число 0-островков.
источник
JavaScript (ES7),
138 ... 107106 байтВозвращает массив
[ones, zeros]
.Попробуйте онлайн!
Как?
Для сохранения байтов один и тот же код используется как для корневой итерации, так и для рекурсивных итераций, но он ведет себя немного по-разному.
Во время первой итерации:
Во время рекурсивных итераций:
c[v ^ 1]++
комментарии
источник
MATL ,
1412 байтПопробуйте онлайн! Или проверьте все тестовые случаи .
объяснение
источник
К (нгн / к) ,
60 55 51 5046 байтПопробуйте онлайн!
~:\
пара входных данных и их отрицание (буквально: negate iterate-сходятся){
}'
для каждого,/x
сгладить аргумент&
где 1с? - список показателей(0,#*x)\
divmod width (входная), чтобы получить два отдельных списка для ys и xsx-\:'x:
расстояния на ось ∆x и ∆yx*x:
возведи их в квадрат+/
добавить ∆x² и ∆y²2>
матрица соседей{|/'x*\:x}/
переходное закрытие#?
считать уникальные строкиисточник
Wolfram Language (Mathematica) ,
6462 байтаПопробуйте онлайн!
Благодаря attinat : мы можем записать
1<0
вместоFalse
и сохранить два байта.версия без гольфа:
Конечно, есть встроенная Mathematica,
MorphologicalComponents
которая принимает массив (или изображение) и возвращает его с заменой пикселей каждого морфологически связанного острова на индекс острова. ПринятиеMax
этого результата дает число островов (фоновые нули остаются равными нулю, а индекс островов начинается с 1). Нам нужно сделать это отдельно для массива (с указанием количества 1-островков) и одного минуса массива (с указанием количества 0-островков). Чтобы убедиться, что диагональные соседи не считаются соседями, необходимо указать эту опциюCornerNeighbors->False
.источник
Rule
Python 3,
144127 байтЭто решение использует
cv2
потрясающие возможности обработки изображений. Несмотря на менее удивительные, супер длинные и удобочитаемые имена методов, он превосходит оба других ответа Python!Golfed:
Expanded:
источник
4
вместоconnectivity=4
иn.uint8
неdtype=n.uint8
возможно?cv2.connectedComponents
метод, поэтому я был озадачен и подумал, что, возможно, была другая причина для необходимости имен аргументов. Как я уже сказал, я не слишком знаком с Python. Все, что я узнал от этого, отсюда на CCGC. ;) Но имеет смысл использовать имена переменных, чтобы пропустить другие необязательные аргументы.J ,
46 4443 байт-1 байт благодаря @miles
Попробуйте онлайн!
тесты и
,&
-.
обертка, украденная из ответа @ jonah,&
-.
для ввода и его отрицания делаем:4$.$.
(y, x) координаты единиц как матрицы n × 21#.[:|@-"1/~
Манхэттенские расстояния: abs (∆x) + abs (∆y)2>
матрица соседей[:+./ .*~^:_:
переходное закрытие#&~.&(
)
количество уникальных строкисточник
,&#&~.
чтобы избежать ограничения[:
Сетчатка 0.8.2 , 155 байт
Попробуйте онлайн! Ссылка включает в себя тестовый пример. Объяснение:
Если есть
1
, измените его на;
и добавьтеa
в конец ввода, чтобы он не мешал.Наводнение залейте больше соседних
1
s с;
s.Повторяйте, пока все острова
1
s не были превращены в;
s.Если есть
0
, измените его на:
и добавьтеb
к концу ввода, чтобы он не мешал.Наводнение залейте больше соседних
0
s с:
s.Повторяйте, пока все острова
0
s не были превращены в:
s.Отдельно посчитайте количество островов
1
s и0
s.источник
Haskell ,
228227225224 байтаПопробуйте онлайн!
Объяснение:
Идея этого решения заключается в следующем: инициализировать матрицу с уникальными значениями в каждой ячейке, положительными для
1
и отрицательными для0
. Затем несколько раз сравнивайте каждую ячейку с ее соседями и, если сосед имеет тот же знак, но число с большим абсолютным значением, замените номер ячейки на номер соседа. Как только это достигнет фиксированной точки, подсчитайте количество различных положительных чисел для количества1
регионов и различных отрицательных чисел для количества0
регионов.В коде:
можно разделить на предварительную обработку (присвоение номеров ячейкам), итерацию и постобработку (подсчет ячеек)
предварительная обработка
Часть предварительной обработки является функцией
Который использует
z
как сокращение для того,zipWith
чтобы сбрить несколько байтов. То, что мы здесь делаем, это сжатие двумерного массива с целочисленными индексами в строках и нечетными целочисленными индексами в столбцах. Мы делаем это, так как мы можем построить уникальное целое число из пары целых чисел,(i,j)
используя формулу(2^i)*(2j+1)
. Если мы генерируем только нечетные целые числа дляj
, мы можем пропустить вычисление2*j+1
, сохранив три байта.С уникальным числом нам теперь нужно только умножить на знак, основанный на значении в матрице, которое получается как
2*x-1
итерация
Итерация выполняется
Поскольку входные данные представлены в виде списка списков, мы выполняем сравнение соседей в каждой строке, транспонируем матрицу, снова выполняем сравнение в каждой строке (что из-за транспонирования является тем, что было в столбцах ранее) и снова транспонируем. Код, который выполняет один из этих шагов:
((.)>>=id$transpose.map l)
где
l
- функция сравнения (подробно описано ниже), котораяtranspose.map l
выполняет половину шагов сравнения и транспонирования.(.)>>=id
выполняет свой аргумент дважды, будучи бессмысленной формой\f -> f.f
и на один байт короче в этом случае из-за правил приоритета оператора.l
определяется в строке выше какl x=z(!)(z(!)x(0:x))$tail x++[0]
. Этот код выполняет оператор сравнения(!)
(см. Ниже) для каждой ячейки, в которой сначала находится ее левый сосед, а затем - его правый сосед, путем сжатия списка по очередиx
со сдвинутым вправо списком0:x
и левым сдвинутым спискомtail x++[0]
. Мы используем нули для заполнения сдвинутых списков, поскольку они никогда не могут появляться в предварительно обработанной матрице.a!b
определяется в строке выше этого какa!b=div(max(a*a)(a*b))a
. То, что мы хотим сделать здесь, это следующее различие в регистре:sgn(a) = -sgn(b)
у нас есть две противоположные области в матрице и мы не хотим их объединять, то естьa
остается неизменнымsgn(b) = 0
у нас есть угловой случай, гдеb
находится отступ, и, следовательно,a
остается неизменнымsgn(a) = sgn(b)
мы хотим объединить две области и взять одну с большим абсолютным значением (для удобства).Обратите внимание, что
sgn(a)
никогда не может быть0
. Мы осуществляем это с помощью приведенной формулы. Если знакиa
иb
отличаются,a*b
меньше или равно нулю, аa*a
всегда больше нуля, поэтому мы выбираем его как максимум и делимa
на, чтобы вернутьсяa
. Иначе,max(a*a)(a*b)
естьabs(a)*max(abs(a),(abs(b))
, и, деля это наa
, мы получаемsgn(a)*max(abs(a),abs(b))
, который является числом с большим абсолютным значением.Для итерации функции,
((.)>>=id$transpose.map l)
пока она не достигнет фиксированной точки, мы используем(until=<<((==)=<<))
, что взято из этого ответа stackoverflow .Постобработка
Для постобработки мы используем часть
которая является просто набором шагов.
(>>=id)
объединяет список списков в один список,nub
избавляется от двойников,(\x->length.($x).filter<$>[(>0),(<0)])
разбивает список на пару списков, один для положительных и один для отрицательных чисел, и вычисляет их длины.источник
Java 10,
359355281280261246 байт-74 байта благодаря @NahuelFouilleul .
Попробуйте онлайн.
Объяснение:
источник
|=2
: 0 -> 2 и 1 -> 3, однако>0
был изменен на==1
|=2
! И я все еще мог бы использовать<2
вместо==1
-1 байт, сначала проверив наличие0
(и, таким образом, они были изменены на2
, а затем используя<2
для проверки1
(которые были изменены3
).Python 3 , 167 байт
Попробуйте онлайн!
Python 2 , 168 байт
Попробуйте онлайн!
-2 байта благодаря Кевину Круйссену
Исправление форматирования +2 байта
объяснение
Счетчик сохраняется на 0 и 1. Для каждой записи в матрице выполняются следующие действия:
Это приводит к ложному срабатыванию для выровненных по левому краю случаев, таких как
или
Если возникает такая ситуация, счетчик уменьшается на 1.
Возвращаемое значение
[#1, #0]
источник
[#1, #0]
. Немного бессмысленно имо, чтобы навязывать это, но это то, что есть сейчас. Во всяком случае, вы можете Гольф{not c}
в{c^1}
, и исправить эту проблему , я уже упоминал, изменивn[c]+=
кn[c^1]+=
подобному вопросу. Хороший ответ, хотя +1 от меня. :)Perl 5 (
-0777p
), 110 байтМожет быть улучшено, используется регулярное выражение для замены
1
на3
, затем0
на2
.TIO
источник
Желе ,
4436 байтПопробуйте онлайн!
Монадическая ссылка, принимающая список списков целых чисел в качестве аргумента и возвращающая список из числа островков 1 и 0 в указанном порядке.
объяснение
Шаг 1
Создайте список всех матричных индексов, каждый с индексами соседа справа (если не справа) и вниз (если не снизу)
Шаг 2
Разделите эти индексы по тому, был ли 1 или 0 на входе. Возвращает один список индексов с соседями для 1 с, а другой для 0.
Шаг 3
Объединение списков с общими членами и выходным количеством
источник
T-SQL 2008, 178 байт
Ввод является табличной переменной.
Тестовые данные, используемые в этом примере:
Попробуйте онлайн
источник
R ,
194172 байтПопробуйте онлайн!
Выполните поиск в глубину, начиная с каждой ячейки матрицы, равной 1 (или нулю).
источник