Обрежьте этот отвлекающий фон!

13

Разве это не раздражает, когда вы делаете снимок, но фон отвлекает от фактического содержания изображения? Я бы сказал, что это так. Мне нужно знать, сколько я должен обрезать, чтобы избавиться от этой проблемы! Но - как обычно - я довольно ленив, поэтому мне нужен кто-то, чтобы сделать это для меня ...

Задача и правила

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

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

пример

[000000010100011011001010000000][101001101101010](5,3)

Контрольные примеры

Вход | Выход

[[0,1,0,0,0,1,0]]
-> (5,1) или (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0]]
-> (3,2) или (2,3)

[[1,1,1,1], [0,0,0,0], [0,0,0,0], [1,0,0,0]]
-> (4,4)

[[0,0,0,0,0,0], [0,1,0,1,0,1], [0,0,0,0,0,0]]
-> (5,1) или (1,5)

[[0,0,0,0,0], [0,1,0,1,0], [0,0,1,0,0], [0,1,0,1,0], [ 0,0,0,0,0]]
-> (3,3)

[[0,0,0,0,0,0], [0,1,0,1,0,0], [0,1,1,0,1,1], [0,0,1, 0,1,0], [0,0,0,0,0,0]]
-> (5,3) или (3,5)
Мистер Xcoder
источник
1
Это кажется очень знакомым; это было в Песочнице некоторое время?
лохматый
8
Это действительно очень близко к связанному вопросу, но я думаю, что его можно считать достаточно отдаленным подмножеством, потому что генерация матрицы не является абсолютно необходимой для вычисления фактической ширины и высоты. Например, одним из возможных алгоритмов было бы подсчитать минимальное количество предельных нулей для каждой строки и столбца и вычесть их из исходных измерений.
Мистер Xcoder

Ответы:

5

APL (Dyalog Unicode) , 10 байтов SBCS

Функция анонимного молчаливого префикса.

(1+⌈/-⌊/)⍸

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

 показатели 1с.

() Примените к этому следующую молчаливую функцию:

⌊/ минимальный (самые низкие у координаты и низкие х координаты)

⌈/- максимальный минус, который (это дает нам диапазон)

1+ один плюс это (быть включительно)

Адам
источник
5

Октава , 57 56 45 байт

Здесь findделается тяжелая работа: это findsиндексы строк и столбцов ненулевых записей. Тогда нам просто нужно найти разницу между максимумом и минимумом (плюс один) для каждого из них отдельно.

Спасибо @beaker и @AndrasDeak за -1 байт, а @LuisMendo за -11 байт!

@(a){[I{1:2}]=find(a),cellfun(@range,I)}{2}+1

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

flawr
источник
3

Желе , 7 байт

S,§t€0Ẉ

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

Как это устроено

S,§t€0Ẉ  Main link. Argument: M (matrix)

S        Take the columnwise sum. Let's call the resulting array A.
  §      Take the sum of each row. Let's call the resulting array B.
 ,       Pair; yield [A, B].
   t€0   Trim surrounding zeroes of A and B.
      Ẉ  Widths; yields the lengths of the trimmed arrays.
Деннис
источник
3

Python 2 ,  63  55 байт

-8 с помощью Винсента (взять матрицу ввода как массив Numpy)

lambda a:[len(`a.max(x)`[7::3].strip('0'))for x in 0,1]

Безымянная функция , принимающая 2-d Numpy массив целых чисел (в {0,1}) , который возвращает список целых чисел, [width,height].

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


Не-Numpy версия в 63 байта (принимает список списков целых чисел в {0,1}):

lambda a:[len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a]

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

Как?

Для матрицы, a, forкаждая ( v) из транспонированной, zip(*a)иa сам находят высоту , необходимую ( с учетом транспонирования Это шириной).

Отображение maxчерез vдает список нулей и единиц, представляющих, если каждая строка vсодержит какие-либо из них. Строковое представление этого списка найдено с помощью backticks ( `...`), это дает строку с начальным [, затем нулями и единицами, разделенными , (запятая + пробел). Мы нарезаем эту строку, начиная с индекса один, с шагом в три, [1::3]получая нам строку только из нулей и единиц, что позволяет нам использовать строковую функцию stripдля удаления внешних нулей (strip('0') ).

Например:

      a = [[0,0,0,0,0]           map(max,a)                    = [0,1,1]
          ,[0,1,0,0,0]          `map(max,a)`[1::3]             = '011'
          ,[0,0,0,1,0]]         `map(max,a)`[1::3].strip('0')  = '11'
                            len(`map(max,a)`[1::3].strip('0')) = 2

zip(*a) = [(0,0,0)         map(max,zip(*a))                    = [0,1,0,1,0]
          ,(0,1,0)        `map(max,zip(*a))`[1::3]             = '01010'
          ,(0,0,0)        `map(max,zip(*a))`[1::3].strip('0')  = '101'
          ,(0,0,1)    len(`map(max,zip(*a))`[1::3].strip('0')) = 3
          ,(0,0,0)]

    --> [len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a] = [3,2]
Джонатан Аллан
источник
57 байт с использованием массива numpy.
Винсент
Если мы принимаем входные данные как не встроенный тип, разве мы не должны считать какой-то оператор импорта, чтобы позволить нам сделать это? (Может быть, мы просто назвали пост "Python 2 с numpy" - я не совсем уверен) ... если у вас есть время, вы можете спросить в девятнадцатом байтовом чате?
Джонатан Аллан
1
... также 55 байт, верно?
Джонатан Аллан
1
Я не мог найти четкого ответа на PPCG Meta , поэтому я не уверен в этом. И да, действительно 55 байт :)
Винсент
1
Я просто спросил. Согласно этому сообщению , импорт не должен быть включен.
Винсент
1

Сетчатка 0.8.2 , 83 байта

+`^0+¶|¶0+$

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5
(¶?)*0*(.*1)0*
$#1 $.2

Попробуйте онлайн! Объяснение:

+`^0+¶|¶0+$

Удалить начальные и конечные нулевые строки.

+1`((.)*).(¶(?<-2>.)*).(?<=(1)¶.*|(.))
$1$3$4$5

Удалите все 0буквы в строках над последним. Удалите все 1s два, но измените цифру внизу на следующей строке на a 1в этом случае. Это поразрядно или по строкам.

(¶?)*0*(.*1)0*
$#1 $.2

Подсчитайте количество строк как количество новых строк плюс 1 и количество столбцов как количество цифр между первым и последним 1.

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

J , 31 байт

[:$([:|.@|:}.^:(0=1#.{.))^:4^:_

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

Объяснение:

                            ^:_ - repeat until the result stops changing
   (                    )^:4    - repeat 4 times
             ^:(        )       - is
                  1#.           - the sum of
                      {.        - the first row
                 =              - equal 
                0               - to 0
           }.                   - if yes, drop the first row
    [:|.@|:                     - transpose and reverse (rotate 90 degrees) 
[:$                             - what's the shape of the result?
Гален Иванов
источник
1

q / kdb +, 16 байт

sum@'(|/;|/')@\:
Томас Смит
источник
1

Mathematica, 34 байта

Max@#-Min@#+1&/@(#~Position~1)&

Чистая функция. Принимает вложенный список целых чисел в качестве входных данных и возвращает список из двух целых чисел (высота, сопровождаемая шириной) в качестве выходных данных. Символ Unicode - это U + F3C7 для \[Transpose].

LegionMammal978
источник
1

05AB1E , 11 9 байтов

ζ‚Oε0Û0Üg

-2 байта благодаря @ Mr.Xcoder .

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

Объяснение:

ζ            # Swap the rows and columns of the (implicit) input-list
            # Pair it with the (implicit) input-list
  O          # Take the sum of each column and row
   ε         # Map Both the list of column-sums and list of row-sums to:
    0Û       #  Remove all leading zeros
      0Ü     #  Remove all trailing zeros
        g    #  Take the length of the remaining lists
Кевин Круйссен
источник
1
ζ‚Oε0Û0Ügэкономит 2 байта.
г-н Xcoder
@ Mr.Xcoder А, конечно. Я был уже не слишком доволен этим обменом. Не могу поверить, что я сначала не думал о создании пары, а
потом
0

Japt 16 15 байт

[UUy]®=ðd)ÎaZÌÄ

Попробуйте или запустите все тесты


объяснение

[   ]               :Create an array containing
 U                  : The input and
  Uy                : The input transposed
     ®              :Map each Z
       ð            : Indices of elements where
        d           :  Any element is truthy (not 0)
      =  )          : Reassign to Z
          Î         : First element
           a        : Absolute difference with
            ZÌ      :  Last element
              Ä     :   Plus 1
мохнатый
источник