Определите, содержит ли сетка другую сетку

10

Задача
Создать функцию принимает в качестве входных данных два двумерных массива символов (или строк, если язык программирования не содержит символы в качестве типа данных): a и b. Если ваш язык не поддерживает эти входные данные, вы можете использовать любую другую стандартную однобайтовую переменную.

Ваша задача - определить, содержит ли b. Если это так, верните true. В противном случае верните false.

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

a:

123
456
789

b:

123
456
789

должен вернуть истину.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

должен вернуть истину.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

должен вернуть false.

a:

abc
def

b:

1abc2
3def4
5ghi6

должен вернуть истину

a:

ab
cd

b:

#ab##
##cd#

должен вернуть false

Меньше байтов побеждает.

опасность
источник
2
Привет и добро пожаловать в Codegolf! Я отредактировал ваши тестовые примеры, чтобы (надеюсь) сделать их немного более понятными. Обратите внимание, что у нас есть песочница для работы над задачами, прежде чем отправлять их на главную. Удачи!
FryAmTheEggman
2
Кроме того, могу ли я принять первый массив как массив строк, а второй - как строку, разделенную символами новой строки, даже если в моем языке (C #) есть встроенный символьный тип?
Воплощение невежества
@Neil Контрольные примеры 2 и 3 не квадратные.
Робин Райдер
5
Не могли бы вы добавить правдоподобный контрольный пример, где aнет bлевого края, и фальшивый контрольный пример, где каждая строка aпоявляется в последовательных строках, bно с левыми краями в шахматном порядке?
Лохматый
@EmbodimentofIgnorance да
Опасность

Ответы:

9

Brachylog (v2), 4 байта

s\s\

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

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

объяснение

s\s\
s     a substring of rows of {the left input}
 \…\  assert rectangular; swap row and column operations
  s   a substring of <s>rows</s> columns of {the above matrix}
      {implicit} assert that the result can be {the right input}

«Утверждать прямоугольник», очевидно, бессмысленно, поскольку вопрос уже гарантирует это. Остальная часть программы выполняет поиск сетки для нас путем определения подстроки строк и столбцов, то есть подматрицы.

Мета-обсуждение

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

оборота ais523
источник
Кратчайший ответ здесь, поэтому я приму его.
Опасность
7

Python 2 , 67 байт

f=lambda a,b,r=4:b*r and f(a,b[1:],r)|f(a,zip(*b)[::-1],r-1)or a==b

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

Вводит в виде списков кортежей символов.

Пробует все подсетки bи проверяет, есть ли aсреди них. Подрешетки создаются путем рекурсивного ветвления либо при удалении первого ряда, bлибо при его повороте на 90 градусов. Ровно после четырех поворотов проверяет, bравно ли обрезанное значение a.

XNOR
источник
1
@mazzy Я думаю, что входные сетки должны быть прямоугольниками.
xnor
5

J , 21 15 8 7 байтов

1#.,@E.

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

-7 байт благодаря Bolce Bussiere

оригинальный ответ

J , 21 15 байт

<@[e.&,$@[<;.3]

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

-6 байт благодаря FrownyFrog

как

  • <@[ в штучной упаковке левый арг
  • $@[<;.3] все прямоугольники в правом аргументе имеют ту же форму, что и левый аргумент
  • теперь передайте их как левый и правый аргумент ...
  • является левый арг вяза правый арг, после выравнивания обоих e.&,
Ион
источник
Я думаю, что это может быть<@[e.&,$@[<;.3]
FrownyFrog
Ах, конечно! Если вы хотите
Иона
1
-7 Б +/@:,@E.. Э. в значительной степени создан для этой задачи.
Болс Бюссьер
tyvm @BolceBussiere. Я обновлю это сегодня вечером.
Иона
4

Древесный уголь , 26 байт

⌈⭆η⭆ι⁼θE✂ηκ⁺Lθκ¹✂νμ⁺L§θ⁰μ¹

Попробуйте онлайн! Ссылка на подробную версию кода. Основываясь на моем ответе « Подсчитать смежные подматрицы» , единственное отличие состоит в том, что вместо взятия суммы совпадений я беру максимум, а из-за неявного преобразования строки из-за использования результата уже получается строка, которая сохраняет байт.

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

05AB1E , 10 байтов

øŒεøŒI.å}à

Принимает bкак первый вход, aкак второй. Оба ввода в виде символьных матриц.

Port of @ Mr.Xcoder 's 05AB1E ответит на этот связанный вызов , так что не забудьте его поддержать!

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

Объяснение:

øŒ          # Get the sublists of every column of the (implicit) input `b`
  ε         # Map each list of sublists to:
   øŒ       #  Get the sublists of every column again
            #  (now we have all sub-matrices of `b`)
     I    #  Check if the second input `a` is in this list of sub-matrices
          # After the map: check if any are truthy by taking the maximum
            # (which is output implicitly as result)
Кевин Круйссен
источник
3

JavaScript (ES6) , 131 112 105 байт

105 байтов:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&x.some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(l,j)==2*j)))

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

Изменения:

  • m[i]в xи n[z]в l: полностью забыл, что эти переменные уже были созданы
  • &&в &: обе стороны оператора уже логические, поэтому побитовый оператор будет работать

112 байт:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(n[z],j)==2*j)))

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

Изменения:

  • map((c,j)=>{...}).some(s=>s)в some((c,j)=>{...}): Избыточность
  • m[i+z].join()в m[i+z]+'': более короткий способ преобразовать массив в строку
  • indexOf(n[z].join(),j)в indexOf(n[z],j): The indexOf метода уже преобразует n[z] в строку

131 байт:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].map((c,j)=>n.every((l,z)=>m[i+z].join().indexOf(n[z].join(),j)==2*j)).some(s=>s))

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

Удобочитаемый:

function f (m, n) {
  return m.some((x, i) => {
    return i <= m.length - n.length
      && m[i].map((c, j) => {
        return n.every((l, z) => {
          return m[i + z].join().indexOf(n[z].join(), j) == 2 * j
        })
      })
        .some(s => s)
  })
}

Вместо того, чтобы сравнивать отдельные значения, я проверил, были ли строки из сетки N включены в линии сетки M, и если да, то по каким индексам. Если все строки включены, начиная с одного и того же индекса, то сетка N содержится в сетке M.

М. Павиза
источник
2

PowerShell , 71 102 85 98 байт

спасибо @ Джо Кинг; добавлены тестовые случаи.

param($a,$b)!!($a|%{$p=[regex]::Escape($_)
$b|sls $p -a -ca|% m*}|group index|?{"$a"-ceq$_.Group})

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

Меньше гольфа:

param($a,$b)

$matches = $a|%{
    $pattern = [regex]::Escape($_)
    $b|Select-String $pattern -AllMatches -CaseSensitive|% Matches
}

$relevantGroupsByMatchPosition = $matches|group index|?{
    "$a"-ceq$_.Group  # the '$_.Group' contains matches in source order
                      # -ceq is case sensitivity equation operator
                      # -ceq performs an implicit conversion to the left operand type
}

!!($relevantGroupsByMatchPosition)  # true if the variable is not $null
Mazzy
источник
1

Javascript, 150 байт

f=(a,b)=>{_='length';for(r=i=0;i<=b[_]-a[_];i++)for(j=0;j<=b[0][_]-a[0][_];j++){u=0;a.map((l,y)=>l.map((c,x)=>u=u||b[i+y][j+x]!=c));r=r||!u;}return r}

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

Йохан дю Туа
источник